SERVER-36108 speed up BSONArrayBuilder by counting in decimal

Now removed constexpr that broke Windows build.

7 files changed, 344 insertions, 36 deletions

diff --git a/src/mongo/bson/SConscript b/src/mongo/bson/SConscript
index fbe9ef1dae0..f1d9ab122ea 100644
--- a/src/mongo/bson/SConscript
+++ b/src/mongo/bson/SConscript
@@ -65,6 +65,16 @@ env.CppUnitTest(
     ],
 )
 
+env.Benchmark(
+    target='bsonobjbuilder_bm',
+    source=[
+        'bsonobjbuilder_bm.cpp',
+    ],
+    LIBDEPS=[
+        '$BUILD_DIR/mongo/base',
+    ],
+)
+
 env.CppUnitTest(
     target='bsonelement_test',
     source=[
diff --git a/src/mongo/bson/bsonobjbuilder.h b/src/mongo/bson/bsonobjbuilder.h
index 6162495c1cd..ef92065d9a0 100644
--- a/src/mongo/bson/bsonobjbuilder.h
+++ b/src/mongo/bson/bsonobjbuilder.h
@@ -48,7 +48,7 @@
 #include "mongo/bson/util/builder.h"
 #include "mongo/platform/decimal128.h"
 #include "mongo/stdx/type_traits.h"
-#include "mongo/util/itoa.h"
+#include "mongo/util/decimal_counter.h"
 
 namespace mongo {
 
@@ -810,20 +810,20 @@ private:
 
 class BSONArrayBuilder {
 public:
-    BSONArrayBuilder() : _i(0), _b() {}
-    BSONArrayBuilder(BufBuilder& _b) : _i(0), _b(_b) {}
-    BSONArrayBuilder(int initialSize) : _i(0), _b(initialSize) {}
+    BSONArrayBuilder() {}
+    BSONArrayBuilder(BufBuilder& _b) : _b(_b) {}
+    BSONArrayBuilder(int initialSize) : _b(initialSize) {}
 
     template <typename T>
     BSONArrayBuilder& append(const T& x) {
-        ItoA itoa(_i++);
-        _b.append(itoa, x);
+        _b.append(_fieldCount, x);
+        ++_fieldCount;
         return *this;
     }
 
     BSONArrayBuilder& append(const BSONElement& e) {
-        ItoA itoa(_i++);
-        _b.appendAs(e, itoa);
+        _b.appendAs(e, _fieldCount);
+        ++_fieldCount;
         return *this;
     }
 
@@ -833,19 +833,19 @@ public:
 
     template <typename T>
     BSONArrayBuilder& operator<<(const T& x) {
-        ItoA itoa(_i++);
-        _b << itoa << x;
+        _b << _fieldCount << x;
+        ++_fieldCount;
         return *this;
     }
 
     void appendNull() {
-        ItoA itoa(_i++);
-        _b.appendNull(itoa);
+        _b.appendNull(_fieldCount);
+        ++_fieldCount;
     }
 
     void appendUndefined() {
-        ItoA itoa(_i++);
-        _b.appendUndefined(itoa);
+        _b.appendUndefined(_fieldCount);
+        ++_fieldCount;
     }
 
     /**
@@ -875,59 +875,57 @@ public:
 
     // These two just use next position
     BufBuilder& subobjStart() {
-        ItoA itoa(_i++);
-        return _b.subobjStart(itoa);
+        return _b.subobjStart(_fieldCount++);
     }
     BufBuilder& subarrayStart() {
-        ItoA itoa(_i++);
-        return _b.subarrayStart(itoa);
+        return _b.subarrayStart(_fieldCount++);
     }
 
     BSONArrayBuilder& appendRegex(StringData regex, StringData options = "") {
-        ItoA itoa(_i++);
-        _b.appendRegex(itoa, regex, options);
+        _b.appendRegex(_fieldCount, regex, options);
+        ++_fieldCount;
         return *this;
     }
 
     BSONArrayBuilder& appendBinData(int len, BinDataType type, const void* data) {
-        ItoA itoa(_i++);
-        _b.appendBinData(itoa, len, type, data);
+        _b.appendBinData(_fieldCount, len, type, data);
+        ++_fieldCount;
         return *this;
     }
 
     BSONArrayBuilder& appendCode(StringData code) {
-        ItoA itoa(_i++);
-        _b.appendCode(itoa, code);
+        _b.appendCode(_fieldCount, code);
+        ++_fieldCount;
         return *this;
     }
 
     BSONArrayBuilder& appendCodeWScope(StringData code, const BSONObj& scope) {
-        ItoA itoa(_i++);
-        _b.appendCodeWScope(itoa, code, scope);
+        _b.appendCodeWScope(_fieldCount, code, scope);
+        ++_fieldCount;
         return *this;
     }
 
     BSONArrayBuilder& appendTimeT(time_t dt) {
-        ItoA itoa(_i++);
-        _b.appendTimeT(itoa, dt);
+        _b.appendTimeT(_fieldCount, dt);
+        ++_fieldCount;
         return *this;
     }
 
     BSONArrayBuilder& appendDate(Date_t dt) {
-        ItoA itoa(_i++);
-        _b.appendDate(itoa, dt);
+        _b.appendDate(_fieldCount, dt);
+        ++_fieldCount;
         return *this;
     }
 
     BSONArrayBuilder& appendBool(bool val) {
-        ItoA itoa(_i++);
-        _b.appendBool(itoa, val);
+        _b.appendBool(_fieldCount, val);
+        ++_fieldCount;
         return *this;
     }
 
     BSONArrayBuilder& appendTimestamp(unsigned long long ts) {
-        ItoA itoa(_i++);
-        _b.appendTimestamp(itoa, ts);
+        _b.appendTimestamp(_fieldCount, ts);
+        ++_fieldCount;
         return *this;
     }
 
@@ -939,7 +937,7 @@ public:
         return _b.len();
     }
     int arrSize() const {
-        return _i;
+        return _fieldCount;
     }
 
     BufBuilder& bb() {
@@ -947,7 +945,7 @@ public:
     }
 
 private:
-    std::uint32_t _i;
+    DecimalCounter<uint32_t> _fieldCount;
     BSONObjBuilder _b;
 };
 
diff --git a/src/mongo/bson/bsonobjbuilder_bm.cpp b/src/mongo/bson/bsonobjbuilder_bm.cpp
new file mode 100644
index 00000000000..53410f72615
--- /dev/null
+++ b/src/mongo/bson/bsonobjbuilder_bm.cpp
@@ -0,0 +1,52 @@
+/**
+ *    Copyright (C) 2018 MongoDB Inc.
+ *
+ *    This program is free software: you can redistribute it and/or  modify
+ *    it under the terms of the GNU Affero General Public License, version 3,
+ *    as published by the Free Software Foundation.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    GNU Affero General Public License for more details.
+ *
+ *    You should have received a copy of the GNU Affero General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ *    As a special exception, the copyright holders give permission to link the
+ *    code of portions of this program with the OpenSSL library under certain
+ *    conditions as described in each individual source file and distribute
+ *    linked combinations including the program with the OpenSSL library. You
+ *    must comply with the GNU Affero General Public License in all respects for
+ *    all of the code used other than as permitted herein. If you modify file(s)
+ *    with this exception, you may extend this exception to your version of the
+ *    file(s), but you are not obligated to do so. If you do not wish to do so,
+ *    delete this exception statement from your version. If you delete this
+ *    exception statement from all source files in the program, then also delete
+ *    it in the license file.
+ */
+
+#include "mongo/platform/basic.h"
+
+#include <benchmark/benchmark.h>
+
+#include "mongo/bson/bsonobjbuilder.h"
+
+namespace mongo {
+
+void BM_arrayBuilder(benchmark::State& state) {
+    size_t totalBytes = 0;
+    for (auto _ : state) {
+        benchmark::ClobberMemory();
+        BSONArrayBuilder array;
+        for (auto j = 0; j < state.range(0); j++)
+            array.append(j);
+        totalBytes += array.len();
+        benchmark::DoNotOptimize(array.done());
+    }
+    state.SetBytesProcessed(totalBytes);
+}
+
+BENCHMARK(BM_arrayBuilder)->Ranges({{{1}, {100'000}}});
+
+}  // namespace mongo
diff --git a/src/mongo/util/SConscript b/src/mongo/util/SConscript
index ffca101f781..7935d4930ec 100644
--- a/src/mongo/util/SConscript
+++ b/src/mongo/util/SConscript
@@ -608,6 +608,13 @@ env.Library(
 )
 
 env.CppUnitTest(
+    target='decimal_counter_test',
+    source=[
+        'decimal_counter_test.cpp',
+    ],
+)
+
+env.CppUnitTest(
     target='itoa_test',
     source=[
         'itoa_test.cpp',
@@ -685,6 +692,15 @@ env.CppUnitTest(
 )
 
 env.Benchmark(
+    target='decimal_counter_bm',
+    source=[
+        'decimal_counter_bm.cpp',
+    ],
+    LIBDEPS=[
+    ],
+)
+
+env.Benchmark(
     target='future_bm',
     source=[
         'future_bm.cpp',
diff --git a/src/mongo/util/decimal_counter.h b/src/mongo/util/decimal_counter.h
new file mode 100644
index 00000000000..c4a89a1a6a7
--- /dev/null
+++ b/src/mongo/util/decimal_counter.h
@@ -0,0 +1,103 @@
+/**
+ *    Copyright (C) 2018 MongoDB, Inc.
+ *
+ *    This program is free software: you can redistribute it and/or  modify
+ *    it under the terms of the GNU Affero General Public License, version 3,
+ *    as published by the Free Software Foundation.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    GNU Affero General Public License for more details.
+ *
+ *    You should have received a copy of the GNU Affero General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ *    As a special exception, the copyright holders give permission to link the
+ *    code of portions of this program with the OpenSSL library under certain
+ *    conditions as described in each individual source file and distribute
+ *    linked combinations including the program with the OpenSSL library. You
+ *    must comply with the GNU Affero General Public License in all respects for
+ *    all of the code used other than as permitted herein. If you modify file(s)
+ *    with this exception, you may extend this exception to your version of the
+ *    file(s), but you are not obligated to do so. If you do not wish to do so,
+ *    delete this exception statement from your version. If you delete this
+ *    exception statement from all source files in the program, then also delete
+ *    it in the license file.
+ */
+
+#pragma once
+
+#include <cstdint>
+#include <limits>
+
+#include "mongo/base/string_data.h"
+
+namespace mongo {
+/**
+ * Stores unsigned counter as well as its decimal ASCII representation, avoiding the need for
+ * separate binary to decimal conversions. This speeds up code that needs string representations
+ * for all counter values.
+ */
+template <typename T>
+class DecimalCounter {
+public:
+    static_assert(std::is_unsigned<T>::value, "DecimalCounter requires an unsigned type");
+    constexpr operator StringData() const {
+        return {_digits, static_cast<size_t>(_lastDigitIndex + 1)};
+    }
+    constexpr operator uint32_t() const {
+        return _counter;
+    }
+
+    /**
+     *  Increments the counter and its decimal representation. The decimal representation wraps
+     *  independently of the binary counter.
+     */
+    DecimalCounter<T>& operator++() {
+        // Common case: just increment the last digit and we're done with the string part.
+        char* lastPtr = _digits + _lastDigitIndex;
+        if (MONGO_unlikely((*lastPtr)++ == '9')) {
+            // Let zeroPtr point at the first char in the string, such that it and all digits
+            // after need to change to zeroes.
+            char* zeroPtr = lastPtr;
+            while (zeroPtr > _digits && zeroPtr[-1] == '9')
+                --zeroPtr;
+
+            // If digits wasn't all nines, increment the first non-nine.
+            if (zeroPtr > _digits) {
+                zeroPtr[-1]++;
+            } else if (lastPtr < _digits + sizeof(_digits) - 2) {
+                // Rare case: new power of 10 increases string length, so start with a one.
+                *zeroPtr++ = '1';
+                _lastDigitIndex++;
+                lastPtr++;
+            }
+            // Zero out the rest.
+            do {
+                *zeroPtr++ = '0';
+            } while (zeroPtr <= lastPtr);
+        }
+        if (MONGO_unlikely(++_counter == 0))
+            *this = {};
+        return *this;
+    }
+
+    /**
+     *  Post-inrement version of operator++. Typically slower than pre-increment due to the need
+     *  to return the pre-image by value.
+     */
+    DecimalCounter<T> operator++(int) {
+        auto pre = *this;
+        operator++();
+        return pre;
+    }
+
+private:
+    // Add 1, because digit10 is 1 less than the maximum number of digits, and 1 for the final '\0'.
+    static constexpr size_t kBufSize = std::numeric_limits<T>::digits10 + 2;
+    char _digits[kBufSize] = {'0'};  // Remainder is zero-initialized.
+    uint8_t _lastDigitIndex = 0;     // Indicates the last digit in _digits.
+    T _counter = 0;
+};
+}
diff --git a/src/mongo/util/decimal_counter_bm.cpp b/src/mongo/util/decimal_counter_bm.cpp
new file mode 100644
index 00000000000..4dad2e17940
--- /dev/null
+++ b/src/mongo/util/decimal_counter_bm.cpp
@@ -0,0 +1,76 @@
+/**
+ *    Copyright (C) 2018 MongoDB Inc.
+ *
+ *    This program is free software: you can redistribute it and/or  modify
+ *    it under the terms of the GNU Affero General Public License, version 3,
+ *    as published by the Free Software Foundation.
+ *
+ *    This program is distributed in the hope that it will be useful,
+ *    but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *    GNU Affero General Public License for more details.
+ *
+ *    You should have received a copy of the GNU Affero General Public License
+ *    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ *    As a special exception, the copyright holders give permission to link the
+ *    code of portions of this program with the OpenSSL library under certain
+ *    conditions as described in each individual source file and distribute
+ *    linked combinations including the program with the OpenSSL library. You
+ *    must comply with the GNU Affero General Public License in all respects for
+ *    all of the code used other than as permitted herein. If you modify file(s)
+ *    with this exception, you may extend this exception to your version of the
+ *    file(s), but you are not obligated to do so. If you do not wish to do so,
+ *    delete this exception statement from your version. If you delete this
+ *    exception statement from all source files in the program, then also delete
+ *    it in the license file.
+ */
+
+#include "mongo/platform/basic.h"
+
+#include <benchmark/benchmark.h>
+
+#include "mongo/util/decimal_counter.h"
+#include "mongo/util/itoa.h"
+
+namespace mongo {
+
+void BM_decimalCounterPreInc(benchmark::State& state) {
+    DecimalCounter<uint32_t> count;
+    for (auto _ : state) {
+        benchmark::ClobberMemory();
+        benchmark::DoNotOptimize(StringData(++count));
+    }
+}
+
+void BM_decimalCounterPostInc(benchmark::State& state) {
+    DecimalCounter<uint32_t> count;
+    for (auto _ : state) {
+        benchmark::ClobberMemory();
+        benchmark::DoNotOptimize(StringData(count++));
+    }
+}
+
+void BM_ItoACounter(benchmark::State& state) {
+    uint32_t count = 0;
+    for (auto _ : state) {
+        benchmark::ClobberMemory();
+        benchmark::DoNotOptimize(StringData(ItoA(++count)));
+    }
+}
+
+void BM_to_stringCounter(benchmark::State& state) {
+    uint32_t count = 0;
+    std::string str;
+    for (auto _ : state) {
+        benchmark::ClobberMemory();
+        benchmark::DoNotOptimize(std::to_string(++count));
+    }
+}
+
+BENCHMARK(BM_decimalCounterPreInc);
+BENCHMARK(BM_decimalCounterPostInc);
+BENCHMARK(BM_ItoACounter);
+BENCHMARK(BM_to_stringCounter);
+
+}  // namespace mongo
diff --git a/src/mongo/util/decimal_counter_test.cpp b/src/mongo/util/decimal_counter_test.cpp
new file mode 100644
index 00000000000..cff11c768a5
--- /dev/null
+++ b/src/mongo/util/decimal_counter_test.cpp
@@ -0,0 +1,53 @@
+/**
+ * Copyright (C) 2018 MongoDB Inc.
+ *
+ * This program is free software: you can redistribute it and/or  modify
+ * it under the terms of the GNU Affero General Public License, version 3,
+ * as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ * As a special exception, the copyright holders give permission to link the
+ * code of portions of this program with the OpenSSL library under certain
+ * conditions as described in each individual source file and distribute
+ * linked combinations including the program with the OpenSSL library. You
+ * must comply with the GNU Affero General Public License in all respects
+ * for all of the code used other than as permitted herein. If you modify
+ * file(s) with this exception, you may extend this exception to your
+ * version of the file(s), but you are not obligated to do so. If you do not
+ * wish to do so, delete this exception statement from your version. If you
+ * delete this exception statement from all source files in the program,
+ * then also delete it in the license file.
+ */
+
+#include "mongo/platform/basic.h"
+
+#include <array>
+#include <cstdint>
+#include <limits>
+
+#include "mongo/base/string_data.h"
+#include "mongo/unittest/unittest.h"
+#include "mongo/util/decimal_counter.h"
+
+namespace {
+using namespace mongo;
+
+TEST(DecimalCounter, CountUntilWrapAround) {
+    DecimalCounter<uint16_t> counter;
+    uint16_t check = 0;
+    do {
+        StringData str = counter;
+        ASSERT_EQ(std::to_string(check), str.toString());
+        ASSERT_EQ(str.rawData()[str.size()], '\0');
+        ASSERT_EQ(uint16_t(++counter), ++check);
+    } while (check);
+    ASSERT_EQ(StringData(counter), "0"_sd);
+}
+}  // namespace