A C++17 hash table benchmark, covering
- the compact separate chaining hash tables
- the tudocomp sparse compact hash tables
- Rigtorp's hash table
- Tessil's sparse hash table
- Google's sparse hash table
- Gregory Popovitch's Sparsepp
- C++ STL's
unordered_map
The external requirements are available as git submodules.
git submodule init
git submodule update
- Command line tools
- cmake
- make
- a C++17 compiler like gcc or clang
- glog for the tudocomp sparse compact hash tables
- celero for benchmarking
- gtest (optional) for tests
We use tudostats for measuring time and memory usage. The output is a JSON file.
Compile flags can be modified in the file CMakeLists.txt
.
The compile flag -DSTATS_DISABLED=1
disables tudostats.
When tudostats are enabled:
- the flag
-DMALLOC_DISABLED=1
disables memory measurement, which can speed up the benchmarks. - the flag
-DPRINT_STATS
lets tudostats print statistics of the separate chaining hash tables.
The hash tables to use can be enabled/disabled in defs.hpp
.
Fills hash tables with n
key-value pairs with 32-bit keys and v
bit values.
v
can range between 1 and 8. If you need larger value bit widths, you need to specify a larger integer type for the values (default_value_type
in defs.hpp
).
The same as randomcopy
with the difference that the hash table know in advance the minimum size 2^{k-16}
, where k
is the smallest power of two larger or equal to n
.
This allows compact hash tables to allocate buckets. The mock_key_type
in reservecopy.cpp
is the type in which a quotient can be stored.
Measures the time for insertion, deletions, successful and unsuccesful queries. Each experiment is conducted multiple times, and the average time with deviation is returned. Needs the celero library installed.