From 27d839b2ab77ab822c578835b09f72129b80c68a Mon Sep 17 00:00:00 2001 From: Geert Bosch Date: Sun, 8 Jul 2018 09:32:03 -0400 Subject: SERVER-36108 speed up BSONArrayBuilder by counting in decimal Now removed constexpr that broke Windows build. --- src/mongo/bson/SConscript | 10 ++++ src/mongo/bson/bsonobjbuilder.h | 70 +++++++++++----------- src/mongo/bson/bsonobjbuilder_bm.cpp | 52 ++++++++++++++++ src/mongo/util/SConscript | 16 +++++ src/mongo/util/decimal_counter.h | 103 ++++++++++++++++++++++++++++++++ src/mongo/util/decimal_counter_bm.cpp | 76 +++++++++++++++++++++++ src/mongo/util/decimal_counter_test.cpp | 53 ++++++++++++++++ 7 files changed, 344 insertions(+), 36 deletions(-) create mode 100644 src/mongo/bson/bsonobjbuilder_bm.cpp create mode 100644 src/mongo/util/decimal_counter.h create mode 100644 src/mongo/util/decimal_counter_bm.cpp create mode 100644 src/mongo/util/decimal_counter_test.cpp 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 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 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 _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 . + * + * 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 + +#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 @@ -607,6 +607,13 @@ env.Library( ], ) +env.CppUnitTest( + target='decimal_counter_test', + source=[ + 'decimal_counter_test.cpp', + ], +) + env.CppUnitTest( target='itoa_test', source=[ @@ -684,6 +691,15 @@ env.CppUnitTest( ], ) +env.Benchmark( + target='decimal_counter_bm', + source=[ + 'decimal_counter_bm.cpp', + ], + LIBDEPS=[ + ], +) + env.Benchmark( target='future_bm', source=[ 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 . + * + * 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 +#include + +#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 +class DecimalCounter { +public: + static_assert(std::is_unsigned::value, "DecimalCounter requires an unsigned type"); + constexpr operator StringData() const { + return {_digits, static_cast(_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& 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 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::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 . + * + * 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 + +#include "mongo/util/decimal_counter.h" +#include "mongo/util/itoa.h" + +namespace mongo { + +void BM_decimalCounterPreInc(benchmark::State& state) { + DecimalCounter count; + for (auto _ : state) { + benchmark::ClobberMemory(); + benchmark::DoNotOptimize(StringData(++count)); + } +} + +void BM_decimalCounterPostInc(benchmark::State& state) { + DecimalCounter 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 . + * + * 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 +#include +#include + +#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 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 -- cgit v1.2.1