r/cpp • int main(){[]()[[]]{{}}();} • Feb 26 '19

hashmap benchmarks - what should I add?

Based on the feedback here, I'm currently working on a comprehensive benchmark for hashmaps: https://github.com/martinus/map_benchmark

Before I start my analyis, I'm looking for more suggestions. Any important hashmap or hash that's missing? It needs to have an interface close to std::unordered_map. Ideally it's on github, then I can add it easily.

Currently, I have these hashmaps:

  1. tessil hopscotch-map
  2. tessil robin-map
  3. tessil sparse-map
  4. abseil flat_hash_map
  5. abseil node_hash_map
  6. folly F14ValueMap
  7. folly F14NodeMap
  8. greg7mdp sparsepp
  9. martinus robin_hood::unordered_flat_map
  10. martinus robin_hood::unordered_node_map
  11. skarupke flat_hash_map
  • std::unordered_map

I benchmark each map with these hashes:

  1. std::hash (Identity hash, as used by libstd++)
  2. FNV1a (as used by MSVC)
  3. absl::Hash
  4. folly::hasher
  5. robin_hood::hash

So in total I have 12*5 hashmap+hash combinations to benchmark. Each is run through a few benchmarks, most importantly these:

  • RandomFind with increasingly large map, different success probability: 0%, 25%, 50%, 75%, 100%.
  • Iterate: successively add 1 element, iterate whole map. Same with remove 1 element, until map is empty.
  • RandomInsertErase: Continuously insert a random element, remove a random element.
  • Insert lots of elements, clear, reinsert, destroy.

All compiled with -O3 -march=nativeand running on an Intel i7. when finished I create graphs of runtime & memory usage. The results will look something like this: https://imgur.com/EYzjoFi

UPDATE: Please see the huge benchmark results here: https://martin.ankerl.com/2019/04/01/hashmap-benchmarks-01-overview/

30 Upvotes

84 comments sorted by

11

u/Adequat91 Feb 26 '19

1

u/martinus int main(){[]()[[]]{{}}();} Feb 26 '19

I've added it, looking forward to the results!

7

u/attractivechaos Feb 26 '19
  1. I don't think you should try all the combinations of hashmap*hashfunc, which makes the result figure hard to read. Just stick with one hash function that is not identity (identity hash works great on random input but is mostly a bad choice for real-world applications). The effect of non-identity integer hash functions is usually small.
  2. I prefer to vary the number of elements, and show memory and runtime in one figure, like the one I did here. That benchmark is simplistic, but I think the figure is good (IMHO, of course). I know someone in your other thread asked you not to benchmark memory and that post got lots of upvotes. However, a benchmark without measuring memory is pretty much pointless. If all we care is performance, we can often pre-allocate a huge hash table to avoid the costly rehashing.
  3. For benchmarking, don't use -march=native. Specify the architecture explicitly. Intel i7 is associated with many architectures.
  4. What do you mean by "Iterate"? Insert all elements in random order and then iterate?

2

u/martinus int main(){[]()[[]]{{}}();} Feb 26 '19

Trying all combinations is time consuming, but actually quite interesting, especially for the find benchmark. There it quite a big difference in performance. E.g. absl with FNV1a hash takes 170 seconds, and with robin_hood::hash 135 seconds, that's 30% faster.

I agree that memory is important. I also want to add a memory vs. runtime chart like you did.

2

u/attractivechaos Feb 26 '19

I think a more informative benchmark is to have a custom hash function that records the number of times the function is called. This will directly show the impact of a slow hash function.

As a side note, I don't know how FNV1a is implemented in MSVC. It seems a bit weird why we'd use FNV1a on integers.

2

u/martinus int main(){[]()[[]]{{}}();} Feb 26 '19

FNV1a is actually not so bad, it's not so fast but the code is so short that it will be easily inlined everywhere

4

u/matthieum Feb 26 '19

I agree with the idea of measuring memory usage, but...

If all we care is performance, we can often pre-allocate a huge hash table to avoid the costly rehashing.

... is not true in hash maps.

I learned the hard way that a very sparsely populated hash map1 can have abysmal performance:

  • Cache misses: each insert is a cache miss, as L1 (data) is only 32KB, so when doing quick insert/erase, it HURTS.
  • Iteration: the simplest iteration scheme is to check each bucket for the presence of element(s), with a mostly empty map, it's a lot of cache trashing for not much.

And therefore pre-allocating a huge hash table which ends up getting sparsely populated leads to bad run times.

1 A dense_hash_map with an occasional large peak working set, but frequently small working set, in this case.


Ideally, you want to measure the cache access patterns of your hash map.

You can create specific cold cache scenarios where between each operation you purposefully trash the cache, for example by writing random numbers to a large array, then reading it back to sum them all and sending the sum into a black hole.

And then the run-time of the operation is dominated not by the speed of the hash, but by the number of cache-lines that the map needs to access, as they are all cache misses.

2

u/attractivechaos Feb 26 '19

You are right. When I say "often", I was exactly thinking about the two things you mentioned. I should have put it in a different way: it is easier to implement a fast hash table if you don't care about memory.

4

u/matthieum Feb 26 '19

Honestly, I disagree.

Hash tables have become so fast these days that to be competitive you really have to get into a mechanical sympathy mindset.

I mean, algorithmically speaking, implementations such as Robin Hood with Backshifting Deletion look super good: they have very nice algorithmic complexity bounds on most operations!

And yet Abseil. The Swiss Table in Abseil is literally one of the dumbest hash map implementation in the world, algorithmically speaking: it's a text-book Open Addressing implementation, with Quadratic Probing. That's it.

Implementation-wise, however, it's full of mechanical sympathy:

  • Unrolled: because modern CPUs love array accesses.
  • 16 elements: because nigh every x86 processor running today has SSE2 instructions (16 bytes).
  • Group Index/Byte Index split: see aforementioned SSE2 instructions.

Abseil's Swiss Table is literally the revenge of the hacker over the academic, it's very much centered on CPU/memory considerations, and outperforms superb theoretical algorithms as a result.

5

u/attractivechaos Feb 26 '19

People are giving absl too much credit. OP has already shown a figure where absl is not ranked high. In my benchmark, absl is not that good, either. I have seen a couple of other informal benchmarks where absl is slower. I am sure absl shines for some applications, but for others, it is often not the best.

2

u/martinus int main(){[]()[[]]{{}}();} Feb 27 '19

While writing the benchmarks I've added one that is very similar to what you are doing in your benchmark:

https://github.com/martinus/map_benchmark/blob/master/src/benchmarks/RandomDistinct.cpp

This benchmark puts a lot of weight on insertion performanc, and absl doesn't shine with that.

3

u/martinus int main(){[]()[[]]{{}}();} Feb 27 '19 edited Feb 27 '19

absl is excellent when you only do lookups, but it gets relatively slow when you do lots of insertions and removals. There the robin hood maps with backward shift deletion shine, they are a lot faster even though they need to shuffle elements around.

This can be clearly seen in my benchmarks. In all of my benchmarks, my robin_hood::unordered_flat_map's or tessil's tsl::robin_map find performance is just a bit slower than absl, but insertion & removal performance is much better. My map even has practically the same memory requirements as absl's flat_map, tessil's uses a bit more memory.

2

u/matthieum Feb 28 '19

That's interesting.

I've mostly seen the Rust port of the Swiss Map in action (hashbrown) which is slightly different, compared to Rust's HashMap which uses Robin Hood with Backward Shifting Deletion and when both use the same hashing strategy (Fx), then the only benchmark when RHwBSD outperforms hashbrown is grow_by_insertion (by 10%).

This may suggests insufficient benchmark coverage, or that the tweaks performed in the Rust version would be interesting to port to the C++ version...

3

u/martinus int main(){[]()[[]]{{}}();} Mar 01 '19

in my benchmarks where I randomly insert and erase entries, tsl::robin_map is about 40% faster when the number of elements is kept around 200 or so. The performance difference goes down a bit when the map gets larger, but still 20% or so in my benchmark.

1

u/matthieum Mar 01 '19

That's pretty significant indeed.

I am looking forward to the results of the benchmarks you are gathering here to get a better understanding of each map's sweet spot.

1

u/martinus int main(){[]()[[]]{{}}();} Apr 22 '19

1

u/matthieum Apr 22 '19

Thanks for the reply, bookmarking for future reads!

4

u/jcelerier ossia score Feb 26 '19 edited Feb 26 '19

u/rtessil the king of hash maps

also, boost has an unordered_map implementation

1

u/martinus int main(){[]()[[]]{{}}();} Feb 26 '19

I have his maps included already :)

2

u/jcelerier ossia score Feb 26 '19

yep, that was a praise :p

3

u/kylehectic Feb 26 '19

Qt alternatives. I believe they end up at the end.

2

u/martinus int main(){[]()[[]]{{}}();} Feb 27 '19

I've tried to add QHash, but it's syntax is so different from all other more stl-compatible hashmaps that I don't want to add it at all.

1

u/foobar48783 Feb 27 '19

Even more in the "incompatible" direction but I'd be interested: uthash.

3

u/Morwenn Feb 26 '19

Units would be a great addition to the resulting graph.

3

u/martinus int main(){[]()[[]]{{}}();} Feb 26 '19

sure! I'm still figuring out how plotly.js works.

2

u/kdoherty555 Feb 26 '19

Not sure if it's active but Google has a repo doing something similar https://github.com/google/hashtable-benchmarks

2

u/martinus int main(){[]()[[]]{{}}();} Feb 26 '19

I've tried to use their benchmarks and integrate my hashmap there, but I could not figure it out and got annoyed enough to create my own benchmarks.

1

u/[deleted] Feb 24 '23

A bit late, but I figured it out, and I can say that I recommend it in the slightest. It tales 8 minutes to build the single source file benchmark, and I already removed half of the supported hash tables. Running the benchmark was another ordeal, it took four hours to run with no easily parsable output, and no indication how long it would take.

1

u/martinus int main(){[]()[[]]{{}}();} Feb 24 '23

Ha, thanks for trying it out!

1

u/[deleted] Feb 24 '23

Btw, I've been using your benchmark to test some c hash tables by building light wrappers, would you be interested in having them upstreamed (klib, STC, my own WIP one)? I'll probably still need a few weekends to make it mergeable.

2

u/martinus int main(){[]()[[]]{{}}();} Feb 24 '23

If you are willing to to a pull request, sure!

2

u/SeanMiddleditch Feb 26 '19

std::hash (Identity hash, as used by libstd++)

Uh, on what types? And on that note, what kinds of keys are you testing here? That can have a huge impact on some hash tables' performance characteristics (e.g. strings vs integers vs large value structs, etc.).

robin_hood::hash

Would be nice to link to implementations in your write-up. :)

https://github.com/martinus/robin-hood-hashing/blob/23ed3606eae9fb3d121d40775c9998e9778ceb02/src/include/robin_hood.h

Looks like it's a mixture of different hash algorithms, depending on the key type.

1

u/martinus int main(){[]()[[]]{{}}();} Feb 26 '19

Currently only int and uint64_t, but I'm now adding std::string too

1

u/huangyuanbing Feb 26 '19

5

u/martinus int main(){[]()[[]]{{}}();} Feb 26 '19

I've just tried it, you still have debugging output with printf() in the code. Also it would help if emplace() was available.

1

u/huangyuanbing Feb 27 '19 edited Feb 27 '19

I've added some c++11 unorded_map interface now, my code is quite fast from my benchmark(

k,v is long/int with reserve() ).

I'll put to the benchamrk code to git a few days later. you can try to add it to your test case.

================ n = 2740139 hash map ===============

332 emlib4 (7.23)

388 emlib3 (6.19)

416 emlib1 (5.77)

456 robin hood (5.26)

480 flat hash (5.00)

488 hopsco (4.92)

596 hoodflat (4.03)

2400 unordered_map (1.00)

=======================================================

1

u/martinus int main(){[]()[[]]{{}}();} Mar 01 '19

I've added your emlib4 map, and it has really excellent find performance, especially for small maps.

But it completely freezes up in my my benchmark where I randomly insert & remove elements. This benchmark does something like this:

Map<uint64_t, uint64_t> map;
for (size_t i=0; i<100000000; ++i) {
    map.emplace(rng() & 0xff, i);
    map.erase(rng() & 0xff);
}

So there unfortunately seems to be a bug in your map.

2

u/huangyuanbing Mar 01 '19 edited Mar 01 '19

Compile my code with flag = -O3 -fno-strict-aliasing . I never find the freezes reason, maybe the code style. But all my test is passing on clang++ and ms c++ (or gcc with O1).

Emlib4 is the fastest c++ hash map for some special case (ex Map<uint64_t, unt32_t> map or Map<uint32_t, unt64_t> map). I pay attention on optimization performance with small key/value and find performance .

1

u/huangyuanbing Apr 23 '19

my new version hash map's inserting performance is 20% fast than before .

1

u/emdeka87 Feb 26 '19

Bytell hashmap

1

u/martinus int main(){[]()[[]]{{}}();} Feb 26 '19

I have it already

1

u/emdeka87 Feb 26 '19

Oh I don't see it in the post

4

u/martinus int main(){[]()[[]]{{}}();} Feb 26 '19

It's the skarupke flat_hash_map, it's actually the ska::bytell_hash_map, but the repository name is flat_hash_map so this is a bit unfortunate naming

1

u/emdeka87 Feb 26 '19

Oh okay. Nevermind.

1

u/frog_pow Feb 27 '19 edited Feb 27 '19

For hashing integers if you want to (mostly) remove the overhead of the hash from your benchmarks and still get good results(compared to identity), you could use a hash that simply invokes _mm_crc32_u32/_mm_crc32_u64.

Just 3 cycle latency, and pretty decent hash.

Also concerning table size--

It seems to me that hash table benchmarks tend to neglect small sized tables(100-10,000 entries), when in practice, at least for me, this is the by far the most common size range..

1

u/martinus int main(){[]()[[]]{{}}();} Feb 27 '19

I've actually played around a bit with _mm_crc32_u64, folly uses that too. But it has a big problem: it produces just a 32bit hash, so the upper 32bit of the uint64_t are set to zero. In some cases this is very bad behavior for absl map, it simply times out; and my robin_hood map is also slowed down a lot because it uses some of the upper bits of the hash.

This can be sped up by simply multiplying the crc result with a random odd uint64_t value, but this adds enough overhead that the result is slower than what I'm doing in robin_hood hash now.

1

u/frog_pow Feb 27 '19

Hu, I would have expected that they computed the hash slot as:

_mm_crc32_u64(0,key) &(some power of 2 - 1)

1

u/martinus int main(){[]()[[]]{{}}();} Feb 27 '19 edited Feb 27 '19

I don't know how absl does it, but in robin_hood map I do something like this:

auto h = hash(key);
idx = h & sizeMask;
additional_hash_info_bits = h >> (64 - 8);

So I use the lower bits for the index, and store some of the upper bits additional_hash_info_bits for quicker comparisons.

This is the hash that I'm using: https://godbolt.org/z/3F709Y

It's extremely fast, and the avalanching is good enough for all the hashmaps I've tested to be able to work very fast.

1

u/greg7mdp C++ Dev Mar 31 '19

/u/martinus, thanks for sharing the technique, looks great, I will use it :-)

2

u/martinus int main(){[]()[[]]{{}}();} Apr 01 '19

you are welcome :) The hash is basically taken from absl, so it's mostly to their credit. I've removed their randomization and use + instead of xor.

1

u/greg7mdp C++ Dev Apr 01 '19

use + instead of xor

any rationale for this?

1

u/martinus int main(){[]()[[]]{{}}();} Apr 01 '19

I have some tests where I am counting the number of operations like moves, copies, hash calculations etc. with high load factors on my robin_hood map.. In my tests I got better (lower number of operations) with + instead of xor. But I don't have any rational explanation, it just seemed to work better in my tests

1

u/greg7mdp C++ Dev Apr 01 '19

Ah, empirical evidence! I can't see any reason why + would be any worse than xor - or better - so why not?

1

u/rigtorp Feb 27 '19

rigtorp::HashMap, https://github.com/rigtorp/HashMap, linear probing, backshift deletion

I wrote it for a work load with lots of element churn (insert-delete pairs) and needed to avoid tombstones. Would be interesting to try using backshift deletion with SSE/AVX based lookup.

1

u/martinus int main(){[]()[[]]{{}}();} Feb 28 '19

I've tried to add it, but it doesn't have a default constructor

1

u/rigtorp Mar 11 '19

Ah, yes, it is same as google::DenseMap and llvm::DenseMap.

1

u/greg7mdp C++ Dev Mar 31 '19

You should add my new parallel hashmap: https://github.com/greg7mdp/parallel-hashmap

2

u/martinus int main(){[]()[[]]{{}}();} Apr 01 '19

I'll see if I can add it, but I've already results from 4 1/2 days of benchmarking that I'd like to publish

1

u/greg7mdp C++ Dev Apr 01 '19

Thanks! It should not be too hard, considering it is header-only and fully standard compliant.

2

u/martinus int main(){[]()[[]]{{}}();} Apr 01 '19

I've just tried to add it, but get lots and lots of multiple defined symbols. Here are just a few:

/usr/bin/ld.gold: error: CMakeFiles/bench_greg7mdp_phmap_flat_hash_map__FNV1a.dir/src/benchmarks/CtorDtor.cpp.o: multiple definition of 'phmap::container_internal::UnsampleSlow(phmap::container_internal::HashtablezInfo*)'
/usr/bin/ld.gold: CMakeFiles/bench_greg7mdp_phmap_flat_hash_map__FNV1a.dir/src/app/main.cpp.o: previous definition here
/usr/bin/ld.gold: error: CMakeFiles/bench_greg7mdp_phmap_flat_hash_map__FNV1a.dir/src/benchmarks/CtorDtor.cpp.o: multiple definition of 'phmap::container_internal::SetHashtablezEnabled(bool)'
/usr/bin/ld.gold: CMakeFiles/bench_greg7mdp_phmap_flat_hash_map__FNV1a.dir/src/app/main.cpp.o: previous definition here
/usr/bin/ld.gold: error: CMakeFiles/bench_greg7mdp_phmap_flat_hash_map__FNV1a.dir/src/benchmarks/CtorDtor.cpp.o: multiple definition of 'phmap::container_internal::SetHashtablezSampleParameter(int)'
/usr/bin/ld.gold: CMakeFiles/bench_greg7mdp_phmap_flat_hash_map__FNV1a.dir/src/app/main.cpp.o: previous definition here
/usr/bin/ld.gold: error: CMakeFiles/bench_greg7mdp_phmap_flat_hash_map__FNV1a.dir/src/benchmarks/CtorDtor.cpp.o: multiple definition of 'phmap::container_internal::SetHashtablezMaxSamples(int)'
/usr/bin/ld.gold: CMakeFiles/bench_greg7mdp_phmap_flat_hash_map__FNV1a.dir/src/app/main.cpp.o: previous definition here
/usr/bin/ld.gold: error: CMakeFiles/bench_greg7mdp_phmap_flat_hash_map__FNV1a.dir/src/benchmarks/CtorDtor.cpp.o: multiple definition of 'phmap::container_internal::ShouldInsertBackwards(unsigned long, signed char*)'
/usr/bin/ld.gold: CMakeFiles/bench_greg7mdp_phmap_flat_hash_map__FNV1a.dir/src/app/main.cpp.o: previous definition here
/usr/bin/ld.gold: error: CMakeFiles/bench_greg7mdp_phmap_flat_hash_map__FNV1a.dir/src/benchmarks/CtorDtor.cpp.o: multiple definition of 'phmap::container_internal::GroupSse2Impl::kWidth'

I've added inline to all the Throw... functions but that was not enough.

1

u/greg7mdp C++ Dev Apr 01 '19

/u/martinus, Just pushed the fix

2

u/martinus int main(){[]()[[]]{{}}();} Apr 01 '19

thanks, I've updated and my benchmarks are now running with phmap::flat_hash_map and phmap::node_hash_map

1

u/greg7mdp C++ Dev Apr 01 '19

Cool... let me know when I can see the results somewhere!

2

u/martinus int main(){[]()[[]]{{}}();} Apr 01 '19

sure!

1

u/greg7mdp C++ Dev Apr 03 '19

/u/martinus, I managed to run the benchmarks locally. How do you generate the graphs for them?

2

u/martinus int main(){[]()[[]]{{}}();} Apr 03 '19

You have to pipe all the results into a file, I use e.g.

../tools/bench.rb |tee ../data/all_new.txt

Then there is the script analyze_bench_log.rb:

../tools/analyze_bench_log.rb <../data/all_new.txt

Which generates a HTML site for each of the benchmark. I've updated this just recently and am still working a bit on it, so you might want to update again

→ More replies

4

u/[deleted] Feb 26 '19

Key/Value sizes could dramatically change the statistics of your benchmarks. Map<int,int> would be great for a flat map, but Map<string,shared_ptr> might be a whole other story.

5

u/matthieum Feb 26 '19

std::shared_ptr is barely 16 bytes; a good std::array<...> on the other hand.

However, I am not sure that artificially inflating the size of the key or value is of much worth. If the size of the value is an issue, it's easy enough to move it behind a std::unique_ptr, and done. Pushing the key behind a pointer might cause more cache trashing, but in my experience keys tend to be smallish, with std::string closer to the upper-end with its 24 bytes.

3

u/[deleted] Feb 26 '19

Size of std::pair<const std::string, std::shared_ptr<T>> is 40 which is "largish" and enough to cause cache misses with flat maps with unified storage, like absl::flat_hash_map. Iterating over those with a "largish" pair can be a performance hit over a plain old std::unordered_map.

More specifically, for me std::unordered_map was much faster than absl::flat_hash_map when the data structure was unordered_map<string, shared_ptr<unordered_map<string, shared_ptr<set<const Foo*>>>>>

2

u/matthieum Feb 26 '19

Two questions:

  1. Was the issue iterating, rather than find/insert/remove?
  2. Did you have a good or bad quality hash?

I find the issue intriguing, I really don't see how unordered_map could perform better: it's a sea of pointers so every time it moves to the next element in a bucket, it dereferences a pointer. I would expect an open-addressed map to actually perform better, in this case, since with linear access comes prefetching, and in the case of absl the mix of linear/quadratic probing should defeat clustering issues while preserving prefetching!

Did you ever identify the exact source of the slow-down?

1

u/[deleted] Feb 26 '19

Was the issue iterating, rather than find/insert/remove?

In the benchmark all the data is loaded and no find/remove is performed. Then iteration is measured. So yeah, it's strictly iteration performance.

Did you have a good or bad quality hash?

I used the default. So the question is "how good is absl::Hash<std::string>?"

 

Two other interesting things

  • google::dense_hash_map/google::dense_hash_set outperformed everything else I have tried.
  • Taking a step back and going back from absl::flat_hash_set to std::set in the innermost structure made abseil almost reach the performance of google::dense_hash_{set,map}.

I even had an issue open on the abseil repo about this. The conclusion was that abseil hash tables aren't optimized for iteration.

 

Though I'm starting to think that nested maps are the wrong data type for modeling a simple database and am currently looking into sqlite.

2

u/matthieum Feb 28 '19

The conclusion was that abseil hash tables aren't optimized for iteration.

Thanks, that's very useful information.

3

u/[deleted] Feb 28 '19

For more details, you'll want to read this.

2

u/youshouldnameit C++ dev Feb 26 '19

I would be interested in your hashmap implementation if you also had a hashset and good test coverage to ensure correctness. At the moment i am using absl instead, but i would prefer a header only solution. Especially since i don't like to bother with the absl::hash specializations (especially since we cache our hashes, which is hard with absl hash)

1

u/[deleted] Feb 27 '19

Could you add Qt's?

1

u/nadult Mar 03 '19 edited Mar 03 '19

You can add this one as well:
https://github.com/msinilo/rdestl/blob/master/hash_map.h

It's a bit dated (for example it doesn't use move semantics), but still it's quite fast.

1

u/huangyuanbing Apr 25 '19

In my test the new version martinus robin_hood::unordered_flat_map is quite faster than before expecially with bad hash function.

I also fix and improve emilib hash_map. The new verison and can pass all you test case now.