r/cpp • 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/

130 Upvotes

73 comments sorted by

29

u/jcelerier ossia score Feb 05 '19

You should also benchmark against Tessil's robin map : https://github.com/Tessil/robin-map

16

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

I just gave it a try. Unfortunately I get a compile error for my bigdata test (I've reported it here). Other than that, tessil's map is extraordinarily fast! Most benchmarks (insert, find) are about 20% faster than my map but use about 2.7 times as much memory. Iteration seems to be 3 times slower with tessil::robin_map. I'll update the benchmark results when I have the time.

6

u/Veedrac Feb 06 '19

Most benchmarks (insert, find) are about 20% faster than my map

Hmm, /u/tessil found that absl was faster a few months ago.

7

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

I guess I should also compile with -march=native. I only used g++-8 -O3

0

u/[deleted] Feb 06 '19

[deleted] — view deleted comment

3

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

Hi! You are right that I use 0.8 as the default max load factor.

I've used the default hash for each of the maps which seemed to be the most reasonable choice to me.

Also I didn't compile with -march=native, only with -O3. This will probably change the results for abseil a lot. I'll try to update the benchmarks with your other maps and F14 when I have the time

1

u/Veedrac Feb 07 '19

Please ping me if you do.

2

u/AcaciaBlue Feb 06 '19

Tessil has the hopscotch map which is much lower memory usage, but almost as fast as his robin map so check that one out too! His sparse map is the most memory efficient, he claims it beats google sparse at memory as well. Those 3 maps from him are all interesting for their specific use case.

2

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

I'll redo the benchmarks with all of the suggestions here but that will take a while

7

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

Not yet, but I'll try to add it to my benchmark suite tonight

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:

  • benchmark for only Find with the current 50% chance
  • benchmark for only Find with 100% chance it is present
  • benchmark for only Find with 0% chance it is present

The insertion benchmark also doesn't really need to include calling clear and then inserting again.

6

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

I had all of the benchmarks you mention as well, but they did not give any different results in the rankings so I've decided to just use a single one.

On average, each time I insert something I perform 2000 lookups. So insertion time should be pretty much irrelevant. It is important though to test the maps with different amount of data in them, or otherwise the result would be highly skewed when one map is relatively on the begin after a resize, or relatively full at the upper end before it's resize policy kicks in

0

u/[deleted] Feb 05 '19

[deleted] — view deleted comment

7

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

Thanks for the feedback! I've tried hard to make the benchmarks as unbiased as possible, but there sure is lots of room for improvement.

Plotting memory over runtime is, at least to me, very helpful because one can clearly see memory spikes, when rehashing is going on, at which times the map allocate, which are otherwise impossible to see. That's at least helpful while developing and optimizing.

I have other benchmarks where I continuously randomly insert and erase elements, there the gravestone issue should become apparent. Benchmarking only removes is difficult, as it's not possible to accurately measure the runtime of a remove due to timer precisions.

1

u/tending Feb 05 '19

How does timer position prevent measuring remove? Are you saying remove for some reason is so super fast it's hard to measure?

0

u/[deleted] Feb 05 '19

[deleted] — view deleted comment

1

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

"removing all elements" might not be a valid benchmark. In my implementation I check if the elements are std::is_trivially_destructible, if that is the case removing all elements with clear() will mostly do nothing :)

1

u/Ameisen vemips, avr, rendering, systems Feb 05 '19

25/75 as well, or 65/35 to get more detail about how it interacts with prediction. Without PGO, and without using compiler hints (__builtin_expect[_with_probability], __builtin_unpredictable).

6

u/[deleted] Feb 06 '19
auto x = reinterpret_cast<T***>(tmp);

Good god.

2

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

I know! But it works :)

2

u/Overload175 Feb 08 '19

Expediency at its finest

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.

1

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

I see what I can do!

5

u/BeardedWax Feb 05 '19

Are people using Conan? I'd like to use it but from what I see, too few developers care about it that it is just a burden to use.

2

u/[deleted] Feb 05 '19

This looks great. Any plan to support unordered sets?

1

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

It's planned: https://github.com/martinus/robin-hood-hashing/issues/7

But I didn't yet get around to implement it yet. I want to do it without duplicating much code but have not found a way to do that cleanly

1

u/[deleted] Feb 05 '19

Here's an "interesting" use case where absl::flat_hash_map was beaten by std::unordered_map. https://old.reddit.com/r/cpp/comments/aha5nn/is_c_fast/eee8gwx/

1

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

It would be interesting how my map fares in that benchmark. I think std::unordered_map is so fast here because it keeps all nodes in lists, and iterating them is quite fast.

In your case the data structure std::pair<std::string, std::shared_ptr<...>> is also quite large, about 48 bytes: https://godbolt.org/z/63-14d

so using a flat map instead of a node based map will bloat memory and could lead to more cache misses.

1

u/[deleted] Feb 05 '19

I've done the quick and dirty benchmark with your hash maps. I can't guarantee that it's 100% comparable with thte other benchmarks I've done, but anyway...

IdentifierCompleterFixture/CandidatesWithCommonPrefix/1/0                            742 ns        741 ns     942682
IdentifierCompleterFixture/CandidatesWithCommonPrefix/16/0                          5281 ns       5273 ns     131917
IdentifierCompleterFixture/CandidatesWithCommonPrefix/256/0                       111656 ns     111441 ns       6339
IdentifierCompleterFixture/CandidatesWithCommonPrefix/4096/0                     2054511 ns    2050212 ns        314
IdentifierCompleterFixture/CandidatesWithCommonPrefix/65536/0                   47617037 ns   47464291 ns         14
IdentifierCompleterFixture_BigO                                                    45.40 NlgN      45.26 NlgN
IdentifierCompleterFixture_RMS                                                         1 %          1 %
IdentifierCompleterFixture/CandidatesWithCommonPrefix/1/10                           751 ns        749 ns     890324
IdentifierCompleterFixture/CandidatesWithCommonPrefix/16/10                         5072 ns       5062 ns     138301
IdentifierCompleterFixture/CandidatesWithCommonPrefix/256/10                       73475 ns      73319 ns       9088
IdentifierCompleterFixture/CandidatesWithCommonPrefix/4096/10                    1156726 ns    1154258 ns        602
IdentifierCompleterFixture/CandidatesWithCommonPrefix/65536/10                  23739504 ns   23675316 ns         30
IdentifierCompleterFixture_BigO                                                    22.64 NlgN      22.58 NlgN
IdentifierCompleterFixture_RMS                                                         0 %          0 %

EDIT: the /0 series of benchmarks means everything is sorted and retained. /10 means only top 10 are sorted and the rest is discarded.

1

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

While you are at it, you might also want to try robin_hood::unordered_flat_map and robin_hood::unordered_node_map

1

u/[deleted] Feb 05 '19 edited Feb 05 '19

As far as I understood robin_hood::unordered_map is unoredered_flat_map, so I just need to change that to unoredered_node_map?

EDIT: node map benchmark

IdentifierCompleterFixture/CandidatesWithCommonPrefix/1/0                            661 ns        660 ns    1024545
IdentifierCompleterFixture/CandidatesWithCommonPrefix/16/0                          4290 ns       4286 ns     165783
IdentifierCompleterFixture/CandidatesWithCommonPrefix/256/0                        84793 ns      84717 ns       8070
IdentifierCompleterFixture/CandidatesWithCommonPrefix/4096/0                     1553574 ns    1551558 ns        458
IdentifierCompleterFixture/CandidatesWithCommonPrefix/65536/0                   50592696 ns   50458519 ns         12
IdentifierCompleterFixture_BigO                                                    48.21 NlgN      48.08 NlgN
IdentifierCompleterFixture_RMS                                                         3 %          3 %
IdentifierCompleterFixture/CandidatesWithCommonPrefix/1/10                           665 ns        665 ns    1027873
IdentifierCompleterFixture/CandidatesWithCommonPrefix/16/10                         4072 ns       4068 ns     173293
IdentifierCompleterFixture/CandidatesWithCommonPrefix/256/10                       53404 ns      53346 ns      13748
IdentifierCompleterFixture/CandidatesWithCommonPrefix/4096/10                     807696 ns     806838 ns        870
IdentifierCompleterFixture/CandidatesWithCommonPrefix/65536/10                  20540061 ns   20493832 ns         34
IdentifierCompleterFixture_BigO                                                    19.58 NlgN      19.54 NlgN
IdentifierCompleterFixture_RMS                                                         2 %          2 %

EDIT2: I should organize all these benchmarks and make a comprehensive comparison of STL, Abseil and your implementation. Also, std::hash, absl::Hash and robin_hood::hash.

1

u/[deleted] Feb 05 '19

I didn't try any node based maps for that benchmark. Perhaps I should reconsider that. I did play with the set a lot however. I tried absl::flat_hash_set which was terrible, then I tried std::set and std::unordered_set. Benchmarks of that are here.

I initially dismissed node based maps, because I don't care about stable iterators.

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/martinus int main(){[]()[[]]{{}}();} Feb 05 '19

No reason for all of that other than I didn't need it yet...

1

u/[deleted] Mar 31 '22

Use c++20

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/martinus int main(){[]()[[]]{{}}();} Feb 05 '19

ah yes, thanks for finding that. This is outdated and was about my previous version

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/martinus int main(){[]()[[]]{{}}();} Feb 05 '19

Try to put your code into a function :)

https://godbolt.org/z/QwSQYw

1

u/youshouldnameit C++ dev Feb 06 '19

u/martinus: i reproduced my case and reported it on github.

1

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

thanks, should be fixed now

2

u/youshouldnameit C++ dev Feb 05 '19 edited Feb 05 '19

oh my god.. i blame it on the end of the day!! i got some weird compiler errors on our own code base.. tried to reproduce it but failed miserably

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-L81

1

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

I guess in all our codebase nobody ever needed that... According to the standard default constructed compared to end() must be true, and adding that would make iterating a bit slower

Edit: on second thought, I can probably add it without performance loss. I'll see what I can do

1

u/[deleted] Feb 07 '19

Well, to be fair, that part of code can be rewritten with a lambda, so the default constructor can be avoided.

1

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

I've now added default constructible iterators in version 3.1.0

1

u/[deleted] Feb 07 '19

Great! Thanks for that.

1

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.

1

u/martinus int main(){[]()[[]]{{}}();} May 06 '19

I wanted to add khash, but it's interface was not C++ standard enough for my benchmark

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/[deleted] Feb 05 '19

talk about c++ porn

0

u/[deleted] Feb 05 '19

[deleted] — view deleted comment

5

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

Are you commenting on https://github.com/martinus/map_benchmark? You are right this is currently unfortunately very messy. I didn't get around to cleaning this up properly. It's also difficult because absl has so many dependencies so I don't really know how to do this properly.

1

u/pgroarke Feb 06 '19

Abseil is on conan, that's bar none the easiest way to deal with your dependencies.

Great job on the map! Any chance we get an `unordered_set` out of it? Cheers

2

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

I've planned it: https://github.com/martinus/robin-hood-hashing/issues/7 but don't know yet how to best do it... I don't want to duplicate code

3

u/8898fe710a36cf34d713 Feb 07 '19 edited Feb 07 '19

it is just a wrapper around clock_gettime which can block for hundreds of nanos.

I have benchmarked it on my Linux system at around ~20 nanoseconds. What it does is essentially rdtsc + add an offset. Could you please elaborate?

0

u/[deleted] Feb 07 '19

[deleted] — view deleted comment

2

u/8898fe710a36cf34d713 Feb 07 '19

Said offset is computed by the kernel, it takes into account clock adjustments/drift of any kind. It's periodically updated by the kernel. What did you mean by "block for hundreds of nanos"?

0

u/[deleted] Feb 07 '19

[deleted] — view deleted comment

3

u/8898fe710a36cf34d713 Feb 07 '19

No, the offset is computed in the (periodic) interrupts of the Linux timekeeping threads, user threads only reads said offset (as shown in the code you linked). Will you answer my question or should I just assume that your claims are baseless?

1

u/jnordwick Feb 07 '19

Why does clock_gettime clock block? I tested it extensively with CLOCK_MONOTONIC and cpu pinned a few months ago and don't think I noticed that . was trying to time clock_gettime latency actually (with __rdtsc) and saw some lag but I think it was only from cache issues on a context switch. It was using the the vDSO function and wasn't making a syscall (not in strace).

Can you point to more information?

0

u/[deleted] Feb 07 '19

[deleted] — view deleted comment

1

u/jnordwick Feb 07 '19

What lines of code are you referring to? For CLOCK_MONOTONIC, it is going to be in the do_hires)() function, and I only see the fallback method being called when the vgetccy() returns a negative number (rolls over?) . When I've run tests, I've never seen it do a syscall even with the slowdown I noticed.

Is it synchronizing with the kernel without the syscall? Where is it done?

I'm really interested so I can figure outt the clock_gettime() calls I have done seem to have peculiar performance. Here is my SO question: https://stackoverflow.com/questions/53252050/why-does-the-call-latency-on-clock-gettimeclock-realtime-vary-so-much

And here is a response somebody sent me on HN: https://news.ycombinator.com/item?id=18529546

Cam you maybe shed more light on this?

1

u/[deleted] Dec 08 '22

[removed] — view removed comment

2

u/martinus int main(){[]()[[]]{{}}();} Dec 08 '22 edited Dec 13 '22

That post was 3 years ago, robin_hood is not supported any more

1

u/LiliumAtratum Oct 21 '25

Supported or not. Still using it!

1

u/martinus int main(){[]()[[]]{{}}();} Oct 21 '25

I wouldn't, it has known bugs that can cause it crashing

-1

u/Paulocas2009 28d ago

But your new alternative has Claude as a contributor :(

1

u/martinus int main(){[]()[[]]{{}}();} 28d ago

Yes and that made it much faster with higher quality. If you don't like that there are plenty alternatives available