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

This benchmark is the same as previous, but with 4000 lookups for every 4 inserts until the map contains 500k elements.

Results

Hashes

Same behavior as for the other benchmarks: robin_hood::hash is fastest, absl::Hash second, and libstdc++-v3 problematic.

Hashmaps

This time emilib::HashMap is not the winner any more. It seems to be well tuned for smaller maps, but the fastest maps for larger data are phmap::flat_hash_map and absl::flat_hash_map. I find it interesting that the node maps are performing so well even though they add a layer of indirection. robin_hood::unordered_node_map even performs a bit better than robin_hood::unordered_flat_map. robin_hood::unordered_flat_map’s peak memory is very small, only tsl::sparse_map uses less RAM - unfortunately below the measurement barrier, so I only have 0 as a number.

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)