Table of Contents

• Overview
• Construction Benchmarks
  • Construction & Destruction 👈
  • Construction & Insert 1 int & Destruction
• Modifying Benchmarks
  • Insert & Erase 100M int
  • Insert & Access with Varying Probability int
  • Insert & Erase uint64_t
  • Insert & Erase std::string
• Accessing
  • Find 1 – 2000 uint64_t
  • Find 1 – 500k uint64_t
  • Find 1 – 100k std::string
  • Find 1 – 1M std::string
  • Iterating
• Conclusion

To get started, the first benchmark is a very simple one: measure how fast the hashmap can be constructed and destructed. Some maps perform some kind of lazy initialization, where data is only allocated when the first element is inserted, some immediately initialize their data structures.

The full benchmark code is this:

for (size_t n = 0; n < 100'000'000; ++n) {
    Map<int, int> map;
    result += map.size();
}

After the loop is done, the variable result is used in a verification step. It also helps that the compiler does not simply optimize the code away, but it probably for some maps anyways.

Results

Hashes

The hashing algorithm used should be completely irrelevant, as no element is inserted. The results are grouped by the hashing algorithm, and the individual hashes have mostly the same times.

Hashmaps

Construction is generally very fast, and a non-issue. The slowest map to construct is boost::multi_index::hashed_unique, which takes 40.7ns to construct. Anything below 2-3ns is probably just measurement noise. Note that the benchmark results are very consistent regardless of the used hash function (as it should be).

Chart

1. blue: average time to construct one map.