string_view_benchmark.cc
Go to the documentation of this file.
1 // 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 
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"
28 #include "absl/base/macros.h"
29 #include "absl/strings/str_cat.h"
30 
31 namespace {
32 
33 // Provide a forcibly out-of-line wrapper for operator== that can be used in
34 // benchmarks to measure the impact of inlining.
36 bool 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*.
41 void DoEqualityComparisons(benchmark::State& state, absl::string_view a,
43  for (auto _ : state) {
44  benchmark::DoNotOptimize(a == b);
45  }
46 }
47 
48 void BM_EqualIdentical(benchmark::State& state) {
49  std::string x(state.range(0), 'a');
50  DoEqualityComparisons(state, x, x);
51 }
52 BENCHMARK(BM_EqualIdentical)->DenseRange(0, 3)->Range(4, 1 << 10);
53 
54 void BM_EqualSame(benchmark::State& state) {
55  std::string x(state.range(0), 'a');
56  std::string y = x;
57  DoEqualityComparisons(state, x, y);
58 }
59 BENCHMARK(BM_EqualSame)
60  ->DenseRange(0, 10)
61  ->Arg(20)
62  ->Arg(40)
63  ->Arg(70)
64  ->Arg(110)
65  ->Range(160, 4096);
66 
67 void 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 }
76 BENCHMARK(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.
86 void DoConstantSizeInlinedEqualityComparisons(benchmark::State& state,
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 }
99 void 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.
105 BENCHMARK(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.
111 void 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 
126 void 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.
132 BENCHMARK(BM_EqualConstantSizeNonInlined)->DenseRange(2, 4);
133 
134 void 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 }
148 BENCHMARK(BM_CompareSame)->DenseRange(0, 3)->Range(4, 1 << 10);
149 
150 void 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 }
157 BENCHMARK(BM_find_string_view_len_one)->Range(1, 1 << 20);
158 
159 void 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 }
166 BENCHMARK(BM_find_string_view_len_two)->Range(1, 1 << 20);
167 
168 void 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 }
175 BENCHMARK(BM_find_one_char)->Range(1, 1 << 20);
176 
177 void 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 }
184 BENCHMARK(BM_rfind_one_char)->Range(1, 1 << 20);
185 
186 void 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 
200 void BM_find_first_of_short(benchmark::State& state) {
201  BM_worst_case_find_first_of(state, 10);
202 }
203 
204 void BM_find_first_of_medium(benchmark::State& state) {
205  BM_worst_case_find_first_of(state, 100);
206 }
207 
208 void BM_find_first_of_long(benchmark::State& state) {
209  BM_worst_case_find_first_of(state, 1000);
210 }
211 
212 BENCHMARK(BM_find_first_of_short)->DenseRange(0, 4)->Arg(8)->Arg(16)->Arg(32);
213 BENCHMARK(BM_find_first_of_medium)->DenseRange(0, 4)->Arg(8)->Arg(16)->Arg(32);
214 BENCHMARK(BM_find_first_of_long)->DenseRange(0, 4)->Arg(8)->Arg(16)->Arg(32);
215 
216 struct 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.
226 template <typename Map, int WordsPerKey>
227 void 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);
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 
298 void BM_StdMap_4(benchmark::State& state) {
299  StringViewMapBenchmark<EasyMap, 4>(state);
300 }
301 BENCHMARK(BM_StdMap_4)->Range(1 << 10, 1 << 16);
302 
303 void BM_StdMap_8(benchmark::State& state) {
304  StringViewMapBenchmark<EasyMap, 8>(state);
305 }
306 BENCHMARK(BM_StdMap_8)->Range(1 << 10, 1 << 16);
307 
308 void 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 }
316 BENCHMARK(BM_CopyToStringNative)->Range(1 << 3, 1 << 12);
317 
318 void 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 }
327 BENCHMARK(BM_AppendToStringNative)->Range(1 << 3, 1 << 12);
328 
329 } // namespace
void StrAppend(std::string *dest, const AlphaNum &a)
Definition: str_cat.cc:193
auto keys(const Set &s) -> std::vector< typename std::decay< typename Set::key_type >::type >
#define ABSL_RAW_CHECK(condition, message)
Definition: raw_logging.h:57
#define ABSL_ATTRIBUTE_NOINLINE
Definition: attributes.h:136
#define ABSL_ARRAYSIZE(array)
Definition: macros.h:42
uint64_t b
Definition: layout_test.cc:50
int compare(string_view x) const noexcept
Definition: string_view.h:369


abseil_cpp
Author(s):
autogenerated on Wed Jun 19 2019 19:19:58