From d5a2cec006d14c6801ddeb768bf2574a1cf4fa7f Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Thu, 4 Jan 2024 13:14:50 -0800 Subject: 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 --- absl/strings/str_cat_test.cc | 46 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 46 insertions(+) (limited to 'absl/strings/str_cat_test.cc') 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 +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(v)); + VerifyInteger(static_cast(v)); + VerifyInteger(static_cast(v)); + VerifyInteger(static_cast(v)); + VerifyInteger(static_cast(v)); // NOLINT + VerifyInteger(static_cast(v)); // NOLINT + VerifyInteger(static_cast(v)); // NOLINT + VerifyInteger(static_cast(v)); // NOLINT + VerifyInteger(static_cast(v)); // NOLINT + VerifyInteger(static_cast(v)); // NOLINT + VerifyInteger(static_cast(v)); // NOLINT + VerifyInteger(static_cast(v)); // NOLINT + const uint64_t next = j == 0 ? 1 : j * base; + if (next <= j) { + break; + } + j = next; + } + } + } + } } TEST(StrCat, Enums) { -- cgit v1.2.3