1//===----------------------------------------------------------------------===// 2// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6// 7//===----------------------------------------------------------------------===// 8 9#include <algorithm> 10#include <cstdint> 11#include <map> 12#include <random> 13#include <vector> 14 15#include "CartesianBenchmarks.h" 16#include "benchmark/benchmark.h" 17#include "test_macros.h" 18 19// When VALIDATE is defined the benchmark will run to validate the benchmarks. 20// The time taken by several operations depend on whether or not an element 21// exists. To avoid errors in the benchmark these operations have a validation 22// mode to test the benchmark. Since they are not meant to be benchmarked the 23// number of sizes tested is limited to 1. 24//#define VALIDATE 25 26namespace { 27 28enum class Mode { Hit, Miss }; 29 30struct AllModes : EnumValuesAsTuple<AllModes, Mode, 2> { 31 static constexpr const char* Names[] = {"ExistingElement", "NewElement"}; 32}; 33 34// The positions of the hints to pick: 35// - Begin picks the first item. The item cannot be put before this element. 36// - Thrid picks the third item. This is just an element with a valid entry 37// before and after it. 38// - Correct contains the correct hint. 39// - End contains a hint to the end of the map. 40enum class Hint { Begin, Third, Correct, End }; 41struct AllHints : EnumValuesAsTuple<AllHints, Hint, 4> { 42 static constexpr const char* Names[] = {"Begin", "Third", "Correct", "End"}; 43}; 44 45enum class Order { Sorted, Random }; 46struct AllOrders : EnumValuesAsTuple<AllOrders, Order, 2> { 47 static constexpr const char* Names[] = {"Sorted", "Random"}; 48}; 49 50struct TestSets { 51 std::vector<uint64_t> Keys; 52 std::vector<std::map<uint64_t, int64_t> > Maps; 53 std::vector< 54 std::vector<typename std::map<uint64_t, int64_t>::const_iterator> > 55 Hints; 56}; 57 58enum class Shuffle { None, Keys, Hints }; 59 60TestSets makeTestingSets(size_t MapSize, Mode mode, Shuffle shuffle, 61 size_t max_maps) { 62 /* 63 * The shuffle does not retain the random number generator to use the same 64 * set of random numbers for every iteration. 65 */ 66 TestSets R; 67 68 int MapCount = std::min(max_maps, 1000000 / MapSize); 69 70 for (uint64_t I = 0; I < MapSize; ++I) { 71 R.Keys.push_back(mode == Mode::Hit ? 2 * I + 2 : 2 * I + 1); 72 } 73 if (shuffle == Shuffle::Keys) 74 std::shuffle(R.Keys.begin(), R.Keys.end(), std::mt19937()); 75 76 for (int M = 0; M < MapCount; ++M) { 77 auto& map = R.Maps.emplace_back(); 78 auto& hints = R.Hints.emplace_back(); 79 for (uint64_t I = 0; I < MapSize; ++I) { 80 hints.push_back(map.insert(std::make_pair(2 * I + 2, 0)).first); 81 } 82 if (shuffle == Shuffle::Hints) 83 std::shuffle(hints.begin(), hints.end(), std::mt19937()); 84 } 85 86 return R; 87} 88 89struct Base { 90 size_t MapSize; 91 Base(size_t T) : MapSize(T) {} 92 93 std::string baseName() const { return "_MapSize=" + std::to_string(MapSize); } 94}; 95 96//*******************************************************************| 97// Member functions | 98//*******************************************************************| 99 100struct ConstructorDefault { 101 void run(benchmark::State& State) const { 102 for (auto _ : State) { 103 benchmark::DoNotOptimize(std::map<uint64_t, int64_t>()); 104 } 105 } 106 107 std::string name() const { return "BM_ConstructorDefault"; } 108}; 109 110struct ConstructorIterator : Base { 111 using Base::Base; 112 113 void run(benchmark::State& State) const { 114 auto Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1); 115 auto& Map = Data.Maps.front(); 116 while (State.KeepRunningBatch(MapSize)) { 117#ifndef VALIDATE 118 benchmark::DoNotOptimize( 119 std::map<uint64_t, int64_t>(Map.begin(), Map.end())); 120#else 121 std::map<uint64_t, int64_t> M{Map.begin(), Map.end()}; 122 if (M != Map) 123 State.SkipWithError("Map copy not identical"); 124#endif 125 } 126 } 127 128 std::string name() const { return "BM_ConstructorIterator" + baseName(); } 129}; 130 131struct ConstructorCopy : Base { 132 using Base::Base; 133 134 void run(benchmark::State& State) const { 135 auto Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1); 136 auto& Map = Data.Maps.front(); 137 while (State.KeepRunningBatch(MapSize)) { 138#ifndef VALIDATE 139 std::map<uint64_t, int64_t> M(Map); 140 benchmark::DoNotOptimize(M); 141#else 142 std::map<uint64_t, int64_t> M(Map); 143 if (M != Map) 144 State.SkipWithError("Map copy not identical"); 145#endif 146 } 147 } 148 149 std::string name() const { return "BM_ConstructorCopy" + baseName(); } 150}; 151 152struct ConstructorMove : Base { 153 using Base::Base; 154 155 void run(benchmark::State& State) const { 156 auto Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1000); 157 while (State.KeepRunningBatch(MapSize * Data.Maps.size())) { 158 for (auto& Map : Data.Maps) { 159 std::map<uint64_t, int64_t> M(std::move(Map)); 160 benchmark::DoNotOptimize(M); 161 } 162 State.PauseTiming(); 163 Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1000); 164 State.ResumeTiming(); 165 } 166 } 167 168 std::string name() const { return "BM_ConstructorMove" + baseName(); } 169}; 170 171//*******************************************************************| 172// Capacity | 173//*******************************************************************| 174 175struct Empty : Base { 176 using Base::Base; 177 178 void run(benchmark::State& State) const { 179 auto Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1); 180 auto& Map = Data.Maps.front(); 181 for (auto _ : State) { 182#ifndef VALIDATE 183 benchmark::DoNotOptimize(Map.empty()); 184#else 185 if (Map.empty()) 186 State.SkipWithError("Map contains an invalid number of elements."); 187#endif 188 } 189 } 190 191 std::string name() const { return "BM_Empty" + baseName(); } 192}; 193 194struct Size : Base { 195 using Base::Base; 196 197 void run(benchmark::State& State) const { 198 auto Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1); 199 auto& Map = Data.Maps.front(); 200 for (auto _ : State) { 201#ifndef VALIDATE 202 benchmark::DoNotOptimize(Map.size()); 203#else 204 if (Map.size() != MapSize) 205 State.SkipWithError("Map contains an invalid number of elements."); 206#endif 207 } 208 } 209 210 std::string name() const { return "BM_Size" + baseName(); } 211}; 212 213//*******************************************************************| 214// Modifiers | 215//*******************************************************************| 216 217struct Clear : Base { 218 using Base::Base; 219 220 void run(benchmark::State& State) const { 221 auto Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1000); 222 while (State.KeepRunningBatch(MapSize * Data.Maps.size())) { 223 for (auto& Map : Data.Maps) { 224 Map.clear(); 225 benchmark::DoNotOptimize(Map); 226 } 227 State.PauseTiming(); 228 Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1000); 229 State.ResumeTiming(); 230 } 231 } 232 233 std::string name() const { return "BM_Clear" + baseName(); } 234}; 235 236template <class Mode, class Order> 237struct Insert : Base { 238 using Base::Base; 239 240 void run(benchmark::State& State) const { 241 auto Data = makeTestingSets( 242 MapSize, Mode(), 243 Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1000); 244 while (State.KeepRunningBatch(MapSize * Data.Maps.size())) { 245 for (auto& Map : Data.Maps) { 246 for (auto K : Data.Keys) { 247#ifndef VALIDATE 248 benchmark::DoNotOptimize(Map.insert(std::make_pair(K, 1))); 249#else 250 bool Inserted = Map.insert(std::make_pair(K, 1)).second; 251 if (Mode() == ::Mode::Hit) { 252 if (Inserted) 253 State.SkipWithError("Inserted a duplicate element"); 254 } else { 255 if (!Inserted) 256 State.SkipWithError("Failed to insert e new element"); 257 } 258#endif 259 } 260 } 261 262 State.PauseTiming(); 263 Data = makeTestingSets(MapSize, Mode(), 264 Order::value == ::Order::Random ? Shuffle::Keys 265 : Shuffle::None, 266 1000); 267 State.ResumeTiming(); 268 } 269 } 270 271 std::string name() const { 272 return "BM_Insert" + baseName() + Mode::name() + Order::name(); 273 } 274}; 275 276template <class Mode, class Hint> 277struct InsertHint : Base { 278 using Base::Base; 279 280 template < ::Hint hint> 281 typename std::enable_if<hint == ::Hint::Correct>::type 282 run(benchmark::State& State) const { 283 auto Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000); 284 while (State.KeepRunningBatch(MapSize * Data.Maps.size())) { 285 for (size_t I = 0; I < Data.Maps.size(); ++I) { 286 auto& Map = Data.Maps[I]; 287 auto H = Data.Hints[I].begin(); 288 for (auto K : Data.Keys) { 289#ifndef VALIDATE 290 benchmark::DoNotOptimize(Map.insert(*H, std::make_pair(K, 1))); 291#else 292 auto Inserted = Map.insert(*H, std::make_pair(K, 1)); 293 if (Mode() == ::Mode::Hit) { 294 if (Inserted != *H) 295 State.SkipWithError("Inserted a duplicate element"); 296 } else { 297 if (++Inserted != *H) 298 State.SkipWithError("Failed to insert a new element"); 299 } 300#endif 301 ++H; 302 } 303 } 304 305 State.PauseTiming(); 306 Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000); 307 State.ResumeTiming(); 308 } 309 } 310 311 template < ::Hint hint> 312 typename std::enable_if<hint != ::Hint::Correct>::type 313 run(benchmark::State& State) const { 314 auto Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000); 315 while (State.KeepRunningBatch(MapSize * Data.Maps.size())) { 316 for (size_t I = 0; I < Data.Maps.size(); ++I) { 317 auto& Map = Data.Maps[I]; 318 auto Third = *(Data.Hints[I].begin() + 2); 319 for (auto K : Data.Keys) { 320 auto Itor = hint == ::Hint::Begin 321 ? Map.begin() 322 : hint == ::Hint::Third ? Third : Map.end(); 323#ifndef VALIDATE 324 benchmark::DoNotOptimize(Map.insert(Itor, std::make_pair(K, 1))); 325#else 326 size_t Size = Map.size(); 327 Map.insert(Itor, std::make_pair(K, 1)); 328 if (Mode() == ::Mode::Hit) { 329 if (Size != Map.size()) 330 State.SkipWithError("Inserted a duplicate element"); 331 } else { 332 if (Size + 1 != Map.size()) 333 State.SkipWithError("Failed to insert a new element"); 334 } 335#endif 336 } 337 } 338 339 State.PauseTiming(); 340 Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000); 341 State.ResumeTiming(); 342 } 343 } 344 345 void run(benchmark::State& State) const { 346 static constexpr auto h = Hint(); 347 run<h>(State); 348 } 349 350 std::string name() const { 351 return "BM_InsertHint" + baseName() + Mode::name() + Hint::name(); 352 } 353}; 354 355template <class Mode, class Order> 356struct InsertAssign : Base { 357 using Base::Base; 358 359 void run(benchmark::State& State) const { 360 auto Data = makeTestingSets( 361 MapSize, Mode(), 362 Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1000); 363 while (State.KeepRunningBatch(MapSize * Data.Maps.size())) { 364 for (auto& Map : Data.Maps) { 365 for (auto K : Data.Keys) { 366#ifndef VALIDATE 367 benchmark::DoNotOptimize(Map.insert_or_assign(K, 1)); 368#else 369 bool Inserted = Map.insert_or_assign(K, 1).second; 370 if (Mode() == ::Mode::Hit) { 371 if (Inserted) 372 State.SkipWithError("Inserted a duplicate element"); 373 } else { 374 if (!Inserted) 375 State.SkipWithError("Failed to insert e new element"); 376 } 377#endif 378 } 379 } 380 381 State.PauseTiming(); 382 Data = makeTestingSets(MapSize, Mode(), 383 Order::value == ::Order::Random ? Shuffle::Keys 384 : Shuffle::None, 385 1000); 386 State.ResumeTiming(); 387 } 388 } 389 390 std::string name() const { 391 return "BM_InsertAssign" + baseName() + Mode::name() + Order::name(); 392 } 393}; 394 395template <class Mode, class Hint> 396struct InsertAssignHint : Base { 397 using Base::Base; 398 399 template < ::Hint hint> 400 typename std::enable_if<hint == ::Hint::Correct>::type 401 run(benchmark::State& State) const { 402 auto Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000); 403 while (State.KeepRunningBatch(MapSize * Data.Maps.size())) { 404 for (size_t I = 0; I < Data.Maps.size(); ++I) { 405 auto& Map = Data.Maps[I]; 406 auto H = Data.Hints[I].begin(); 407 for (auto K : Data.Keys) { 408#ifndef VALIDATE 409 benchmark::DoNotOptimize(Map.insert_or_assign(*H, K, 1)); 410#else 411 auto Inserted = Map.insert_or_assign(*H, K, 1); 412 if (Mode() == ::Mode::Hit) { 413 if (Inserted != *H) 414 State.SkipWithError("Inserted a duplicate element"); 415 } else { 416 if (++Inserted != *H) 417 State.SkipWithError("Failed to insert a new element"); 418 } 419#endif 420 ++H; 421 } 422 } 423 424 State.PauseTiming(); 425 Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000); 426 State.ResumeTiming(); 427 } 428 } 429 430 template < ::Hint hint> 431 typename std::enable_if<hint != ::Hint::Correct>::type 432 run(benchmark::State& State) const { 433 auto Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000); 434 while (State.KeepRunningBatch(MapSize * Data.Maps.size())) { 435 for (size_t I = 0; I < Data.Maps.size(); ++I) { 436 auto& Map = Data.Maps[I]; 437 auto Third = *(Data.Hints[I].begin() + 2); 438 for (auto K : Data.Keys) { 439 auto Itor = hint == ::Hint::Begin 440 ? Map.begin() 441 : hint == ::Hint::Third ? Third : Map.end(); 442#ifndef VALIDATE 443 benchmark::DoNotOptimize(Map.insert_or_assign(Itor, K, 1)); 444#else 445 size_t Size = Map.size(); 446 Map.insert_or_assign(Itor, K, 1); 447 if (Mode() == ::Mode::Hit) { 448 if (Size != Map.size()) 449 State.SkipWithError("Inserted a duplicate element"); 450 } else { 451 if (Size + 1 != Map.size()) 452 State.SkipWithError("Failed to insert a new element"); 453 } 454#endif 455 } 456 } 457 458 State.PauseTiming(); 459 Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000); 460 State.ResumeTiming(); 461 } 462 } 463 464 void run(benchmark::State& State) const { 465 static constexpr auto h = Hint(); 466 run<h>(State); 467 } 468 469 std::string name() const { 470 return "BM_InsertAssignHint" + baseName() + Mode::name() + Hint::name(); 471 } 472}; 473 474template <class Mode, class Order> 475struct Emplace : Base { 476 using Base::Base; 477 478 void run(benchmark::State& State) const { 479 480 auto Data = makeTestingSets( 481 MapSize, Mode(), 482 Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1000); 483 while (State.KeepRunningBatch(MapSize * Data.Maps.size())) { 484 for (auto& Map : Data.Maps) { 485 for (auto K : Data.Keys) { 486#ifndef VALIDATE 487 benchmark::DoNotOptimize(Map.emplace(K, 1)); 488#else 489 bool Inserted = Map.emplace(K, 1).second; 490 if (Mode() == ::Mode::Hit) { 491 if (Inserted) 492 State.SkipWithError("Emplaced a duplicate element"); 493 } else { 494 if (!Inserted) 495 State.SkipWithError("Failed to emplace a new element"); 496 } 497#endif 498 } 499 } 500 501 State.PauseTiming(); 502 Data = makeTestingSets(MapSize, Mode(), 503 Order::value == ::Order::Random ? Shuffle::Keys 504 : Shuffle::None, 505 1000); 506 State.ResumeTiming(); 507 } 508 } 509 510 std::string name() const { 511 return "BM_Emplace" + baseName() + Mode::name() + Order::name(); 512 } 513}; 514 515template <class Mode, class Hint> 516struct EmplaceHint : Base { 517 using Base::Base; 518 519 template < ::Hint hint> 520 typename std::enable_if<hint == ::Hint::Correct>::type 521 run(benchmark::State& State) const { 522 auto Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000); 523 while (State.KeepRunningBatch(MapSize * Data.Maps.size())) { 524 for (size_t I = 0; I < Data.Maps.size(); ++I) { 525 auto& Map = Data.Maps[I]; 526 auto H = Data.Hints[I].begin(); 527 for (auto K : Data.Keys) { 528#ifndef VALIDATE 529 benchmark::DoNotOptimize(Map.emplace_hint(*H, K, 1)); 530#else 531 auto Inserted = Map.emplace_hint(*H, K, 1); 532 if (Mode() == ::Mode::Hit) { 533 if (Inserted != *H) 534 State.SkipWithError("Emplaced a duplicate element"); 535 } else { 536 if (++Inserted != *H) 537 State.SkipWithError("Failed to emplace a new element"); 538 } 539#endif 540 ++H; 541 } 542 } 543 544 State.PauseTiming(); 545 Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000); 546 State.ResumeTiming(); 547 } 548 } 549 550 template < ::Hint hint> 551 typename std::enable_if<hint != ::Hint::Correct>::type 552 run(benchmark::State& State) const { 553 auto Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000); 554 while (State.KeepRunningBatch(MapSize * Data.Maps.size())) { 555 for (size_t I = 0; I < Data.Maps.size(); ++I) { 556 auto& Map = Data.Maps[I]; 557 auto Third = *(Data.Hints[I].begin() + 2); 558 for (auto K : Data.Keys) { 559 auto Itor = hint == ::Hint::Begin 560 ? Map.begin() 561 : hint == ::Hint::Third ? Third : Map.end(); 562#ifndef VALIDATE 563 benchmark::DoNotOptimize(Map.emplace_hint(Itor, K, 1)); 564#else 565 size_t Size = Map.size(); 566 Map.emplace_hint(Itor, K, 1); 567 if (Mode() == ::Mode::Hit) { 568 if (Size != Map.size()) 569 State.SkipWithError("Emplaced a duplicate element"); 570 } else { 571 if (Size + 1 != Map.size()) 572 State.SkipWithError("Failed to emplace a new element"); 573 } 574#endif 575 } 576 } 577 578 State.PauseTiming(); 579 Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000); 580 State.ResumeTiming(); 581 } 582 } 583 584 void run(benchmark::State& State) const { 585 static constexpr auto h = Hint(); 586 run<h>(State); 587 } 588 589 std::string name() const { 590 return "BM_EmplaceHint" + baseName() + Mode::name() + Hint::name(); 591 } 592}; 593 594template <class Mode, class Order> 595struct TryEmplace : Base { 596 using Base::Base; 597 598 void run(benchmark::State& State) const { 599 600 auto Data = makeTestingSets( 601 MapSize, Mode(), 602 Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1000); 603 while (State.KeepRunningBatch(MapSize * Data.Maps.size())) { 604 for (auto& Map : Data.Maps) { 605 for (auto K : Data.Keys) { 606#ifndef VALIDATE 607 benchmark::DoNotOptimize(Map.try_emplace(K, 1)); 608#else 609 bool Inserted = Map.try_emplace(K, 1).second; 610 if (Mode() == ::Mode::Hit) { 611 if (Inserted) 612 State.SkipWithError("Emplaced a duplicate element"); 613 } else { 614 if (!Inserted) 615 State.SkipWithError("Failed to emplace a new element"); 616 } 617#endif 618 } 619 } 620 621 State.PauseTiming(); 622 Data = makeTestingSets(MapSize, Mode(), 623 Order::value == ::Order::Random ? Shuffle::Keys 624 : Shuffle::None, 625 1000); 626 State.ResumeTiming(); 627 } 628 } 629 630 std::string name() const { 631 return "BM_TryEmplace" + baseName() + Mode::name() + Order::name(); 632 } 633}; 634 635template <class Mode, class Hint> 636struct TryEmplaceHint : Base { 637 using Base::Base; 638 639 template < ::Hint hint> 640 typename std::enable_if<hint == ::Hint::Correct>::type 641 run(benchmark::State& State) const { 642 auto Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000); 643 while (State.KeepRunningBatch(MapSize * Data.Maps.size())) { 644 for (size_t I = 0; I < Data.Maps.size(); ++I) { 645 auto& Map = Data.Maps[I]; 646 auto H = Data.Hints[I].begin(); 647 for (auto K : Data.Keys) { 648#ifndef VALIDATE 649 benchmark::DoNotOptimize(Map.try_emplace(*H, K, 1)); 650#else 651 auto Inserted = Map.try_emplace(*H, K, 1); 652 if (Mode() == ::Mode::Hit) { 653 if (Inserted != *H) 654 State.SkipWithError("Emplaced a duplicate element"); 655 } else { 656 if (++Inserted != *H) 657 State.SkipWithError("Failed to emplace a new element"); 658 } 659#endif 660 ++H; 661 } 662 } 663 664 State.PauseTiming(); 665 Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000); 666 State.ResumeTiming(); 667 } 668 } 669 670 template < ::Hint hint> 671 typename std::enable_if<hint != ::Hint::Correct>::type 672 run(benchmark::State& State) const { 673 auto Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000); 674 while (State.KeepRunningBatch(MapSize * Data.Maps.size())) { 675 for (size_t I = 0; I < Data.Maps.size(); ++I) { 676 auto& Map = Data.Maps[I]; 677 auto Third = *(Data.Hints[I].begin() + 2); 678 for (auto K : Data.Keys) { 679 auto Itor = hint == ::Hint::Begin 680 ? Map.begin() 681 : hint == ::Hint::Third ? Third : Map.end(); 682#ifndef VALIDATE 683 benchmark::DoNotOptimize(Map.try_emplace(Itor, K, 1)); 684#else 685 size_t Size = Map.size(); 686 Map.try_emplace(Itor, K, 1); 687 if (Mode() == ::Mode::Hit) { 688 if (Size != Map.size()) 689 State.SkipWithError("Emplaced a duplicate element"); 690 } else { 691 if (Size + 1 != Map.size()) 692 State.SkipWithError("Failed to emplace a new element"); 693 } 694#endif 695 } 696 } 697 698 State.PauseTiming(); 699 Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000); 700 State.ResumeTiming(); 701 } 702 } 703 704 void run(benchmark::State& State) const { 705 static constexpr auto h = Hint(); 706 run<h>(State); 707 } 708 709 std::string name() const { 710 return "BM_TryEmplaceHint" + baseName() + Mode::name() + Hint::name(); 711 } 712}; 713 714template <class Mode, class Order> 715struct Erase : Base { 716 using Base::Base; 717 718 void run(benchmark::State& State) const { 719 auto Data = makeTestingSets( 720 MapSize, Mode(), 721 Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1000); 722 while (State.KeepRunningBatch(MapSize * Data.Maps.size())) { 723 for (auto& Map : Data.Maps) { 724 for (auto K : Data.Keys) { 725#ifndef VALIDATE 726 benchmark::DoNotOptimize(Map.erase(K)); 727#else 728 size_t I = Map.erase(K); 729 if (Mode() == ::Mode::Hit) { 730 if (I == 0) 731 State.SkipWithError("Did not find the existing element"); 732 } else { 733 if (I == 1) 734 State.SkipWithError("Did find the non-existing element"); 735 } 736#endif 737 } 738 } 739 740 State.PauseTiming(); 741 Data = makeTestingSets(MapSize, Mode(), 742 Order::value == ::Order::Random ? Shuffle::Keys 743 : Shuffle::None, 744 1000); 745 State.ResumeTiming(); 746 } 747 } 748 749 std::string name() const { 750 return "BM_Erase" + baseName() + Mode::name() + Order::name(); 751 } 752}; 753 754template <class Order> 755struct EraseIterator : Base { 756 using Base::Base; 757 758 void run(benchmark::State& State) const { 759 auto Data = makeTestingSets( 760 MapSize, Mode::Hit, 761 Order::value == ::Order::Random ? Shuffle::Hints : Shuffle::None, 1000); 762 while (State.KeepRunningBatch(MapSize * Data.Maps.size())) { 763 for (size_t I = 0; I < Data.Maps.size(); ++I) { 764 auto& Map = Data.Maps[I]; 765 for (auto H : Data.Hints[I]) { 766 benchmark::DoNotOptimize(Map.erase(H)); 767 } 768#ifdef VALIDATE 769 if (!Map.empty()) 770 State.SkipWithError("Did not erase the entire map"); 771#endif 772 } 773 774 State.PauseTiming(); 775 Data = makeTestingSets(MapSize, Mode::Hit, 776 Order::value == ::Order::Random ? Shuffle::Hints 777 : Shuffle::None, 778 1000); 779 State.ResumeTiming(); 780 } 781 } 782 783 std::string name() const { 784 return "BM_EraseIterator" + baseName() + Order::name(); 785 } 786}; 787 788struct EraseRange : Base { 789 using Base::Base; 790 791 void run(benchmark::State& State) const { 792 auto Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1000); 793 while (State.KeepRunningBatch(MapSize * Data.Maps.size())) { 794 for (auto& Map : Data.Maps) { 795#ifndef VALIDATE 796 benchmark::DoNotOptimize(Map.erase(Map.begin(), Map.end())); 797#else 798 Map.erase(Map.begin(), Map.end()); 799 if (!Map.empty()) 800 State.SkipWithError("Did not erase the entire map"); 801#endif 802 } 803 804 State.PauseTiming(); 805 Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1000); 806 State.ResumeTiming(); 807 } 808 } 809 810 std::string name() const { return "BM_EraseRange" + baseName(); } 811}; 812 813//*******************************************************************| 814// Lookup | 815//*******************************************************************| 816 817template <class Mode, class Order> 818struct Count : Base { 819 using Base::Base; 820 821 void run(benchmark::State& State) const { 822 auto Data = makeTestingSets( 823 MapSize, Mode(), 824 Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1); 825 auto& Map = Data.Maps.front(); 826 while (State.KeepRunningBatch(MapSize)) { 827 for (auto K : Data.Keys) { 828#ifndef VALIDATE 829 benchmark::DoNotOptimize(Map.count(K)); 830#else 831 size_t I = Map.count(K); 832 if (Mode() == ::Mode::Hit) { 833 if (I == 0) 834 State.SkipWithError("Did not find the existing element"); 835 } else { 836 if (I == 1) 837 State.SkipWithError("Did find the non-existing element"); 838 } 839#endif 840 } 841 } 842 } 843 844 std::string name() const { 845 return "BM_Count" + baseName() + Mode::name() + Order::name(); 846 } 847}; 848 849template <class Mode, class Order> 850struct Find : Base { 851 using Base::Base; 852 853 void run(benchmark::State& State) const { 854 auto Data = makeTestingSets( 855 MapSize, Mode(), 856 Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1); 857 auto& Map = Data.Maps.front(); 858 while (State.KeepRunningBatch(MapSize)) { 859 for (auto K : Data.Keys) { 860#ifndef VALIDATE 861 benchmark::DoNotOptimize(Map.find(K)); 862#else 863 auto Itor = Map.find(K); 864 if (Mode() == ::Mode::Hit) { 865 if (Itor == Map.end()) 866 State.SkipWithError("Did not find the existing element"); 867 } else { 868 if (Itor != Map.end()) 869 State.SkipWithError("Did find the non-existing element"); 870 } 871#endif 872 } 873 } 874 } 875 876 std::string name() const { 877 return "BM_Find" + baseName() + Mode::name() + Order::name(); 878 } 879}; 880 881template <class Mode, class Order> 882struct EqualRange : Base { 883 using Base::Base; 884 885 void run(benchmark::State& State) const { 886 auto Data = makeTestingSets( 887 MapSize, Mode(), 888 Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1); 889 auto& Map = Data.Maps.front(); 890 while (State.KeepRunningBatch(MapSize)) { 891 for (auto K : Data.Keys) { 892#ifndef VALIDATE 893 benchmark::DoNotOptimize(Map.equal_range(K)); 894#else 895 auto Range = Map.equal_range(K); 896 if (Mode() == ::Mode::Hit) { 897 // Adjust validation for the last element. 898 auto Key = K; 899 if (Range.second == Map.end() && K == 2 * MapSize) { 900 --Range.second; 901 Key -= 2; 902 } 903 if (Range.first == Map.end() || Range.first->first != K || 904 Range.second == Map.end() || Range.second->first - 2 != Key) 905 State.SkipWithError("Did not find the existing element"); 906 } else { 907 if (Range.first == Map.end() || Range.first->first - 1 != K || 908 Range.second == Map.end() || Range.second->first - 1 != K) 909 State.SkipWithError("Did find the non-existing element"); 910 } 911#endif 912 } 913 } 914 } 915 916 std::string name() const { 917 return "BM_EqualRange" + baseName() + Mode::name() + Order::name(); 918 } 919}; 920 921template <class Mode, class Order> 922struct LowerBound : Base { 923 using Base::Base; 924 925 void run(benchmark::State& State) const { 926 auto Data = makeTestingSets( 927 MapSize, Mode(), 928 Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1); 929 auto& Map = Data.Maps.front(); 930 while (State.KeepRunningBatch(MapSize)) { 931 for (auto K : Data.Keys) { 932#ifndef VALIDATE 933 benchmark::DoNotOptimize(Map.lower_bound(K)); 934#else 935 auto Itor = Map.lower_bound(K); 936 if (Mode() == ::Mode::Hit) { 937 if (Itor == Map.end() || Itor->first != K) 938 State.SkipWithError("Did not find the existing element"); 939 } else { 940 if (Itor == Map.end() || Itor->first - 1 != K) 941 State.SkipWithError("Did find the non-existing element"); 942 } 943#endif 944 } 945 } 946 } 947 948 std::string name() const { 949 return "BM_LowerBound" + baseName() + Mode::name() + Order::name(); 950 } 951}; 952 953template <class Mode, class Order> 954struct UpperBound : Base { 955 using Base::Base; 956 957 void run(benchmark::State& State) const { 958 auto Data = makeTestingSets( 959 MapSize, Mode(), 960 Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1); 961 auto& Map = Data.Maps.front(); 962 while (State.KeepRunningBatch(MapSize)) { 963 for (auto K : Data.Keys) { 964#ifndef VALIDATE 965 benchmark::DoNotOptimize(Map.upper_bound(K)); 966#else 967 std::map<uint64_t, int64_t>::iterator Itor = Map.upper_bound(K); 968 if (Mode() == ::Mode::Hit) { 969 // Adjust validation for the last element. 970 auto Key = K; 971 if (Itor == Map.end() && K == 2 * MapSize) { 972 --Itor; 973 Key -= 2; 974 } 975 if (Itor == Map.end() || Itor->first - 2 != Key) 976 State.SkipWithError("Did not find the existing element"); 977 } else { 978 if (Itor == Map.end() || Itor->first - 1 != K) 979 State.SkipWithError("Did find the non-existing element"); 980 } 981#endif 982 } 983 } 984 } 985 986 std::string name() const { 987 return "BM_UpperBound" + baseName() + Mode::name() + Order::name(); 988 } 989}; 990 991} // namespace 992 993int main(int argc, char** argv) { 994 benchmark::Initialize(&argc, argv); 995 if (benchmark::ReportUnrecognizedArguments(argc, argv)) 996 return 1; 997 998#ifdef VALIDATE 999 const std::vector<size_t> MapSize{10}; 1000#else 1001 const std::vector<size_t> MapSize{10, 100, 1000, 10000, 100000, 1000000}; 1002#endif 1003 1004 // Member functions 1005 makeCartesianProductBenchmark<ConstructorDefault>(); 1006 makeCartesianProductBenchmark<ConstructorIterator>(MapSize); 1007 makeCartesianProductBenchmark<ConstructorCopy>(MapSize); 1008 makeCartesianProductBenchmark<ConstructorMove>(MapSize); 1009 1010 // Capacity 1011 makeCartesianProductBenchmark<Empty>(MapSize); 1012 makeCartesianProductBenchmark<Size>(MapSize); 1013 1014 // Modifiers 1015 makeCartesianProductBenchmark<Clear>(MapSize); 1016 makeCartesianProductBenchmark<Insert, AllModes, AllOrders>(MapSize); 1017 makeCartesianProductBenchmark<InsertHint, AllModes, AllHints>(MapSize); 1018 makeCartesianProductBenchmark<InsertAssign, AllModes, AllOrders>(MapSize); 1019 makeCartesianProductBenchmark<InsertAssignHint, AllModes, AllHints>(MapSize); 1020 1021 makeCartesianProductBenchmark<Emplace, AllModes, AllOrders>(MapSize); 1022 makeCartesianProductBenchmark<EmplaceHint, AllModes, AllHints>(MapSize); 1023 makeCartesianProductBenchmark<TryEmplace, AllModes, AllOrders>(MapSize); 1024 makeCartesianProductBenchmark<TryEmplaceHint, AllModes, AllHints>(MapSize); 1025 makeCartesianProductBenchmark<Erase, AllModes, AllOrders>(MapSize); 1026 makeCartesianProductBenchmark<EraseIterator, AllOrders>(MapSize); 1027 makeCartesianProductBenchmark<EraseRange>(MapSize); 1028 1029 // Lookup 1030 makeCartesianProductBenchmark<Count, AllModes, AllOrders>(MapSize); 1031 makeCartesianProductBenchmark<Find, AllModes, AllOrders>(MapSize); 1032 makeCartesianProductBenchmark<EqualRange, AllModes, AllOrders>(MapSize); 1033 makeCartesianProductBenchmark<LowerBound, AllModes, AllOrders>(MapSize); 1034 makeCartesianProductBenchmark<UpperBound, AllModes, AllOrders>(MapSize); 1035 1036 benchmark::RunSpecifiedBenchmarks(); 1037} 1038