4 files changed, 55 insertions, 4 deletions
diff --git a/absl/strings/internal/cordz_info.h b/absl/strings/internal/cordz_info.h
index 13aaee17..026d5b99 100644
--- a/absl/strings/internal/cordz_info.h
+++ b/absl/strings/internal/cordz_info.h
@@ -158,6 +158,11 @@ class ABSL_LOCKABLE CordzInfo : public CordzHandle {
     return rep_;
   }
 
+  // Sets the current value of `rep_` for testing purposes only.
+  void SetCordRepForTesting(CordRep* rep) ABSL_NO_THREAD_SAFETY_ANALYSIS {
+    rep_ = rep;
+  }
+
   // Returns the stack trace for where the cord was first sampled. Cords are
   // potentially sampled when they promote from an inlined cord to a tree or
   // ring representation, which is not necessarily the location where the cord
diff --git a/absl/strings/internal/resize_uninitialized.h b/absl/strings/internal/resize_uninitialized.h
index e42628e3..749c66e7 100644
--- a/absl/strings/internal/resize_uninitialized.h
+++ b/absl/strings/internal/resize_uninitialized.h
@@ -17,6 +17,7 @@
 #ifndef ABSL_STRINGS_INTERNAL_RESIZE_UNINITIALIZED_H_
 #define ABSL_STRINGS_INTERNAL_RESIZE_UNINITIALIZED_H_
 
+#include <algorithm>
 #include <string>
 #include <type_traits>
 #include <utility>
@@ -66,6 +67,28 @@ inline void STLStringResizeUninitialized(string_type* s, size_t new_size) {
   ResizeUninitializedTraits<string_type>::Resize(s, new_size);
 }
 
+// Used to ensure exponential growth so that the amortized complexity of
+// increasing the string size by a small amount is O(1), in contrast to
+// O(str->size()) in the case of precise growth.
+template <typename string_type>
+void STLStringReserveAmortized(string_type* s, size_t new_size) {
+  const size_t cap = s->capacity();
+  if (new_size > cap) {
+    // Make sure to always grow by at least a factor of 2x.
+    s->reserve((std::max)(new_size, 2 * cap));
+  }
+}
+
+// Like STLStringResizeUninitialized(str, new_size), except guaranteed to use
+// exponential growth so that the amortized complexity of increasing the string
+// size by a small amount is O(1), in contrast to O(str->size()) in the case of
+// precise growth.
+template <typename string_type>
+void STLStringResizeUninitializedAmortized(string_type* s, size_t new_size) {
+  STLStringReserveAmortized(s, new_size);
+  STLStringResizeUninitialized(s, new_size);
+}
+
 }  // namespace strings_internal
 ABSL_NAMESPACE_END
 }  // namespace absl
diff --git a/absl/strings/internal/resize_uninitialized_test.cc b/absl/strings/internal/resize_uninitialized_test.cc
index 0f8b3c2a..01ee476b 100644
--- a/absl/strings/internal/resize_uninitialized_test.cc
+++ b/absl/strings/internal/resize_uninitialized_test.cc
@@ -24,11 +24,13 @@ int resize_call_count = 0;
 // resize() method has been called.
 struct resizable_string {
   size_t size() const { return 0; }
+  size_t capacity() const { return 0; }
   char& operator[](size_t) {
     static char c = '\0';
     return c;
   }
   void resize(size_t) { resize_call_count += 1; }
+  void reserve(size_t) {}
 };
 
 int resize_default_init_call_count = 0;
@@ -37,12 +39,14 @@ int resize_default_init_call_count = 0;
 // resize() and __resize_default_init() methods have been called.
 struct resize_default_init_string {
   size_t size() const { return 0; }
+  size_t capacity() const { return 0; }
   char& operator[](size_t) {
     static char c = '\0';
     return c;
   }
   void resize(size_t) { resize_call_count += 1; }
   void __resize_default_init(size_t) { resize_default_init_call_count += 1; }
+  void reserve(size_t) {}
 };
 
 TEST(ResizeUninit, WithAndWithout) {
@@ -60,6 +64,9 @@ TEST(ResizeUninit, WithAndWithout) {
     absl::strings_internal::STLStringResizeUninitialized(&rs, 237);
     EXPECT_EQ(resize_call_count, 1);
     EXPECT_EQ(resize_default_init_call_count, 0);
+    absl::strings_internal::STLStringResizeUninitializedAmortized(&rs, 1000);
+    EXPECT_EQ(resize_call_count, 2);
+    EXPECT_EQ(resize_default_init_call_count, 0);
   }
 
   resize_call_count = 0;
@@ -76,7 +83,23 @@ TEST(ResizeUninit, WithAndWithout) {
     absl::strings_internal::STLStringResizeUninitialized(&rus, 237);
     EXPECT_EQ(resize_call_count, 0);
     EXPECT_EQ(resize_default_init_call_count, 1);
+    absl::strings_internal::STLStringResizeUninitializedAmortized(&rus, 1000);
+    EXPECT_EQ(resize_call_count, 0);
+    EXPECT_EQ(resize_default_init_call_count, 2);
+  }
+}
+
+TEST(ResizeUninit, Amortized) {
+  std::string str;
+  size_t prev_cap = str.capacity();
+  int cap_increase_count = 0;
+  for (int i = 0; i < 1000; ++i) {
+    absl::strings_internal::STLStringResizeUninitializedAmortized(&str, i);
+    size_t new_cap = str.capacity();
+    if (new_cap > prev_cap) ++cap_increase_count;
+    prev_cap = new_cap;
   }
+  EXPECT_LT(cap_increase_count, 50);
 }
 
 }  // namespace
diff --git a/absl/strings/str_cat.cc b/absl/strings/str_cat.cc
index dd5d25b0..f4a77493 100644
--- a/absl/strings/str_cat.cc
+++ b/absl/strings/str_cat.cc
@@ -174,7 +174,7 @@ void AppendPieces(std::string* dest,
     ASSERT_NO_OVERLAP(*dest, piece);
     total_size += piece.size();
   }
-  strings_internal::STLStringResizeUninitialized(dest, total_size);
+  strings_internal::STLStringResizeUninitializedAmortized(dest, total_size);
 
   char* const begin = &(*dest)[0];
   char* out = begin + old_size;
@@ -199,7 +199,7 @@ 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::STLStringResizeUninitialized(
+  strings_internal::STLStringResizeUninitializedAmortized(
       dest, old_size + a.size() + b.size());
   char* const begin = &(*dest)[0];
   char* out = begin + old_size;
@@ -214,7 +214,7 @@ void StrAppend(std::string* dest, const AlphaNum& a, const AlphaNum& b,
   ASSERT_NO_OVERLAP(*dest, b);
   ASSERT_NO_OVERLAP(*dest, c);
   std::string::size_type old_size = dest->size();
-  strings_internal::STLStringResizeUninitialized(
+  strings_internal::STLStringResizeUninitializedAmortized(
       dest, old_size + a.size() + b.size() + c.size());
   char* const begin = &(*dest)[0];
   char* out = begin + old_size;
@@ -231,7 +231,7 @@ void StrAppend(std::string* dest, const AlphaNum& a, const AlphaNum& b,
   ASSERT_NO_OVERLAP(*dest, c);
   ASSERT_NO_OVERLAP(*dest, d);
   std::string::size_type old_size = dest->size();
-  strings_internal::STLStringResizeUninitialized(
+  strings_internal::STLStringResizeUninitializedAmortized(
       dest, old_size + a.size() + b.size() + c.size() + d.size());
   char* const begin = &(*dest)[0];
   char* out = begin + old_size;