Improve performance of escape functions. These functions would previously do read and writes character by character. Now we follow a different pattern: 1) Find first character that needs to be escaped 2) Memcpy all previous characters 3) Write that character 4) Repeat until no character needing to be escaped is found 5) Memcpy all remaining characters In the hot path, this basically looks like: if not any(needs_escaping(c) for c in source): memcpy(source, dest) Memcpy is much faster than copying byte-by-byte, so this is much more performant. These functions now run more than twice as fast as before. Profiling revealed that we spend about 4% of time in escaping, so this should be around a 2% performance boost (which I did measure but due to how small it is I couldn't get statistically significant data). Change-Id: Idaaa43263a9aec6c38effca464cc49646a6a6964 Reviewed-on: https://gn-review.googlesource.com/c/gn/+/27740 Reviewed-by: Takuto Ikuta <tikuta@google.com> Commit-Queue: Matt Stark <msta@google.com>
diff --git a/src/gn/escape.cc b/src/gn/escape.cc index 7c633fe..8d902d4 100644 --- a/src/gn/escape.cc +++ b/src/gn/escape.cc
@@ -6,6 +6,8 @@ #include <stddef.h> +#include <array> + #include "base/compiler_specific.h" #include "base/json/string_escape.h" #include "base/logging.h" @@ -22,7 +24,7 @@ // A "1" in this lookup table means that char is valid in the Posix shell. // clang-format off -const char kShellValid[0x80] = { +constexpr char kShellValid[256] = { // 00-1f: all are invalid 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, @@ -40,31 +42,72 @@ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0}; // clang-format on -size_t EscapeStringToString_Space(std::string_view str, char* dest) { - size_t i = 0; - for (const auto& elem : str) { - if (elem == ' ') - dest[i++] = '\\'; - dest[i++] = elem; +constexpr std::array<char, 256> PosixEscapesTo(const char (&entries)[256]) { + std::array<char, 256> table{}; + for (size_t i = 0; i < table.size(); ++i) { + if (entries[i] == 0) { + table[i] = '\\'; + } } - return i; + table[':'] = '$'; + return table; +} + +constexpr auto kPosixNinjaTable = PosixEscapesTo(kShellValid); + +constexpr std::array<bool, 256> InitNinjaEscapeTable() { + std::array<bool, 256> table{}; + table['$'] = true; + table[' '] = true; + table[':'] = true; + return table; +} + +constexpr auto kNinjaEscapeTable = InitNinjaEscapeTable(); + +char* EscapeStringToString_Space(std::string_view str, char* out) { + size_t in_idx = 0; + for (size_t delim = str.find(' '); UNLIKELY(delim != std::string_view::npos); + delim = str.find(' ', in_idx)) { + size_t len = delim - in_idx; + memcpy(out, str.data() + in_idx, len); + out += len; + *out++ = '\\'; + *out++ = ' '; + in_idx = delim + 1; + } + size_t len = str.size() - in_idx; + memcpy(out, str.data() + in_idx, len); + out += len; + return out; } // 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 bool ShouldEscapeCharForNinja(char ch) { - return ch == '$' || ch == ' ' || ch == ':'; + return kNinjaEscapeTable[static_cast<uint8_t>(ch)]; } -size_t EscapeStringToString_Ninja(std::string_view str, char* dest) { - size_t i = 0; - for (const auto& elem : str) { - if (ShouldEscapeCharForNinja(elem)) - dest[i++] = '$'; - dest[i++] = elem; +// Performance could be further improved with architecture-specific SIMD +// (e.g. SSE2 on x86, NEON on ARM), but that is platform-dependent, so we +// refrain from doing so for now. +char* EscapeStringToString_Ninja(std::string_view str, char* out) { + size_t in_idx = 0; + for (size_t i = 0; i < str.size(); ++i) { + if (UNLIKELY(ShouldEscapeCharForNinja(str[i]))) { + size_t len = i - in_idx; + memcpy(out, str.data() + in_idx, len); + out += len; + *out++ = '$'; + *out++ = str[i]; + in_idx = i + 1; + } } - return i; + size_t len = str.size() - in_idx; + memcpy(out, str.data() + in_idx, len); + out += len; + return out; } inline bool ShouldEscapeCharForCompilationDatabase(char ch) { @@ -76,8 +119,7 @@ size_t i = 0; bool quote = false; for (const auto& elem : str) { - if (static_cast<unsigned>(elem) >= 0x80 || - !kShellValid[static_cast<int>(elem)]) { + if (!kShellValid[static_cast<uint8_t>(elem)]) { quote = true; break; } @@ -138,75 +180,92 @@ 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. - return EscapeStringToString_Ninja(str, dest); - } else { - if (!inhibit_quoting) - dest[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 (j < str.size() && str[j] == '\\') { - j++; - backslash_count++; - } - if (j == str.size()) { - // Backslashes at end of string. Backslash-escape all of them since - // they'll be followed by a quote. - 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. - 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. - memset(dest + i, '\\', backslash_count); - i += backslash_count; - if (ShouldEscapeCharForNinja(str[j])) - dest[i++] = '$'; - dest[i++] = str[j]; - } - } - - if (!inhibit_quoting) - dest[i++] = '"'; - if (needed_quoting) - *needed_quoting = true; + // '$', ' ', and ':' mean we need ninja escaping. ' ' and '"' mean we need + // shell escaping. + size_t idx = str.find_first_of("$: \""); + if (LIKELY(idx == std::string::npos)) { + // Super-fast-path: No shell escaping or Ninja escaping required. + memcpy(dest, str.data(), str.size()); + return str.size(); } + + // If the special character found was NOT a space or quote (i.e. it was '$' + // or ':'), check if there are any spaces or quotes in the rest of the string. + if (str[idx] != ' ' && str[idx] != '"' && + str.find_first_of(" \"", idx + 1) == std::string::npos) { + // Fast-path: Needs Ninja escaping, but no Windows command-line quoting. + // We know that the up until here doesn't require any escaping + memcpy(dest, str.data(), idx); + char* out = &dest[idx]; + // Ninja always escapes with a $ + *out++ = '$'; + *out++ = str[idx]; + // Escape the rest of the string with ninja. + out = EscapeStringToString_Ninja(str.substr(idx + 1), out); + return out - dest; + } + + if (!inhibit_quoting) + dest[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 (j < str.size() && str[j] == '\\') { + j++; + backslash_count++; + } + if (j == str.size()) { + // Backslashes at end of string. Backslash-escape all of them since + // they'll be followed by a quote. + 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. + 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. + memset(dest + i, '\\', backslash_count); + i += backslash_count; + if (ShouldEscapeCharForNinja(str[j])) + dest[i++] = '$'; + dest[i++] = str[j]; + } + } + + if (!inhibit_quoting) + dest[i++] = '"'; + if (needed_quoting) + *needed_quoting = true; + return i; } -size_t EscapeStringToString_PosixNinjaFork(std::string_view str, char* dest) { - 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[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[i++] = '$'; - dest[i++] = ':'; - } else if (static_cast<unsigned>(elem) >= 0x80 || - !kShellValid[static_cast<int>(elem)]) { - // All other invalid shell chars get backslash-escaped. - dest[i++] = '\\'; - dest[i++] = elem; - } else { - // Everything else is a literal. - dest[i++] = elem; +char* EscapeStringToString_PosixNinjaFork(std::string_view str, char* out) { + size_t start = 0; + for (size_t i = 0; i < str.size(); ++i) { + char esc = kPosixNinjaTable[static_cast<uint8_t>(str[i])]; + if (UNLIKELY(esc != '\0')) { + size_t len = i - start; + memcpy(out, str.data() + start, len); + out += len; + char c = str[i]; + *out++ = esc; + if (c == ' ' || c == '$') { + *out++ = '$'; + } + *out++ = c; + start = i + 1; } } - return i; + size_t len = str.size() - start; + memcpy(out, str.data() + start, len); + out += len; + return out; } // Escapes |str| into |dest| and returns the number of characters written. @@ -219,27 +278,20 @@ strncpy(dest, str.data(), str.size()); return str.size(); case ESCAPE_SPACE: - return EscapeStringToString_Space(str, dest); + return EscapeStringToString_Space(str, dest) - dest; case ESCAPE_NINJA: - return EscapeStringToString_Ninja(str, dest); + return EscapeStringToString_Ninja(str, dest) - dest; case ESCAPE_DEPFILE: return EscapeStringToString_Depfile(str, dest); case ESCAPE_COMPILATION_DATABASE: return EscapeStringToString_CompilationDatabase(str, dest); case ESCAPE_NINJA_COMMAND: switch (options.platform) { - case ESCAPE_PLATFORM_CURRENT: -#if defined(OS_WIN) - return EscapeStringToString_WindowsNinjaFork( - str, options.inhibit_quoting, dest, needed_quoting); -#else - return EscapeStringToString_PosixNinjaFork(str, dest); -#endif case ESCAPE_PLATFORM_WIN: return EscapeStringToString_WindowsNinjaFork( str, options.inhibit_quoting, dest, needed_quoting); case ESCAPE_PLATFORM_POSIX: - return EscapeStringToString_PosixNinjaFork(str, dest); + return EscapeStringToString_PosixNinjaFork(str, dest) - dest; default: NOTREACHED(); } @@ -254,11 +306,11 @@ } // namespace char* Escaped::Space::WriteToBuf(char* out) const { - return &out[EscapeStringToString_Space(str, out)]; + return EscapeStringToString_Space(str, out); } char* Escaped::Ninja::WriteToBuf(char* out) const { - return &out[EscapeStringToString_Ninja(str, out)]; + return EscapeStringToString_Ninja(str, out); } char* Escaped::Depfile::WriteToBuf(char* out) const { @@ -275,20 +327,14 @@ char* Escaped::Command::WriteToBuf(char* out) const { switch (platform) { - case ESCAPE_PLATFORM_CURRENT: -#if defined(OS_WIN) - return &out[EscapeStringToString_WindowsNinjaFork(str, inhibit_quoting, - out, nullptr)]; -#else - return &out[EscapeStringToString_PosixNinjaFork(str, out)]; -#endif case ESCAPE_PLATFORM_WIN: return &out[EscapeStringToString_WindowsNinjaFork(str, inhibit_quoting, out, nullptr)]; case ESCAPE_PLATFORM_POSIX: - return &out[EscapeStringToString_PosixNinjaFork(str, out)]; + return EscapeStringToString_PosixNinjaFork(str, out); + default: + NOTREACHED(); } - NOTREACHED(); return out; }
diff --git a/src/gn/escape.h b/src/gn/escape.h index fd316dc..ce6850f 100644 --- a/src/gn/escape.h +++ b/src/gn/escape.h
@@ -8,6 +8,8 @@ #include <string> #include <string_view> +#include "util/build_config.h" + class StringOutputBuffer; enum EscapingMode { @@ -41,12 +43,16 @@ }; enum EscapingPlatform { - // Do escaping for the current platform. - ESCAPE_PLATFORM_CURRENT, - // Force escaping for the given platform. ESCAPE_PLATFORM_POSIX, ESCAPE_PLATFORM_WIN, + +// Do escaping for the current platform. +#if defined(OS_WIN) + ESCAPE_PLATFORM_CURRENT = ESCAPE_PLATFORM_WIN, +#else + ESCAPE_PLATFORM_CURRENT = ESCAPE_PLATFORM_POSIX, +#endif }; struct EscapeOptions {
diff --git a/src/gn/escape_unittest.cc b/src/gn/escape_unittest.cc index dcbfd16..62fd2e2 100644 --- a/src/gn/escape_unittest.cc +++ b/src/gn/escape_unittest.cc
@@ -29,6 +29,10 @@ // Regular string is passed, even if it has backslashes. EXPECT_EQ("foo\\bar", EscapeString("foo\\bar", opts, nullptr)); + // Colon and dollar sign get escaped for Ninja, but not quoted for Windows. + EXPECT_EQ("C$:\\foo\\bar", EscapeString("C:\\foo\\bar", opts, nullptr)); + EXPECT_EQ("foo$$bar", EscapeString("foo$bar", opts, nullptr)); + // Spaces means the string is quoted, normal backslahes untouched. bool needs_quoting = false; EXPECT_EQ("\"foo\\$ bar\"", EscapeString("foo\\ bar", opts, &needs_quoting));