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

In many use cases find performance is probably considered the most important benchmark. This benchmark was tricky to implement, as it should be as unbiased as possible. It tries to do the following:

• Lookup with different probability of being found: 0%, 25%, 50%, 75%, and 100% success ratio, to make sure we are not biased about lookup probability.
• Lookups with different amount of data in the map, to make sure we have a wide range of fullness factors.
• Lookups with different bitmasks of the entry, to make sure we are not biased towards small numbers.

It works this way:

1. Each iteration, 4 random entries are created in a Map<size_t, size_t>. Depending on the desired lookup probability, 0, 1, 2, 3, or all 4 entries will be chosen either from a unique random number generator, or one with the same initial seed used for the lookups. Additionally, the order of these 4 entries is shuffled to introduce even more randomness.
2. After insertion, a number of lookups are performed, and when an entry is found it’s value is accessed.
3. Repeat until the map is full.

Here, we perform 2 million lookups for every 4 inserts, until the map contains 2000 elements.

Results

Hashes

As always, robin_hood::hash is fastest, closely followed by absl::Hash. libstdc++-v3 has quite a few problems with the upper bitmask, resulting in huge numbers for many hashmaps and several timeouts.

Hashmaps

In this benchmark both emilib::HashMap is the fastest with robin_hood::hash. tsl::robin_map comes close, but no ciguar. Unfortunately it was not possible to get any peak memory numbers, the maps are just to small for that. std::unordered_map is by far the slowest.

Chart

Each entry shows average time for a single find and access operation (if found). The final number is average over all entries.

1. blue: 0% find success, bitmask 0x00000000FFFFFFFF (only lower bits)
2. orange: 0% find success, bitmask 0xFFFFFFFF00000000 (only upper bits)
3. green: 25% find success, bitmask 0x00000000FFFFFFFF (only lower bits)
4. red: 25% find success, bitmask 0xFFFFFFFF00000000 (only upper bits)
5. magenta: 50% find success, bitmask 0x00000000FFFFFFFF (only lower bits)
6. brown: 50% find success, bitmask 0xFFFFFFFF00000000 (only upper bits)
7. pink: 75% find success, bitmask 0x00000000FFFFFFFF (only lower bits)
8. gray: 75% find success, bitmask 0xFFFFFFFF00000000 (only upper bits)
9. lime: 100% find success, bitmask 0x00000000FFFFFFFF (only lower bits)
10. cyan: 100% find success, bitmask 0xFFFFFFFF00000000 (only upper bits)