Optimize string escape functions When generating Chromium's build files, this reduces the number of cycles gn uses across all threads from 41,325,733,995 to 38,453,104,830 (-7%) indicated by callgrind. Runtime is also reduced from 3.45s to 3.43s (-0.6%) measured with 100 samples. GN is likely bound more by disk IO and exec_script()'s than CPU cycles, so that would explain why runtime reduction is only 0.6%. But 0.6% is still better than 0%. BUG=None R=brettw Change-Id: Ief145407a0bf3ef00b13ce2532df4ff028f05c89 Reviewed-on: https://gn-review.googlesource.com/c/gn/+/4620 Reviewed-by: Brett Wilson <brettw@google.com> Commit-Queue: Brett Wilson <brettw@google.com>
diff --git a/tools/gn/escape.cc b/tools/gn/escape.cc index 53c8d89..f2b1324 100644 --- a/tools/gn/escape.cc +++ b/tools/gn/escape.cc
@@ -6,11 +6,21 @@ #include <stddef.h> +#include <memory> + +#include "base/compiler_specific.h" #include "base/logging.h" #include "util/build_config.h" namespace { +constexpr size_t kStackStringBufferSize = 1024; +#if defined(OS_WIN) +constexpr size_t kMaxEscapedCharsPerChar = 2; +#else +constexpr size_t kMaxEscapedCharsPerChar = 3; +#endif + // A "1" in this lookup table means that char is valid in the Posix shell. const char kShellValid[0x80] = { // 00-1f: all are invalid @@ -29,33 +39,50 @@ // p q r s t u v w x y z { | } ~ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0}; -// Append one character to the given string, escaping it for Ninja. -// +// Uses the stack if the space needed is small and the heap otherwise. +class StackOrHeapBuffer { + public: + explicit StackOrHeapBuffer(size_t buf_size) { + if (UNLIKELY(buf_size > kStackStringBufferSize)) + heap_buf.reset(new char[buf_size]); + } + operator char*() { return heap_buf ? heap_buf.get() : stack_buf; } + + private: + char stack_buf[kStackStringBufferSize]; + std::unique_ptr<char[]> heap_buf; +}; + // Ninja's escaping rules are very simple. We always escape colons even // though they're OK in many places, in case the resulting string is used on // the left-hand-side of a rule. -inline void NinjaEscapeChar(char ch, std::string* dest) { - if (ch == '$' || ch == ' ' || ch == ':') - dest->push_back('$'); - dest->push_back(ch); +inline bool ShouldEscapeCharForNinja(char ch) { + return ch == '$' || ch == ' ' || ch == ':'; } -void EscapeStringToString_Ninja(const base::StringPiece& str, - const EscapeOptions& options, - std::string* dest, - bool* needed_quoting) { - for (const auto& elem : str) - NinjaEscapeChar(elem, dest); +size_t EscapeStringToString_Ninja(const base::StringPiece& str, + const EscapeOptions& options, + char* dest, + bool* needed_quoting) { + size_t i = 0; + for (const auto& elem : str) { + if (ShouldEscapeCharForNinja(elem)) + dest[i++] = '$'; + dest[i++] = elem; + } + return i; } -void EscapeStringToString_NinjaPreformatted(const base::StringPiece& str, - std::string* dest) { +size_t EscapeStringToString_NinjaPreformatted(const base::StringPiece& str, + char* dest) { // Only Ninja-escape $. + size_t i = 0; for (const auto& elem : str) { if (elem == '$') - dest->push_back('$'); - dest->push_back(elem); + dest[i++] = '$'; + dest[i++] = elem; } + return i; } // Escape for CommandLineToArgvW and additionally escape Ninja characters. @@ -66,119 +93,124 @@ // See: // http://blogs.msdn.com/b/twistylittlepassagesallalike/archive/2011/04/23/everyone-quotes-arguments-the-wrong-way.aspx // http://blogs.msdn.com/b/oldnewthing/archive/2010/09/17/10063629.aspx -void EscapeStringToString_WindowsNinjaFork(const base::StringPiece& str, - const EscapeOptions& options, - std::string* dest, - bool* needed_quoting) { +size_t EscapeStringToString_WindowsNinjaFork(const base::StringPiece& str, + const EscapeOptions& options, + char* dest, + bool* needed_quoting) { // We assume we don't have any whitespace chars that aren't spaces. DCHECK(str.find_first_of("\r\n\v\t") == std::string::npos); + size_t i = 0; if (str.find_first_of(" \"") == std::string::npos) { // Simple case, don't quote. - EscapeStringToString_Ninja(str, options, dest, needed_quoting); + return EscapeStringToString_Ninja(str, options, dest, needed_quoting); } else { if (!options.inhibit_quoting) - dest->push_back('"'); + dest[i++] = '"'; - for (size_t i = 0; i < str.size(); i++) { + for (size_t j = 0; j < str.size(); j++) { // Count backslashes in case they're followed by a quote. size_t backslash_count = 0; - while (i < str.size() && str[i] == '\\') { - i++; + while (j < str.size() && str[j] == '\\') { + j++; backslash_count++; } - if (i == str.size()) { + if (j == str.size()) { // Backslashes at end of string. Backslash-escape all of them since // they'll be followed by a quote. - dest->append(backslash_count * 2, '\\'); - } else if (str[i] == '"') { + memset(dest + i, '\\', backslash_count * 2); + i += backslash_count * 2; + } else if (str[j] == '"') { // 0 or more backslashes followed by a quote. Backslash-escape the // backslashes, then backslash-escape the quote. - dest->append(backslash_count * 2 + 1, '\\'); - dest->push_back('"'); + memset(dest + i, '\\', backslash_count * 2 + 1); + i += backslash_count * 2 + 1; + dest[i++] = '"'; } else { // Non-special Windows character, just escape for Ninja. Also, add any // backslashes we read previously, these are literals. - dest->append(backslash_count, '\\'); - NinjaEscapeChar(str[i], dest); + memset(dest + i, '\\', backslash_count); + i += backslash_count; + if (ShouldEscapeCharForNinja(str[j])) + dest[i++] = '$'; + dest[i++] = str[j]; } } if (!options.inhibit_quoting) - dest->push_back('"'); + dest[i++] = '"'; if (needed_quoting) *needed_quoting = true; } + return i; } -void EscapeStringToString_PosixNinjaFork(const base::StringPiece& str, - const EscapeOptions& options, - std::string* dest, - bool* needed_quoting) { +size_t EscapeStringToString_PosixNinjaFork(const base::StringPiece& str, + const EscapeOptions& options, + char* dest, + bool* needed_quoting) { + size_t i = 0; for (const auto& elem : str) { if (elem == '$' || elem == ' ') { // Space and $ are special to both Ninja and the shell. '$' escape for // Ninja, then backslash-escape for the shell. - dest->push_back('\\'); - dest->push_back('$'); - dest->push_back(elem); + dest[i++] = '\\'; + dest[i++] = '$'; + dest[i++] = elem; } else if (elem == ':') { // Colon is the only other Ninja special char, which is not special to // the shell. - dest->push_back('$'); - dest->push_back(':'); + dest[i++] = '$'; + dest[i++] = ':'; } else if (static_cast<unsigned>(elem) >= 0x80 || !kShellValid[static_cast<int>(elem)]) { // All other invalid shell chars get backslash-escaped. - dest->push_back('\\'); - dest->push_back(elem); + dest[i++] = '\\'; + dest[i++] = elem; } else { // Everything else is a literal. - dest->push_back(elem); + dest[i++] = elem; } } + return i; } -void EscapeStringToString(const base::StringPiece& str, - const EscapeOptions& options, - std::string* dest, - bool* needed_quoting) { +// Escapes |str| into |dest| and returns the number of characters written. +size_t EscapeStringToString(const base::StringPiece& str, + const EscapeOptions& options, + char* dest, + bool* needed_quoting) { switch (options.mode) { case ESCAPE_NONE: - dest->append(str.data(), str.size()); - break; + strncpy(dest, str.data(), str.size()); + return str.size(); case ESCAPE_NINJA: - EscapeStringToString_Ninja(str, options, dest, needed_quoting); - break; + return EscapeStringToString_Ninja(str, options, dest, needed_quoting); case ESCAPE_NINJA_COMMAND: switch (options.platform) { case ESCAPE_PLATFORM_CURRENT: #if defined(OS_WIN) - EscapeStringToString_WindowsNinjaFork(str, options, dest, - needed_quoting); + return EscapeStringToString_WindowsNinjaFork(str, options, dest, + needed_quoting); #else - EscapeStringToString_PosixNinjaFork(str, options, dest, - needed_quoting); + return EscapeStringToString_PosixNinjaFork(str, options, dest, + needed_quoting); #endif - break; case ESCAPE_PLATFORM_WIN: - EscapeStringToString_WindowsNinjaFork(str, options, dest, - needed_quoting); - break; + return EscapeStringToString_WindowsNinjaFork(str, options, dest, + needed_quoting); case ESCAPE_PLATFORM_POSIX: - EscapeStringToString_PosixNinjaFork(str, options, dest, - needed_quoting); - break; + return EscapeStringToString_PosixNinjaFork(str, options, dest, + needed_quoting); default: NOTREACHED(); } - break; case ESCAPE_NINJA_PREFORMATTED_COMMAND: - EscapeStringToString_NinjaPreformatted(str, dest); - break; + return EscapeStringToString_NinjaPreformatted(str, dest); default: NOTREACHED(); } + return 0; } } // namespace @@ -186,17 +218,14 @@ std::string EscapeString(const base::StringPiece& str, const EscapeOptions& options, bool* needed_quoting) { - std::string result; - result.reserve(str.size() + 4); // Guess we'll add a couple of extra chars. - EscapeStringToString(str, options, &result, needed_quoting); - return result; + StackOrHeapBuffer dest(str.size() * kMaxEscapedCharsPerChar); + return std::string(dest, + EscapeStringToString(str, options, dest, needed_quoting)); } void EscapeStringToStream(std::ostream& out, const base::StringPiece& str, const EscapeOptions& options) { - std::string escaped; - EscapeStringToString(str, options, &escaped, nullptr); - if (!escaped.empty()) - out.write(escaped.data(), escaped.size()); + StackOrHeapBuffer dest(str.size() * kMaxEscapedCharsPerChar); + out.write(dest, EscapeStringToString(str, options, dest, nullptr)); }