Speed up StrAppend by up to 4x.

PiperOrigin-RevId: 552802740
Change-Id: I662da1b03bfffb7939b44ea3850566d3c209c6cc

1 files changed, 121 insertions, 31 deletions

diff --git a/absl/strings/str_cat.h b/absl/strings/str_cat.h
index d5f71ff0..f5f2c016 100644
--- a/absl/strings/str_cat.h
+++ b/absl/strings/str_cat.h
@@ -91,7 +91,9 @@
 #include <array>
 #include <cstdint>
 #include <cstring>
+#include <functional>
 #include <string>
+#include <tuple>
 #include <type_traits>
 #include <utility>
 #include <vector>
@@ -99,6 +101,7 @@
 #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"
@@ -409,6 +412,93 @@ 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 <typename F, typename Acc>
+auto FoldLeft(const F&, Acc&& acc) {
+  return std::forward<Acc>(acc);
+}
+template <typename F, typename Acc, typename First, typename... Rest>
+auto FoldLeft(const F& f, Acc&& acc, First&& first, Rest&&... rest) {
+  return FoldLeft(f, f(std::forward<Acc>(acc), std::forward<First>(first)),
+                  std::forward<Rest>(rest)...);
+}
+
+template <std::size_t... Indices, typename Tuple>
+inline void StrAppendTemplate(std::index_sequence<Indices...>,
+                              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<N>` and is used as a
+  //   helper to writing Fold expressions on `Tuple`.
+  assert(FoldLeft(std::logical_and<>{},
+                  !HaveOverlap(*dest, std::get<Indices>(args).Piece())...));
+  size_t old_size = dest->size();
+  size_t new_size =
+      FoldLeft(std::plus<>{}, old_size, std::get<Indices>(args).size()...);
+  strings_internal::STLStringResizeUninitializedAmortized(dest, new_size);
+  FoldLeft(AppendAlphaNum, &(*dest)[old_size], std::get<Indices>(args)...);
+}
+
+template <std::size_t... Indices, typename Tuple>
+inline std::string StrCatTemplate(std::index_sequence<Indices...>, Tuple args) {
+  // See implementation comments in `StrAppendTemplate`.
+  std::string dest;
+  size_t size = FoldLeft(std::plus<size_t>{}, size_t{0},
+                         std::get<Indices>(args).size()...);
+  strings_internal::STLStringResizeUninitializedAmortized(&dest, size);
+  FoldLeft(AppendAlphaNum, &dest[0], std::get<Indices>(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 <typename... AV>
+inline void StrAppendImpl(std::string* dest, const AV&... args) {
+  strings_internal::StrAppendTemplate(
+      std::make_index_sequence<sizeof...(AV)>{}, dest,
+      std::forward_as_tuple(static_cast<const AlphaNum&>(args)...));
+}
+
+template <typename... AV>
+inline std::string StrCatImpl(const AV&... args) {
+  return strings_internal::StrCatTemplate(
+      std::make_index_sequence<sizeof...(AV)>{},
+      std::forward_as_tuple(static_cast<const AlphaNum&>(args)...));
+}
+
+}  // namespace strings_internal
+
 // -----------------------------------------------------------------------------
 // StrCat()
 // -----------------------------------------------------------------------------
@@ -436,36 +526,32 @@ class AlphaNum {
 // 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<absl::string_view> pieces);
-void AppendPieces(std::string* dest,
-                  std::initializer_list<absl::string_view> 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 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);
+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);
+}
 
 // Support 5 or more arguments
 template <typename... AV>
 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::CatPieces(
-      {a.Piece(), b.Piece(), c.Piece(), d.Piece(), e.Piece(),
-       static_cast<const AlphaNum&>(args).Piece()...});
+  return strings_internal::StrCatImpl(a, b, c, d, e, args...);
 }
 
 // -----------------------------------------------------------------------------
@@ -494,23 +580,27 @@ 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*) {}
-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);
-
+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);
+}
 // Support 5 or more arguments
 template <typename... AV>
 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::AppendPieces(
-      dest, {a.Piece(), b.Piece(), c.Piece(), d.Piece(), e.Piece(),
-             static_cast<const AlphaNum&>(args).Piece()...});
+  strings_internal::StrAppendImpl(dest, a, b, c, d, e, args...);
 }
 
 // Helper function for the future StrCat default floating-point format, %.6g