3 ms·

Experimenting with Robin Hood Hashing

26 points by signa11 11mo ago

rurban 11mo ago
Don't compare apples to oranges. unordered_map is so slow because it has to guarantee pointer stability, doing seperate chaining, whilst the open addressing hashtables doing probing and moving do not. They are at least 2x faster. Compare to linear probing, quadratic probing, double hashing, cuckoo, or swiss tables.
- tialaramex 11mo ago
  This seems like it has causality upside down. The pointer stability and weird bucketing API for std::unordered_map happen to be consequence of its design, and you're stupidly allowed to rely on them, and so it can't be trivially replaced with a better hash table. But most people didn't want this. std::unordered_map is just a more modern example of WG21's ability to clutch failure from the jaws of success than say std::vector<bool> The approach taken in std::unordered_map was a historical footnote when C++ 98 shipped, but what's crazy is that it didn't ship in C++ 98 it's from C++ 11. The ISO document specifying this archaic hash table design as the standard C++ hash table is from the Obama Presidency like Rust 1.0. So while maybe it's unfair in one sense, in another sense it makes absolute sense to compare against std::unordered_map because this is what you get out of the box.
  - SkiFire13 11mo ago
    > So while maybe it's unfair in one sense, in another sense it makes absolute sense to compare against std::unordered_map because this is what you get out of the box. That's not really a reason to omit comparisons with other better implementations.
    - tialaramex 11mo ago
      That's entirely fair, it would be nice to compare against other popular hash tables too.
  - gpderetta 11mo ago
    > [pointer stability] you're stupidly allowed to rely on them that's a bit unfair. Those are properties that can be very useful if you need them.
    - cb321 11mo ago
      Indeed. One of the main reasons STL defaults to a non-moving hash table is because "deleting in the middle of an iteration" was viewed as an important property. Like it or not (I do not), the entire container part of the original 1990s Stepanov STL was oriented around "iteration/iterators" as the high priority abstraction. Trying to think like a DB engineer is probably helpful here. Point or range query workloads absolutely afford different optimization/specializations than full table scan iterations. Any mistake here is more in thinking "one size fits all workloads". That may as much be a mistake of user communities as of language designers. (E.g. 'expert' advice like "just always use X" instead of "well, it depends...".) So, the charitable reading of tialaramex's "most people" is a weakly articulated assertion about workloads (though I absolutely agree with your specific point).
      - tialaramex 11mo ago
        I'm not at all convinced I need to be read "charitably". I think it's just straightforwardly true that most people writing C++ with a std::unordered_map do not use this property of std::unordered_map. In particular the "deleting arbitrary other entries while walking the unordered map" is a weird thing to be doing. It's not necessarily wrong but it's weird to need precisely this (which it so happens the std::unordered_map can do) but not e.g. inserting arbitrary stuff into the map (which might grow and thus invalidate your iterator) Note that "Delete yourself if you want" is an operation we can afford in the otherwise more optimal containers, so if that is the only deletion you want then you again over-paid by choosing this weird container type with pointer stability. I do not believe that Stepanov chose this particular hash table because this one had properties he specifically wanted, maybe you have a reference which can prove me wrong? I think this was the type he was most familiar with, and the STL is illustrating generic programming - an important idea - not showing off the most optimal data structures and algorithms.
vander_elst 11mo ago
I understood what's going on in this article only after reading the paper. It's might be good to define things s bit better in the article or say that the paper is a prerequisite for reading the article
- avadodin 11mo ago
  The paper itself is an overview that doesn't discuss the cache-friendly optimizations in the original 1986 PhD thesis so it feels like a hash table all the way down.
xxs 11mo ago
Aside already mentioned comparison to unordered_map, there appears to have a bug, on line 61: "p = (p + 1) & LenV". It should be mod (%) like the rest of the code. Morealso mod is slow in general and it should be replaced by bitwise and (&) and power of 2 sized map, then using LenV-1.
optimalsolver 11mo ago
Shoutout to unordered_dense, a drop-in replacement for C++ unordered_map that uses this: https://github.com/martinus/unordered_dense https://github.com/martinus/unordered_dense

26 points by signa11 11mo ago

rurban 11mo ago

Don't compare apples to oranges. unordered_map is so slow because it has to guarantee pointer stability, doing seperate chaining, whilst the open addressing hashtables doing probing and moving do not. They are at least 2x faster. Compare to linear probing, quadratic probing, double hashing, cuckoo, or swiss tables.

tialaramex 11mo ago
This seems like it has causality upside down. The pointer stability and weird bucketing API for std::unordered_map happen to be consequence of its design, and you're stupidly allowed to rely on them, and so it can't be trivially replaced with a better hash table. But most people didn't want this. std::unordered_map is just a more modern example of WG21's ability to clutch failure from the jaws of success than say std::vector<bool> The approach taken in std::unordered_map was a historical footnote when C++ 98 shipped, but what's crazy is that it didn't ship in C++ 98 it's from C++ 11. The ISO document specifying this archaic hash table design as the standard C++ hash table is from the Obama Presidency like Rust 1.0. So while maybe it's unfair in one sense, in another sense it makes absolute sense to compare against std::unordered_map because this is what you get out of the box.
- SkiFire13 11mo ago
  > So while maybe it's unfair in one sense, in another sense it makes absolute sense to compare against std::unordered_map because this is what you get out of the box. That's not really a reason to omit comparisons with other better implementations.
  - tialaramex 11mo ago
    That's entirely fair, it would be nice to compare against other popular hash tables too.
- gpderetta 11mo ago
  > [pointer stability] you're stupidly allowed to rely on them that's a bit unfair. Those are properties that can be very useful if you need them.
  - cb321 11mo ago
    Indeed. One of the main reasons STL defaults to a non-moving hash table is because "deleting in the middle of an iteration" was viewed as an important property. Like it or not (I do not), the entire container part of the original 1990s Stepanov STL was oriented around "iteration/iterators" as the high priority abstraction. Trying to think like a DB engineer is probably helpful here. Point or range query workloads absolutely afford different optimization/specializations than full table scan iterations. Any mistake here is more in thinking "one size fits all workloads". That may as much be a mistake of user communities as of language designers. (E.g. 'expert' advice like "just always use X" instead of "well, it depends...".) So, the charitable reading of tialaramex's "most people" is a weakly articulated assertion about workloads (though I absolutely agree with your specific point).
    - tialaramex 11mo ago
      I'm not at all convinced I need to be read "charitably". I think it's just straightforwardly true that most people writing C++ with a std::unordered_map do not use this property of std::unordered_map. In particular the "deleting arbitrary other entries while walking the unordered map" is a weird thing to be doing. It's not necessarily wrong but it's weird to need precisely this (which it so happens the std::unordered_map can do) but not e.g. inserting arbitrary stuff into the map (which might grow and thus invalidate your iterator) Note that "Delete yourself if you want" is an operation we can afford in the otherwise more optimal containers, so if that is the only deletion you want then you again over-paid by choosing this weird container type with pointer stability. I do not believe that Stepanov chose this particular hash table because this one had properties he specifically wanted, maybe you have a reference which can prove me wrong? I think this was the type he was most familiar with, and the STL is illustrating generic programming - an important idea - not showing off the most optimal data structures and algorithms.

vander_elst 11mo ago

I understood what's going on in this article only after reading the paper. It's might be good to define things s bit better in the article or say that the paper is a prerequisite for reading the article

avadodin 11mo ago
The paper itself is an overview that doesn't discuss the cache-friendly optimizations in the original 1986 PhD thesis so it feels like a hash table all the way down.

xxs 11mo ago

Aside already mentioned comparison to unordered_map, there appears to have a bug, on line 61: "p = (p + 1) & LenV". It should be mod (%) like the rest of the code. Morealso mod is slow in general and it should be replaced by bitwise and (&) and power of 2 sized map, then using LenV-1.

optimalsolver 11mo ago

Shoutout to unordered_dense, a drop-in replacement for C++ unordered_map that uses this: https://github.com/martinus/unordered_dense https://github.com/martinus/unordered_dense