blob: 0d74e23e2fc9706a4a56710411c04c34133ce796 [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
Austin Schuhb4691e92020-12-31 12:37:18 -080033void BM_StringViewFromString(benchmark::State& state) {
34 std::string s(state.range(0), 'x');
35 std::string* ps = &s;
36 struct SV {
37 SV() = default;
38 explicit SV(const std::string& s) : sv(s) {}
39 absl::string_view sv;
40 } sv;
41 SV* psv = &sv;
42 benchmark::DoNotOptimize(ps);
43 benchmark::DoNotOptimize(psv);
44 for (auto _ : state) {
45 new (psv) SV(*ps);
46 benchmark::DoNotOptimize(sv);
47 }
48}
49BENCHMARK(BM_StringViewFromString)->Arg(12)->Arg(128);
50
Austin Schuh36244a12019-09-21 17:52:38 -070051// Provide a forcibly out-of-line wrapper for operator== that can be used in
52// benchmarks to measure the impact of inlining.
53ABSL_ATTRIBUTE_NOINLINE
54bool NonInlinedEq(absl::string_view a, absl::string_view b) { return a == b; }
55
56// We use functions that cannot be inlined to perform the comparison loops so
57// that inlining of the operator== can't optimize away *everything*.
58ABSL_ATTRIBUTE_NOINLINE
59void DoEqualityComparisons(benchmark::State& state, absl::string_view a,
60 absl::string_view b) {
61 for (auto _ : state) {
62 benchmark::DoNotOptimize(a == b);
63 }
64}
65
66void BM_EqualIdentical(benchmark::State& state) {
67 std::string x(state.range(0), 'a');
68 DoEqualityComparisons(state, x, x);
69}
70BENCHMARK(BM_EqualIdentical)->DenseRange(0, 3)->Range(4, 1 << 10);
71
72void BM_EqualSame(benchmark::State& state) {
73 std::string x(state.range(0), 'a');
74 std::string y = x;
75 DoEqualityComparisons(state, x, y);
76}
77BENCHMARK(BM_EqualSame)
78 ->DenseRange(0, 10)
79 ->Arg(20)
80 ->Arg(40)
81 ->Arg(70)
82 ->Arg(110)
83 ->Range(160, 4096);
84
85void BM_EqualDifferent(benchmark::State& state) {
86 const int len = state.range(0);
87 std::string x(len, 'a');
88 std::string y = x;
89 if (len > 0) {
90 y[len - 1] = 'b';
91 }
92 DoEqualityComparisons(state, x, y);
93}
94BENCHMARK(BM_EqualDifferent)->DenseRange(0, 3)->Range(4, 1 << 10);
95
96// This benchmark is intended to check that important simplifications can be
97// made with absl::string_view comparisons against constant strings. The idea is
98// that if constant strings cause redundant components of the comparison, the
99// compiler should detect and eliminate them. Here we use 8 different strings,
100// each with the same size. Provided our comparison makes the implementation
101// inline-able by the compiler, it should fold all of these away into a single
102// size check once per loop iteration.
103ABSL_ATTRIBUTE_NOINLINE
104void DoConstantSizeInlinedEqualityComparisons(benchmark::State& state,
105 absl::string_view a) {
106 for (auto _ : state) {
107 benchmark::DoNotOptimize(a == "aaa");
108 benchmark::DoNotOptimize(a == "bbb");
109 benchmark::DoNotOptimize(a == "ccc");
110 benchmark::DoNotOptimize(a == "ddd");
111 benchmark::DoNotOptimize(a == "eee");
112 benchmark::DoNotOptimize(a == "fff");
113 benchmark::DoNotOptimize(a == "ggg");
114 benchmark::DoNotOptimize(a == "hhh");
115 }
116}
117void BM_EqualConstantSizeInlined(benchmark::State& state) {
118 std::string x(state.range(0), 'a');
119 DoConstantSizeInlinedEqualityComparisons(state, x);
120}
121// We only need to check for size of 3, and <> 3 as this benchmark only has to
122// do with size differences.
123BENCHMARK(BM_EqualConstantSizeInlined)->DenseRange(2, 4);
124
125// This benchmark exists purely to give context to the above timings: this is
126// what they would look like if the compiler is completely unable to simplify
127// between two comparisons when they are comparing against constant strings.
128ABSL_ATTRIBUTE_NOINLINE
129void DoConstantSizeNonInlinedEqualityComparisons(benchmark::State& state,
130 absl::string_view a) {
131 for (auto _ : state) {
132 // Force these out-of-line to compare with the above function.
133 benchmark::DoNotOptimize(NonInlinedEq(a, "aaa"));
134 benchmark::DoNotOptimize(NonInlinedEq(a, "bbb"));
135 benchmark::DoNotOptimize(NonInlinedEq(a, "ccc"));
136 benchmark::DoNotOptimize(NonInlinedEq(a, "ddd"));
137 benchmark::DoNotOptimize(NonInlinedEq(a, "eee"));
138 benchmark::DoNotOptimize(NonInlinedEq(a, "fff"));
139 benchmark::DoNotOptimize(NonInlinedEq(a, "ggg"));
140 benchmark::DoNotOptimize(NonInlinedEq(a, "hhh"));
141 }
142}
143
144void BM_EqualConstantSizeNonInlined(benchmark::State& state) {
145 std::string x(state.range(0), 'a');
146 DoConstantSizeNonInlinedEqualityComparisons(state, x);
147}
148// We only need to check for size of 3, and <> 3 as this benchmark only has to
149// do with size differences.
150BENCHMARK(BM_EqualConstantSizeNonInlined)->DenseRange(2, 4);
151
152void BM_CompareSame(benchmark::State& state) {
153 const int len = state.range(0);
154 std::string x;
155 for (int i = 0; i < len; i++) {
156 x += 'a';
157 }
158 std::string y = x;
159 absl::string_view a = x;
160 absl::string_view b = y;
161
162 for (auto _ : state) {
Austin Schuhb4691e92020-12-31 12:37:18 -0800163 benchmark::DoNotOptimize(a);
164 benchmark::DoNotOptimize(b);
Austin Schuh36244a12019-09-21 17:52:38 -0700165 benchmark::DoNotOptimize(a.compare(b));
166 }
167}
168BENCHMARK(BM_CompareSame)->DenseRange(0, 3)->Range(4, 1 << 10);
169
Austin Schuhb4691e92020-12-31 12:37:18 -0800170void BM_CompareFirstOneLess(benchmark::State& state) {
171 const int len = state.range(0);
172 std::string x(len, 'a');
173 std::string y = x;
174 y.back() = 'b';
175 absl::string_view a = x;
176 absl::string_view b = y;
177
178 for (auto _ : state) {
179 benchmark::DoNotOptimize(a);
180 benchmark::DoNotOptimize(b);
181 benchmark::DoNotOptimize(a.compare(b));
182 }
183}
184BENCHMARK(BM_CompareFirstOneLess)->DenseRange(1, 3)->Range(4, 1 << 10);
185
186void BM_CompareSecondOneLess(benchmark::State& state) {
187 const int len = state.range(0);
188 std::string x(len, 'a');
189 std::string y = x;
190 x.back() = 'b';
191 absl::string_view a = x;
192 absl::string_view b = y;
193
194 for (auto _ : state) {
195 benchmark::DoNotOptimize(a);
196 benchmark::DoNotOptimize(b);
197 benchmark::DoNotOptimize(a.compare(b));
198 }
199}
200BENCHMARK(BM_CompareSecondOneLess)->DenseRange(1, 3)->Range(4, 1 << 10);
201
Austin Schuh36244a12019-09-21 17:52:38 -0700202void BM_find_string_view_len_one(benchmark::State& state) {
203 std::string haystack(state.range(0), '0');
204 absl::string_view s(haystack);
205 for (auto _ : state) {
206 benchmark::DoNotOptimize(s.find("x")); // not present; length 1
207 }
208}
209BENCHMARK(BM_find_string_view_len_one)->Range(1, 1 << 20);
210
211void BM_find_string_view_len_two(benchmark::State& state) {
212 std::string haystack(state.range(0), '0');
213 absl::string_view s(haystack);
214 for (auto _ : state) {
215 benchmark::DoNotOptimize(s.find("xx")); // not present; length 2
216 }
217}
218BENCHMARK(BM_find_string_view_len_two)->Range(1, 1 << 20);
219
220void BM_find_one_char(benchmark::State& state) {
221 std::string haystack(state.range(0), '0');
222 absl::string_view s(haystack);
223 for (auto _ : state) {
224 benchmark::DoNotOptimize(s.find('x')); // not present
225 }
226}
227BENCHMARK(BM_find_one_char)->Range(1, 1 << 20);
228
229void BM_rfind_one_char(benchmark::State& state) {
230 std::string haystack(state.range(0), '0');
231 absl::string_view s(haystack);
232 for (auto _ : state) {
233 benchmark::DoNotOptimize(s.rfind('x')); // not present
234 }
235}
236BENCHMARK(BM_rfind_one_char)->Range(1, 1 << 20);
237
238void BM_worst_case_find_first_of(benchmark::State& state, int haystack_len) {
239 const int needle_len = state.range(0);
240 std::string needle;
241 for (int i = 0; i < needle_len; ++i) {
242 needle += 'a' + i;
243 }
244 std::string haystack(haystack_len, '0'); // 1000 zeros.
245
246 absl::string_view s(haystack);
247 for (auto _ : state) {
248 benchmark::DoNotOptimize(s.find_first_of(needle));
249 }
250}
251
252void BM_find_first_of_short(benchmark::State& state) {
253 BM_worst_case_find_first_of(state, 10);
254}
255
256void BM_find_first_of_medium(benchmark::State& state) {
257 BM_worst_case_find_first_of(state, 100);
258}
259
260void BM_find_first_of_long(benchmark::State& state) {
261 BM_worst_case_find_first_of(state, 1000);
262}
263
264BENCHMARK(BM_find_first_of_short)->DenseRange(0, 4)->Arg(8)->Arg(16)->Arg(32);
265BENCHMARK(BM_find_first_of_medium)->DenseRange(0, 4)->Arg(8)->Arg(16)->Arg(32);
266BENCHMARK(BM_find_first_of_long)->DenseRange(0, 4)->Arg(8)->Arg(16)->Arg(32);
267
268struct EasyMap : public std::map<absl::string_view, uint64_t> {
269 explicit EasyMap(size_t) {}
270};
271
272// This templated benchmark helper function is intended to stress operator== or
273// operator< in a realistic test. It surely isn't entirely realistic, but it's
274// a start. The test creates a map of type Map, a template arg, and populates
275// it with table_size key/value pairs. Each key has WordsPerKey words. After
276// creating the map, a number of lookups are done in random order. Some keys
277// are used much more frequently than others in this phase of the test.
278template <typename Map, int WordsPerKey>
279void StringViewMapBenchmark(benchmark::State& state) {
280 const int table_size = state.range(0);
281 const double kFractionOfKeysThatAreHot = 0.2;
282 const int kNumLookupsOfHotKeys = 20;
283 const int kNumLookupsOfColdKeys = 1;
284 const char* words[] = {"the", "quick", "brown", "fox", "jumped",
285 "over", "the", "lazy", "dog", "and",
286 "found", "a", "large", "mushroom", "and",
287 "a", "couple", "crickets", "eating", "pie"};
288 // Create some keys that consist of words in random order.
289 std::random_device r;
290 std::seed_seq seed({r(), r(), r(), r(), r(), r(), r(), r()});
291 std::mt19937 rng(seed);
292 std::vector<std::string> keys(table_size);
293 std::vector<int> all_indices;
294 const int kBlockSize = 1 << 12;
295 std::unordered_set<std::string> t(kBlockSize);
296 std::uniform_int_distribution<int> uniform(0, ABSL_ARRAYSIZE(words) - 1);
297 for (int i = 0; i < table_size; i++) {
298 all_indices.push_back(i);
299 do {
300 keys[i].clear();
301 for (int j = 0; j < WordsPerKey; j++) {
302 absl::StrAppend(&keys[i], j > 0 ? " " : "", words[uniform(rng)]);
303 }
304 } while (!t.insert(keys[i]).second);
305 }
306
307 // Create a list of strings to lookup: a permutation of the array of
308 // keys we just created, with repeats. "Hot" keys get repeated more.
309 std::shuffle(all_indices.begin(), all_indices.end(), rng);
310 const int num_hot = table_size * kFractionOfKeysThatAreHot;
311 const int num_cold = table_size - num_hot;
312 std::vector<int> hot_indices(all_indices.begin(),
313 all_indices.begin() + num_hot);
314 std::vector<int> indices;
315 for (int i = 0; i < kNumLookupsOfColdKeys; i++) {
316 indices.insert(indices.end(), all_indices.begin(), all_indices.end());
317 }
318 for (int i = 0; i < kNumLookupsOfHotKeys - kNumLookupsOfColdKeys; i++) {
319 indices.insert(indices.end(), hot_indices.begin(), hot_indices.end());
320 }
321 std::shuffle(indices.begin(), indices.end(), rng);
322 ABSL_RAW_CHECK(
323 num_cold * kNumLookupsOfColdKeys + num_hot * kNumLookupsOfHotKeys ==
324 indices.size(),
325 "");
326 // After constructing the array we probe it with absl::string_views built from
327 // test_strings. This means operator== won't see equal pointers, so
328 // it'll have to check for equal lengths and equal characters.
329 std::vector<std::string> test_strings(indices.size());
330 for (int i = 0; i < indices.size(); i++) {
331 test_strings[i] = keys[indices[i]];
332 }
333
334 // Run the benchmark. It includes map construction but is mostly
335 // map lookups.
336 for (auto _ : state) {
337 Map h(table_size);
338 for (int i = 0; i < table_size; i++) {
339 h[keys[i]] = i * 2;
340 }
341 ABSL_RAW_CHECK(h.size() == table_size, "");
342 uint64_t sum = 0;
343 for (int i = 0; i < indices.size(); i++) {
344 sum += h[test_strings[i]];
345 }
346 benchmark::DoNotOptimize(sum);
347 }
348}
349
350void BM_StdMap_4(benchmark::State& state) {
351 StringViewMapBenchmark<EasyMap, 4>(state);
352}
353BENCHMARK(BM_StdMap_4)->Range(1 << 10, 1 << 16);
354
355void BM_StdMap_8(benchmark::State& state) {
356 StringViewMapBenchmark<EasyMap, 8>(state);
357}
358BENCHMARK(BM_StdMap_8)->Range(1 << 10, 1 << 16);
359
360void BM_CopyToStringNative(benchmark::State& state) {
361 std::string src(state.range(0), 'x');
362 absl::string_view sv(src);
363 std::string dst;
364 for (auto _ : state) {
365 dst.assign(sv.begin(), sv.end());
366 }
367}
368BENCHMARK(BM_CopyToStringNative)->Range(1 << 3, 1 << 12);
369
370void BM_AppendToStringNative(benchmark::State& state) {
371 std::string src(state.range(0), 'x');
372 absl::string_view sv(src);
373 std::string dst;
374 for (auto _ : state) {
375 dst.clear();
376 dst.insert(dst.end(), sv.begin(), sv.end());
377 }
378}
379BENCHMARK(BM_AppendToStringNative)->Range(1 << 3, 1 << 12);
380
381} // namespace