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

Almost the same as Construction & Destruction, but this time a single element is inserted. All maps that do lazy initialization are now forced to actually provide storage memory, and they have to calculate the hash function at least once to find a proper slot.

The full benchmark code is this:

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

After the loop is done, the variable result is used in a verification step. It should always be 50’000’000.

Results

Hashes

This time a single element is hashed and inserted into the map. The overhead of hashing should only insofar be an influence that it is called once. No collision problems with a single entry. Naturally, libstdc++-v3 is the fastest hashing for that use case because it does practically nothing. Note that the groups in the graph below are sorted: libstdc++-v3 comes first because total runtime is fastest, and robin_hood::hash comes second with a slight overhead.

Hashmaps

emilib1::HashMap is the winner here, with tsl::robin_map a close second, and on par with any hash function except libstdc++-v3.

phmap::parallel_node_hash_map is the slowest of the bunch here, because it allocates multiple tables to be able to operate fast in parallel.

Chart

1. blue: average time to construct map and insert one element.