An Extensive Benchmark of C and C++ Hash Tables

[JacksonAllan]

Comments on the article An Extensive Benchmark of C and C++ Hash Tables belong below.

[Philippe91]

This is outstanding work—I understand that this type of project requires significant effort. However, here's what's missing from my point of view:

• The Qt QHash map (keep in mind that Qt is a very popular framework, so being aware of alternative maps would be beneficial). At the very least, Qt maps are used more frequently than some map implementations you evaluate.

• The benchmark focuses on large containers. In many applications, maps are not nearly as full, so data on smaller containers would have been appreciated.

[JacksonAllan]

Thanks for reading and offering feedback!

Qt maps are used more frequently than some map implementations you evaluate.

I give some details about why I excluded some popular hash tables in this Reddit comment:

Sorry, no Glib/GHashTable. This omission may be surprising, but it was based on a few considerations:

• GHashTable only allows one type for keys and values: void * pointers. This severely limits its flexibility. While integers can be shoehorned into pointers (albeit with some portability concerns), larger data types need to be allocated as separate nodes. There are already two node-based or quasi-node-based tables in the benchmarks (std::unordered_map and uthash), and they—very predictably—cannot keep up with the open addressing tables due to allocation time (on insert) and pointer chasing (everywhere else). This is true even for large buckets, i.e. where some people might expect a node-based container to perform better.
• GHashTable is, as far as I recall, now a Robin Hood hash table. There are already two Robin Hood tables in the benchmarks (ankerl::unordered_dense and tsl::robin_map), and they don't suffer from the aforementioned data-type-size constraint. In fact, there were originally three Robin Hood tables (because CC's cc_map was a Robin Hood table up until this year). I didn't see much benefit in adding another one unless there was a good reason to believe it would be more competitive than those already included (Edit: The two remaining Robin Hood tables are both for C++. Adding Glib might be good for the sake of C users looking specifically for a Robin Hood table).
• I really struggled to get Glib working with MinGW (I'm on Windows), although it could be that the problem lies somewhere between the chair and the keyboard. Generally, I was disinclined to include large libraries that do not allow their hash-table component to be installed separately, libraries that are difficult to install, libraries that would be difficult to package with the benchmarks, libraries that force the use of a particular build system, etc. (absl::flat_hash_map is the exception here, and even then it is not being included in the "proper" manner). I wanted to focus on ones that users can install and use with minimal fuss. Facebook's F14 is another rather glaring omission that I made on this basis (it explicitly does not support MinGW). Qt's QHashTable also fits into this category. [Emphasis added]
  Please correct me if I'm wrong in any of my comments about GHashTable. It's been a long time since I looked into it. I'm not averse to adding it to the article as part of some later revision.

Another reason that some popular C++ tables don't appear is that these benchmarks started life as a benchmark suite primarily for C tables, with only the C++ tables generally regarded as the fastest and most cutting-edge included to serve as a yardstick for the C tables. However, the article has now garnered quite a bit interest from C++ developers, so I think it would be good for a revision to add (besides Glib) QHash. I'm not sure I can do much about F14, though, since including it would probably require switching to MSVC or to Linux (which would be a colossal pain for me and my one computer).

The benchmark focuses on large containers. In many applications, maps are not nearly as full, so data on smaller containers would have been appreciated.

I touch on this issue here and here. For the sake of brevity, I'll quote just the most relevant parts of those comments:

Also, it's worth noting that the results for different key counts do not necessarily correspond to different key counts in practice. Rather, the results in the lower-key-count benchmarks should reflect the situation when the tables are hotter in the cache, whereas the high-key-count benchmarks should reflect the situation when the table are colder (I mention this point, too, in the article). In the former scenario, instructions matter most; in the latter, cache efficiency matters most. This means that tables with small key counts may behave more like what we seen in the high-key-count benchmark if they are being used infrequently or the application is doing enough other processing that there is competition over cache space (this was one of my reasons for selecting those ones for embedding with the article's text).

I suspect the important factor might be not how many keys you have per se, but how hot you expect your table to be in the cache when the time comes to use it (e.g. if your table's keys are counted in the thousands and your program mainly does hash-table operations, look to the 0-to-200,000-key benchmarks).

I agree with the user who said that a logarithmic scale might have been better, but I also discuss some of the drawbacks of that route here. The TLDR is that a logarithmic scale does not, in and of itself, prevent me from manipulating the impression given by the results, particularly in the heatmap, in favor of certain libraries (including my own).

[ManishJu]

thanks for the amazing work! Can you please also include
ExcaliburHash : https://github.com/SergeyMakeev/ExcaliburHash?tab=readme-ov-file
MeowHash : https://github.com/cmuratori/meow_hash

[wscott]

He didn't compare any hashes.

[ManishJu]

hey @wscott wouldn't some hash tables performance metrics infer some hash functions performance ? Would love to read more about these if you have some nice literature link . :)

[wscott]

I thought both the links you posted were hash functions and not hash tables, but I see now that the first is a hash table and only the second is a hash function.

from the article:

All the tables benchmarked are configured to use the same hash functions, namely the MurmurHash3 finalizer for integer keys and FNV-1a for string keys.

So he didn't compare how changing the hash function would impact different data structures.

If you want to look at how changing the hash function impacts performance look here which was also linked in the article.

[bftjoe]

Please add PGM index. https://github.com/gvinciguerra/PGM-index/blob/master/examples/updates.cpp

PGM index doesn't even need a hash function for integer keys.

And maybe fph https://github.com/renzibei/fph-table

[nlescoua]

Great article, for C you might be interested in :
https://github.com/technicolor-research/cuckoopp

It features a cuckoo hash table with memory layout optimized for SIMD lookup, and the addition of a small bloom filter in each bucket to improve negative lookups. It can work looking up single value but also offers a batch lookup interface that allow further performance optimizations like prefetching, loop unrolling,…

[Zhihan-Lu]

Amazing work! Thanks a lot for the detailed explanation.

Does the author have statistics for the CPU and Memory usage when benchmarking each table? I am wondering when the system's CPU load is high, whether the performance of the SIMD tables will be impacted.

[JacksonAllan]

Thanks for reading!

I talk a little about the fact that the benchmarks do not measure memory usage here. The relevant part of my comment reads:

The fact that these benchmarks do not measure memory usage is probably their biggest weakness. I made this choice early on in order to limit the scope of the project, but I ended up regretting it as I added more tables that displayed more varied ways of storing data and therefore couldn't be easily compared—in terms of memory usage—to the others based only on one or two numbers (e.g. per-bucket-overhead). Ultimately, I decided that if I'm going to measure memory usage, it will have to be in some kind of follow-up article/project. But do take a look at this benchmark, which—although it only includes one pair of data types—does measure memory usage and look at speed in the context of it. Edit: Also, I believe that martinus' benchmarks included memory usage.

Unfortunately, integrating measurements of memory usage into the project would require serious restructuring so that each table is benchmarked in a separate process rather than in one monolithic benchmarking program. But for most of the open addressing tables, it should hopefully be possible to make a fairly accurate estimate of their memory usage based on the description I included in the article, especially because they mostly use the same growth policy and therefore grown in sync with one another.

I am wondering when the system's CPU load is high, whether the performance of the SIMD tables will be impacted.

That's a good question. I'll try to summon @joaquintides, who developed boost::unordered_flat_map, to see whether he can shed any light on the matter. My own experiments with SIMD table were less successful than the Boost table, so I moved away from SIMD in favor of in-table chaining early in the development of my libraries (although that's I choice I might have reconsidered if I'd known about Boost's performance at that time).

[joaquintides]

I am wondering when the system's CPU load is high, whether the performance of the SIMD tables will be impacted.

That's a good question. I'll try to summon @joaquintides, who developed boost::unordered_flat_map, to see whether he can shed any light on the matter.

I don't have any significant insight to provide here. The tables tested are single threaded, so an increase in CPU load from external threads/processes boils down to having time slicing for the table-related code and to more cache pressure. This would result in degraded performance, maybe in a higher degree for the more cache-friendly tables, but I'm speculating here.

[tnodir]

Can you please also add TommyDS?

[MaskRay]

It might be nice to have more analysis on memory consumption and code size.

Do you have recommendation for improvements on https://github.com/llvm/llvm-project/blob/main/llvm/include/llvm/ADT/DenseMap.h ? It is like Google's original dense hash map. It has strong constraints on code size and memory consumption, which might make migration to other hash maps difficult.
Its load factor 75% is low, though.

[aws-taylor]

+1 It would be awesome if the LLVM data structures were included in the analysis.

[nmehran]

This project has been a source of inspiration in some internal testing I have done -- thank you for your time and effort.

I want to share a folly environment you can develop and benchmark with, on any platform, using Docker: folly-docker-env

I have performed benchmarks for close to 90% of the libraries requested above, and will open-source the code and results in a matter of time.

[nmehran]

The shims branch is complete. Feel free to use them in your own projects.

• cwisstable
• excalibur
• folly_f14_fast
• folly_f14_node
• folly_f14_value
• folly_f14_vector
• fph_dynamic_map
• indivi_flat_umap
• llvm_dense_map
• pgm_dynamic
• tommyds_dyn
• tommyds_hash
• tommyds_lin
• qt6_hash

Use this container and branch to run Qt, LLVM, and Folly with c_cpp_hash_tables_benchmark. It works on Linux, macOS, and Windows, and includes scripts for scaling, huge pages, and live-mounting local code (or config) without rebuilding the container.

A minimal branch remains to demonstrate result stabilization techniques and share a few small surprises.

[gaujay]

Thanks @nmehran, did you have the chance to make progress on an updated table with all results?
I think lots a people would be interested to see a broader comparison with all these hash maps (including those small surprises).

[nmehran]

I've been quite busy, but I appreciate the follow up @gaujay @JacksonAllan.

It is quite easy to run the updated benchmark via the command ./run_hash_env.sh ./run_benchmarks.sh via hash_env_docker once you check out the c_cpp_hash_tables_benchmark/main branch in that repo. It includes the new "reinsert after erasure" and all of the shims (you just need to select them in the config.h file, as before).

I have ran the benchmarks on 20,000 - 20,000,000 and am happy to share the results. I've also decoupled the html and csv output logic from the main.cpp into a benchmark_output.h file and enhanced the heatmap and graphs. The new output code is open source in the dev branch here and most results are here: https://nmehran.github.io/hash-table-benchmark-report/

I had to make some choices as to what to include in this report. I've included top performers, where a hash table led in at least one category, classics (abseil), and popular demand (llvm, qt, folly). Others that were omitted were simply too slow (noncompetitive), or unfavorable (could not change the hash function, could not resize, etc).

[gaujay]

Looks great! The new interactive options are really nice, thanks.
Was it run on a Linux/GCC x64 machine, using murmur/fnv hashes?
(Note: you might want to add some cache_flush after insertions to reduce bias/noise)

The lib 'omm' seems to perform well but I don't see a shim for it in the repo.
Looking at graphs, I'm guessing it's a variation on Boost design (maybe without the anti-drift mechanism?)

[nmehran]

Thanks @gaujay, and you're welcome!

Yes, this was run on a standard Linux/GCC x64 machine, using the standard murmur/fnv hashes and benchmark definitions in this repo. The main difference is that I used a more advanced internal benchmark suite that employs several techniques to reduce noise and bias. This includes using a dedicated dispatcher core, cycling the test order for each run, implementing more robust cache flushing (including where you mentioned), and other tricks. It uses a task queuing system. I plan on adding some of these enhancements to the public dev branch when I get the time!

The omm library is a privately licensed C library for now, but it may become open-source in the future.

[oliness]

I tried it with boost 1.88 (current version). Boost is slightly better on my 1.8ghz i7 with 1.88, although it's still weaker at Iterating than anything else.

I tested by adding the boost path to a g++ include, do you have a one-liner to copy it into a single file like for 1.85? Would be good to keep it up to date.

[gaujay]

Finally published an updated version of the suite:
https://github.com/gaujay/c_cpp_hash_tables_benchmark

I added the 're-insert after erase' benchmark (to showcase tombstones effect)
along with some minor changes for better cross-platform repeatability.

I did it to test a new unordered map I was working on (flat_wmap).
Updated benchmark results with different compilers are available here:
https://github.com/gaujay/indivi_collection/tree/main/bench/flat_unordered

[oliness]

Looks great, would you accept a pr for changing the Boost test to use a checkout of boost_unordered?

Currently at 1.88, can then be quickly updated with new versions to track improvement/regression. Boost also have a number of related containers and I'd like to test them all.

[gaujay]

I like the idea but not sure this repo is the right place, as it still misses lots of things:

• not all shims support the new benchmark (some miss the new 'eraseN()' method)
• added the shims for folly and indivi, but not the libs
• not all libs support the new std::string data type

It would be nice however to incorporate some of the improvements to the original repo, including your proposition.
PS: I did some tests with boost 1.88 but I'm not sure there was any performance change since 1.84

[JacksonAllan]

Apologies for being absent for a while - I've been inundated with work. I've set aside a day mid-week to go through all the new developments and hopefully update the original repo. For now, let me just thank everyone (@gaujay, @oliness, @nmehran, @joaquintides, @martinus) for taking the time to help improve this project.

[gaujay]

Great! Just updated my fork again to remove the need for a new shim function (eraseN) to enable the re-insert benchmark.
Also added indivi lib as an embedded third-party for convenience (separate commit).

If you're interested, here are some notes about the other changes:

• Added some flush_cache calls between insert and other operations to avoid cache hotness bias.
  Now the performance for data fitting in L1 cache (i.e. small maps) is properly growing with size.
• Changed default operation count from 1000 to 500. This allow to keep curves details better (with less caching bias, for small maps especially) while keeping noise low. I also fixed the iteration count that was 1000 instead of the expected 5000.
• Replaced random engine/distribution with portable ones (std::mt19937_64 and modulo). Also use fixed seeds per run, so every benchmark use the same pseudo-random data.
• Changed blueprints integer keys from 0-N sequences to random values, also to avoid bias.