Optimize integer-to-string conversions

The updated code is designed to:
- Be branch-predictor-friendly
- Be cache-friendly
- Minimize the lengths of critical paths
- Minimize slow operations (particularly multiplications)
- Minimize binary/codegen bloat

The most notable performance trick here is perhaps the precomputation & caching of the number of digits, so that we can reuse/exploit it when writing the output.

This precomputation of the exact length enables 2 further performance benefits:
- It makes `StrCat` and `StrAppend` zero-copy when only integers are passed, by avoiding intermediate `AlphaNum` entirely in those cases. If needed in the future, we can probably also make many other mixtures of non-integer types zero-copy as well.
- It avoids over-reservation of the string buffer, allowing for more strings to fit inside SSO, which will likely have further performance benefits.

There is also a side benefit of preventing `FastIntToBuffer` from writing beyond the end of the buffer, which has caused buffer overflows in the past.

The new code continues to use & extend some of the existing core tricks (such as the division-by-100 trick), as those are already efficient.

PiperOrigin-RevId: 595785531
Change-Id: Id6920e7e038fec10b2c45f213de75dc7e2cbddd1

1 files changed, 46 insertions, 0 deletions

diff --git a/absl/strings/str_cat_test.cc b/absl/strings/str_cat_test.cc
index 66eddf0d..b30a86fe 100644
--- a/absl/strings/str_cat_test.cc
+++ b/absl/strings/str_cat_test.cc
@@ -39,6 +39,24 @@
 
 namespace {
 
+template <typename Integer>
+void VerifyInteger(Integer value) {
+  const std::string expected = std::to_string(value);
+
+  EXPECT_EQ(absl::StrCat(value), expected);
+
+  const char* short_prefix = "x";
+  const char* long_prefix = "2;k.msabxiuow2[09i;o3k21-93-9=29]";
+
+  std::string short_str = short_prefix;
+  absl::StrAppend(&short_str, value);
+  EXPECT_EQ(short_str, short_prefix + expected);
+
+  std::string long_str = long_prefix;
+  absl::StrAppend(&long_str, value);
+  EXPECT_EQ(long_str, long_prefix + expected);
+}
+
 // Test absl::StrCat of ints and longs of various sizes and signdedness.
 TEST(StrCat, Ints) {
   const short s = -1;  // NOLINT(runtime/int)
@@ -68,6 +86,34 @@ TEST(StrCat, Ints) {
   EXPECT_EQ(answer, "-9-12");
   answer = absl::StrCat(uintptr, 0);
   EXPECT_EQ(answer, "130");
+
+  for (const uint32_t base : {2u, 10u}) {
+    for (const int extra_shift : {0, 12}) {
+      for (uint64_t i = 0; i < (1 << 8); ++i) {
+        uint64_t j = i;
+        while (true) {
+          uint64_t v = j ^ (extra_shift != 0 ? (j << extra_shift) * base : 0);
+          VerifyInteger(static_cast<bool>(v));
+          VerifyInteger(static_cast<wchar_t>(v));
+          VerifyInteger(static_cast<signed char>(v));
+          VerifyInteger(static_cast<unsigned char>(v));
+          VerifyInteger(static_cast<short>(v));               // NOLINT
+          VerifyInteger(static_cast<unsigned short>(v));      // NOLINT
+          VerifyInteger(static_cast<int>(v));                 // NOLINT
+          VerifyInteger(static_cast<unsigned int>(v));        // NOLINT
+          VerifyInteger(static_cast<long>(v));                // NOLINT
+          VerifyInteger(static_cast<unsigned long>(v));       // NOLINT
+          VerifyInteger(static_cast<long long>(v));           // NOLINT
+          VerifyInteger(static_cast<unsigned long long>(v));  // NOLINT
+          const uint64_t next = j == 0 ? 1 : j * base;
+          if (next <= j) {
+            break;
+          }
+          j = next;
+        }
+      }
+    }
+  }
 }
 
 TEST(StrCat, Enums) {