blob: 46909cb093d4439ffb35de24d2b6e8cac4fb6136 [file] [log] [blame]
Austin Schuh36244a12019-09-21 17:52:38 -07001// Copyright 2018 The Abseil Authors.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// https://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#include "absl/strings/string_view.h"
16
17#include <algorithm>
18#include <cstdint>
19#include <map>
20#include <random>
21#include <string>
22#include <unordered_set>
23#include <vector>
24
25#include "benchmark/benchmark.h"
26#include "absl/base/attributes.h"
27#include "absl/base/internal/raw_logging.h"
28#include "absl/base/macros.h"
29#include "absl/strings/str_cat.h"
30
31namespace {
32
33// Provide a forcibly out-of-line wrapper for operator== that can be used in
34// benchmarks to measure the impact of inlining.
35ABSL_ATTRIBUTE_NOINLINE
36bool NonInlinedEq(absl::string_view a, absl::string_view b) { return a == b; }
37
38// We use functions that cannot be inlined to perform the comparison loops so
39// that inlining of the operator== can't optimize away *everything*.
40ABSL_ATTRIBUTE_NOINLINE
41void DoEqualityComparisons(benchmark::State& state, absl::string_view a,
42 absl::string_view b) {
43 for (auto _ : state) {
44 benchmark::DoNotOptimize(a == b);
45 }
46}
47
48void BM_EqualIdentical(benchmark::State& state) {
49 std::string x(state.range(0), 'a');
50 DoEqualityComparisons(state, x, x);
51}
52BENCHMARK(BM_EqualIdentical)->DenseRange(0, 3)->Range(4, 1 << 10);
53
54void BM_EqualSame(benchmark::State& state) {
55 std::string x(state.range(0), 'a');
56 std::string y = x;
57 DoEqualityComparisons(state, x, y);
58}
59BENCHMARK(BM_EqualSame)
60 ->DenseRange(0, 10)
61 ->Arg(20)
62 ->Arg(40)
63 ->Arg(70)
64 ->Arg(110)
65 ->Range(160, 4096);
66
67void BM_EqualDifferent(benchmark::State& state) {
68 const int len = state.range(0);
69 std::string x(len, 'a');
70 std::string y = x;
71 if (len > 0) {
72 y[len - 1] = 'b';
73 }
74 DoEqualityComparisons(state, x, y);
75}
76BENCHMARK(BM_EqualDifferent)->DenseRange(0, 3)->Range(4, 1 << 10);
77
78// This benchmark is intended to check that important simplifications can be
79// made with absl::string_view comparisons against constant strings. The idea is
80// that if constant strings cause redundant components of the comparison, the
81// compiler should detect and eliminate them. Here we use 8 different strings,
82// each with the same size. Provided our comparison makes the implementation
83// inline-able by the compiler, it should fold all of these away into a single
84// size check once per loop iteration.
85ABSL_ATTRIBUTE_NOINLINE
86void DoConstantSizeInlinedEqualityComparisons(benchmark::State& state,
87 absl::string_view a) {
88 for (auto _ : state) {
89 benchmark::DoNotOptimize(a == "aaa");
90 benchmark::DoNotOptimize(a == "bbb");
91 benchmark::DoNotOptimize(a == "ccc");
92 benchmark::DoNotOptimize(a == "ddd");
93 benchmark::DoNotOptimize(a == "eee");
94 benchmark::DoNotOptimize(a == "fff");
95 benchmark::DoNotOptimize(a == "ggg");
96 benchmark::DoNotOptimize(a == "hhh");
97 }
98}
99void BM_EqualConstantSizeInlined(benchmark::State& state) {
100 std::string x(state.range(0), 'a');
101 DoConstantSizeInlinedEqualityComparisons(state, x);
102}
103// We only need to check for size of 3, and <> 3 as this benchmark only has to
104// do with size differences.
105BENCHMARK(BM_EqualConstantSizeInlined)->DenseRange(2, 4);
106
107// This benchmark exists purely to give context to the above timings: this is
108// what they would look like if the compiler is completely unable to simplify
109// between two comparisons when they are comparing against constant strings.
110ABSL_ATTRIBUTE_NOINLINE
111void DoConstantSizeNonInlinedEqualityComparisons(benchmark::State& state,
112 absl::string_view a) {
113 for (auto _ : state) {
114 // Force these out-of-line to compare with the above function.
115 benchmark::DoNotOptimize(NonInlinedEq(a, "aaa"));
116 benchmark::DoNotOptimize(NonInlinedEq(a, "bbb"));
117 benchmark::DoNotOptimize(NonInlinedEq(a, "ccc"));
118 benchmark::DoNotOptimize(NonInlinedEq(a, "ddd"));
119 benchmark::DoNotOptimize(NonInlinedEq(a, "eee"));
120 benchmark::DoNotOptimize(NonInlinedEq(a, "fff"));
121 benchmark::DoNotOptimize(NonInlinedEq(a, "ggg"));
122 benchmark::DoNotOptimize(NonInlinedEq(a, "hhh"));
123 }
124}
125
126void BM_EqualConstantSizeNonInlined(benchmark::State& state) {
127 std::string x(state.range(0), 'a');
128 DoConstantSizeNonInlinedEqualityComparisons(state, x);
129}
130// We only need to check for size of 3, and <> 3 as this benchmark only has to
131// do with size differences.
132BENCHMARK(BM_EqualConstantSizeNonInlined)->DenseRange(2, 4);
133
134void BM_CompareSame(benchmark::State& state) {
135 const int len = state.range(0);
136 std::string x;
137 for (int i = 0; i < len; i++) {
138 x += 'a';
139 }
140 std::string y = x;
141 absl::string_view a = x;
142 absl::string_view b = y;
143
144 for (auto _ : state) {
145 benchmark::DoNotOptimize(a.compare(b));
146 }
147}
148BENCHMARK(BM_CompareSame)->DenseRange(0, 3)->Range(4, 1 << 10);
149
150void BM_find_string_view_len_one(benchmark::State& state) {
151 std::string haystack(state.range(0), '0');
152 absl::string_view s(haystack);
153 for (auto _ : state) {
154 benchmark::DoNotOptimize(s.find("x")); // not present; length 1
155 }
156}
157BENCHMARK(BM_find_string_view_len_one)->Range(1, 1 << 20);
158
159void BM_find_string_view_len_two(benchmark::State& state) {
160 std::string haystack(state.range(0), '0');
161 absl::string_view s(haystack);
162 for (auto _ : state) {
163 benchmark::DoNotOptimize(s.find("xx")); // not present; length 2
164 }
165}
166BENCHMARK(BM_find_string_view_len_two)->Range(1, 1 << 20);
167
168void BM_find_one_char(benchmark::State& state) {
169 std::string haystack(state.range(0), '0');
170 absl::string_view s(haystack);
171 for (auto _ : state) {
172 benchmark::DoNotOptimize(s.find('x')); // not present
173 }
174}
175BENCHMARK(BM_find_one_char)->Range(1, 1 << 20);
176
177void BM_rfind_one_char(benchmark::State& state) {
178 std::string haystack(state.range(0), '0');
179 absl::string_view s(haystack);
180 for (auto _ : state) {
181 benchmark::DoNotOptimize(s.rfind('x')); // not present
182 }
183}
184BENCHMARK(BM_rfind_one_char)->Range(1, 1 << 20);
185
186void BM_worst_case_find_first_of(benchmark::State& state, int haystack_len) {
187 const int needle_len = state.range(0);
188 std::string needle;
189 for (int i = 0; i < needle_len; ++i) {
190 needle += 'a' + i;
191 }
192 std::string haystack(haystack_len, '0'); // 1000 zeros.
193
194 absl::string_view s(haystack);
195 for (auto _ : state) {
196 benchmark::DoNotOptimize(s.find_first_of(needle));
197 }
198}
199
200void BM_find_first_of_short(benchmark::State& state) {
201 BM_worst_case_find_first_of(state, 10);
202}
203
204void BM_find_first_of_medium(benchmark::State& state) {
205 BM_worst_case_find_first_of(state, 100);
206}
207
208void BM_find_first_of_long(benchmark::State& state) {
209 BM_worst_case_find_first_of(state, 1000);
210}
211
212BENCHMARK(BM_find_first_of_short)->DenseRange(0, 4)->Arg(8)->Arg(16)->Arg(32);
213BENCHMARK(BM_find_first_of_medium)->DenseRange(0, 4)->Arg(8)->Arg(16)->Arg(32);
214BENCHMARK(BM_find_first_of_long)->DenseRange(0, 4)->Arg(8)->Arg(16)->Arg(32);
215
216struct EasyMap : public std::map<absl::string_view, uint64_t> {
217 explicit EasyMap(size_t) {}
218};
219
220// This templated benchmark helper function is intended to stress operator== or
221// operator< in a realistic test. It surely isn't entirely realistic, but it's
222// a start. The test creates a map of type Map, a template arg, and populates
223// it with table_size key/value pairs. Each key has WordsPerKey words. After
224// creating the map, a number of lookups are done in random order. Some keys
225// are used much more frequently than others in this phase of the test.
226template <typename Map, int WordsPerKey>
227void StringViewMapBenchmark(benchmark::State& state) {
228 const int table_size = state.range(0);
229 const double kFractionOfKeysThatAreHot = 0.2;
230 const int kNumLookupsOfHotKeys = 20;
231 const int kNumLookupsOfColdKeys = 1;
232 const char* words[] = {"the", "quick", "brown", "fox", "jumped",
233 "over", "the", "lazy", "dog", "and",
234 "found", "a", "large", "mushroom", "and",
235 "a", "couple", "crickets", "eating", "pie"};
236 // Create some keys that consist of words in random order.
237 std::random_device r;
238 std::seed_seq seed({r(), r(), r(), r(), r(), r(), r(), r()});
239 std::mt19937 rng(seed);
240 std::vector<std::string> keys(table_size);
241 std::vector<int> all_indices;
242 const int kBlockSize = 1 << 12;
243 std::unordered_set<std::string> t(kBlockSize);
244 std::uniform_int_distribution<int> uniform(0, ABSL_ARRAYSIZE(words) - 1);
245 for (int i = 0; i < table_size; i++) {
246 all_indices.push_back(i);
247 do {
248 keys[i].clear();
249 for (int j = 0; j < WordsPerKey; j++) {
250 absl::StrAppend(&keys[i], j > 0 ? " " : "", words[uniform(rng)]);
251 }
252 } while (!t.insert(keys[i]).second);
253 }
254
255 // Create a list of strings to lookup: a permutation of the array of
256 // keys we just created, with repeats. "Hot" keys get repeated more.
257 std::shuffle(all_indices.begin(), all_indices.end(), rng);
258 const int num_hot = table_size * kFractionOfKeysThatAreHot;
259 const int num_cold = table_size - num_hot;
260 std::vector<int> hot_indices(all_indices.begin(),
261 all_indices.begin() + num_hot);
262 std::vector<int> indices;
263 for (int i = 0; i < kNumLookupsOfColdKeys; i++) {
264 indices.insert(indices.end(), all_indices.begin(), all_indices.end());
265 }
266 for (int i = 0; i < kNumLookupsOfHotKeys - kNumLookupsOfColdKeys; i++) {
267 indices.insert(indices.end(), hot_indices.begin(), hot_indices.end());
268 }
269 std::shuffle(indices.begin(), indices.end(), rng);
270 ABSL_RAW_CHECK(
271 num_cold * kNumLookupsOfColdKeys + num_hot * kNumLookupsOfHotKeys ==
272 indices.size(),
273 "");
274 // After constructing the array we probe it with absl::string_views built from
275 // test_strings. This means operator== won't see equal pointers, so
276 // it'll have to check for equal lengths and equal characters.
277 std::vector<std::string> test_strings(indices.size());
278 for (int i = 0; i < indices.size(); i++) {
279 test_strings[i] = keys[indices[i]];
280 }
281
282 // Run the benchmark. It includes map construction but is mostly
283 // map lookups.
284 for (auto _ : state) {
285 Map h(table_size);
286 for (int i = 0; i < table_size; i++) {
287 h[keys[i]] = i * 2;
288 }
289 ABSL_RAW_CHECK(h.size() == table_size, "");
290 uint64_t sum = 0;
291 for (int i = 0; i < indices.size(); i++) {
292 sum += h[test_strings[i]];
293 }
294 benchmark::DoNotOptimize(sum);
295 }
296}
297
298void BM_StdMap_4(benchmark::State& state) {
299 StringViewMapBenchmark<EasyMap, 4>(state);
300}
301BENCHMARK(BM_StdMap_4)->Range(1 << 10, 1 << 16);
302
303void BM_StdMap_8(benchmark::State& state) {
304 StringViewMapBenchmark<EasyMap, 8>(state);
305}
306BENCHMARK(BM_StdMap_8)->Range(1 << 10, 1 << 16);
307
308void BM_CopyToStringNative(benchmark::State& state) {
309 std::string src(state.range(0), 'x');
310 absl::string_view sv(src);
311 std::string dst;
312 for (auto _ : state) {
313 dst.assign(sv.begin(), sv.end());
314 }
315}
316BENCHMARK(BM_CopyToStringNative)->Range(1 << 3, 1 << 12);
317
318void BM_AppendToStringNative(benchmark::State& state) {
319 std::string src(state.range(0), 'x');
320 absl::string_view sv(src);
321 std::string dst;
322 for (auto _ : state) {
323 dst.clear();
324 dst.insert(dst.end(), sv.begin(), sv.end());
325 }
326}
327BENCHMARK(BM_AppendToStringNative)->Range(1 << 3, 1 << 12);
328
329} // namespace