diff options
Diffstat (limited to 'absl/strings')
| -rw-r--r-- | absl/strings/BUILD.bazel | 65 | ||||
| -rw-r--r-- | absl/strings/str_cat_benchmark.cc | 142 | ||||
| -rw-r--r-- | absl/strings/str_join_benchmark.cc | 98 | ||||
| -rw-r--r-- | absl/strings/str_replace_benchmark.cc | 124 | ||||
| -rw-r--r-- | absl/strings/str_split_benchmark.cc | 158 | ||||
| -rw-r--r-- | absl/strings/string_view_benchmark.cc | 331 |
6 files changed, 918 insertions, 0 deletions
diff --git a/absl/strings/BUILD.bazel b/absl/strings/BUILD.bazel index 1e52312b47c6..cb21385a30be 100644 --- a/absl/strings/BUILD.bazel +++ b/absl/strings/BUILD.bazel @@ -173,6 +173,20 @@ cc_test( ) cc_test( + name = "string_view_benchmark", + srcs = ["string_view_benchmark.cc"], + copts = ABSL_TEST_COPTS, + tags = ["benchmark"], + visibility = ["//visibility:private"], + deps = [ + ":strings", + "//absl/base", + "//absl/base:core_headers", + "@com_github_google_benchmark//:benchmark", + ], +) + +cc_test( name = "string_view_test", size = "small", srcs = ["string_view_test.cc"], @@ -201,6 +215,19 @@ cc_test( ) cc_test( + name = "str_replace_benchmark", + srcs = ["str_replace_benchmark.cc"], + copts = ABSL_TEST_COPTS, + tags = ["benchmark"], + visibility = ["//visibility:private"], + deps = [ + ":strings", + "//absl/base", + "@com_github_google_benchmark//:benchmark", + ], +) + +cc_test( name = "str_replace_test", size = "small", srcs = ["str_replace_test.cc"], @@ -226,6 +253,19 @@ cc_test( ) cc_test( + name = "str_split_benchmark", + srcs = ["str_split_benchmark.cc"], + copts = ABSL_TEST_COPTS, + tags = ["benchmark"], + visibility = ["//visibility:private"], + deps = [ + ":strings", + "//absl/base", + "@com_github_google_benchmark//:benchmark", + ], +) + +cc_test( name = "ostringstream_test", size = "small", srcs = ["internal/ostringstream_test.cc"], @@ -268,6 +308,19 @@ cc_test( ) cc_test( + name = "str_join_benchmark", + srcs = ["str_join_benchmark.cc"], + copts = ABSL_TEST_COPTS, + tags = ["benchmark"], + visibility = ["//visibility:private"], + deps = [ + ":strings", + "//absl/memory", + "@com_github_google_benchmark//:benchmark", + ], +) + +cc_test( name = "str_cat_test", size = "small", srcs = ["str_cat_test.cc"], @@ -281,6 +334,18 @@ cc_test( ) cc_test( + name = "str_cat_benchmark", + srcs = ["str_cat_benchmark.cc"], + copts = ABSL_TEST_COPTS, + tags = ["benchmark"], + visibility = ["//visibility:private"], + deps = [ + ":strings", + "@com_github_google_benchmark//:benchmark", + ], +) + +cc_test( name = "numbers_test", size = "small", srcs = [ diff --git a/absl/strings/str_cat_benchmark.cc b/absl/strings/str_cat_benchmark.cc new file mode 100644 index 000000000000..1791410c6e3a --- /dev/null +++ b/absl/strings/str_cat_benchmark.cc @@ -0,0 +1,142 @@ +// Copyright 2018 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include "absl/strings/str_cat.h" + +#include <cstdint> +#include <string> + +#include "benchmark/benchmark.h" +#include "absl/strings/substitute.h" + +namespace { + +const char kStringOne[] = "Once Upon A Time, "; +const char kStringTwo[] = "There was a std::string benchmark"; + +// We want to include negative numbers in the benchmark, so this function +// is used to count 0, 1, -1, 2, -2, 3, -3, ... +inline int IncrementAlternatingSign(int i) { + return i > 0 ? -i : 1 - i; +} + +void BM_Sum_By_StrCat(benchmark::State& state) { + int i = 0; + char foo[100]; + for (auto _ : state) { + // NOLINTNEXTLINE(runtime/printf) + strcpy(foo, absl::StrCat(kStringOne, i, kStringTwo, i * 65536ULL).c_str()); + int sum = 0; + for (char* f = &foo[0]; *f != 0; ++f) { + sum += *f; + } + benchmark::DoNotOptimize(sum); + i = IncrementAlternatingSign(i); + } +} +BENCHMARK(BM_Sum_By_StrCat); + +void BM_StrCat_By_snprintf(benchmark::State& state) { + int i = 0; + char on_stack[1000]; + for (auto _ : state) { + snprintf(on_stack, sizeof(on_stack), "%s %s:%d", kStringOne, kStringTwo, i); + i = IncrementAlternatingSign(i); + } +} +BENCHMARK(BM_StrCat_By_snprintf); + +void BM_StrCat_By_Strings(benchmark::State& state) { + int i = 0; + for (auto _ : state) { + std::string result = + std::string(kStringOne) + " " + kStringTwo + ":" + absl::StrCat(i); + benchmark::DoNotOptimize(result); + i = IncrementAlternatingSign(i); + } +} +BENCHMARK(BM_StrCat_By_Strings); + +void BM_StrCat_By_StringOpPlus(benchmark::State& state) { + int i = 0; + for (auto _ : state) { + std::string result = kStringOne; + result += " "; + result += kStringTwo; + result += ":"; + result += absl::StrCat(i); + benchmark::DoNotOptimize(result); + i = IncrementAlternatingSign(i); + } +} +BENCHMARK(BM_StrCat_By_StringOpPlus); + +void BM_StrCat_By_StrCat(benchmark::State& state) { + int i = 0; + for (auto _ : state) { + std::string result = absl::StrCat(kStringOne, " ", kStringTwo, ":", i); + benchmark::DoNotOptimize(result); + i = IncrementAlternatingSign(i); + } +} +BENCHMARK(BM_StrCat_By_StrCat); + +void BM_HexCat_By_StrCat(benchmark::State& state) { + int i = 0; + for (auto _ : state) { + std::string result = + absl::StrCat(kStringOne, " ", absl::Hex(int64_t{i} + 0x10000000)); + benchmark::DoNotOptimize(result); + i = IncrementAlternatingSign(i); + } +} +BENCHMARK(BM_HexCat_By_StrCat); + +void BM_HexCat_By_Substitute(benchmark::State& state) { + int i = 0; + for (auto _ : state) { + std::string result = absl::Substitute( + "$0 $1", kStringOne, reinterpret_cast<void*>(int64_t{i} + 0x10000000)); + benchmark::DoNotOptimize(result); + i = IncrementAlternatingSign(i); + } +} +BENCHMARK(BM_HexCat_By_Substitute); + +void BM_FloatToString_By_StrCat(benchmark::State& state) { + int i = 0; + float foo = 0.0f; + for (auto _ : state) { + std::string result = absl::StrCat(foo += 1.001f, " != ", int64_t{i}); + benchmark::DoNotOptimize(result); + i = IncrementAlternatingSign(i); + } +} +BENCHMARK(BM_FloatToString_By_StrCat); + +void BM_DoubleToString_By_SixDigits(benchmark::State& state) { + int i = 0; + double foo = 0.0; + for (auto _ : state) { + std::string result = + absl::StrCat(absl::SixDigits(foo += 1.001), " != ", int64_t{i}); + benchmark::DoNotOptimize(result); + i = IncrementAlternatingSign(i); + } +} +BENCHMARK(BM_DoubleToString_By_SixDigits); + +} // namespace + +BENCHMARK_MAIN(); diff --git a/absl/strings/str_join_benchmark.cc b/absl/strings/str_join_benchmark.cc new file mode 100644 index 000000000000..79cad5e39300 --- /dev/null +++ b/absl/strings/str_join_benchmark.cc @@ -0,0 +1,98 @@ +// +// Copyright 2018 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include "absl/strings/str_join.h" + +#include <string> +#include <vector> +#include <utility> + +#include "benchmark/benchmark.h" + +namespace { + +void BM_Join2_Strings(benchmark::State& state) { + const int string_len = state.range(0); + const int num_strings = state.range(1); + const std::string s(string_len, 'x'); + const std::vector<std::string> v(num_strings, s); + for (auto _ : state) { + std::string s = absl::StrJoin(v, "-"); + benchmark::DoNotOptimize(s); + } +} +BENCHMARK(BM_Join2_Strings) + ->ArgPair(1 << 0, 1 << 3) + ->ArgPair(1 << 10, 1 << 3) + ->ArgPair(1 << 13, 1 << 3) + ->ArgPair(1 << 0, 1 << 10) + ->ArgPair(1 << 10, 1 << 10) + ->ArgPair(1 << 13, 1 << 10) + ->ArgPair(1 << 0, 1 << 13) + ->ArgPair(1 << 10, 1 << 13) + ->ArgPair(1 << 13, 1 << 13); + +void BM_Join2_Ints(benchmark::State& state) { + const int num_ints = state.range(0); + const std::vector<int> v(num_ints, 42); + for (auto _ : state) { + std::string s = absl::StrJoin(v, "-"); + benchmark::DoNotOptimize(s); + } +} +BENCHMARK(BM_Join2_Ints)->Range(0, 1 << 13); + +void BM_Join2_KeysAndValues(benchmark::State& state) { + const int string_len = state.range(0); + const int num_pairs = state.range(1); + const std::string s(string_len, 'x'); + const std::vector<std::pair<std::string, int>> v(num_pairs, std::make_pair(s, 42)); + for (auto _ : state) { + std::string s = absl::StrJoin(v, ",", absl::PairFormatter("=")); + benchmark::DoNotOptimize(s); + } +} +BENCHMARK(BM_Join2_KeysAndValues) + ->ArgPair(1 << 0, 1 << 3) + ->ArgPair(1 << 10, 1 << 3) + ->ArgPair(1 << 13, 1 << 3) + ->ArgPair(1 << 0, 1 << 10) + ->ArgPair(1 << 10, 1 << 10) + ->ArgPair(1 << 13, 1 << 10) + ->ArgPair(1 << 0, 1 << 13) + ->ArgPair(1 << 10, 1 << 13) + ->ArgPair(1 << 13, 1 << 13); + +void BM_JoinStreamable(benchmark::State& state) { + const int string_len = state.range(0); + const int num_strings = state.range(1); + const std::vector<std::string> v(num_strings, std::string(string_len, 'x')); + for (auto _ : state) { + std::string s = absl::StrJoin(v, "", absl::StreamFormatter()); + benchmark::DoNotOptimize(s); + } +} +BENCHMARK(BM_JoinStreamable) + ->ArgPair(0, 0) + ->ArgPair(16, 1) + ->ArgPair(256, 1) + ->ArgPair(16, 16) + ->ArgPair(256, 16) + ->ArgPair(16, 256) + ->ArgPair(256, 256); + +} // namespace + +BENCHMARK_MAIN(); diff --git a/absl/strings/str_replace_benchmark.cc b/absl/strings/str_replace_benchmark.cc new file mode 100644 index 000000000000..9dd72eb6e77c --- /dev/null +++ b/absl/strings/str_replace_benchmark.cc @@ -0,0 +1,124 @@ +// Copyright 2018 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include "absl/strings/str_replace.h" + +#include <cstring> +#include <string> + +#include "benchmark/benchmark.h" +#include "absl/base/internal/raw_logging.h" + +namespace { + +std::string* big_string; +std::string* after_replacing_the; +std::string* after_replacing_many; + +struct Replacement { + const char* needle; + const char* replacement; +} replacements[] = { + {"the", "box"}, // + {"brown", "quick"}, // + {"jumped", "liquored"}, // + {"dozen", "brown"}, // + {"lazy", "pack"}, // + {"liquor", "shakes"}, // +}; + +// Here, we set up a std::string for use in global-replace benchmarks. +// We started with a million blanks, and then deterministically insert +// 10,000 copies each of two pangrams. The result is a std::string that is +// 40% blank space and 60% these words. 'the' occurs 18,247 times and +// all the substitutions together occur 49,004 times. +// +// We then create "after_replacing_the" to be a std::string that is a result of +// replacing "the" with "box" in big_string. +// +// And then we create "after_replacing_many" to be a std::string that is result +// of preferring several substitutions. +void SetUpStrings() { + if (big_string == nullptr) { + size_t r = 0; + big_string = new std::string(1000 * 1000, ' '); + for (std::string phrase : {"the quick brown fox jumped over the lazy dogs", + "pack my box with the five dozen liquor jugs"}) { + for (int i = 0; i < 10 * 1000; ++i) { + r = r * 237 + 41; // not very random. + memcpy(&(*big_string)[r % (big_string->size() - phrase.size())], + phrase.data(), phrase.size()); + } + } + // big_string->resize(50); + // OK, we've set up the std::string, now let's set up expectations - first by + // just replacing "the" with "box" + after_replacing_the = new std::string(*big_string); + for (size_t pos = 0; + (pos = after_replacing_the->find("the", pos)) != std::string::npos;) { + memcpy(&(*after_replacing_the)[pos], "box", 3); + } + // And then with all the replacements. + after_replacing_many = new std::string(*big_string); + for (size_t pos = 0;;) { + size_t next_pos = static_cast<size_t>(-1); + const char* needle_string = nullptr; + const char* replacement_string = nullptr; + for (const auto& r : replacements) { + auto needlepos = after_replacing_many->find(r.needle, pos); + if (needlepos != std::string::npos && needlepos < next_pos) { + next_pos = needlepos; + needle_string = r.needle; + replacement_string = r.replacement; + } + } + if (next_pos > after_replacing_many->size()) break; + after_replacing_many->replace(next_pos, strlen(needle_string), + replacement_string); + next_pos += strlen(replacement_string); + pos = next_pos; + } + } +} + +void BM_StrReplaceAllOneReplacement(benchmark::State& state) { + SetUpStrings(); + std::string src = *big_string; + for (auto _ : state) { + std::string dest = absl::StrReplaceAll(src, {{"the", "box"}}); + ABSL_RAW_CHECK(dest == *after_replacing_the, + "not benchmarking intended behavior"); + } +} +BENCHMARK(BM_StrReplaceAllOneReplacement); + +void BM_StrReplaceAll(benchmark::State& state) { + SetUpStrings(); + std::string src = *big_string; + for (auto _ : state) { + std::string dest = absl::StrReplaceAll(src, {{"the", "box"}, + {"brown", "quick"}, + {"jumped", "liquored"}, + {"dozen", "brown"}, + {"lazy", "pack"}, + {"liquor", "shakes"}}); + ABSL_RAW_CHECK(dest == *after_replacing_many, + "not benchmarking intended behavior"); + } +} +BENCHMARK(BM_StrReplaceAll); + +} // namespace + +BENCHMARK_MAIN(); diff --git a/absl/strings/str_split_benchmark.cc b/absl/strings/str_split_benchmark.cc new file mode 100644 index 000000000000..c35787b7ef4b --- /dev/null +++ b/absl/strings/str_split_benchmark.cc @@ -0,0 +1,158 @@ +// Copyright 2018 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include "absl/strings/str_split.h" + +#include <iterator> +#include <string> +#include <unordered_map> +#include <unordered_set> +#include <vector> + +#include "benchmark/benchmark.h" +#include "absl/base/internal/raw_logging.h" +#include "absl/strings/string_view.h" + +namespace { + +std::string MakeTestString(int desired_length) { + static const int kAverageValueLen = 25; + std::string test(desired_length * kAverageValueLen, 'x'); + for (int i = 1; i < test.size(); i += kAverageValueLen) { + test[i] = ';'; + } + return test; +} + +void BM_Split2StringPiece(benchmark::State& state) { + std::string test = MakeTestString(state.range(0)); + for (auto _ : state) { + std::vector<absl::string_view> result = absl::StrSplit(test, ';'); + benchmark::DoNotOptimize(result); + } +} +BENCHMARK_RANGE(BM_Split2StringPiece, 0, 1 << 20); + +void BM_Split2StringPieceLifted(benchmark::State& state) { + std::string test = MakeTestString(state.range(0)); + std::vector<absl::string_view> result; + for (auto _ : state) { + result = absl::StrSplit(test, ';'); + } + benchmark::DoNotOptimize(result); +} +BENCHMARK_RANGE(BM_Split2StringPieceLifted, 0, 1 << 20); + +void BM_Split2String(benchmark::State& state) { + std::string test = MakeTestString(state.range(0)); + for (auto _ : state) { + std::vector<std::string> result = absl::StrSplit(test, ';'); + benchmark::DoNotOptimize(result); + } +} +BENCHMARK_RANGE(BM_Split2String, 0, 1 << 20); + +// This benchmark is for comparing Split2 to Split1 (SplitStringUsing). In +// particular, this benchmark uses SkipEmpty() to match SplitStringUsing's +// behavior. +void BM_Split2SplitStringUsing(benchmark::State& state) { + std::string test = MakeTestString(state.range(0)); + for (auto _ : state) { + std::vector<std::string> result = absl::StrSplit(test, ';', absl::SkipEmpty()); + benchmark::DoNotOptimize(result); + } +} +BENCHMARK_RANGE(BM_Split2SplitStringUsing, 0, 1 << 20); + +void BM_SplitStringToUnorderedSet(benchmark::State& state) { + const int len = state.range(0); + std::string test(len, 'x'); + for (int i = 1; i < len; i += 2) { + test[i] = ';'; + } + for (auto _ : state) { + std::unordered_set<std::string> result = + absl::StrSplit(test, ':', absl::SkipEmpty()); + benchmark::DoNotOptimize(result); + } +} +BENCHMARK_RANGE(BM_SplitStringToUnorderedSet, 0, 1 << 20); + +void BM_SplitStringToUnorderedMap(benchmark::State& state) { + const int len = state.range(0); + std::string test(len, 'x'); + for (int i = 1; i < len; i += 2) { + test[i] = ';'; + } + for (auto _ : state) { + std::unordered_map<std::string, std::string> result = + absl::StrSplit(test, ':', absl::SkipEmpty()); + benchmark::DoNotOptimize(result); + } +} +BENCHMARK_RANGE(BM_SplitStringToUnorderedMap, 0, 1 << 20); + +void BM_SplitStringAllowEmpty(benchmark::State& state) { + const int len = state.range(0); + std::string test(len, 'x'); + for (int i = 1; i < len; i += 2) { + test[i] = ';'; + } + for (auto _ : state) { + std::vector<std::string> result = absl::StrSplit(test, ';'); + benchmark::DoNotOptimize(result); + } +} +BENCHMARK_RANGE(BM_SplitStringAllowEmpty, 0, 1 << 20); + +struct OneCharLiteral { + char operator()() const { return 'X'; } +}; + +struct OneCharStringLiteral { + const char* operator()() const { return "X"; } +}; + +template <typename DelimiterFactory> +void BM_SplitStringWithOneChar(benchmark::State& state) { + const auto delimiter = DelimiterFactory()(); + std::vector<absl::string_view> pieces; + size_t v = 0; + for (auto _ : state) { + pieces = absl::StrSplit("The quick brown fox jumps over the lazy dog", + delimiter); + v += pieces.size(); + } + ABSL_RAW_CHECK(v == state.iterations(), ""); +} +BENCHMARK_TEMPLATE(BM_SplitStringWithOneChar, OneCharLiteral); +BENCHMARK_TEMPLATE(BM_SplitStringWithOneChar, OneCharStringLiteral); + +template <typename DelimiterFactory> +void BM_SplitStringWithOneCharNoVector(benchmark::State& state) { + const auto delimiter = DelimiterFactory()(); + size_t v = 0; + for (auto _ : state) { + auto splitter = absl::StrSplit( + "The quick brown fox jumps over the lazy dog", delimiter); + v += std::distance(splitter.begin(), splitter.end()); + } + ABSL_RAW_CHECK(v == state.iterations(), ""); +} +BENCHMARK_TEMPLATE(BM_SplitStringWithOneCharNoVector, OneCharLiteral); +BENCHMARK_TEMPLATE(BM_SplitStringWithOneCharNoVector, OneCharStringLiteral); + +} // namespace + +BENCHMARK_MAIN(); diff --git a/absl/strings/string_view_benchmark.cc b/absl/strings/string_view_benchmark.cc new file mode 100644 index 000000000000..c66f0fbd5430 --- /dev/null +++ b/absl/strings/string_view_benchmark.cc @@ -0,0 +1,331 @@ +// Copyright 2018 The Abseil Authors. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include "absl/strings/string_view.h" + +#include <algorithm> +#include <cstdint> +#include <map> +#include <random> +#include <string> +#include <unordered_set> +#include <vector> + +#include "benchmark/benchmark.h" +#include "absl/base/attributes.h" +#include "absl/base/internal/raw_logging.h" +#include "absl/base/macros.h" +#include "absl/strings/str_cat.h" + +namespace { + +// Provide a forcibly out-of-line wrapper for operator== that can be used in +// benchmarks to measure the impact of inlining. +ABSL_ATTRIBUTE_NOINLINE +bool NonInlinedEq(absl::string_view a, absl::string_view b) { return a == b; } + +// We use functions that cannot be inlined to perform the comparison loops so +// that inlining of the operator== can't optimize away *everything*. +ABSL_ATTRIBUTE_NOINLINE +void DoEqualityComparisons(benchmark::State& state, absl::string_view a, + absl::string_view b) { + for (auto _ : state) { + benchmark::DoNotOptimize(a == b); + } +} + +void BM_EqualIdentical(benchmark::State& state) { + std::string x(state.range(0), 'a'); + DoEqualityComparisons(state, x, x); +} +BENCHMARK(BM_EqualIdentical)->DenseRange(0, 3)->Range(4, 1 << 10); + +void BM_EqualSame(benchmark::State& state) { + std::string x(state.range(0), 'a'); + std::string y = x; + DoEqualityComparisons(state, x, y); +} +BENCHMARK(BM_EqualSame) + ->DenseRange(0, 10) + ->Arg(20) + ->Arg(40) + ->Arg(70) + ->Arg(110) + ->Range(160, 4096); + +void BM_EqualDifferent(benchmark::State& state) { + const int len = state.range(0); + std::string x(len, 'a'); + std::string y = x; + if (len > 0) { + y[len - 1] = 'b'; + } + DoEqualityComparisons(state, x, y); +} +BENCHMARK(BM_EqualDifferent)->DenseRange(0, 3)->Range(4, 1 << 10); + +// This benchmark is intended to check that important simplifications can be +// made with absl::string_view comparisons against constant strings. The idea is +// that if constant strings cause redundant components of the comparison, the +// compiler should detect and eliminate them. Here we use 8 different strings, +// each with the same size. Provided our comparison makes the implementation +// inline-able by the compiler, it should fold all of these away into a single +// size check once per loop iteration. +ABSL_ATTRIBUTE_NOINLINE +void DoConstantSizeInlinedEqualityComparisons(benchmark::State& state, + absl::string_view a) { + for (auto _ : state) { + benchmark::DoNotOptimize(a == "aaa"); + benchmark::DoNotOptimize(a == "bbb"); + benchmark::DoNotOptimize(a == "ccc"); + benchmark::DoNotOptimize(a == "ddd"); + benchmark::DoNotOptimize(a == "eee"); + benchmark::DoNotOptimize(a == "fff"); + benchmark::DoNotOptimize(a == "ggg"); + benchmark::DoNotOptimize(a == "hhh"); + } +} +void BM_EqualConstantSizeInlined(benchmark::State& state) { + std::string x(state.range(0), 'a'); + DoConstantSizeInlinedEqualityComparisons(state, x); +} +// We only need to check for size of 3, and <> 3 as this benchmark only has to +// do with size differences. +BENCHMARK(BM_EqualConstantSizeInlined)->DenseRange(2, 4); + +// This benchmark exists purely to give context to the above timings: this is +// what they would look like if the compiler is completely unable to simplify +// between two comparisons when they are comparing against constant strings. +ABSL_ATTRIBUTE_NOINLINE +void DoConstantSizeNonInlinedEqualityComparisons(benchmark::State& state, + absl::string_view a) { + for (auto _ : state) { + // Force these out-of-line to compare with the above function. + benchmark::DoNotOptimize(NonInlinedEq(a, "aaa")); + benchmark::DoNotOptimize(NonInlinedEq(a, "bbb")); + benchmark::DoNotOptimize(NonInlinedEq(a, "ccc")); + benchmark::DoNotOptimize(NonInlinedEq(a, "ddd")); + benchmark::DoNotOptimize(NonInlinedEq(a, "eee")); + benchmark::DoNotOptimize(NonInlinedEq(a, "fff")); + benchmark::DoNotOptimize(NonInlinedEq(a, "ggg")); + benchmark::DoNotOptimize(NonInlinedEq(a, "hhh")); + } +} + +void BM_EqualConstantSizeNonInlined(benchmark::State& state) { + std::string x(state.range(0), 'a'); + DoConstantSizeNonInlinedEqualityComparisons(state, x); +} +// We only need to check for size of 3, and <> 3 as this benchmark only has to +// do with size differences. +BENCHMARK(BM_EqualConstantSizeNonInlined)->DenseRange(2, 4); + +void BM_CompareSame(benchmark::State& state) { + const int len = state.range(0); + std::string x; + for (int i = 0; i < len; i++) { + x += 'a'; + } + std::string y = x; + absl::string_view a = x; + absl::string_view b = y; + + for (auto _ : state) { + benchmark::DoNotOptimize(a.compare(b)); + } +} +BENCHMARK(BM_CompareSame)->DenseRange(0, 3)->Range(4, 1 << 10); + +void BM_find_string_view_len_one(benchmark::State& state) { + std::string haystack(state.range(0), '0'); + absl::string_view s(haystack); + for (auto _ : state) { + s.find("x"); // not present; length 1 + } +} +BENCHMARK(BM_find_string_view_len_one)->Range(1, 1 << 20); + +void BM_find_string_view_len_two(benchmark::State& state) { + std::string haystack(state.range(0), '0'); + absl::string_view s(haystack); + for (auto _ : state) { + s.find("xx"); // not present; length 2 + } +} +BENCHMARK(BM_find_string_view_len_two)->Range(1, 1 << 20); + +void BM_find_one_char(benchmark::State& state) { + std::string haystack(state.range(0), '0'); + absl::string_view s(haystack); + for (auto _ : state) { + s.find('x'); // not present + } +} +BENCHMARK(BM_find_one_char)->Range(1, 1 << 20); + +void BM_rfind_one_char(benchmark::State& state) { + std::string haystack(state.range(0), '0'); + absl::string_view s(haystack); + for (auto _ : state) { + s.rfind('x'); // not present + } +} +BENCHMARK(BM_rfind_one_char)->Range(1, 1 << 20); + +void BM_worst_case_find_first_of(benchmark::State& state, int haystack_len) { + const int needle_len = state.range(0); + std::string needle; + for (int i = 0; i < needle_len; ++i) { + needle += 'a' + i; + } + std::string haystack(haystack_len, '0'); // 1000 zeros. + + absl::string_view s(haystack); + for (auto _ : state) { + s.find_first_of(needle); + } +} + +void BM_find_first_of_short(benchmark::State& state) { + BM_worst_case_find_first_of(state, 10); +} + +void BM_find_first_of_medium(benchmark::State& state) { + BM_worst_case_find_first_of(state, 100); +} + +void BM_find_first_of_long(benchmark::State& state) { + BM_worst_case_find_first_of(state, 1000); +} + +BENCHMARK(BM_find_first_of_short)->DenseRange(0, 4)->Arg(8)->Arg(16)->Arg(32); +BENCHMARK(BM_find_first_of_medium)->DenseRange(0, 4)->Arg(8)->Arg(16)->Arg(32); +BENCHMARK(BM_find_first_of_long)->DenseRange(0, 4)->Arg(8)->Arg(16)->Arg(32); + +struct EasyMap : public std::map<absl::string_view, uint64_t> { + explicit EasyMap(size_t) {} +}; + +// This templated benchmark helper function is intended to stress operator== or +// operator< in a realistic test. It surely isn't entirely realistic, but it's +// a start. The test creates a map of type Map, a template arg, and populates +// it with table_size key/value pairs. Each key has WordsPerKey words. After +// creating the map, a number of lookups are done in random order. Some keys +// are used much more frequently than others in this phase of the test. +template <typename Map, int WordsPerKey> +void StringViewMapBenchmark(benchmark::State& state) { + const int table_size = state.range(0); + const double kFractionOfKeysThatAreHot = 0.2; + const int kNumLookupsOfHotKeys = 20; + const int kNumLookupsOfColdKeys = 1; + const char* words[] = {"the", "quick", "brown", "fox", "jumped", + "over", "the", "lazy", "dog", "and", + "found", "a", "large", "mushroom", "and", + "a", "couple", "crickets", "eating", "pie"}; + // Create some keys that consist of words in random order. + std::random_device r; + std::seed_seq seed({r(), r(), r(), r(), r(), r(), r(), r()}); + std::mt19937 rng(seed); + std::vector<std::string> keys(table_size); + std::vector<int> all_indices; + const int kBlockSize = 1 << 12; + std::unordered_set<std::string> t(kBlockSize); + std::uniform_int_distribution<int> uniform(0, ABSL_ARRAYSIZE(words) - 1); + for (int i = 0; i < table_size; i++) { + all_indices.push_back(i); + do { + keys[i].clear(); + for (int j = 0; j < WordsPerKey; j++) { + absl::StrAppend(&keys[i], j > 0 ? " " : "", words[uniform(rng)]); + } + } while (!t.insert(keys[i]).second); + } + + // Create a list of strings to lookup: a permutation of the array of + // keys we just created, with repeats. "Hot" keys get repeated more. + std::shuffle(all_indices.begin(), all_indices.end(), rng); + const int num_hot = table_size * kFractionOfKeysThatAreHot; + const int num_cold = table_size - num_hot; + std::vector<int> hot_indices(all_indices.begin(), + all_indices.begin() + num_hot); + std::vector<int> indices; + for (int i = 0; i < kNumLookupsOfColdKeys; i++) { + indices.insert(indices.end(), all_indices.begin(), all_indices.end()); + } + for (int i = 0; i < kNumLookupsOfHotKeys - kNumLookupsOfColdKeys; i++) { + indices.insert(indices.end(), hot_indices.begin(), hot_indices.end()); + } + std::shuffle(indices.begin(), indices.end(), rng); + ABSL_RAW_CHECK( + num_cold * kNumLookupsOfColdKeys + num_hot * kNumLookupsOfHotKeys == + indices.size(), + ""); + // After constructing the array we probe it with absl::string_views built from + // test_strings. This means operator== won't see equal pointers, so + // it'll have to check for equal lengths and equal characters. + std::vector<std::string> test_strings(indices.size()); + for (int i = 0; i < indices.size(); i++) { + test_strings[i] = keys[indices[i]]; + } + + // Run the benchmark. It includes map construction but is mostly + // map lookups. + for (auto _ : state) { + Map h(table_size); + for (int i = 0; i < table_size; i++) { + h[keys[i]] = i * 2; + } + ABSL_RAW_CHECK(h.size() == table_size, ""); + uint64_t sum = 0; + for (int i = 0; i < indices.size(); i++) { + sum += h[test_strings[i]]; + } + benchmark::DoNotOptimize(sum); + } +} + +void BM_StdMap_4(benchmark::State& state) { + StringViewMapBenchmark<EasyMap, 4>(state); +} +BENCHMARK(BM_StdMap_4)->Range(1 << 10, 1 << 16); + +void BM_StdMap_8(benchmark::State& state) { + StringViewMapBenchmark<EasyMap, 8>(state); +} +BENCHMARK(BM_StdMap_8)->Range(1 << 10, 1 << 16); + +void BM_CopyToStringNative(benchmark::State& state) { + std::string src(state.range(0), 'x'); + absl::string_view sv(src); + std::string dst; + for (auto _ : state) { + dst.assign(sv.begin(), sv.end()); + } +} +BENCHMARK(BM_CopyToStringNative)->Range(1 << 3, 1 << 12); + +void BM_AppendToStringNative(benchmark::State& state) { + std::string src(state.range(0), 'x'); + absl::string_view sv(src); + std::string dst; + for (auto _ : state) { + dst.clear(); + dst.insert(dst.end(), sv.begin(), sv.end()); + } +} +BENCHMARK(BM_AppendToStringNative)->Range(1 << 3, 1 << 12); + +} // namespace + +BENCHMARK_MAIN(); |