Index: libcxx/benchmarks/map.bench.cpp =================================================================== --- /dev/null +++ libcxx/benchmarks/map.bench.cpp @@ -0,0 +1,1037 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include +#include +#include +#include +#include + +#include "CartesianBenchmarks.h" +#include "benchmark/benchmark.h" +#include "test_macros.h" + +// When VALIDATE is defined the benchmark will run to validate the benchmarks. +// The time taken by several operations depend on whether or not an element +// exists. To avoid errors in the benchmark these operations have a validation +// mode to test the benchmark. Since they are not meant to be benchmarked the +// number of sizes tested is limited to 1. +//#define VALIDATE + +namespace { + +enum class Mode { Hit, Miss }; + +struct AllModes : EnumValuesAsTuple { + static constexpr const char* Names[] = {"ExistingElement", "NewElement"}; +}; + +// The positions of the hints to pick: +// - Begin picks the first item. The item cannot be put before this element. +// - Thrid picks the third item. This is just an element with a valid entry +// before and after it. +// - Correct contains the correct hint. +// - End contains a hint to the end of the map. +enum class Hint { Begin, Third, Correct, End }; +struct AllHints : EnumValuesAsTuple { + static constexpr const char* Names[] = {"Begin", "Third", "Correct", "End"}; +}; + +enum class Order { Sorted, Random }; +struct AllOrders : EnumValuesAsTuple { + static constexpr const char* Names[] = {"Sorted", "Random"}; +}; + +struct TestSets { + std::vector Keys; + std::vector > Maps; + std::vector< + std::vector::const_iterator> > + Hints; +}; + +enum class Shuffle { None, Keys, Hints }; + +TestSets makeTestingSets(size_t MapSize, Mode mode, Shuffle shuffle, + size_t max_maps) { + /* + * The shuffle does not retain the random number generator to use the same + * set of random numbers for every iteration. + */ + TestSets R; + + int MapCount = std::min(max_maps, 1000000 / MapSize); + + for (uint64_t I = 0; I < MapSize; ++I) { + R.Keys.push_back(mode == Mode::Hit ? 2 * I + 2 : 2 * I + 1); + } + if (shuffle == Shuffle::Keys) + std::shuffle(R.Keys.begin(), R.Keys.end(), std::mt19937()); + + for (int M = 0; M < MapCount; ++M) { + auto& map = R.Maps.emplace_back(); + auto& hints = R.Hints.emplace_back(); + for (uint64_t I = 0; I < MapSize; ++I) { + hints.push_back(map.insert(std::make_pair(2 * I + 2, 0)).first); + } + if (shuffle == Shuffle::Hints) + std::shuffle(hints.begin(), hints.end(), std::mt19937()); + } + + return R; +} + +struct Base { + size_t MapSize; + Base(size_t T) : MapSize(T) {} + + std::string baseName() const { return "_MapSize=" + std::to_string(MapSize); } +}; + +//*******************************************************************| +// Member functions | +//*******************************************************************| + +struct ConstructorDefault { + void run(benchmark::State& State) const { + for (auto _ : State) { + benchmark::DoNotOptimize(std::map()); + } + } + + std::string name() const { return "BM_ConstructorDefault"; } +}; + +struct ConstructorIterator : Base { + using Base::Base; + + void run(benchmark::State& State) const { + auto Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1); + auto& Map = Data.Maps.front(); + while (State.KeepRunningBatch(MapSize)) { +#ifndef VALIDATE + benchmark::DoNotOptimize( + std::map(Map.begin(), Map.end())); +#else + std::map M{Map.begin(), Map.end()}; + if (M != Map) + State.SkipWithError("Map copy not identical"); +#endif + } + } + + std::string name() const { return "BM_ConstructorIterator" + baseName(); } +}; + +struct ConstructorCopy : Base { + using Base::Base; + + void run(benchmark::State& State) const { + auto Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1); + auto& Map = Data.Maps.front(); + while (State.KeepRunningBatch(MapSize)) { +#ifndef VALIDATE + std::map M(Map); + benchmark::DoNotOptimize(M); +#else + std::map M(Map); + if (M != Map) + State.SkipWithError("Map copy not identical"); +#endif + } + } + + std::string name() const { return "BM_ConstructorCopy" + baseName(); } +}; + +struct ConstructorMove : Base { + using Base::Base; + + void run(benchmark::State& State) const { + auto Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1000); + while (State.KeepRunningBatch(MapSize * Data.Maps.size())) { + for (auto& Map : Data.Maps) { + std::map M(std::move(Map)); + benchmark::DoNotOptimize(M); + } + State.PauseTiming(); + Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1000); + State.ResumeTiming(); + } + } + + std::string name() const { return "BM_ConstructorMove" + baseName(); } +}; + +//*******************************************************************| +// Capacity | +//*******************************************************************| + +struct Empty : Base { + using Base::Base; + + void run(benchmark::State& State) const { + auto Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1); + auto& Map = Data.Maps.front(); + for (auto _ : State) { +#ifndef VALIDATE + benchmark::DoNotOptimize(Map.empty()); +#else + if (Map.empty()) + State.SkipWithError("Map contains an invalid number of elements."); +#endif + } + } + + std::string name() const { return "BM_Empty" + baseName(); } +}; + +struct Size : Base { + using Base::Base; + + void run(benchmark::State& State) const { + auto Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1); + auto& Map = Data.Maps.front(); + for (auto _ : State) { +#ifndef VALIDATE + benchmark::DoNotOptimize(Map.size()); +#else + if (Map.size() != MapSize) + State.SkipWithError("Map contains an invalid number of elements."); +#endif + } + } + + std::string name() const { return "BM_Size" + baseName(); } +}; + +//*******************************************************************| +// Modifiers | +//*******************************************************************| + +struct Clear : Base { + using Base::Base; + + void run(benchmark::State& State) const { + auto Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1000); + while (State.KeepRunningBatch(MapSize * Data.Maps.size())) { + for (auto& Map : Data.Maps) { + Map.clear(); + benchmark::DoNotOptimize(Map); + } + State.PauseTiming(); + Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1000); + State.ResumeTiming(); + } + } + + std::string name() const { return "BM_Clear" + baseName(); } +}; + +template +struct Insert : Base { + using Base::Base; + + void run(benchmark::State& State) const { + auto Data = makeTestingSets( + MapSize, Mode(), + Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1000); + while (State.KeepRunningBatch(MapSize * Data.Maps.size())) { + for (auto& Map : Data.Maps) { + for (auto K : Data.Keys) { +#ifndef VALIDATE + benchmark::DoNotOptimize(Map.insert(std::make_pair(K, 1))); +#else + bool Inserted = Map.insert(std::make_pair(K, 1)).second; + if (Mode() == ::Mode::Hit) { + if (Inserted) + State.SkipWithError("Inserted a duplicate element"); + } else { + if (!Inserted) + State.SkipWithError("Failed to insert e new element"); + } +#endif + } + } + + State.PauseTiming(); + Data = makeTestingSets(MapSize, Mode(), + Order::value == ::Order::Random ? Shuffle::Keys + : Shuffle::None, + 1000); + State.ResumeTiming(); + } + } + + std::string name() const { + return "BM_Insert" + baseName() + Mode::name() + Order::name(); + } +}; + +template +struct InsertHint : Base { + using Base::Base; + + template < ::Hint hint> + typename std::enable_if::type + run(benchmark::State& State) const { + auto Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000); + while (State.KeepRunningBatch(MapSize * Data.Maps.size())) { + for (size_t I = 0; I < Data.Maps.size(); ++I) { + auto& Map = Data.Maps[I]; + auto H = Data.Hints[I].begin(); + for (auto K : Data.Keys) { +#ifndef VALIDATE + benchmark::DoNotOptimize(Map.insert(*H, std::make_pair(K, 1))); +#else + auto Inserted = Map.insert(*H, std::make_pair(K, 1)); + if (Mode() == ::Mode::Hit) { + if (Inserted != *H) + State.SkipWithError("Inserted a duplicate element"); + } else { + if (++Inserted != *H) + State.SkipWithError("Failed to insert a new element"); + } +#endif + ++H; + } + } + + State.PauseTiming(); + Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000); + State.ResumeTiming(); + } + } + + template < ::Hint hint> + typename std::enable_if::type + run(benchmark::State& State) const { + auto Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000); + while (State.KeepRunningBatch(MapSize * Data.Maps.size())) { + for (size_t I = 0; I < Data.Maps.size(); ++I) { + auto& Map = Data.Maps[I]; + auto Third = *(Data.Hints[I].begin() + 2); + for (auto K : Data.Keys) { + auto Itor = hint == ::Hint::Begin + ? Map.begin() + : hint == ::Hint::Third ? Third : Map.end(); +#ifndef VALIDATE + benchmark::DoNotOptimize(Map.insert(Itor, std::make_pair(K, 1))); +#else + size_t Size = Map.size(); + Map.insert(Itor, std::make_pair(K, 1)); + if (Mode() == ::Mode::Hit) { + if (Size != Map.size()) + State.SkipWithError("Inserted a duplicate element"); + } else { + if (Size + 1 != Map.size()) + State.SkipWithError("Failed to insert a new element"); + } +#endif + } + } + + State.PauseTiming(); + Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000); + State.ResumeTiming(); + } + } + + void run(benchmark::State& State) const { + static constexpr auto h = Hint(); + run(State); + } + + std::string name() const { + return "BM_InsertHint" + baseName() + Mode::name() + Hint::name(); + } +}; + +template +struct InsertAssign : Base { + using Base::Base; + + void run(benchmark::State& State) const { + auto Data = makeTestingSets( + MapSize, Mode(), + Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1000); + while (State.KeepRunningBatch(MapSize * Data.Maps.size())) { + for (auto& Map : Data.Maps) { + for (auto K : Data.Keys) { +#ifndef VALIDATE + benchmark::DoNotOptimize(Map.insert_or_assign(K, 1)); +#else + bool Inserted = Map.insert_or_assign(K, 1).second; + if (Mode() == ::Mode::Hit) { + if (Inserted) + State.SkipWithError("Inserted a duplicate element"); + } else { + if (!Inserted) + State.SkipWithError("Failed to insert e new element"); + } +#endif + } + } + + State.PauseTiming(); + Data = makeTestingSets(MapSize, Mode(), + Order::value == ::Order::Random ? Shuffle::Keys + : Shuffle::None, + 1000); + State.ResumeTiming(); + } + } + + std::string name() const { + return "BM_InsertAssign" + baseName() + Mode::name() + Order::name(); + } +}; + +template +struct InsertAssignHint : Base { + using Base::Base; + + template < ::Hint hint> + typename std::enable_if::type + run(benchmark::State& State) const { + auto Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000); + while (State.KeepRunningBatch(MapSize * Data.Maps.size())) { + for (size_t I = 0; I < Data.Maps.size(); ++I) { + auto& Map = Data.Maps[I]; + auto H = Data.Hints[I].begin(); + for (auto K : Data.Keys) { +#ifndef VALIDATE + benchmark::DoNotOptimize(Map.insert_or_assign(*H, K, 1)); +#else + auto Inserted = Map.insert_or_assign(*H, K, 1); + if (Mode() == ::Mode::Hit) { + if (Inserted != *H) + State.SkipWithError("Inserted a duplicate element"); + } else { + if (++Inserted != *H) + State.SkipWithError("Failed to insert a new element"); + } +#endif + ++H; + } + } + + State.PauseTiming(); + Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000); + State.ResumeTiming(); + } + } + + template < ::Hint hint> + typename std::enable_if::type + run(benchmark::State& State) const { + auto Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000); + while (State.KeepRunningBatch(MapSize * Data.Maps.size())) { + for (size_t I = 0; I < Data.Maps.size(); ++I) { + auto& Map = Data.Maps[I]; + auto Third = *(Data.Hints[I].begin() + 2); + for (auto K : Data.Keys) { + auto Itor = hint == ::Hint::Begin + ? Map.begin() + : hint == ::Hint::Third ? Third : Map.end(); +#ifndef VALIDATE + benchmark::DoNotOptimize(Map.insert_or_assign(Itor, K, 1)); +#else + size_t Size = Map.size(); + Map.insert_or_assign(Itor, K, 1); + if (Mode() == ::Mode::Hit) { + if (Size != Map.size()) + State.SkipWithError("Inserted a duplicate element"); + } else { + if (Size + 1 != Map.size()) + State.SkipWithError("Failed to insert a new element"); + } +#endif + } + } + + State.PauseTiming(); + Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000); + State.ResumeTiming(); + } + } + + void run(benchmark::State& State) const { + static constexpr auto h = Hint(); + run(State); + } + + std::string name() const { + return "BM_InsertAssignHint" + baseName() + Mode::name() + Hint::name(); + } +}; + +template +struct Emplace : Base { + using Base::Base; + + void run(benchmark::State& State) const { + + auto Data = makeTestingSets( + MapSize, Mode(), + Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1000); + while (State.KeepRunningBatch(MapSize * Data.Maps.size())) { + for (auto& Map : Data.Maps) { + for (auto K : Data.Keys) { +#ifndef VALIDATE + benchmark::DoNotOptimize(Map.emplace(K, 1)); +#else + bool Inserted = Map.emplace(K, 1).second; + if (Mode() == ::Mode::Hit) { + if (Inserted) + State.SkipWithError("Emplaced a duplicate element"); + } else { + if (!Inserted) + State.SkipWithError("Failed to emplace a new element"); + } +#endif + } + } + + State.PauseTiming(); + Data = makeTestingSets(MapSize, Mode(), + Order::value == ::Order::Random ? Shuffle::Keys + : Shuffle::None, + 1000); + State.ResumeTiming(); + } + } + + std::string name() const { + return "BM_Emplace" + baseName() + Mode::name() + Order::name(); + } +}; + +template +struct EmplaceHint : Base { + using Base::Base; + + template < ::Hint hint> + typename std::enable_if::type + run(benchmark::State& State) const { + auto Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000); + while (State.KeepRunningBatch(MapSize * Data.Maps.size())) { + for (size_t I = 0; I < Data.Maps.size(); ++I) { + auto& Map = Data.Maps[I]; + auto H = Data.Hints[I].begin(); + for (auto K : Data.Keys) { +#ifndef VALIDATE + benchmark::DoNotOptimize(Map.emplace_hint(*H, K, 1)); +#else + auto Inserted = Map.emplace_hint(*H, K, 1); + if (Mode() == ::Mode::Hit) { + if (Inserted != *H) + State.SkipWithError("Emplaced a duplicate element"); + } else { + if (++Inserted != *H) + State.SkipWithError("Failed to emplace a new element"); + } +#endif + ++H; + } + } + + State.PauseTiming(); + Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000); + State.ResumeTiming(); + } + } + + template < ::Hint hint> + typename std::enable_if::type + run(benchmark::State& State) const { + auto Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000); + while (State.KeepRunningBatch(MapSize * Data.Maps.size())) { + for (size_t I = 0; I < Data.Maps.size(); ++I) { + auto& Map = Data.Maps[I]; + auto Third = *(Data.Hints[I].begin() + 2); + for (auto K : Data.Keys) { + auto Itor = hint == ::Hint::Begin + ? Map.begin() + : hint == ::Hint::Third ? Third : Map.end(); +#ifndef VALIDATE + benchmark::DoNotOptimize(Map.emplace_hint(Itor, K, 1)); +#else + size_t Size = Map.size(); + Map.emplace_hint(Itor, K, 1); + if (Mode() == ::Mode::Hit) { + if (Size != Map.size()) + State.SkipWithError("Emplaced a duplicate element"); + } else { + if (Size + 1 != Map.size()) + State.SkipWithError("Failed to emplace a new element"); + } +#endif + } + } + + State.PauseTiming(); + Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000); + State.ResumeTiming(); + } + } + + void run(benchmark::State& State) const { + static constexpr auto h = Hint(); + run(State); + } + + std::string name() const { + return "BM_EmplaceHint" + baseName() + Mode::name() + Hint::name(); + } +}; + +template +struct TryEmplace : Base { + using Base::Base; + + void run(benchmark::State& State) const { + + auto Data = makeTestingSets( + MapSize, Mode(), + Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1000); + while (State.KeepRunningBatch(MapSize * Data.Maps.size())) { + for (auto& Map : Data.Maps) { + for (auto K : Data.Keys) { +#ifndef VALIDATE + benchmark::DoNotOptimize(Map.try_emplace(K, 1)); +#else + bool Inserted = Map.try_emplace(K, 1).second; + if (Mode() == ::Mode::Hit) { + if (Inserted) + State.SkipWithError("Emplaced a duplicate element"); + } else { + if (!Inserted) + State.SkipWithError("Failed to emplace a new element"); + } +#endif + } + } + + State.PauseTiming(); + Data = makeTestingSets(MapSize, Mode(), + Order::value == ::Order::Random ? Shuffle::Keys + : Shuffle::None, + 1000); + State.ResumeTiming(); + } + } + + std::string name() const { + return "BM_TryEmplace" + baseName() + Mode::name() + Order::name(); + } +}; + +template +struct TryEmplaceHint : Base { + using Base::Base; + + template < ::Hint hint> + typename std::enable_if::type + run(benchmark::State& State) const { + auto Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000); + while (State.KeepRunningBatch(MapSize * Data.Maps.size())) { + for (size_t I = 0; I < Data.Maps.size(); ++I) { + auto& Map = Data.Maps[I]; + auto H = Data.Hints[I].begin(); + for (auto K : Data.Keys) { +#ifndef VALIDATE + benchmark::DoNotOptimize(Map.try_emplace(*H, K, 1)); +#else + auto Inserted = Map.try_emplace(*H, K, 1); + if (Mode() == ::Mode::Hit) { + if (Inserted != *H) + State.SkipWithError("Emplaced a duplicate element"); + } else { + if (++Inserted != *H) + State.SkipWithError("Failed to emplace a new element"); + } +#endif + ++H; + } + } + + State.PauseTiming(); + Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000); + State.ResumeTiming(); + } + } + + template < ::Hint hint> + typename std::enable_if::type + run(benchmark::State& State) const { + auto Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000); + while (State.KeepRunningBatch(MapSize * Data.Maps.size())) { + for (size_t I = 0; I < Data.Maps.size(); ++I) { + auto& Map = Data.Maps[I]; + auto Third = *(Data.Hints[I].begin() + 2); + for (auto K : Data.Keys) { + auto Itor = hint == ::Hint::Begin + ? Map.begin() + : hint == ::Hint::Third ? Third : Map.end(); +#ifndef VALIDATE + benchmark::DoNotOptimize(Map.try_emplace(Itor, K, 1)); +#else + size_t Size = Map.size(); + Map.try_emplace(Itor, K, 1); + if (Mode() == ::Mode::Hit) { + if (Size != Map.size()) + State.SkipWithError("Emplaced a duplicate element"); + } else { + if (Size + 1 != Map.size()) + State.SkipWithError("Failed to emplace a new element"); + } +#endif + } + } + + State.PauseTiming(); + Data = makeTestingSets(MapSize, Mode(), Shuffle::None, 1000); + State.ResumeTiming(); + } + } + + void run(benchmark::State& State) const { + static constexpr auto h = Hint(); + run(State); + } + + std::string name() const { + return "BM_TryEmplaceHint" + baseName() + Mode::name() + Hint::name(); + } +}; + +template +struct Erase : Base { + using Base::Base; + + void run(benchmark::State& State) const { + auto Data = makeTestingSets( + MapSize, Mode(), + Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1000); + while (State.KeepRunningBatch(MapSize * Data.Maps.size())) { + for (auto& Map : Data.Maps) { + for (auto K : Data.Keys) { +#ifndef VALIDATE + benchmark::DoNotOptimize(Map.erase(K)); +#else + size_t I = Map.erase(K); + if (Mode() == ::Mode::Hit) { + if (I == 0) + State.SkipWithError("Did not find the existing element"); + } else { + if (I == 1) + State.SkipWithError("Did find the non-existing element"); + } +#endif + } + } + + State.PauseTiming(); + Data = makeTestingSets(MapSize, Mode(), + Order::value == ::Order::Random ? Shuffle::Keys + : Shuffle::None, + 1000); + State.ResumeTiming(); + } + } + + std::string name() const { + return "BM_Erase" + baseName() + Mode::name() + Order::name(); + } +}; + +template +struct EraseIterator : Base { + using Base::Base; + + void run(benchmark::State& State) const { + auto Data = makeTestingSets( + MapSize, Mode::Hit, + Order::value == ::Order::Random ? Shuffle::Hints : Shuffle::None, 1000); + while (State.KeepRunningBatch(MapSize * Data.Maps.size())) { + for (size_t I = 0; I < Data.Maps.size(); ++I) { + auto& Map = Data.Maps[I]; + for (auto H : Data.Hints[I]) { + benchmark::DoNotOptimize(Map.erase(H)); + } +#ifdef VALIDATE + if (!Map.empty()) + State.SkipWithError("Did not erase the entire map"); +#endif + } + + State.PauseTiming(); + Data = makeTestingSets(MapSize, Mode::Hit, + Order::value == ::Order::Random ? Shuffle::Hints + : Shuffle::None, + 1000); + State.ResumeTiming(); + } + } + + std::string name() const { + return "BM_EraseIterator" + baseName() + Order::name(); + } +}; + +struct EraseRange : Base { + using Base::Base; + + void run(benchmark::State& State) const { + auto Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1000); + while (State.KeepRunningBatch(MapSize * Data.Maps.size())) { + for (auto& Map : Data.Maps) { +#ifndef VALIDATE + benchmark::DoNotOptimize(Map.erase(Map.begin(), Map.end())); +#else + Map.erase(Map.begin(), Map.end()); + if (!Map.empty()) + State.SkipWithError("Did not erase the entire map"); +#endif + } + + State.PauseTiming(); + Data = makeTestingSets(MapSize, Mode::Hit, Shuffle::None, 1000); + State.ResumeTiming(); + } + } + + std::string name() const { return "BM_EraseRange" + baseName(); } +}; + +//*******************************************************************| +// Lookup | +//*******************************************************************| + +template +struct Count : Base { + using Base::Base; + + void run(benchmark::State& State) const { + auto Data = makeTestingSets( + MapSize, Mode(), + Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1); + auto& Map = Data.Maps.front(); + while (State.KeepRunningBatch(MapSize)) { + for (auto K : Data.Keys) { +#ifndef VALIDATE + benchmark::DoNotOptimize(Map.count(K)); +#else + size_t I = Map.count(K); + if (Mode() == ::Mode::Hit) { + if (I == 0) + State.SkipWithError("Did not find the existing element"); + } else { + if (I == 1) + State.SkipWithError("Did find the non-existing element"); + } +#endif + } + } + } + + std::string name() const { + return "BM_Count" + baseName() + Mode::name() + Order::name(); + } +}; + +template +struct Find : Base { + using Base::Base; + + void run(benchmark::State& State) const { + auto Data = makeTestingSets( + MapSize, Mode(), + Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1); + auto& Map = Data.Maps.front(); + while (State.KeepRunningBatch(MapSize)) { + for (auto K : Data.Keys) { +#ifndef VALIDATE + benchmark::DoNotOptimize(Map.find(K)); +#else + auto Itor = Map.find(K); + if (Mode() == ::Mode::Hit) { + if (Itor == Map.end()) + State.SkipWithError("Did not find the existing element"); + } else { + if (Itor != Map.end()) + State.SkipWithError("Did find the non-existing element"); + } +#endif + } + } + } + + std::string name() const { + return "BM_Find" + baseName() + Mode::name() + Order::name(); + } +}; + +template +struct EqualRange : Base { + using Base::Base; + + void run(benchmark::State& State) const { + auto Data = makeTestingSets( + MapSize, Mode(), + Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1); + auto& Map = Data.Maps.front(); + while (State.KeepRunningBatch(MapSize)) { + for (auto K : Data.Keys) { +#ifndef VALIDATE + benchmark::DoNotOptimize(Map.equal_range(K)); +#else + auto Range = Map.equal_range(K); + if (Mode() == ::Mode::Hit) { + // Adjust validation for the last element. + auto Key = K; + if (Range.second == Map.end() && K == 2 * MapSize) { + --Range.second; + Key -= 2; + } + if (Range.first == Map.end() || Range.first->first != K || + Range.second == Map.end() || Range.second->first - 2 != Key) + State.SkipWithError("Did not find the existing element"); + } else { + if (Range.first == Map.end() || Range.first->first - 1 != K || + Range.second == Map.end() || Range.second->first - 1 != K) + State.SkipWithError("Did find the non-existing element"); + } +#endif + } + } + } + + std::string name() const { + return "BM_EqualRange" + baseName() + Mode::name() + Order::name(); + } +}; + +template +struct LowerBound : Base { + using Base::Base; + + void run(benchmark::State& State) const { + auto Data = makeTestingSets( + MapSize, Mode(), + Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1); + auto& Map = Data.Maps.front(); + while (State.KeepRunningBatch(MapSize)) { + for (auto K : Data.Keys) { +#ifndef VALIDATE + benchmark::DoNotOptimize(Map.lower_bound(K)); +#else + auto Itor = Map.lower_bound(K); + if (Mode() == ::Mode::Hit) { + if (Itor == Map.end() || Itor->first != K) + State.SkipWithError("Did not find the existing element"); + } else { + if (Itor == Map.end() || Itor->first - 1 != K) + State.SkipWithError("Did find the non-existing element"); + } +#endif + } + } + } + + std::string name() const { + return "BM_LowerBound" + baseName() + Mode::name() + Order::name(); + } +}; + +template +struct UpperBound : Base { + using Base::Base; + + void run(benchmark::State& State) const { + auto Data = makeTestingSets( + MapSize, Mode(), + Order::value == ::Order::Random ? Shuffle::Keys : Shuffle::None, 1); + auto& Map = Data.Maps.front(); + while (State.KeepRunningBatch(MapSize)) { + for (auto K : Data.Keys) { +#ifndef VALIDATE + benchmark::DoNotOptimize(Map.upper_bound(K)); +#else + std::map::iterator Itor = Map.upper_bound(K); + if (Mode() == ::Mode::Hit) { + // Adjust validation for the last element. + auto Key = K; + if (Itor == Map.end() && K == 2 * MapSize) { + --Itor; + Key -= 2; + } + if (Itor == Map.end() || Itor->first - 2 != Key) + State.SkipWithError("Did not find the existing element"); + } else { + if (Itor == Map.end() || Itor->first - 1 != K) + State.SkipWithError("Did find the non-existing element"); + } +#endif + } + } + } + + std::string name() const { + return "BM_UpperBound" + baseName() + Mode::name() + Order::name(); + } +}; + +} // namespace + +int main(int argc, char** argv) { + benchmark::Initialize(&argc, argv); + if (benchmark::ReportUnrecognizedArguments(argc, argv)) + return 1; + +#ifdef VALIDATE + const std::vector MapSize{10}; +#else + const std::vector MapSize{10, 100, 1000, 10000, 100000, 1000000}; +#endif + + // Member functions + makeCartesianProductBenchmark(); + makeCartesianProductBenchmark(MapSize); + makeCartesianProductBenchmark(MapSize); + makeCartesianProductBenchmark(MapSize); + + // Capacity + makeCartesianProductBenchmark(MapSize); + makeCartesianProductBenchmark(MapSize); + + // Modifiers + makeCartesianProductBenchmark(MapSize); + makeCartesianProductBenchmark(MapSize); + makeCartesianProductBenchmark(MapSize); + makeCartesianProductBenchmark(MapSize); + makeCartesianProductBenchmark(MapSize); + + makeCartesianProductBenchmark(MapSize); + makeCartesianProductBenchmark(MapSize); + makeCartesianProductBenchmark(MapSize); + makeCartesianProductBenchmark(MapSize); + makeCartesianProductBenchmark(MapSize); + makeCartesianProductBenchmark(MapSize); + makeCartesianProductBenchmark(MapSize); + + // Lookup + makeCartesianProductBenchmark(MapSize); + makeCartesianProductBenchmark(MapSize); + makeCartesianProductBenchmark(MapSize); + makeCartesianProductBenchmark(MapSize); + makeCartesianProductBenchmark(MapSize); + + benchmark::RunSpecifiedBenchmarks(); +}