[1/2] Add a benchmark for map operations.

[Mordante]

Summary

Before tackling bug 38722 make sure there is a baseline benchmark.

[mclow.lists]

There are several cases for "insert with hint". This tests one of them - the case where the hint is a dreferenceable iterator that points to the correct place in the map.

There are (at least) two other cases:

• The hint is a dreferenceable iterator that points to the wrong place in the map.
• The hint is not a dereferenceable iterator at all (think end())

[Mordante]

I added 3 extra iterator positions for all hint cases:

• end() as you suggested.
• begin() this is most of the time the wrong iterator.
• the third element this is most of the time the wrong iterator. Just to avoid the code will use special optimizations on begin() and end().

[mclow.lists]

libcxx/benchmarks/map.bench.cpp

58

The fact that the keys you use to test are ordered is troubling to me. See comment on erase

684

Isn't this just "Erase the first element" over and over until the map is empty?

713

Same with this one - isn't this just erasing the first element over and over?

[Mordante]

Adds additional tests to makes sure the order doesn't result in always removing the first element as observed by @mclow.lists .

[ldionne]

@Mordante Can this be rebased on master? Also, I'd be curious to have @mvels look at this since he's been doing performance work for libc++ (albeit in unrelated areas).

[Mordante]

Rebased against master.

[ldionne]

How did you compile that? ninja -C build cxx-benchmarks fail after applying your patch:

In file included from <llvm>/libcxx/benchmarks/map.bench.cpp:15:
<llvm>/libcxx/benchmarks/CartesianBenchmarks.h:65:71: warning: pack fold expression is a C++17 extension [-Wc++17-extensions]
  (internal::makeBenchmarkImpl<B>(A, std::tuple<U..., T>(), rest...), ...);
                                                                      ^
<llvm>/libcxx/benchmarks/map.bench.cpp:77:9: error: cannot form a reference to 'void'
    auto& map = R.Maps.emplace_back();
        ^
<llvm>/libcxx/benchmarks/map.bench.cpp:78:9: error: cannot form a reference to 'void'
    auto& hints = R.Hints.emplace_back();
        ^
<llvm>/libcxx/benchmarks/map.bench.cpp:367:40: error: no member named 'insert_or_assign' in 'std::__1::map<unsigned long long, long long, std::__1::less<unsigned long long>, std::__1::allocator<std::__1::pair<const unsigned long long, long long> > >'
          benchmark::DoNotOptimize(Map.insert_or_assign(K, 1));
                                   ~~~ ^
<llvm>/libcxx/benchmarks/CartesianBenchmarks.h:46:69: note: in instantiation of member function '(anonymous namespace)::InsertAssign<internal::EnumValue<(anonymous namespace)::AllModes, (anonymous namespace)::Mode, 1>, internal::EnumValue<(anonymous namespace)::AllOrders, (anonymous namespace)::Order, 1> >::run' requested here
                                   [=](benchmark::State& S) { Bench.run(S); });
                                                                    ^
<llvm>/libcxx/benchmarks/CartesianBenchmarks.h:53:3: note: in instantiation of function template specialization 'internal::makeBenchmarkFromValuesImpl<(anonymous namespace)::InsertAssign<internal::EnumValue<(anonymous namespace)::AllModes, (anonymous namespace)::Mode, 1>, internal::EnumValue<(anonymous namespace)::AllOrders, (anonymous namespace)::Order, 1> >, std::__1::vector<std::__1::tuple<unsigned long>, std::__1::allocator<std::__1::tuple<unsigned long> > >, 0>' requested here
  makeBenchmarkFromValuesImpl<B>(A, std::index_sequence_for<Args...>());
  ^
<llvm>/libcxx/benchmarks/CartesianBenchmarks.h:58:3: note: in instantiation of function template specialization 'internal::makeBenchmarkFromValues<(anonymous namespace)::InsertAssign<internal::EnumValue<(anonymous namespace)::AllModes, (anonymous namespace)::Mode, 1>, internal::EnumValue<(anonymous namespace)::AllOrders, (anonymous namespace)::Order, 1> >, unsigned long>' requested here
  makeBenchmarkFromValues<B<U...> >(A);
  ^

[Mordante]

It builds for me, but I had CMAKE_CXX_STANDARD set to 17 for this build. It seems the method used to use C++17 for the benchmarks didn't work. I feel fixing this issue should not be part of this commit. So I created D75955 to fix the issue. With that patch applied it also works for me when CMAKE_CXX_STANDARD set to 14. This is the default value.

[ldionne]

LGTM assuming it build on top of your other patch.

[EricWF]

libcxx/benchmarks/CartesianBenchmarks.h

22

Uh, EnumValue::value should already work, since it's inherited from integral constant, no?

[Mordante]

Good catch, I'll update the patch.

[Mordante]

Addresses @EricWF's comment.

[ldionne]

I'll ship this now. Thanks.

[Mordante]

Thanks for accepting and committing the patch.

libcxx/benchmarks/CartesianBenchmarks.h

 
 #include "benchmark/benchmark.h"
 #include "test_macros.h"
 
 namespace internal {
 
 template <class D, class E, size_t I>
 struct EnumValue : std::integral_constant<E, static_cast<E>(I)> {
+  static const E value = static_cast<E>(I);
   static std::string name() { return std::string("_") + D::Names[I]; }
 };
 
 template <class D, class E, size_t ...Idxs>
 constexpr auto makeEnumValueTuple(std::index_sequence<Idxs...>) {
   return std::make_tuple(EnumValue<D, E, Idxs>{}...);
 }
 

libcxx/benchmarks/map.bench.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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();
+}