Improve performance of StringOutputBuffer. StringOutputBuffer previously used a (start, size, capacity) representation for the current read-write page, updating an offset index on each write. This had two main drawbacks: 1) Every write required base + offset address recalculations. 2) Writable::WriteToBuf took a `size_t& upto` parameter alongside the `char buf[]`, creating a strict-aliasing hazard. This change optimizes StringOutputBuffer: - Adopts a 3-pointer cursor representation (rw_buf_, cur_, end_). In the hot path, writes only advance cur_, keeping the write pointer directly in CPU registers across chained writes. - Updates Writable and WriteToBuf to take and return a char*, eliminating both the aliasing hazard and offset arithmetic. - Splits Reserve into an inlined fast-path check (zero function calls on the hot path) and an out-of-line ReserveSlow for page rollover. - Removes redundant state (ro_size_ and rw_capacity_), computing total size on demand. - Simplifies str(), WriteToFile(), and ContentsEqual() to stream the active page using direct pointer ranges. Change-Id: I56da598fa9acfe31443b2049bbcd48e66a6a6964 Reviewed-on: https://gn-review.googlesource.com/c/gn/+/28180 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 61c41ef..7c633fe 100644 --- a/src/gn/escape.cc +++ b/src/gn/escape.cc
@@ -253,44 +253,43 @@ } // namespace -void Escaped::Space::WriteToBuf(char buf[], size_t& upto) const { - upto += EscapeStringToString_Space(str, &buf[upto]); +char* Escaped::Space::WriteToBuf(char* out) const { + return &out[EscapeStringToString_Space(str, out)]; } -void Escaped::Ninja::WriteToBuf(char buf[], size_t& upto) const { - upto += EscapeStringToString_Ninja(str, &buf[upto]); +char* Escaped::Ninja::WriteToBuf(char* out) const { + return &out[EscapeStringToString_Ninja(str, out)]; } -void Escaped::Depfile::WriteToBuf(char buf[], size_t& upto) const { - upto += EscapeStringToString_Depfile(str, &buf[upto]); +char* Escaped::Depfile::WriteToBuf(char* out) const { + return &out[EscapeStringToString_Depfile(str, out)]; } -void Escaped::CompilationDatabase::WriteToBuf(char buf[], size_t& upto) const { - upto += EscapeStringToString_CompilationDatabase(str, &buf[upto]); +char* Escaped::CompilationDatabase::WriteToBuf(char* out) const { + return &out[EscapeStringToString_CompilationDatabase(str, out)]; } -void Escaped::NinjaPreformatted::WriteToBuf(char buf[], size_t& upto) const { - upto += EscapeStringToString_NinjaPreformatted(str, &buf[upto]); +char* Escaped::NinjaPreformatted::WriteToBuf(char* out) const { + return &out[EscapeStringToString_NinjaPreformatted(str, out)]; } -void Escaped::Command::WriteToBuf(char buf[], size_t& upto) const { +char* Escaped::Command::WriteToBuf(char* out) const { switch (platform) { case ESCAPE_PLATFORM_CURRENT: #if defined(OS_WIN) - upto += EscapeStringToString_WindowsNinjaFork(str, inhibit_quoting, - &buf[upto], nullptr); + return &out[EscapeStringToString_WindowsNinjaFork(str, inhibit_quoting, + out, nullptr)]; #else - upto += EscapeStringToString_PosixNinjaFork(str, &buf[upto]); + return &out[EscapeStringToString_PosixNinjaFork(str, out)]; #endif - break; case ESCAPE_PLATFORM_WIN: - upto += EscapeStringToString_WindowsNinjaFork(str, inhibit_quoting, - &buf[upto], nullptr); - break; + return &out[EscapeStringToString_WindowsNinjaFork(str, inhibit_quoting, + out, nullptr)]; case ESCAPE_PLATFORM_POSIX: - upto += EscapeStringToString_PosixNinjaFork(str, &buf[upto]); - break; + return &out[EscapeStringToString_PosixNinjaFork(str, out)]; } + NOTREACHED(); + return out; } std::string EscapeString(std::string_view str,
diff --git a/src/gn/escape.h b/src/gn/escape.h index f32bf33..fd316dc 100644 --- a/src/gn/escape.h +++ b/src/gn/escape.h
@@ -78,7 +78,7 @@ // Only spaces (' ') are escaped with a preceding backslash ("\ "). In the // worst case (all spaces), each character expands to 2 characters. size_t MaximumSize() const { return str.size() * 2; } - void WriteToBuf(char buf[], size_t& upto) const; + char* WriteToBuf(char* out) const; }; struct Ninja { @@ -87,7 +87,7 @@ // Ninja special characters ('$', ' ', ':') are prefixed with '$' ("$$", // "$ ", "$:"). In the worst case, each character expands to 2 characters. size_t MaximumSize() const { return str.size() * 2; } - void WriteToBuf(char buf[], size_t& upto) const; + char* WriteToBuf(char* out) const; }; struct Depfile { @@ -97,7 +97,7 @@ // '\' and '$' is doubled to "$$". In all cases, each character expands to // at most 2 characters. size_t MaximumSize() const { return str.size() * 2; } - void WriteToBuf(char buf[], size_t& upto) const; + char* WriteToBuf(char* out) const; }; struct NinjaPreformatted { @@ -106,7 +106,7 @@ // Only '$' is escaped by doubling to "$$". In the worst case, each // character expands to 2 characters. size_t MaximumSize() const { return str.size() * 2; } - void WriteToBuf(char buf[], size_t& upto) const; + char* WriteToBuf(char* out) const; }; struct CompilationDatabase { @@ -116,7 +116,7 @@ // "\""), expanding each character to at most 2 characters. Up to 2 // enclosing double quotes are added if any character is invalid in shell. size_t MaximumSize() const { return str.size() * 2 + 2; } - void WriteToBuf(char buf[], size_t& upto) const; + char* WriteToBuf(char* out) const; }; struct Command { @@ -130,7 +130,7 @@ // In the worst case across platforms, 3 chars per input char plus 2 // enclosing quotes. size_t MaximumSize() const { return str.size() * 3 + 2; } - void WriteToBuf(char buf[], size_t& upto) const; + char* WriteToBuf(char* out) const; }; } // namespace Escaped
diff --git a/src/gn/string_output_buffer.cc b/src/gn/string_output_buffer.cc index 85bda0f..21614de 100644 --- a/src/gn/string_output_buffer.cc +++ b/src/gn/string_output_buffer.cc
@@ -15,27 +15,36 @@ void StringOutputBuffer::Clear() { ro_.clear(); - ro_size_ = 0; - rw_.size = 0; + cur_ = rw_buf_.get(); } -void StringOutputBuffer::Reserve(size_t n) { - if (UNLIKELY(page_free_size() < n)) { - if (rw_.size > 0) { - ro_.push_back(std::move(rw_)); - ro_size_ += rw_.size; +void StringOutputBuffer::ReserveSlow(size_t n) { + if (rw_buf_) { + size_t page_size = cur_ - rw_buf_.get(); + if (page_size > 0) { + ro_.push_back(Page{ + .buf = std::move(rw_buf_), + .size = page_size, + }); } - - // Pick the minimum number of pages required to store n bytes. - // So technically, our "Page" could actually be multiple pages - // But unless you attempt to call append on a ridiculously large string, - // this should never happen in practice. - rw_capacity_ = (n + kPageSize - 1) & ~(kPageSize - 1); - rw_ = Page{ - .buf = std::make_unique_for_overwrite<char[]>(rw_capacity_), - .size = 0, - }; } + + // Pick the minimum number of pages required to store n bytes. + // So technically, our "Page" could actually be multiple pages + // But unless you attempt to call append on a ridiculously large string, + // this should never happen in practice. + size_t capacity = (n + kPageSize - 1) & ~(kPageSize - 1); + rw_buf_ = std::make_unique_for_overwrite<char[]>(capacity); + cur_ = rw_buf_.get(); + end_ = cur_ + capacity; +} + +size_t StringOutputBuffer::size() const { + size_t total = rw_buf_ ? static_cast<size_t>(cur_ - rw_buf_.get()) : 0; + for (const auto& page : ro_) { + total += page.size; + } + return total; } std::string StringOutputBuffer::str() const { @@ -44,8 +53,8 @@ for (const auto& page : ro_) { result.append(page.buf.get(), page.size); } - if (rw_.size > 0) { - result.append(rw_.buf.get(), rw_.size); + if (rw_buf_) { + result.append(rw_buf_.get(), cur_); } return result; } @@ -66,24 +75,27 @@ std::vector<char> file_page; file_page.resize(kPageSize); - auto check_page = [&](const Page& page) { + auto check_page = [&](const char* page_buf, size_t page_size) { // Don't use reserve because if we do that, capacity is high enough but not // size. - if (UNLIKELY(file_page.size() < page.size)) { - file_page.resize(page.size); + if (UNLIKELY(file_page.size() < page_size)) { + file_page.resize(page_size); } - file.read(file_page.data(), page.size); + file.read(file_page.data(), page_size); if (!file.good()) return false; - return memcmp(file_page.data(), page.buf.get(), page.size) == 0; + return memcmp(file_page.data(), page_buf, page_size) == 0; }; for (const auto& page : ro_) { - if (!check_page(page)) + if (!check_page(page.buf.get(), page.size)) return false; } - return rw_.size == 0 || check_page(rw_); + if (cur_ > rw_buf_.get()) { + return check_page(rw_buf_.get(), cur_ - rw_buf_.get()); + } + return true; } // Write the contents of this instance to a file at |file_path|. @@ -107,8 +119,8 @@ if (!success) break; } - if (success && rw_.size > 0) { - success = writer.Write(std::string_view(rw_.buf.get(), rw_.size)); + if (success && rw_buf_) { + success = writer.Write(std::string_view(rw_buf_.get(), cur_)); } } if (!writer.Close())
diff --git a/src/gn/string_output_buffer.h b/src/gn/string_output_buffer.h index 102670d..9813582 100644 --- a/src/gn/string_output_buffer.h +++ b/src/gn/string_output_buffer.h
@@ -14,6 +14,8 @@ #include <string_view> #include <vector> +#include "base/compiler_specific.h" + namespace base { class FilePath; } // namespace base @@ -27,11 +29,11 @@ } template <typename T> - requires requires(const T& val, char buf[], size_t& upto) { - val.WriteToBuf(buf, upto); + requires requires(const T& val, char* out) { + { val.WriteToBuf(out) } -> std::same_as<char*>; } -inline void WriteToBuf(const T& val, char buf[], size_t& upto) { - val.WriteToBuf(buf, upto); +inline char* WriteToBuf(const T& val, char* out) { + return val.WriteToBuf(out); } class Err; @@ -39,16 +41,17 @@ inline size_t MaximumSize(std::string_view s) { return s.size(); } -inline void WriteToBuf(std::string_view s, char buf[], size_t& upto) { - memcpy(&buf[upto], s.data(), s.size()); - upto += s.size(); +inline char* WriteToBuf(std::string_view s, char* out) { + memcpy(out, s.data(), s.size()); + return out + s.size(); } inline size_t MaximumSize(char) { return 1; } -inline void WriteToBuf(char c, char buf[], size_t& upto) { - buf[upto++] = c; +inline char* WriteToBuf(char c, char* out) { + *out++ = c; + return out; } template <typename T> @@ -65,16 +68,15 @@ template <typename T> requires(std::integral<T> && !std::same_as<T, char> && !std::same_as<T, bool>) -inline void WriteToBuf(T val, char buf[], size_t& upto) { - upto = - std::to_chars(&buf[upto], &buf[upto + MaximumSize(val)], val).ptr - buf; +inline char* WriteToBuf(T val, char* out) { + return std::to_chars(out, out + MaximumSize(val), val).ptr; } template <typename T> concept Writable = !std::same_as<std::remove_cvref_t<T>, bool> && - requires(const T& val, char buf[], size_t& upto) { + requires(const T& val, char* out) { { MaximumSize(val) } -> std::convertible_to<size_t>; - WriteToBuf(val, buf, upto); + { WriteToBuf(val, out) } -> std::same_as<char*>; }; // An append-only very large storage area for string data. Useful for the parts @@ -103,12 +105,12 @@ std::string str() const; // Return the number of characters stored in this instance. - size_t size() const { return ro_size_ + rw_.size; } + size_t size() const; // Append a value to this instance. void Append(const Writable auto& value) { Reserve(MaximumSize(value)); - WriteToBuf(value, rw_.buf.get(), rw_.size); + cur_ = WriteToBuf(value, cur_); } void Append(const char* str, size_t len) { Append(std::string_view(str, len)); @@ -133,11 +135,17 @@ private: // Return the number of free bytes in the current page. - size_t page_free_size() const { return rw_capacity_ - rw_.size; } + size_t page_free_size() const { return end_ - cur_; } // Ensures that the read-write section of the buffer has at least n bytes // available. - void Reserve(size_t n); + void Reserve(size_t n) { + if (UNLIKELY(page_free_size() < n)) { + ReserveSlow(n); + } + } + + void ReserveSlow(size_t n); static constexpr size_t kPageSize = 65536; @@ -146,16 +154,16 @@ size_t size = 0; }; - // Because this is an extremely hot path, we avoid pointer indirection by - // storing the current page inline. - // The current page is read-write. - Page rw_; - size_t rw_capacity_ = 0; + // The current read-write page buffer and write cursors. + // We use a three-pointer approach instead of (start, size, capacity). + // This is because we are optimizing for writes being as fast as possible, + // so we only need to update cur_ most of the time. + std::unique_ptr<char[]> rw_buf_; + char* cur_ = nullptr; + char* end_ = nullptr; // Completed read-only pages. std::vector<Page> ro_; - // Contains sum([page.size for page in ro_]) - size_t ro_size_ = 0; }; std::string Pretty(const StringOutputBuffer& buffer);
diff --git a/src/gn/string_output_buffer_unittest.cc b/src/gn/string_output_buffer_unittest.cc index e907dd0..36101e5 100644 --- a/src/gn/string_output_buffer_unittest.cc +++ b/src/gn/string_output_buffer_unittest.cc
@@ -147,12 +147,12 @@ return greeting.name.size() + 7; } -void WriteToBuf(const CustomGreeting& greeting, char* buf, size_t& size) { +char* WriteToBuf(const CustomGreeting& greeting, char* buf) { constexpr std::string_view prefix = "Hello, "; - memcpy(buf + size, prefix.data(), prefix.size()); - size += prefix.size(); - memcpy(buf + size, greeting.name.data(), greeting.name.size()); - size += greeting.name.size(); + memcpy(buf, prefix.data(), prefix.size()); + buf += prefix.size(); + memcpy(buf, greeting.name.data(), greeting.name.size()); + return buf + greeting.name.size(); } static_assert(Writable<CustomGreeting>);