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, 134 insertions, 12 deletions

diff --git a/absl/strings/str_cat.cc b/absl/strings/str_cat.cc
index e7f7052a..098ab183 100644
--- a/absl/strings/str_cat.cc
+++ b/absl/strings/str_cat.cc
@@ -21,10 +21,12 @@
 #include <cstring>
 #include <initializer_list>
 #include <string>
+#include <type_traits>
 
 #include "absl/base/config.h"
 #include "absl/base/nullability.h"
 #include "absl/strings/internal/resize_uninitialized.h"
+#include "absl/strings/numbers.h"
 #include "absl/strings/string_view.h"
 
 namespace absl {
@@ -41,8 +43,7 @@ ABSL_NAMESPACE_BEGIN
 namespace {
 // Append is merely a version of memcpy that returns the address of the byte
 // after the area just overwritten.
-inline absl::Nonnull<char*> Append(absl::Nonnull<char*> out,
-                                   const AlphaNum& x) {
+absl::Nonnull<char*> Append(absl::Nonnull<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();
@@ -52,11 +53,6 @@ inline absl::Nonnull<char*> Append(absl::Nonnull<char*> out,
   return after;
 }
 
-inline void STLStringAppendUninitializedAmortized(std::string* dest,
-                                                  size_t to_append) {
-  strings_internal::AppendUninitializedTraits<std::string>::Append(dest,
-                                                                   to_append);
-}
 }  // namespace
 
 std::string StrCat(const AlphaNum& a, const AlphaNum& b) {
@@ -102,6 +98,130 @@ std::string StrCat(const AlphaNum& a, const AlphaNum& b, const AlphaNum& c,
 namespace strings_internal {
 
 // Do not call directly - these are not part of the public API.
+void STLStringAppendUninitializedAmortized(std::string* dest,
+                                           size_t to_append) {
+  strings_internal::AppendUninitializedTraits<std::string>::Append(dest,
+                                                                   to_append);
+}
+
+template <typename Integer>
+std::enable_if_t<std::is_integral<Integer>::value, std::string> IntegerToString(
+    Integer i) {
+  std::string str;
+  const auto /* either bool or std::false_type */ is_negative =
+      absl::numbers_internal::IsNegative(i);
+  const uint32_t digits = absl::numbers_internal::Base10Digits(
+      absl::numbers_internal::UnsignedAbsoluteValue(i));
+  absl::strings_internal::STLStringResizeUninitialized(
+      &str, digits + static_cast<uint32_t>(is_negative));
+  absl::numbers_internal::FastIntToBufferBackward(i, &str[str.size()], digits);
+  return str;
+}
+
+template <>
+std::string IntegerToString(long i) {  // NOLINT
+  if (sizeof(i) <= sizeof(int)) {
+    return IntegerToString(static_cast<int>(i));
+  } else {
+    return IntegerToString(static_cast<long long>(i));  // NOLINT
+  }
+}
+
+template <>
+std::string IntegerToString(unsigned long i) {  // NOLINT
+  if (sizeof(i) <= sizeof(unsigned int)) {
+    return IntegerToString(static_cast<unsigned int>(i));
+  } else {
+    return IntegerToString(static_cast<unsigned long long>(i));  // NOLINT
+  }
+}
+
+template <typename Float>
+std::enable_if_t<std::is_floating_point<Float>::value, std::string>
+FloatToString(Float f) {
+  std::string result;
+  strings_internal::STLStringResizeUninitialized(
+      &result, numbers_internal::kSixDigitsToBufferSize);
+  char* start = &result[0];
+  result.erase(numbers_internal::SixDigitsToBuffer(f, start));
+  return result;
+}
+
+std::string SingleArgStrCat(int x) { return IntegerToString(x); }
+std::string SingleArgStrCat(unsigned int x) { return IntegerToString(x); }
+// NOLINTNEXTLINE
+std::string SingleArgStrCat(long x) { return IntegerToString(x); }
+// NOLINTNEXTLINE
+std::string SingleArgStrCat(unsigned long x) { return IntegerToString(x); }
+// NOLINTNEXTLINE
+std::string SingleArgStrCat(long long x) { return IntegerToString(x); }
+// NOLINTNEXTLINE
+std::string SingleArgStrCat(unsigned long long x) { return IntegerToString(x); }
+std::string SingleArgStrCat(float x) { return FloatToString(x); }
+std::string SingleArgStrCat(double x) { return FloatToString(x); }
+
+template <class Integer>
+std::enable_if_t<std::is_integral<Integer>::value, void> AppendIntegerToString(
+    std::string& str, Integer i) {
+  const auto /* either bool or std::false_type */ is_negative =
+      absl::numbers_internal::IsNegative(i);
+  const uint32_t digits = absl::numbers_internal::Base10Digits(
+      absl::numbers_internal::UnsignedAbsoluteValue(i));
+  absl::strings_internal::STLStringAppendUninitializedAmortized(
+      &str, digits + static_cast<uint32_t>(is_negative));
+  absl::numbers_internal::FastIntToBufferBackward(i, &str[str.size()], digits);
+}
+
+template <>
+void AppendIntegerToString(std::string& str, long i) {  // NOLINT
+  if (sizeof(i) <= sizeof(int)) {
+    return AppendIntegerToString(str, static_cast<int>(i));
+  } else {
+    return AppendIntegerToString(str, static_cast<long long>(i));  // NOLINT
+  }
+}
+
+template <>
+void AppendIntegerToString(std::string& str,
+                           unsigned long i) {  // NOLINT
+  if (sizeof(i) <= sizeof(unsigned int)) {
+    return AppendIntegerToString(str, static_cast<unsigned int>(i));
+  } else {
+    return AppendIntegerToString(str,
+                                 static_cast<unsigned long long>(i));  // NOLINT
+  }
+}
+
+// `SingleArgStrAppend` overloads are defined here for the same reasons as with
+// `SingleArgStrCat` above.
+void SingleArgStrAppend(std::string& str, int x) {
+  return AppendIntegerToString(str, x);
+}
+
+void SingleArgStrAppend(std::string& str, unsigned int x) {
+  return AppendIntegerToString(str, x);
+}
+
+// NOLINTNEXTLINE
+void SingleArgStrAppend(std::string& str, long x) {
+  return AppendIntegerToString(str, x);
+}
+
+// NOLINTNEXTLINE
+void SingleArgStrAppend(std::string& str, unsigned long x) {
+  return AppendIntegerToString(str, x);
+}
+
+// NOLINTNEXTLINE
+void SingleArgStrAppend(std::string& str, long long x) {
+  return AppendIntegerToString(str, x);
+}
+
+// NOLINTNEXTLINE
+void SingleArgStrAppend(std::string& str, unsigned long long x) {
+  return AppendIntegerToString(str, x);
+}
+
 std::string CatPieces(std::initializer_list<absl::string_view> pieces) {
   std::string result;
   size_t total_size = 0;
@@ -138,7 +258,7 @@ void AppendPieces(absl::Nonnull<std::string*> dest,
     ASSERT_NO_OVERLAP(*dest, piece);
     to_append += piece.size();
   }
-  STLStringAppendUninitializedAmortized(dest, to_append);
+  strings_internal::STLStringAppendUninitializedAmortized(dest, to_append);
 
   char* const begin = &(*dest)[0];
   char* out = begin + old_size;
@@ -157,7 +277,7 @@ void AppendPieces(absl::Nonnull<std::string*> dest,
 void StrAppend(absl::Nonnull<std::string*> dest, const AlphaNum& a) {
   ASSERT_NO_OVERLAP(*dest, a);
   std::string::size_type old_size = dest->size();
-  STLStringAppendUninitializedAmortized(dest, a.size());
+  strings_internal::STLStringAppendUninitializedAmortized(dest, a.size());
   char* const begin = &(*dest)[0];
   char* out = begin + old_size;
   out = Append(out, a);
@@ -169,7 +289,8 @@ void StrAppend(absl::Nonnull<std::string*> dest, const AlphaNum& a,
   ASSERT_NO_OVERLAP(*dest, a);
   ASSERT_NO_OVERLAP(*dest, b);
   std::string::size_type old_size = dest->size();
-  STLStringAppendUninitializedAmortized(dest, a.size() + b.size());
+  strings_internal::STLStringAppendUninitializedAmortized(dest,
+                                                          a.size() + b.size());
   char* const begin = &(*dest)[0];
   char* out = begin + old_size;
   out = Append(out, a);
@@ -183,7 +304,8 @@ void StrAppend(absl::Nonnull<std::string*> dest, const AlphaNum& a,
   ASSERT_NO_OVERLAP(*dest, b);
   ASSERT_NO_OVERLAP(*dest, c);
   std::string::size_type old_size = dest->size();
-  STLStringAppendUninitializedAmortized(dest, a.size() + b.size() + c.size());
+  strings_internal::STLStringAppendUninitializedAmortized(
+      dest, a.size() + b.size() + c.size());
   char* const begin = &(*dest)[0];
   char* out = begin + old_size;
   out = Append(out, a);
@@ -199,7 +321,7 @@ void StrAppend(absl::Nonnull<std::string*> dest, const AlphaNum& a,
   ASSERT_NO_OVERLAP(*dest, c);
   ASSERT_NO_OVERLAP(*dest, d);
   std::string::size_type old_size = dest->size();
-  STLStringAppendUninitializedAmortized(
+  strings_internal::STLStringAppendUninitializedAmortized(
       dest, a.size() + b.size() + c.size() + d.size());
   char* const begin = &(*dest)[0];
   char* out = begin + old_size;