summaryrefslogtreecommitdiff
path: root/absl/strings/string_view_benchmark.cc
blob: fb46db18b3c3902b0d7d68ecb53b06a57ad55d3f (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
// 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