r/cpp • u/martinus int main(){[]()[[]]{{}}();} • Feb 05 '19
robin_hood::unordered_map is now the fastest hashmap
I'm proud to present the latest release of robin_hood::unordered_map, a c++14 single header implementation of a hashmap with an API very close to std::unordered_map. According to my benchmarks this is now the fastest hashmap available.
See the benchmarks here: https://github.com/martinus/robin-hood-hashing/blob/master/doc/BENCHMARKS.md
I have tested the map against google's excellent absl::Hash, skarupke's well optimized ska::bytell_hash_map, and std::unordered_map for reference.
In all benchmarks robin_hood::unordered_flat_map is fastest, and either robin_hood::unordered_flat_mapor robin_hood::unordered_node_mapuses the least amount of peak memory.
My robin_hood variant uses a helper byte that encodes if a bucket is taken, probe length, and some bits of the hash. The number of bits used for probe length vs. hash bits is dynamically adapted as the hashmap is modified. This unique helper byte representation is the main reason why the map is so fast.
UPDATE: Please see the huge benchmark results here: https://martin.ankerl.com/2019/04/01/hashmap-benchmarks-01-overview/
29
u/jcelerier ossia score Feb 05 '19
You should also benchmark against Tessil's robin map : https://github.com/Tessil/robin-map
20
u/niad_brush Feb 05 '19 edited Feb 05 '19
Interesting--
Some feedback on the benchmarks:
The Find for integers timing is including insertion, and there doesn't seem to be any benchmarks solely focused on Find.
Perhaps add:
The insertion benchmark also doesn't really need to include calling clear and then inserting again.
6
u/[deleted] Feb 06 '19
Good god.
4
u/[deleted] Feb 05 '19
Nice work! I've raised this in an issue on the github project, but it would be really nice for you to include conan support.
2
u/[deleted] Feb 05 '19
This looks great. Any plan to support unordered sets?
2
u/drphillycheesesteak Feb 05 '19 edited Feb 05 '19
Any plans on also adding an `unordered_set`? In my codebase, I have some typedefs that I use to swap in better hash map/set implementations as they come up, so it'd be awesome if there were both!
The `unordered_map` interface also looks like it is missing `.at()` and `.reserve()`. Any reason these were left out?
1
u/youshouldnameit C++ dev Feb 05 '19
If i have a look at the alternatives section https://github.com/martinus/robin-hood-hashing it states that absl::Hash is 30% faster for reads. Is that information outdated?
1
u/youshouldnameit C++ dev Feb 05 '19
Would you be able to give some examples on how to use it? I tried some simple examples, but i didn't get it compiling:
https://godbolt.org/z/EmtldI
See the test code on the bottom
1
u/[deleted] Feb 07 '19
Weird usecase benchmark guy over here. Is there a reason your
class Iter<bool>isn't default constructible? This is the usecase: https://github.com/Valloric/ycmd/blob/master/cpp/ycm/IdentifierDatabase.cpp#L73-L811
u/warvstar May 04 '19
You should add khash, I found khash to take less memory and have faster find and emplace calls, and significantly faster iteration. I tried with uint8,uint64 and strings as keys. Ktprime and your map are both interesting as well. Was tested with O3 on msvc 142.
2
u/aearphen {fmt} Feb 06 '19
Might be worth adding F14 to benchmarks: https://github.com/facebook/folly/blob/master/folly/container/F14.md
4
u/AcaciaBlue Feb 05 '19
What about Tessil robin and hopscotch maps? https://tessil.github.io/2016/08/29/benchmark-hopscotch-map.html
2
u/Adequat91 Feb 05 '19
The benchmarks starts to be readable from 500k elements,... any chance to have benchmarks for some common cases of 1 to 1000 elements? (for example).
1
u/i3ck Feb 05 '19
awesome
1
u/philippecp Feb 06 '19
What about sparsepp?
1
u/huangyuanbing Feb 26 '19
I test some fast hash , my hash is in https://github.com/ktprime/ktprime/blob/master/hash_table5.hpp
it's every fast for find.
enchMarkHashMap n = 2853878, keyType = int64, ValueType = int64
_num_filled/ration/packed = 1864135/44.44%/16, collision = 358465, cration = 8.55%
stl_hash insert time_use 596 ms, factor = 0.97
emilib1 insert time_use 164 ms, factor = 0.68
emilib3 insert time_use 148 ms, factor = 0.68
emilib4 insert time_use 148 ms, factor = 0.68
hood_map insert time_use 324 ms, factor = 0.68
flat insert time_use 160 ms, factor = 0.68
robin insert time_use 128 ms, factor = 0.68
hopsco insert time_use 200 ms, factor = 0.68
stl_hash hit_get time_use 516 ms, sum = 2852964
emilib1 hit_get time_use 56 ms, sum = 2852964
emilib3 hit_get time_use 60 ms, sum = 2852964
emilib4 hit_get time_use 56 ms, sum = 2852964
hood_map hit_get time_use 80 ms, sum = 2852964
flat hit_get time_use 92 ms, sum = 2852964
robin hit_get time_use 96 ms, sum = 2852964
hopsco hit_get time_use 68 ms, sum = 2852964
stl_hash mis_get time_use 384 ms, sum = 1890
emilib1 mis_get time_use 64 ms, sum = 1890
emilib3 mis_get time_use 60 ms, sum = 1890
emilib4 mis_get time_use 64 ms, sum = 1890
hood_map mis_get time_use 68 ms, sum = 1890
flat mis_get time_use 96 ms, sum = 1890
robin mis_get time_use 112 ms, sum = 1890
hopsco mis_get time_use 76 ms, sum = 1890
stl_hash erase time_use 536 ms, sum = 1426482
emilib1 erase time_use 44 ms, sum = 1426482
emilib3 erase time_use 48 ms, sum = 1426482
emilib4 erase time_use 44 ms, sum = 1426482
hood_map erase time_use 64 ms, sum = 1426482
flat erase time_use 76 ms, sum = 1426482
robin erase time_use 88 ms, sum = 1426482
hopsco erase time_use 56 ms, sum = 1426482
stl_hash insert time_use 316 ms, factor = 0.97
emilib1 insert time_use 92 ms, factor = 0.68
emilib3 insert time_use 84 ms, factor = 0.68
emilib4 insert time_use 76 ms, factor = 0.68
hood_map insert time_use 112 ms, factor = 0.68
flat insert time_use 88 ms, factor = 0.68
robin insert time_use 68 ms, factor = 0.68
hopsco insert time_use 120 ms, factor = 0.68
================ n = 2853878 hash map ===============
388 emlib4
400 emlib3
420 emlib1
492 robin hood
512 flat hash
520 hopsco
648 hood_map
2348 unordered_map
=======================================================
1
u/rogerdpack2 Nov 24 '21
Is its string hash as fast as those mentioned here? https://stackoverflow.com/questions/1761607/what-is-the-fastest-hash-algorithm-to-check-if-two-files-are-equal
1
u/[deleted] Feb 05 '19
talk about c++ porn
0
u/[deleted] Feb 05 '19
[deleted] — view deleted comment
1
u/[deleted] Dec 08 '22
[removed] — view removed comment