string_view_benchmark.cc (13140B)
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 15 #include <algorithm> 16 #include <cstddef> 17 #include <cstdint> 18 #include <map> 19 #include <random> 20 #include <string> 21 #include <unordered_set> 22 #include <vector> 23 24 #include "absl/base/attributes.h" 25 #include "absl/base/internal/raw_logging.h" 26 #include "absl/base/macros.h" 27 #include "absl/strings/str_cat.h" 28 #include "absl/strings/string_view.h" 29 #include "benchmark/benchmark.h" 30 31 namespace { 32 33 void 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 } 49 BENCHMARK(BM_StringViewFromString)->Arg(12)->Arg(128); 50 51 // Provide a forcibly out-of-line wrapper for operator== that can be used in 52 // benchmarks to measure the impact of inlining. 53 ABSL_ATTRIBUTE_NOINLINE 54 bool 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*. 58 ABSL_ATTRIBUTE_NOINLINE 59 void 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 66 void BM_EqualIdentical(benchmark::State& state) { 67 std::string x(state.range(0), 'a'); 68 DoEqualityComparisons(state, x, x); 69 } 70 BENCHMARK(BM_EqualIdentical)->DenseRange(0, 3)->Range(4, 1 << 10); 71 72 void BM_EqualSame(benchmark::State& state) { 73 std::string x(state.range(0), 'a'); 74 std::string y = x; 75 DoEqualityComparisons(state, x, y); 76 } 77 BENCHMARK(BM_EqualSame) 78 ->DenseRange(0, 10) 79 ->Arg(20) 80 ->Arg(40) 81 ->Arg(70) 82 ->Arg(110) 83 ->Range(160, 4096); 84 85 void 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 } 94 BENCHMARK(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. 103 ABSL_ATTRIBUTE_NOINLINE 104 void 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 } 117 void 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. 123 BENCHMARK(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. 128 ABSL_ATTRIBUTE_NOINLINE 129 void 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 144 void 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. 150 BENCHMARK(BM_EqualConstantSizeNonInlined)->DenseRange(2, 4); 151 152 void 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) { 163 benchmark::DoNotOptimize(a); 164 benchmark::DoNotOptimize(b); 165 benchmark::DoNotOptimize(a.compare(b)); 166 } 167 } 168 BENCHMARK(BM_CompareSame)->DenseRange(0, 3)->Range(4, 1 << 10); 169 170 void 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 } 184 BENCHMARK(BM_CompareFirstOneLess)->DenseRange(1, 3)->Range(4, 1 << 10); 185 186 void 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 } 200 BENCHMARK(BM_CompareSecondOneLess)->DenseRange(1, 3)->Range(4, 1 << 10); 201 202 void 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 } 209 BENCHMARK(BM_find_string_view_len_one)->Range(1, 1 << 20); 210 211 void 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 } 218 BENCHMARK(BM_find_string_view_len_two)->Range(1, 1 << 20); 219 220 void 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 } 227 BENCHMARK(BM_find_one_char)->Range(1, 1 << 20); 228 229 void 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 } 236 BENCHMARK(BM_rfind_one_char)->Range(1, 1 << 20); 237 238 void 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 252 void BM_find_first_of_short(benchmark::State& state) { 253 BM_worst_case_find_first_of(state, 10); 254 } 255 256 void BM_find_first_of_medium(benchmark::State& state) { 257 BM_worst_case_find_first_of(state, 100); 258 } 259 260 void BM_find_first_of_long(benchmark::State& state) { 261 BM_worst_case_find_first_of(state, 1000); 262 } 263 264 BENCHMARK(BM_find_first_of_short)->DenseRange(0, 4)->Arg(8)->Arg(16)->Arg(32); 265 BENCHMARK(BM_find_first_of_medium)->DenseRange(0, 4)->Arg(8)->Arg(16)->Arg(32); 266 BENCHMARK(BM_find_first_of_long)->DenseRange(0, 4)->Arg(8)->Arg(16)->Arg(32); 267 268 struct 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. 278 template <typename Map, int WordsPerKey> 279 void 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 350 void BM_StdMap_4(benchmark::State& state) { 351 StringViewMapBenchmark<EasyMap, 4>(state); 352 } 353 BENCHMARK(BM_StdMap_4)->Range(1 << 10, 1 << 16); 354 355 void BM_StdMap_8(benchmark::State& state) { 356 StringViewMapBenchmark<EasyMap, 8>(state); 357 } 358 BENCHMARK(BM_StdMap_8)->Range(1 << 10, 1 << 16); 359 360 void 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 } 368 BENCHMARK(BM_CopyToStringNative)->Range(1 << 3, 1 << 12); 369 370 void 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 } 379 BENCHMARK(BM_AppendToStringNative)->Range(1 << 3, 1 << 12); 380 381 } // namespace