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 test is practically exactly the same as Find 1-2000 size_t, except that it uses 100 byte long std::string. There are 4000 lookups every 4 inserts, until 100k entries inserts.

Results

Hashes

In Insert & Erase std::string we have evaluated that robin_hood::hash is fastest for 100 byte strings, and this is also the case in this benchmark. libstdc++-v3s performance is a tad slower, FNV1a is very slow.

Hashmaps

Here, the robin_hood::unordered_node_map is the clear winner, only narrowly followed by robin_hood::unordered_flat_map. It can clearly be seen that the 1-byte overhead structure is quite important here: in the 0% lookup success case, the performance is much higher because this byte saves us from a lot of std::string comparison checks.

Not only is robin_hood::unordered_node_map the fastest, it has also quite low peak memory usage, only beaten by tsl::sparse_map. E.g. tsl::robin_map uses more than 3 times as much memory.

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, 100 byte size std::string
2. orange: 25% find success, 100 byte size std::string
3. green: 50% find success, 100 byte size std::string
4. red: 75% find success, 100 byte size std::string
5. magenta: 100% find success, 100 byte size std::string