Google Git
Sign in
llvm / llvm-project / libcxx / 88772a846963cc2b2b04b6a95ff63fc82a22f4f7 / . / benchmarks / map.bench.cpp
blob: dd1884f65032e5bff6e6b5ab2c1169d9391e99a1 [file] [log] [blame]
//===----------------------------------------------------------------------===//
//
// 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 <algorithm>
#include <cstdint>
#include <map>
#include <random>
#include <vector>
#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<AllModes, Mode, 2> {
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<AllHints, Hint, 4> {
static constexpr const char* Names[] = {"Begin", "Third", "Correct", "End"};
};
enum class Order { Sorted, Random };
struct AllOrders : EnumValuesAsTuple<AllOrders, Order, 2> {
static constexpr const char* Names[] = {"Sorted", "Random"};
};
struct TestSets {
std::vector<uint64_t> Keys;
std::vector<std::map<uint64_t, int64_t> > Maps;
std::vector<
std::vector<typename std::map<uint64_t, int64_t>::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<uint64_t, int64_t>());
}
}
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<uint64_t, int64_t>(Map.begin(), Map.end()));
#else
std::map<uint64_t, int64_t> 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<uint64_t, int64_t> M(Map);
benchmark::DoNotOptimize(M);
#else
std::map<uint64_t, int64_t> 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<uint64_t, int64_t> 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 <class Mode, class Order>
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 <class Mode, class Hint>
struct InsertHint : Base {
using Base::Base;
template < ::Hint hint>
typename std::enable_if<hint == ::Hint::Correct>::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<hint != ::Hint::Correct>::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<h>(State);
}
std::string name() const {
return "BM_InsertHint" + baseName() + Mode::name() + Hint::name();
}
};
template <class Mode, class Order>
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 <class Mode, class Hint>
struct InsertAssignHint : Base {
using Base::Base;
template < ::Hint hint>
typename std::enable_if<hint == ::Hint::Correct>::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<hint != ::Hint::Correct>::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<h>(State);
}
std::string name() const {
return "BM_InsertAssignHint" + baseName() + Mode::name() + Hint::name();
}
};
template <class Mode, class Order>
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 <class Mode, class Hint>
struct EmplaceHint : Base {
using Base::Base;
template < ::Hint hint>
typename std::enable_if<hint == ::Hint::Correct>::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<hint != ::Hint::Correct>::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<h>(State);
}
std::string name() const {
return "BM_EmplaceHint" + baseName() + Mode::name() + Hint::name();
}
};
template <class Mode, class Order>
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 <class Mode, class Hint>
struct TryEmplaceHint : Base {
using Base::Base;
template < ::Hint hint>
typename std::enable_if<hint == ::Hint::Correct>::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<hint != ::Hint::Correct>::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<h>(State);
}
std::string name() const {
return "BM_TryEmplaceHint" + baseName() + Mode::name() + Hint::name();
}
};
template <class Mode, class Order>
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 <class Order>
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 <class Mode, class Order>
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 <class Mode, class Order>
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 <class Mode, class Order>
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 <class Mode, class Order>
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 <class Mode, class Order>
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<uint64_t, int64_t>::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<size_t> MapSize{10};
#else
const std::vector<size_t> MapSize{10, 100, 1000, 10000, 100000, 1000000};
#endif
// Member functions
makeCartesianProductBenchmark<ConstructorDefault>();
makeCartesianProductBenchmark<ConstructorIterator>(MapSize);
makeCartesianProductBenchmark<ConstructorCopy>(MapSize);
makeCartesianProductBenchmark<ConstructorMove>(MapSize);
// Capacity
makeCartesianProductBenchmark<Empty>(MapSize);
makeCartesianProductBenchmark<Size>(MapSize);
// Modifiers
makeCartesianProductBenchmark<Clear>(MapSize);
makeCartesianProductBenchmark<Insert, AllModes, AllOrders>(MapSize);
makeCartesianProductBenchmark<InsertHint, AllModes, AllHints>(MapSize);
makeCartesianProductBenchmark<InsertAssign, AllModes, AllOrders>(MapSize);
makeCartesianProductBenchmark<InsertAssignHint, AllModes, AllHints>(MapSize);
makeCartesianProductBenchmark<Emplace, AllModes, AllOrders>(MapSize);
makeCartesianProductBenchmark<EmplaceHint, AllModes, AllHints>(MapSize);
makeCartesianProductBenchmark<TryEmplace, AllModes, AllOrders>(MapSize);
makeCartesianProductBenchmark<TryEmplaceHint, AllModes, AllHints>(MapSize);
makeCartesianProductBenchmark<Erase, AllModes, AllOrders>(MapSize);
makeCartesianProductBenchmark<EraseIterator, AllOrders>(MapSize);
makeCartesianProductBenchmark<EraseRange>(MapSize);
// Lookup
makeCartesianProductBenchmark<Count, AllModes, AllOrders>(MapSize);
makeCartesianProductBenchmark<Find, AllModes, AllOrders>(MapSize);
makeCartesianProductBenchmark<EqualRange, AllModes, AllOrders>(MapSize);
makeCartesianProductBenchmark<LowerBound, AllModes, AllOrders>(MapSize);
makeCartesianProductBenchmark<UpperBound, AllModes, AllOrders>(MapSize);
benchmark::RunSpecifiedBenchmarks();
}