SERVER-42034 Optimize ItoA (~13% faster, remove the 1kLoC static table)

1 files changed, 68 insertions, 16 deletions

diff --git a/src/mongo/util/itoa_test.cpp b/src/mongo/util/itoa_test.cpp
index 9d505bd5601..4949928700a 100644
--- a/src/mongo/util/itoa_test.cpp
+++ b/src/mongo/util/itoa_test.cpp
@@ -32,31 +32,83 @@
 #include <array>
 #include <cstdint>
 #include <limits>
+#include <random>
+#include <string>
+#include <vector>
 
 #include "mongo/base/string_data.h"
 #include "mongo/unittest/unittest.h"
+#include "mongo/util/decimal_counter.h"
 #include "mongo/util/itoa.h"
 
+namespace mongo {
 namespace {
-using namespace mongo;
 
 TEST(ItoA, StringDataEquality) {
-    ASSERT_EQ(ItoA::kBufSize - 1, std::to_string(std::numeric_limits<std::uint64_t>::max()).size());
-
-    for (auto testCase : {uint64_t(1),
-                          uint64_t(12),
-                          uint64_t(133),
-                          uint64_t(1446),
-                          uint64_t(17789),
-                          uint64_t(192923),
-                          uint64_t(2389489),
-                          uint64_t(29313479),
-                          uint64_t(1928127389),
-                          std::numeric_limits<std::uint64_t>::max() - 1,
-                          std::numeric_limits<std::uint64_t>::max()}) {
-        ItoA itoa{testCase};
-        ASSERT_EQ(std::to_string(testCase), StringData(itoa));
+    std::vector<uint64_t> cases;
+    auto caseInsert = std::back_inserter(cases);
+    static constexpr auto kMax = std::numeric_limits<uint64_t>::max();
+    {
+        // Manually-specified basics.
+        const uint64_t interesting[]{
+            0,
+            1,
+            10,
+            11,
+            12,
+            99,
+            100,
+            101,
+            110,
+            133,
+            1446,
+            17789,
+            192923,
+            2389489,
+            29313479,
+            1928127389,
+            kMax - 1,
+            kMax,
+        };
+        cases.insert(cases.end(), std::begin(interesting), std::end(interesting));
+    }
+
+    {
+        // Test the neighborhood of several powers of ten.
+        uint64_t tenPower = 10;
+        for (int i = 0; i < 10; ++i) {
+            *caseInsert++ = tenPower - 1;
+            *caseInsert++ = tenPower;
+            *caseInsert++ = tenPower + 1;
+            tenPower *= 10;
+        }
+    }
+
+    static constexpr uint64_t kRampTop = 100'000;
+
+    // Ramp of first several thousand values.
+    for (uint64_t i = 0; i < kRampTop; ++i) {
+        *caseInsert++ = i;
+    }
+
+    {
+        // Large # of pseudorandom integers, spread over the remaining powers of ten.
+        std::mt19937 gen(0);  // deterministic seed 0
+        for (uint64_t i = kRampTop;; i *= 10) {
+            auto upper = (i >= kMax / 10) ? kMax : 10 * i;
+            std::uniform_int_distribution<uint64_t> dis(i, upper);
+            for (uint64_t i = 0; i < 100'000; ++i) {
+                *caseInsert++ = dis(gen);
+            }
+            if (upper == kMax)
+                break;
+        }
+    }
+
+    for (const auto& i : cases) {
+        ASSERT_EQ(StringData(ItoA{i}), std::to_string(i));
     }
 }
 
 }  // namespace
+}  // namespace mongo