btree_benchmark.cc (29972B)
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 <stdint.h> 16 17 #include <algorithm> 18 #include <functional> 19 #include <map> 20 #include <numeric> 21 #include <random> 22 #include <set> 23 #include <string> 24 #include <type_traits> 25 #include <unordered_map> 26 #include <unordered_set> 27 #include <vector> 28 29 #include "absl/algorithm/container.h" 30 #include "absl/base/internal/raw_logging.h" 31 #include "absl/container/btree_map.h" 32 #include "absl/container/btree_set.h" 33 #include "absl/container/btree_test.h" 34 #include "absl/container/flat_hash_map.h" 35 #include "absl/container/flat_hash_set.h" 36 #include "absl/container/internal/hashtable_debug.h" 37 #include "absl/hash/hash.h" 38 #include "absl/log/log.h" 39 #include "absl/memory/memory.h" 40 #include "absl/random/random.h" 41 #include "absl/strings/cord.h" 42 #include "absl/strings/str_format.h" 43 #include "absl/time/time.h" 44 #include "benchmark/benchmark.h" 45 46 namespace absl { 47 ABSL_NAMESPACE_BEGIN 48 namespace container_internal { 49 namespace { 50 51 constexpr size_t kBenchmarkValues = 1 << 20; 52 53 // How many times we add and remove sub-batches in one batch of *AddRem 54 // benchmarks. 55 constexpr size_t kAddRemBatchSize = 1 << 2; 56 57 // Generates n values in the range [0, 4 * n]. 58 template <typename V> 59 std::vector<V> GenerateValues(int n) { 60 constexpr int kSeed = 23; 61 return GenerateValuesWithSeed<V>(n, 4 * n, kSeed); 62 } 63 64 // Benchmark insertion of values into a container. 65 template <typename T> 66 void BM_InsertImpl(benchmark::State& state, bool sorted) { 67 using V = typename remove_pair_const<typename T::value_type>::type; 68 typename KeyOfValue<typename T::key_type, V>::type key_of_value; 69 70 std::vector<V> values = GenerateValues<V>(kBenchmarkValues); 71 if (sorted) { 72 std::sort(values.begin(), values.end()); 73 } 74 T container(values.begin(), values.end()); 75 76 // Remove and re-insert 10% of the keys per batch. 77 const int batch_size = (kBenchmarkValues + 9) / 10; 78 while (state.KeepRunningBatch(batch_size)) { 79 state.PauseTiming(); 80 const auto i = static_cast<int>(state.iterations()); 81 82 for (int j = i; j < i + batch_size; j++) { 83 int x = j % kBenchmarkValues; 84 container.erase(key_of_value(values[x])); 85 } 86 87 state.ResumeTiming(); 88 89 for (int j = i; j < i + batch_size; j++) { 90 int x = j % kBenchmarkValues; 91 container.insert(values[x]); 92 } 93 } 94 } 95 96 template <typename T> 97 void BM_Insert(benchmark::State& state) { 98 BM_InsertImpl<T>(state, false); 99 } 100 101 template <typename T> 102 void BM_InsertSorted(benchmark::State& state) { 103 BM_InsertImpl<T>(state, true); 104 } 105 106 // Benchmark inserting the first few elements in a container. In b-tree, this is 107 // when the root node grows. 108 template <typename T> 109 void BM_InsertSmall(benchmark::State& state) { 110 using V = typename remove_pair_const<typename T::value_type>::type; 111 112 const int kSize = 8; 113 std::vector<V> values = GenerateValues<V>(kSize); 114 T container; 115 116 while (state.KeepRunningBatch(kSize)) { 117 for (int i = 0; i < kSize; ++i) { 118 benchmark::DoNotOptimize(container.insert(values[i])); 119 } 120 state.PauseTiming(); 121 // Do not measure the time it takes to clear the container. 122 container.clear(); 123 state.ResumeTiming(); 124 } 125 } 126 127 template <typename T> 128 void BM_LookupImpl(benchmark::State& state, bool sorted) { 129 using V = typename remove_pair_const<typename T::value_type>::type; 130 typename KeyOfValue<typename T::key_type, V>::type key_of_value; 131 132 std::vector<V> values = GenerateValues<V>(kBenchmarkValues); 133 if (sorted) { 134 std::sort(values.begin(), values.end()); 135 } 136 T container(values.begin(), values.end()); 137 138 while (state.KeepRunning()) { 139 int idx = state.iterations() % kBenchmarkValues; 140 benchmark::DoNotOptimize(container.find(key_of_value(values[idx]))); 141 } 142 } 143 144 // Benchmark lookup of values in a container. 145 template <typename T> 146 void BM_Lookup(benchmark::State& state) { 147 BM_LookupImpl<T>(state, false); 148 } 149 150 // Benchmark lookup of values in a full container, meaning that values 151 // are inserted in-order to take advantage of biased insertion, which 152 // yields a full tree. 153 template <typename T> 154 void BM_FullLookup(benchmark::State& state) { 155 BM_LookupImpl<T>(state, true); 156 } 157 158 // Benchmark erasing values from a container. 159 template <typename T> 160 void BM_Erase(benchmark::State& state) { 161 using V = typename remove_pair_const<typename T::value_type>::type; 162 typename KeyOfValue<typename T::key_type, V>::type key_of_value; 163 std::vector<V> values = GenerateValues<V>(kBenchmarkValues); 164 T container(values.begin(), values.end()); 165 166 // Remove and re-insert 10% of the keys per batch. 167 const int batch_size = (kBenchmarkValues + 9) / 10; 168 while (state.KeepRunningBatch(batch_size)) { 169 const int i = state.iterations(); 170 171 for (int j = i; j < i + batch_size; j++) { 172 int x = j % kBenchmarkValues; 173 container.erase(key_of_value(values[x])); 174 } 175 176 state.PauseTiming(); 177 for (int j = i; j < i + batch_size; j++) { 178 int x = j % kBenchmarkValues; 179 container.insert(values[x]); 180 } 181 state.ResumeTiming(); 182 } 183 } 184 185 // Benchmark erasing multiple values from a container. 186 template <typename T> 187 void BM_EraseRange(benchmark::State& state) { 188 using V = typename remove_pair_const<typename T::value_type>::type; 189 typename KeyOfValue<typename T::key_type, V>::type key_of_value; 190 std::vector<V> values = GenerateValues<V>(kBenchmarkValues); 191 T container(values.begin(), values.end()); 192 193 // Remove and re-insert 10% of the keys per batch. 194 const int batch_size = (kBenchmarkValues + 9) / 10; 195 while (state.KeepRunningBatch(batch_size)) { 196 const int i = state.iterations(); 197 198 const int start_index = i % kBenchmarkValues; 199 200 state.PauseTiming(); 201 { 202 std::vector<V> removed; 203 removed.reserve(batch_size); 204 auto itr = container.find(key_of_value(values[start_index])); 205 auto start = itr; 206 for (int j = 0; j < batch_size; j++) { 207 if (itr == container.end()) { 208 state.ResumeTiming(); 209 container.erase(start, itr); 210 state.PauseTiming(); 211 itr = container.begin(); 212 start = itr; 213 } 214 removed.push_back(*itr++); 215 } 216 217 state.ResumeTiming(); 218 container.erase(start, itr); 219 state.PauseTiming(); 220 221 container.insert(removed.begin(), removed.end()); 222 } 223 state.ResumeTiming(); 224 } 225 } 226 227 // Predicate that erases every other element. We can't use a lambda because 228 // C++11 doesn't support generic lambdas. 229 // TODO(b/207389011): consider adding benchmarks that remove different fractions 230 // of keys (e.g. 10%, 90%). 231 struct EraseIfPred { 232 uint64_t i = 0; 233 template <typename T> 234 bool operator()(const T&) { 235 return ++i % 2; 236 } 237 }; 238 239 // Benchmark erasing multiple values from a container with a predicate. 240 template <typename T> 241 void BM_EraseIf(benchmark::State& state) { 242 using V = typename remove_pair_const<typename T::value_type>::type; 243 std::vector<V> values = GenerateValues<V>(kBenchmarkValues); 244 245 // Removes half of the keys per batch. 246 const int batch_size = (kBenchmarkValues + 1) / 2; 247 EraseIfPred pred; 248 while (state.KeepRunningBatch(batch_size)) { 249 state.PauseTiming(); 250 { 251 T container(values.begin(), values.end()); 252 state.ResumeTiming(); 253 erase_if(container, pred); 254 benchmark::DoNotOptimize(container); 255 state.PauseTiming(); 256 } 257 state.ResumeTiming(); 258 } 259 } 260 261 // Benchmark steady-state insert (into first half of range) and remove (from 262 // second half of range), treating the container approximately like a queue with 263 // log-time access for all elements. This benchmark does not test the case where 264 // insertion and removal happen in the same region of the tree. This benchmark 265 // counts two value constructors. 266 template <typename T> 267 void BM_QueueAddRem(benchmark::State& state) { 268 using V = typename remove_pair_const<typename T::value_type>::type; 269 typename KeyOfValue<typename T::key_type, V>::type key_of_value; 270 271 ABSL_RAW_CHECK(kBenchmarkValues % 2 == 0, "for performance"); 272 273 T container; 274 275 const size_t half = kBenchmarkValues / 2; 276 std::vector<int> remove_keys(half); 277 std::vector<int> add_keys(half); 278 279 // We want to do the exact same work repeatedly, and the benchmark can end 280 // after a different number of iterations depending on the speed of the 281 // individual run so we use a large batch size here and ensure that we do 282 // deterministic work every batch. 283 while (state.KeepRunningBatch(half * kAddRemBatchSize)) { 284 state.PauseTiming(); 285 286 container.clear(); 287 288 for (size_t i = 0; i < half; ++i) { 289 remove_keys[i] = i; 290 add_keys[i] = i; 291 } 292 constexpr int kSeed = 5; 293 std::mt19937_64 rand(kSeed); 294 std::shuffle(remove_keys.begin(), remove_keys.end(), rand); 295 std::shuffle(add_keys.begin(), add_keys.end(), rand); 296 297 // Note needs lazy generation of values. 298 Generator<V> g(kBenchmarkValues * kAddRemBatchSize); 299 300 for (size_t i = 0; i < half; ++i) { 301 container.insert(g(add_keys[i])); 302 container.insert(g(half + remove_keys[i])); 303 } 304 305 // There are three parts each of size "half": 306 // 1 is being deleted from [offset - half, offset) 307 // 2 is standing [offset, offset + half) 308 // 3 is being inserted into [offset + half, offset + 2 * half) 309 size_t offset = 0; 310 311 for (size_t i = 0; i < kAddRemBatchSize; ++i) { 312 std::shuffle(remove_keys.begin(), remove_keys.end(), rand); 313 std::shuffle(add_keys.begin(), add_keys.end(), rand); 314 offset += half; 315 316 state.ResumeTiming(); 317 for (size_t idx = 0; idx < half; ++idx) { 318 container.erase(key_of_value(g(offset - half + remove_keys[idx]))); 319 container.insert(g(offset + half + add_keys[idx])); 320 } 321 state.PauseTiming(); 322 } 323 state.ResumeTiming(); 324 } 325 } 326 327 // Mixed insertion and deletion in the same range using pre-constructed values. 328 template <typename T> 329 void BM_MixedAddRem(benchmark::State& state) { 330 using V = typename remove_pair_const<typename T::value_type>::type; 331 typename KeyOfValue<typename T::key_type, V>::type key_of_value; 332 333 ABSL_RAW_CHECK(kBenchmarkValues % 2 == 0, "for performance"); 334 335 T container; 336 337 // Create two random shuffles 338 std::vector<int> remove_keys(kBenchmarkValues); 339 std::vector<int> add_keys(kBenchmarkValues); 340 341 // We want to do the exact same work repeatedly, and the benchmark can end 342 // after a different number of iterations depending on the speed of the 343 // individual run so we use a large batch size here and ensure that we do 344 // deterministic work every batch. 345 while (state.KeepRunningBatch(kBenchmarkValues * kAddRemBatchSize)) { 346 state.PauseTiming(); 347 348 container.clear(); 349 350 constexpr int kSeed = 7; 351 std::mt19937_64 rand(kSeed); 352 353 std::vector<V> values = GenerateValues<V>(kBenchmarkValues * 2); 354 355 // Insert the first half of the values (already in random order) 356 container.insert(values.begin(), values.begin() + kBenchmarkValues); 357 358 // Insert the first half of the values (already in random order) 359 for (size_t i = 0; i < kBenchmarkValues; ++i) { 360 // remove_keys and add_keys will be swapped before each round, 361 // therefore fill add_keys here w/ the keys being inserted, so 362 // they'll be the first to be removed. 363 remove_keys[i] = i + kBenchmarkValues; 364 add_keys[i] = i; 365 } 366 367 for (size_t i = 0; i < kAddRemBatchSize; ++i) { 368 remove_keys.swap(add_keys); 369 std::shuffle(remove_keys.begin(), remove_keys.end(), rand); 370 std::shuffle(add_keys.begin(), add_keys.end(), rand); 371 372 state.ResumeTiming(); 373 for (size_t idx = 0; idx < kBenchmarkValues; ++idx) { 374 container.erase(key_of_value(values[remove_keys[idx]])); 375 container.insert(values[add_keys[idx]]); 376 } 377 state.PauseTiming(); 378 } 379 state.ResumeTiming(); 380 } 381 } 382 383 // Insertion at end, removal from the beginning. This benchmark 384 // counts two value constructors. 385 // TODO(ezb): we could add a GenerateNext version of generator that could reduce 386 // noise for string-like types. 387 template <typename T> 388 void BM_Fifo(benchmark::State& state) { 389 using V = typename remove_pair_const<typename T::value_type>::type; 390 391 T container; 392 // Need lazy generation of values as state.max_iterations is large. 393 Generator<V> g(kBenchmarkValues + state.max_iterations); 394 395 for (int i = 0; i < kBenchmarkValues; i++) { 396 container.insert(g(i)); 397 } 398 399 while (state.KeepRunning()) { 400 container.erase(container.begin()); 401 container.insert(container.end(), g(state.iterations() + kBenchmarkValues)); 402 } 403 } 404 405 // Iteration (forward) through the tree 406 template <typename T> 407 void BM_FwdIter(benchmark::State& state) { 408 using V = typename remove_pair_const<typename T::value_type>::type; 409 410 std::vector<V> values = GenerateValues<V>(kBenchmarkValues); 411 T container(values.begin(), values.end()); 412 413 auto iter = container.end(); 414 415 while (state.KeepRunning()) { 416 if (iter == container.end()) iter = container.begin(); 417 auto *v = &(*iter); 418 benchmark::DoNotOptimize(v); 419 benchmark::DoNotOptimize(++iter); 420 } 421 } 422 423 // Benchmark random range-construction of a container. 424 template <typename T> 425 void BM_RangeConstructionImpl(benchmark::State& state, bool sorted) { 426 using V = typename remove_pair_const<typename T::value_type>::type; 427 428 std::vector<V> values = GenerateValues<V>(kBenchmarkValues); 429 if (sorted) { 430 std::sort(values.begin(), values.end()); 431 } 432 { 433 T container(values.begin(), values.end()); 434 } 435 436 while (state.KeepRunning()) { 437 T container(values.begin(), values.end()); 438 benchmark::DoNotOptimize(container); 439 } 440 } 441 442 template <typename T> 443 void BM_InsertRangeRandom(benchmark::State& state) { 444 BM_RangeConstructionImpl<T>(state, false); 445 } 446 447 template <typename T> 448 void BM_InsertRangeSorted(benchmark::State& state) { 449 BM_RangeConstructionImpl<T>(state, true); 450 } 451 452 #define STL_ORDERED_TYPES(value) \ 453 using stl_set_##value = std::set<value>; \ 454 using stl_map_##value = std::map<value, intptr_t>; \ 455 using stl_multiset_##value = std::multiset<value>; \ 456 using stl_multimap_##value = std::multimap<value, intptr_t> 457 458 using StdString = std::string; 459 STL_ORDERED_TYPES(int32_t); 460 STL_ORDERED_TYPES(int64_t); 461 STL_ORDERED_TYPES(StdString); 462 STL_ORDERED_TYPES(Cord); 463 STL_ORDERED_TYPES(Time); 464 465 #define STL_UNORDERED_TYPES(value) \ 466 using stl_unordered_set_##value = std::unordered_set<value>; \ 467 using stl_unordered_map_##value = std::unordered_map<value, intptr_t>; \ 468 using flat_hash_set_##value = flat_hash_set<value>; \ 469 using flat_hash_map_##value = flat_hash_map<value, intptr_t>; \ 470 using stl_unordered_multiset_##value = std::unordered_multiset<value>; \ 471 using stl_unordered_multimap_##value = \ 472 std::unordered_multimap<value, intptr_t> 473 474 #define STL_UNORDERED_TYPES_CUSTOM_HASH(value, hash) \ 475 using stl_unordered_set_##value = std::unordered_set<value, hash>; \ 476 using stl_unordered_map_##value = std::unordered_map<value, intptr_t, hash>; \ 477 using flat_hash_set_##value = flat_hash_set<value, hash>; \ 478 using flat_hash_map_##value = flat_hash_map<value, intptr_t, hash>; \ 479 using stl_unordered_multiset_##value = std::unordered_multiset<value, hash>; \ 480 using stl_unordered_multimap_##value = \ 481 std::unordered_multimap<value, intptr_t, hash> 482 483 STL_UNORDERED_TYPES_CUSTOM_HASH(Cord, absl::Hash<absl::Cord>); 484 485 STL_UNORDERED_TYPES(int32_t); 486 STL_UNORDERED_TYPES(int64_t); 487 STL_UNORDERED_TYPES(StdString); 488 STL_UNORDERED_TYPES_CUSTOM_HASH(Time, absl::Hash<absl::Time>); 489 490 #define BTREE_TYPES(value) \ 491 using btree_256_set_##value = \ 492 btree_set<value, std::less<value>, std::allocator<value>>; \ 493 using btree_256_map_##value = \ 494 btree_map<value, intptr_t, std::less<value>, \ 495 std::allocator<std::pair<const value, intptr_t>>>; \ 496 using btree_256_multiset_##value = \ 497 btree_multiset<value, std::less<value>, std::allocator<value>>; \ 498 using btree_256_multimap_##value = \ 499 btree_multimap<value, intptr_t, std::less<value>, \ 500 std::allocator<std::pair<const value, intptr_t>>> 501 502 BTREE_TYPES(int32_t); 503 BTREE_TYPES(int64_t); 504 BTREE_TYPES(StdString); 505 BTREE_TYPES(Cord); 506 BTREE_TYPES(Time); 507 508 #define MY_BENCHMARK4(type, func) \ 509 void BM_##type##_##func(benchmark::State& state) { BM_##func<type>(state); } \ 510 BENCHMARK(BM_##type##_##func) 511 512 #define MY_BENCHMARK3_STL(type) \ 513 MY_BENCHMARK4(type, Insert); \ 514 MY_BENCHMARK4(type, InsertSorted); \ 515 MY_BENCHMARK4(type, InsertSmall); \ 516 MY_BENCHMARK4(type, Lookup); \ 517 MY_BENCHMARK4(type, FullLookup); \ 518 MY_BENCHMARK4(type, Erase); \ 519 MY_BENCHMARK4(type, EraseRange); \ 520 MY_BENCHMARK4(type, QueueAddRem); \ 521 MY_BENCHMARK4(type, MixedAddRem); \ 522 MY_BENCHMARK4(type, Fifo); \ 523 MY_BENCHMARK4(type, FwdIter); \ 524 MY_BENCHMARK4(type, InsertRangeRandom); \ 525 MY_BENCHMARK4(type, InsertRangeSorted) 526 527 #define MY_BENCHMARK3(type) \ 528 MY_BENCHMARK4(type, EraseIf); \ 529 MY_BENCHMARK3_STL(type) 530 531 #define MY_BENCHMARK2_SUPPORTS_MULTI_ONLY(type) \ 532 MY_BENCHMARK3_STL(stl_##type); \ 533 MY_BENCHMARK3_STL(stl_unordered_##type); \ 534 MY_BENCHMARK3(btree_256_##type) 535 536 #define MY_BENCHMARK2(type) \ 537 MY_BENCHMARK2_SUPPORTS_MULTI_ONLY(type); \ 538 MY_BENCHMARK3(flat_hash_##type) 539 540 // Define MULTI_TESTING to see benchmarks for multi-containers also. 541 // 542 // You can use --copt=-DMULTI_TESTING. 543 #ifdef MULTI_TESTING 544 #define MY_BENCHMARK(type) \ 545 MY_BENCHMARK2(set_##type); \ 546 MY_BENCHMARK2(map_##type); \ 547 MY_BENCHMARK2_SUPPORTS_MULTI_ONLY(multiset_##type); \ 548 MY_BENCHMARK2_SUPPORTS_MULTI_ONLY(multimap_##type) 549 #else 550 #define MY_BENCHMARK(type) \ 551 MY_BENCHMARK2(set_##type); \ 552 MY_BENCHMARK2(map_##type) 553 #endif 554 555 MY_BENCHMARK(int32_t); 556 MY_BENCHMARK(int64_t); 557 MY_BENCHMARK(StdString); 558 MY_BENCHMARK(Cord); 559 MY_BENCHMARK(Time); 560 561 // Define a type whose size and cost of moving are independently customizable. 562 // When sizeof(value_type) increases, we expect btree to no longer have as much 563 // cache-locality advantage over STL. When cost of moving increases, we expect 564 // btree to actually do more work than STL because it has to move values around 565 // and STL doesn't have to. 566 template <int Size, int Copies> 567 struct BigType { 568 BigType() : BigType(0) {} 569 explicit BigType(int x) { std::iota(values.begin(), values.end(), x); } 570 571 void Copy(const BigType& other) { 572 for (int i = 0; i < Size && i < Copies; ++i) values[i] = other.values[i]; 573 // If Copies > Size, do extra copies. 574 for (int i = Size, idx = 0; i < Copies; ++i) { 575 int64_t tmp = other.values[idx]; 576 benchmark::DoNotOptimize(tmp); 577 idx = idx + 1 == Size ? 0 : idx + 1; 578 } 579 } 580 581 BigType(const BigType& other) { Copy(other); } 582 BigType& operator=(const BigType& other) { 583 Copy(other); 584 return *this; 585 } 586 587 // Compare only the first Copies elements if Copies is less than Size. 588 bool operator<(const BigType& other) const { 589 return std::lexicographical_compare( 590 values.begin(), values.begin() + std::min(Size, Copies), 591 other.values.begin(), other.values.begin() + std::min(Size, Copies)); 592 } 593 bool operator==(const BigType& other) const { 594 return std::equal(values.begin(), values.begin() + std::min(Size, Copies), 595 other.values.begin()); 596 } 597 598 // Support absl::Hash. 599 template <typename State> 600 friend State AbslHashValue(State h, const BigType& b) { 601 for (int i = 0; i < Size && i < Copies; ++i) 602 h = State::combine(std::move(h), b.values[i]); 603 return h; 604 } 605 606 std::array<int64_t, Size> values; 607 }; 608 609 #define BIG_TYPE_BENCHMARKS(SIZE, COPIES) \ 610 using stl_set_size##SIZE##copies##COPIES = std::set<BigType<SIZE, COPIES>>; \ 611 using stl_map_size##SIZE##copies##COPIES = \ 612 std::map<BigType<SIZE, COPIES>, intptr_t>; \ 613 using stl_multiset_size##SIZE##copies##COPIES = \ 614 std::multiset<BigType<SIZE, COPIES>>; \ 615 using stl_multimap_size##SIZE##copies##COPIES = \ 616 std::multimap<BigType<SIZE, COPIES>, intptr_t>; \ 617 using stl_unordered_set_size##SIZE##copies##COPIES = \ 618 std::unordered_set<BigType<SIZE, COPIES>, \ 619 absl::Hash<BigType<SIZE, COPIES>>>; \ 620 using stl_unordered_map_size##SIZE##copies##COPIES = \ 621 std::unordered_map<BigType<SIZE, COPIES>, intptr_t, \ 622 absl::Hash<BigType<SIZE, COPIES>>>; \ 623 using flat_hash_set_size##SIZE##copies##COPIES = \ 624 flat_hash_set<BigType<SIZE, COPIES>>; \ 625 using flat_hash_map_size##SIZE##copies##COPIES = \ 626 flat_hash_map<BigType<SIZE, COPIES>, intptr_t>; \ 627 using stl_unordered_multiset_size##SIZE##copies##COPIES = \ 628 std::unordered_multiset<BigType<SIZE, COPIES>, \ 629 absl::Hash<BigType<SIZE, COPIES>>>; \ 630 using stl_unordered_multimap_size##SIZE##copies##COPIES = \ 631 std::unordered_multimap<BigType<SIZE, COPIES>, intptr_t, \ 632 absl::Hash<BigType<SIZE, COPIES>>>; \ 633 using btree_256_set_size##SIZE##copies##COPIES = \ 634 btree_set<BigType<SIZE, COPIES>>; \ 635 using btree_256_map_size##SIZE##copies##COPIES = \ 636 btree_map<BigType<SIZE, COPIES>, intptr_t>; \ 637 using btree_256_multiset_size##SIZE##copies##COPIES = \ 638 btree_multiset<BigType<SIZE, COPIES>>; \ 639 using btree_256_multimap_size##SIZE##copies##COPIES = \ 640 btree_multimap<BigType<SIZE, COPIES>, intptr_t>; \ 641 MY_BENCHMARK(size##SIZE##copies##COPIES) 642 643 // Define BIG_TYPE_TESTING to see benchmarks for more big types. 644 // 645 // You can use --copt=-DBIG_TYPE_TESTING. 646 #ifndef NODESIZE_TESTING 647 #ifdef BIG_TYPE_TESTING 648 BIG_TYPE_BENCHMARKS(1, 4); 649 BIG_TYPE_BENCHMARKS(4, 1); 650 BIG_TYPE_BENCHMARKS(4, 4); 651 BIG_TYPE_BENCHMARKS(1, 8); 652 BIG_TYPE_BENCHMARKS(8, 1); 653 BIG_TYPE_BENCHMARKS(8, 8); 654 BIG_TYPE_BENCHMARKS(1, 16); 655 BIG_TYPE_BENCHMARKS(16, 1); 656 BIG_TYPE_BENCHMARKS(16, 16); 657 BIG_TYPE_BENCHMARKS(1, 32); 658 BIG_TYPE_BENCHMARKS(32, 1); 659 BIG_TYPE_BENCHMARKS(32, 32); 660 #else 661 BIG_TYPE_BENCHMARKS(32, 32); 662 #endif 663 #endif 664 665 // Benchmark using unique_ptrs to large value types. In order to be able to use 666 // the same benchmark code as the other types, use a type that holds a 667 // unique_ptr and has a copy constructor. 668 template <int Size> 669 struct BigTypePtr { 670 BigTypePtr() : BigTypePtr(0) {} 671 explicit BigTypePtr(int x) { 672 ptr = absl::make_unique<BigType<Size, Size>>(x); 673 } 674 BigTypePtr(const BigTypePtr& other) { 675 ptr = absl::make_unique<BigType<Size, Size>>(*other.ptr); 676 } 677 BigTypePtr(BigTypePtr&& other) noexcept = default; 678 BigTypePtr& operator=(const BigTypePtr& other) { 679 ptr = absl::make_unique<BigType<Size, Size>>(*other.ptr); 680 } 681 BigTypePtr& operator=(BigTypePtr&& other) noexcept = default; 682 683 bool operator<(const BigTypePtr& other) const { return *ptr < *other.ptr; } 684 bool operator==(const BigTypePtr& other) const { return *ptr == *other.ptr; } 685 686 std::unique_ptr<BigType<Size, Size>> ptr; 687 }; 688 689 template <int Size> 690 double ContainerInfo(const btree_set<BigTypePtr<Size>>& b) { 691 const double bytes_used = 692 b.bytes_used() + b.size() * sizeof(BigType<Size, Size>); 693 const double bytes_per_value = bytes_used / b.size(); 694 BtreeContainerInfoLog(b, bytes_used, bytes_per_value); 695 return bytes_per_value; 696 } 697 template <int Size> 698 double ContainerInfo(const btree_map<int, BigTypePtr<Size>>& b) { 699 const double bytes_used = 700 b.bytes_used() + b.size() * sizeof(BigType<Size, Size>); 701 const double bytes_per_value = bytes_used / b.size(); 702 BtreeContainerInfoLog(b, bytes_used, bytes_per_value); 703 return bytes_per_value; 704 } 705 706 #define BIG_TYPE_PTR_BENCHMARKS(SIZE) \ 707 using stl_set_size##SIZE##copies##SIZE##ptr = std::set<BigType<SIZE, SIZE>>; \ 708 using stl_map_size##SIZE##copies##SIZE##ptr = \ 709 std::map<int, BigType<SIZE, SIZE>>; \ 710 using stl_unordered_set_size##SIZE##copies##SIZE##ptr = \ 711 std::unordered_set<BigType<SIZE, SIZE>, \ 712 absl::Hash<BigType<SIZE, SIZE>>>; \ 713 using stl_unordered_map_size##SIZE##copies##SIZE##ptr = \ 714 std::unordered_map<int, BigType<SIZE, SIZE>>; \ 715 using flat_hash_set_size##SIZE##copies##SIZE##ptr = \ 716 flat_hash_set<BigType<SIZE, SIZE>>; \ 717 using flat_hash_map_size##SIZE##copies##SIZE##ptr = \ 718 flat_hash_map<int, BigTypePtr<SIZE>>; \ 719 using btree_256_set_size##SIZE##copies##SIZE##ptr = \ 720 btree_set<BigTypePtr<SIZE>>; \ 721 using btree_256_map_size##SIZE##copies##SIZE##ptr = \ 722 btree_map<int, BigTypePtr<SIZE>>; \ 723 MY_BENCHMARK3_STL(stl_set_size##SIZE##copies##SIZE##ptr); \ 724 MY_BENCHMARK3_STL(stl_unordered_set_size##SIZE##copies##SIZE##ptr); \ 725 MY_BENCHMARK3(flat_hash_set_size##SIZE##copies##SIZE##ptr); \ 726 MY_BENCHMARK3(btree_256_set_size##SIZE##copies##SIZE##ptr); \ 727 MY_BENCHMARK3_STL(stl_map_size##SIZE##copies##SIZE##ptr); \ 728 MY_BENCHMARK3_STL(stl_unordered_map_size##SIZE##copies##SIZE##ptr); \ 729 MY_BENCHMARK3(flat_hash_map_size##SIZE##copies##SIZE##ptr); \ 730 MY_BENCHMARK3(btree_256_map_size##SIZE##copies##SIZE##ptr) 731 732 BIG_TYPE_PTR_BENCHMARKS(32); 733 734 void BM_BtreeSet_IteratorDifference(benchmark::State& state) { 735 absl::InsecureBitGen bitgen; 736 std::vector<int> vec; 737 // Randomize the set's insertion order so the nodes aren't all full. 738 vec.reserve(state.range(0)); 739 for (int i = 0; i < state.range(0); ++i) vec.push_back(i); 740 absl::c_shuffle(vec, bitgen); 741 742 absl::btree_set<int> set; 743 for (int i : vec) set.insert(i); 744 745 size_t distance = absl::Uniform(bitgen, 0u, set.size()); 746 while (state.KeepRunningBatch(distance)) { 747 size_t end = absl::Uniform(bitgen, distance, set.size()); 748 size_t begin = end - distance; 749 benchmark::DoNotOptimize(set.find(static_cast<int>(end)) - 750 set.find(static_cast<int>(begin))); 751 distance = absl::Uniform(bitgen, 0u, set.size()); 752 } 753 } 754 755 BENCHMARK(BM_BtreeSet_IteratorDifference)->Range(1 << 10, 1 << 20); 756 757 void BM_BtreeSet_IteratorAddition(benchmark::State& state) { 758 absl::InsecureBitGen bitgen; 759 std::vector<int> vec; 760 // Randomize the set's insertion order so the nodes aren't all full. 761 vec.reserve(static_cast<size_t>(state.range(0))); 762 for (int i = 0; i < state.range(0); ++i) vec.push_back(i); 763 absl::c_shuffle(vec, bitgen); 764 765 absl::btree_set<int> set; 766 for (int i : vec) set.insert(i); 767 768 size_t distance = absl::Uniform(bitgen, 0u, set.size()); 769 while (state.KeepRunningBatch(distance)) { 770 // Let the increment go all the way to the `end` iterator. 771 const size_t begin = 772 absl::Uniform(absl::IntervalClosed, bitgen, 0u, set.size() - distance); 773 auto it = set.find(static_cast<int>(begin)); 774 benchmark::DoNotOptimize(it += static_cast<int>(distance)); 775 distance = absl::Uniform(bitgen, 0u, set.size()); 776 } 777 } 778 779 BENCHMARK(BM_BtreeSet_IteratorAddition)->Range(1 << 10, 1 << 20); 780 781 void BM_BtreeSet_IteratorSubtraction(benchmark::State& state) { 782 absl::InsecureBitGen bitgen; 783 std::vector<int> vec; 784 // Randomize the set's insertion order so the nodes aren't all full. 785 vec.reserve(static_cast<size_t>(state.range(0))); 786 for (int i = 0; i < state.range(0); ++i) vec.push_back(i); 787 absl::c_shuffle(vec, bitgen); 788 789 absl::btree_set<int> set; 790 for (int i : vec) set.insert(i); 791 792 size_t distance = absl::Uniform(bitgen, 0u, set.size()); 793 while (state.KeepRunningBatch(distance)) { 794 size_t end = absl::Uniform(bitgen, distance, set.size()); 795 auto it = set.find(static_cast<int>(end)); 796 benchmark::DoNotOptimize(it -= static_cast<int>(distance)); 797 distance = absl::Uniform(bitgen, 0u, set.size()); 798 } 799 } 800 801 BENCHMARK(BM_BtreeSet_IteratorSubtraction)->Range(1 << 10, 1 << 20); 802 803 } // namespace 804 } // namespace container_internal 805 ABSL_NAMESPACE_END 806 } // namespace absl