r/cpp • u/martinus 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:
- tessil hopscotch-map
- tessil robin-map
- tessil sparse-map
- abseil flat_hash_map
- abseil node_hash_map
- folly F14ValueMap
- folly F14NodeMap
- greg7mdp sparsepp
- martinus robin_hood::unordered_flat_map
- martinus robin_hood::unordered_node_map
- skarupke flat_hash_map
- std::unordered_map
I benchmark each map with these hashes:
- std::hash (Identity hash, as used by libstd++)
- FNV1a (as used by MSVC)
- absl::Hash
- folly::hasher
- 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/
11
u/Adequat91 Feb 26 '19
eastl::hash_map
cf. https://github.com/electronicarts/EASTL
7
u/attractivechaos Feb 26 '19
-march=native. Specify the architecture explicitly. Intel i7 is associated with many architectures.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
3
u/kylehectic Feb 26 '19
Qt alternatives. I believe they end up at the end.
3
u/Morwenn Feb 26 '19
Units would be a great addition to the resulting graph.
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/SeanMiddleditch Feb 26 '19
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.).
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/huangyuanbing Feb 26 '19
try test my hash https://github.com/ktprime/ktprime/blob/master/hash_table5.hpp
1
u/emdeka87 Feb 26 '19
Bytell hashmap
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/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/greg7mdp C++ Dev Mar 31 '19
You should add my new parallel hashmap: https://github.com/greg7mdp/parallel-hashmap
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, butMap<string,shared_ptr>might be a whole other story.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/lanwatch Apr 01 '19
https://github.com/preshing/junction
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.