From 5d06f796b7ed59234c603457d130d23addc400fd Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Wed, 2 Aug 2023 08:49:17 -0700 Subject: Rollback of "Speed up StrAppend by up to 4x." PiperOrigin-RevId: 553158292 Change-Id: I28350321550accd72da2f9f6f5992af311fe4b00 --- absl/strings/str_cat.cc | 178 ++++++++++++++++++++++++++++++++++++++++++++---- absl/strings/str_cat.h | 152 +++++++++-------------------------------- 2 files changed, 196 insertions(+), 134 deletions(-) diff --git a/absl/strings/str_cat.cc b/absl/strings/str_cat.cc index 5ec02995..2e49c31b 100644 --- a/absl/strings/str_cat.cc +++ b/absl/strings/str_cat.cc @@ -14,9 +14,17 @@ #include "absl/strings/str_cat.h" +#include + +#include +#include #include +#include #include +#include "absl/strings/ascii.h" +#include "absl/strings/internal/resize_uninitialized.h" +#include "absl/strings/numbers.h" #include "absl/strings/string_view.h" namespace absl { @@ -29,26 +37,170 @@ ABSL_NAMESPACE_BEGIN // of a mix of raw C strings, string_views, strings, and integer values. // ---------------------------------------------------------------------- +// Append is merely a version of memcpy that returns the address of the byte +// after the area just overwritten. +static char* Append(char* out, const AlphaNum& x) { + // memcpy is allowed to overwrite arbitrary memory, so doing this after the + // call would force an extra fetch of x.size(). + char* after = out + x.size(); + if (x.size() != 0) { + memcpy(out, x.data(), x.size()); + } + return after; +} + +std::string StrCat(const AlphaNum& a, const AlphaNum& b) { + std::string result; + absl::strings_internal::STLStringResizeUninitialized(&result, + a.size() + b.size()); + char* const begin = &result[0]; + char* out = begin; + out = Append(out, a); + out = Append(out, b); + assert(out == begin + result.size()); + return result; +} + +std::string StrCat(const AlphaNum& a, const AlphaNum& b, const AlphaNum& c) { + std::string result; + strings_internal::STLStringResizeUninitialized( + &result, a.size() + b.size() + c.size()); + char* const begin = &result[0]; + char* out = begin; + out = Append(out, a); + out = Append(out, b); + out = Append(out, c); + assert(out == begin + result.size()); + return result; +} + +std::string StrCat(const AlphaNum& a, const AlphaNum& b, const AlphaNum& c, + const AlphaNum& d) { + std::string result; + strings_internal::STLStringResizeUninitialized( + &result, a.size() + b.size() + c.size() + d.size()); + char* const begin = &result[0]; + char* out = begin; + out = Append(out, a); + out = Append(out, b); + out = Append(out, c); + out = Append(out, d); + assert(out == begin + result.size()); + return result; +} + namespace strings_internal { -bool HaveOverlap(const std::string& x, absl::string_view y) { - if (y.empty()) return false; - // TODO(b/290623057): Re-evaluate the check below: it detects when buffers - // overlap (which is good) but it also introduces undefined behaviour when - // buffers don't overlap (substracting pointers that do not belong to the same - // array is UB [expr.add]). In other words, if compiler assumes that a program - // never has UB, then it can replace `assert(HaveOverlap(x, y))` with - // `assert(false)`. - return (uintptr_t(y.data() - x.data()) <= uintptr_t(x.size())); +// Do not call directly - these are not part of the public API. +std::string CatPieces(std::initializer_list pieces) { + std::string result; + size_t total_size = 0; + for (absl::string_view piece : pieces) total_size += piece.size(); + strings_internal::STLStringResizeUninitialized(&result, total_size); + + char* const begin = &result[0]; + char* out = begin; + for (absl::string_view piece : pieces) { + const size_t this_size = piece.size(); + if (this_size != 0) { + memcpy(out, piece.data(), this_size); + out += this_size; + } + } + assert(out == begin + result.size()); + return result; } -#if defined(__GNUC__) && !defined(__clang__) -char* AppendAlphaNum(char* dst, const AlphaNum& a) { - return std::copy_n(a.data(), a.size(), dst); +// It's possible to call StrAppend with an absl::string_view that is itself a +// fragment of the string we're appending to. However the results of this are +// random. Therefore, check for this in debug mode. Use unsigned math so we +// only have to do one comparison. Note, there's an exception case: appending an +// empty string is always allowed. +#define ASSERT_NO_OVERLAP(dest, src) \ + assert(((src).size() == 0) || \ + (uintptr_t((src).data() - (dest).data()) > uintptr_t((dest).size()))) + +void AppendPieces(std::string* dest, + std::initializer_list pieces) { + size_t old_size = dest->size(); + size_t total_size = old_size; + for (absl::string_view piece : pieces) { + ASSERT_NO_OVERLAP(*dest, piece); + total_size += piece.size(); + } + strings_internal::STLStringResizeUninitializedAmortized(dest, total_size); + + char* const begin = &(*dest)[0]; + char* out = begin + old_size; + for (absl::string_view piece : pieces) { + const size_t this_size = piece.size(); + if (this_size != 0) { + memcpy(out, piece.data(), this_size); + out += this_size; + } + } + assert(out == begin + dest->size()); } -#endif } // namespace strings_internal +void StrAppend(std::string* dest, const AlphaNum& a) { + ASSERT_NO_OVERLAP(*dest, a); + std::string::size_type old_size = dest->size(); + strings_internal::STLStringResizeUninitializedAmortized(dest, + old_size + a.size()); + char* const begin = &(*dest)[0]; + char* out = begin + old_size; + out = Append(out, a); + assert(out == begin + dest->size()); +} + +void StrAppend(std::string* dest, const AlphaNum& a, const AlphaNum& b) { + ASSERT_NO_OVERLAP(*dest, a); + ASSERT_NO_OVERLAP(*dest, b); + std::string::size_type old_size = dest->size(); + strings_internal::STLStringResizeUninitializedAmortized( + dest, old_size + a.size() + b.size()); + char* const begin = &(*dest)[0]; + char* out = begin + old_size; + out = Append(out, a); + out = Append(out, b); + assert(out == begin + dest->size()); +} + +void StrAppend(std::string* dest, const AlphaNum& a, const AlphaNum& b, + const AlphaNum& c) { + ASSERT_NO_OVERLAP(*dest, a); + ASSERT_NO_OVERLAP(*dest, b); + ASSERT_NO_OVERLAP(*dest, c); + std::string::size_type old_size = dest->size(); + strings_internal::STLStringResizeUninitializedAmortized( + dest, old_size + a.size() + b.size() + c.size()); + char* const begin = &(*dest)[0]; + char* out = begin + old_size; + out = Append(out, a); + out = Append(out, b); + out = Append(out, c); + assert(out == begin + dest->size()); +} + +void StrAppend(std::string* dest, const AlphaNum& a, const AlphaNum& b, + const AlphaNum& c, const AlphaNum& d) { + ASSERT_NO_OVERLAP(*dest, a); + ASSERT_NO_OVERLAP(*dest, b); + ASSERT_NO_OVERLAP(*dest, c); + ASSERT_NO_OVERLAP(*dest, d); + std::string::size_type old_size = dest->size(); + strings_internal::STLStringResizeUninitializedAmortized( + dest, old_size + a.size() + b.size() + c.size() + d.size()); + char* const begin = &(*dest)[0]; + char* out = begin + old_size; + out = Append(out, a); + out = Append(out, b); + out = Append(out, c); + out = Append(out, d); + assert(out == begin + dest->size()); +} + ABSL_NAMESPACE_END } // namespace absl diff --git a/absl/strings/str_cat.h b/absl/strings/str_cat.h index f5f2c016..d5f71ff0 100644 --- a/absl/strings/str_cat.h +++ b/absl/strings/str_cat.h @@ -91,9 +91,7 @@ #include #include #include -#include #include -#include #include #include #include @@ -101,7 +99,6 @@ #include "absl/base/attributes.h" #include "absl/base/port.h" #include "absl/strings/internal/has_absl_stringify.h" -#include "absl/strings/internal/resize_uninitialized.h" #include "absl/strings/internal/stringify_sink.h" #include "absl/strings/numbers.h" #include "absl/strings/string_view.h" @@ -412,93 +409,6 @@ class AlphaNum { char digits_[numbers_internal::kFastToBufferSize]; }; -namespace strings_internal { - -// Inlining this function improves performance. However, on GCC this triggers -// [-Werror=stringop-overflow=], and in that case we split declaration and -// definition as a workaround. -#if defined(__GNUC__) && !defined(__clang__) -char* AppendAlphaNum(char* dst, const AlphaNum& a); -#else -inline char* AppendAlphaNum(char* dst, const AlphaNum& a) { - return std::copy_n(a.data(), a.size(), dst); -} -#endif - -// It's possible to call StrAppend with an absl::string_view that is itself a -// fragment of the string we're appending to. However the results of this are -// UB. Therefore, check for this in debug mode. Use unsigned math so we -// only have to do one comparison. Note, there's an exception case: appending an -// empty string is always allowed. -bool HaveOverlap(const std::string& x, absl::string_view y); - -// C++14 compatible alternative to left -// https://en.cppreference.com/w/cpp/language/fold expression. -// TODO(b/290784225): Remove `FoldLeft` once Abseil drops C++14 support. -template -auto FoldLeft(const F&, Acc&& acc) { - return std::forward(acc); -} -template -auto FoldLeft(const F& f, Acc&& acc, First&& first, Rest&&... rest) { - return FoldLeft(f, f(std::forward(acc), std::forward(first)), - std::forward(rest)...); -} - -template -inline void StrAppendTemplate(std::index_sequence, - std::string* dest, Tuple args) { - // Note on `Is` and `Tuple`: - // - // The goal is to pass N arguments to `StrAppend` and retain `N` as a - // compile-time constant. Thus, we cannot use dynamically sized collections - // such as `absl::Span` or `std::initialized_list`: `std::tuple` comes to - // the rescue. - // `Tuple` is a fixed-sized collection of N elements of `const AlphaNum&`. - // `Indices` is deduced from `std::make_index_sequence` and is used as a - // helper to writing Fold expressions on `Tuple`. - assert(FoldLeft(std::logical_and<>{}, - !HaveOverlap(*dest, std::get(args).Piece())...)); - size_t old_size = dest->size(); - size_t new_size = - FoldLeft(std::plus<>{}, old_size, std::get(args).size()...); - strings_internal::STLStringResizeUninitializedAmortized(dest, new_size); - FoldLeft(AppendAlphaNum, &(*dest)[old_size], std::get(args)...); -} - -template -inline std::string StrCatTemplate(std::index_sequence, Tuple args) { - // See implementation comments in `StrAppendTemplate`. - std::string dest; - size_t size = FoldLeft(std::plus{}, size_t{0}, - std::get(args).size()...); - strings_internal::STLStringResizeUninitializedAmortized(&dest, size); - FoldLeft(AppendAlphaNum, &dest[0], std::get(args)...); - return dest; -} - -// Template functions `StrAppendImpl` and `StrCatImpl` are not exported directly -// due to historical reasons: there are many existing dependencies that expect -// 0-4 argument overloads to be non-template functions. Hence implementations -// are wrapped to keep the compatibility (0-4 arguments only, 5+ arguments are -// templates). - -template -inline void StrAppendImpl(std::string* dest, const AV&... args) { - strings_internal::StrAppendTemplate( - std::make_index_sequence{}, dest, - std::forward_as_tuple(static_cast(args)...)); -} - -template -inline std::string StrCatImpl(const AV&... args) { - return strings_internal::StrCatTemplate( - std::make_index_sequence{}, - std::forward_as_tuple(static_cast(args)...)); -} - -} // namespace strings_internal - // ----------------------------------------------------------------------------- // StrCat() // ----------------------------------------------------------------------------- @@ -526,32 +436,36 @@ inline std::string StrCatImpl(const AV&... args) { // quadratic time operation with O(n) dynamic allocations. // // See `StrAppend()` below for more information. + +namespace strings_internal { + +// Do not call directly - this is not part of the public API. +std::string CatPieces(std::initializer_list pieces); +void AppendPieces(std::string* dest, + std::initializer_list pieces); + +} // namespace strings_internal + ABSL_MUST_USE_RESULT inline std::string StrCat() { return std::string(); } + ABSL_MUST_USE_RESULT inline std::string StrCat(const AlphaNum& a) { return std::string(a.data(), a.size()); } -ABSL_MUST_USE_RESULT inline std::string StrCat(const AlphaNum& a, - const AlphaNum& b) { - return strings_internal::StrCatImpl(a, b); -} -ABSL_MUST_USE_RESULT inline std::string StrCat(const AlphaNum& a, - const AlphaNum& b, - const AlphaNum& c) { - return strings_internal::StrCatImpl(a, b, c); -} -ABSL_MUST_USE_RESULT inline std::string StrCat(const AlphaNum& a, - const AlphaNum& b, - const AlphaNum& c, - const AlphaNum& d) { - return strings_internal::StrCatImpl(a, b, c, d); -} + +ABSL_MUST_USE_RESULT std::string StrCat(const AlphaNum& a, const AlphaNum& b); +ABSL_MUST_USE_RESULT std::string StrCat(const AlphaNum& a, const AlphaNum& b, + const AlphaNum& c); +ABSL_MUST_USE_RESULT std::string StrCat(const AlphaNum& a, const AlphaNum& b, + const AlphaNum& c, const AlphaNum& d); // Support 5 or more arguments template ABSL_MUST_USE_RESULT inline std::string StrCat( const AlphaNum& a, const AlphaNum& b, const AlphaNum& c, const AlphaNum& d, const AlphaNum& e, const AV&... args) { - return strings_internal::StrCatImpl(a, b, c, d, e, args...); + return strings_internal::CatPieces( + {a.Piece(), b.Piece(), c.Piece(), d.Piece(), e.Piece(), + static_cast(args).Piece()...}); } // ----------------------------------------------------------------------------- @@ -580,27 +494,23 @@ ABSL_MUST_USE_RESULT inline std::string StrCat( // std::string s = "foobar"; // absl::string_view p = s; // StrAppend(&s, p); + inline void StrAppend(std::string*) {} -inline void StrAppend(std::string* dest, const AlphaNum& a) { - strings_internal::StrAppendImpl(dest, a); -} -inline void StrAppend(std::string* dest, const AlphaNum& a, const AlphaNum& b) { - strings_internal::StrAppendImpl(dest, a, b); -} -inline void StrAppend(std::string* dest, const AlphaNum& a, const AlphaNum& b, - const AlphaNum& c) { - strings_internal::StrAppendImpl(dest, a, b, c); -} -inline void StrAppend(std::string* dest, const AlphaNum& a, const AlphaNum& b, - const AlphaNum& c, const AlphaNum& d) { - strings_internal::StrAppendImpl(dest, a, b, c, d); -} +void StrAppend(std::string* dest, const AlphaNum& a); +void StrAppend(std::string* dest, const AlphaNum& a, const AlphaNum& b); +void StrAppend(std::string* dest, const AlphaNum& a, const AlphaNum& b, + const AlphaNum& c); +void StrAppend(std::string* dest, const AlphaNum& a, const AlphaNum& b, + const AlphaNum& c, const AlphaNum& d); + // Support 5 or more arguments template inline void StrAppend(std::string* dest, const AlphaNum& a, const AlphaNum& b, const AlphaNum& c, const AlphaNum& d, const AlphaNum& e, const AV&... args) { - strings_internal::StrAppendImpl(dest, a, b, c, d, e, args...); + strings_internal::AppendPieces( + dest, {a.Piece(), b.Piece(), c.Piece(), d.Piece(), e.Piece(), + static_cast(args).Piece()...}); } // Helper function for the future StrCat default floating-point format, %.6g -- cgit v1.2.3