Hashmap benchmark report

This benchmark pits my hash map implementation, ASKL's Map, against what I hope is a representative sample of the state of the art:

• Abseil, written in C++ and SwissTable-based
• F14 FastMap, written in C++ and optimised for raw speed
• Rust's standard library HashMap, based on hashbrown
• M*DICT, a high quality hash map written in C
• Verstable, Jackson Allan's clever generic hashtable written in C
• the Python dictionary, which is written in C under the hood
• khash, probably the most famous C hash map, and its descendant khashl

What does ASKL bring to the table? Like all the strong contenders above, it's portable, but it's also thread-safe, comes with an iterator and stable traversal order, and a fun lazy sort feature. It's a hybrid beast somewhat similar to Java's LinkedHashMap.

You can play with it and run the multi-threaded unit tests here: Godbolt

My own focus is fast retrieval of pointer values from string keys, so that's the performance aspect I have optimised ASKL for and what this simple benchmark tries to evaluate.

I have measured four different workloads:

• insert simply inserts "1" to "N" keys with integer values in the map
• update inserts the same data in the map, then update all the values
• retrieve inserts data, then read the values back (the one I care the most about)
• miss inserts data, then purposefully lookup non-existing keys.

The numbers provided here come from my own machine, a M2 Max, and were gathered using hyperfine. All the timings are wall-clock medians in milliseconds, lower is better. Not all implementations have some "reserve" feature, so the benchmark purposefully does not use capacity hints. I have chosen to use each implementation "as-is" including their default hash function, because that's how a developer using the various libraries would experience them. ASKL uses rapidhashNano.

AI disclosure

I have written my hashmap the old-fashioned way, without AI, however the benchmark harness, part of the unit tests and some of the documentation have been edited with AI.

Outputs

• all-benchmarks.csv: full aggregated dataset
• all-benchmarks-under-1m.csv: aggregated dataset restricted to keys <= 1_000_000
• insert.csv, update.csv, retrieve.csv, miss.csv: full per-test CSVs
• insert-under-1m.csv, update-under-1m.csv, retrieve-under-1m.csv, miss-under-1m.csv: zoomed per-test CSVs

Zoomed report: ≤ 1M keys

My own use case involves a moderate amount of data, usually between a few thousand and a hundred thousand key/value pairs, so I have paid special attention to this range of values.

Insert ≤ 1M keys

As you can see, Rust's HashMap crushes everyone here. I essentially compete with M*DICT, but Abseil and Folly close the gap as we reach 1 million keys.

Update ≤ 1M keys

Same story for updates, except khash starts breathing down my neck as we approach the million.

Retrieve ≤ 1M keys

That's what I worked for. I'm elbowing Rust here, but Folly and M*DICT come back for the million.

Miss ≤ 1M keys

I admit I didn't really optimise this, as it's not really a concern for my use case. I get trounced by the usual suspects rather quickly here!

Full report

Insert full range

Insertions are quite fiddly with cuckoo hashing, so without surprise I get beaten by most of the other contenders, especially for large numbers of keys.

Update full range

Here I put up a rather honourable fight. The chart is pretty close to "retrieve", which is the one I have focused on.

Retrieve full range

I did my best to mitigate the impact of the memory wall (pointer tagging helped), but it's real, and I start hitting it hard above 2 million keys. Note the very powerful comeback of khash who rules over everyone else at 10 million keys. I was surprised to still manage to shadow Abseil for this large amount of data.

Miss full range

Not a good one. I still manage to do better than Python and Verstable.

Thank you for reading this far, and I hope you'll enjoy tinkering with ASKL's Map!

By the way, ASKL implements other fun stuff, maybe you'll come for the hashmap and stay for the JSON parser?