This seems like an implementation similar to the one Google engineers have given talks about (w/vectorization, etc) so it's cool to have more options to use a modern performant table like that.
Open-sourcing F14 for memory-efficient hash tables
21–30 of 50 posts
Re: Open-sourcing F14 for memory-efficient hash tables
#22Since the hashes uses open addressing wouldn't they be susceptible to hash poisoning attacks? Java plugged that hole in HashMap in Java 8 by reallocating lists over a certain length as balanced trees. But that strategy isn't possible with open addressing. https://www.nagarro.com/en/blog/post/24/performance-improvem...
Re: Open-sourcing F14 for memory-efficient hash tables
#23Since the hashes uses open addressing wouldn't they be susceptible to hash poisoning attacks? Java plugged that hole in HashMap in Java 8 by reallocating lists over a certain length as balanced trees. But that strategy isn't possible with open addressing. https://www.nagarro.com/en/blog/post/24/performance-improvem...
They use a byte for collision counting, and a byte is enough to reliably detect and punish DOS attackers on 32bit tables (max 4G keys). On 64bit tables I didn't do the math yet.
Re: Open-sourcing F14 for memory-efficient hash tables
#24It's funny how they bring up same birthday probability without referring to the "birthday problem" even if it supports their case for chunking even better.
For a hash table implementation, it's even more relevant that out of 180 people in a room, chances are > 99.999% that two people share a birthday (meaning collisions), whereas the chance that 15 people in that group are born in the same fortnight is still very small.
Re: Open-sourcing F14 for memory-efficient hash tables
#25Can this easily be ported to Rust?
Rust's standard hash table has recently been replaced with Hashbrown, which is a port of Google's SwissTable, which is a close relative of this hash table. So it's basically already done. :)
Re: Open-sourcing F14 for memory-efficient hash tables
#26I'm curious what Rust's implementation looks like in comparison now...
https://github.com/rust-lang/hashbrown is a port of Google's SwissTable algorithm (abseil flat_hash_map). It also uses SIMD filtering and has the potential to be quite good.
Which has been recently upstreamed to the standard library, replacing the old hash map implementation. (This sped up rustc a noticeable amount, incidentally.)
Re: Open-sourcing F14 for memory-efficient hash tables
#27Earlier quoted context omitted.
Have you compared to ska::flat_hash_map or khash? I’ve found the latter to be ideal if my keys/values were POD and the former otherwise. I’m not yet convinced that it’s actually better based on their website. std::unordered_map is infamously slow.
I did look at klib about a year ago. Honestly I don't recall whether I looked at khash in particular; I know I was also considering some of the other klib stuff for other uses. I did use Google's dense_hash_map for a time. For my application, the problem with implementations that use more traditional tombstone algorithms is that removing items from the table doesn't decrease the load, so that at some point the entire…
If I am right, if you delete all elements in F14, there will be no tombstone. However, if you delete some, there may still be some tombstones left. You may still need rehashing due to those remaining tombstones. In that sense, F14 is not eliminating the worst case; it makes the worst case happens less often. Then the question is how "less often". This probably depends on the access pattern.
What is your access pattern? Are insertions and deletions frequently interleaved? Or do you insert a batch and then delete another batch? It will be interesting to have a micro-benchmark to measure how the F14 strategy works in practice.
> I believe khash does as well.
Yes, khash uses the traditional tombstone solution. It rehashes in the same space when there are too many tombstones.
Re: Open-sourcing F14 for memory-efficient hash tables
#28There was a discussion thread on here recently about Google's Hash Table implementation. I wonder how the approaches and design considerations compare to each other.
I'm one of the authors. Seeing the Google presentation at CPPCon convinced us that the potential wins were worth the effort to productionize, but the similarity in the designs is a case of convergent evolution. Since then Google and Facebook have collaborated on a microbenchmark ( https://github.com/google/hashtable-benchmarks/ ), which shows that the algorithms have slightly different tradeoffs but neither dominates…
[deleted]
Re: Open-sourcing F14 for memory-efficient hash tables
#29Earlier quoted context omitted.
I did look at klib about a year ago. Honestly I don't recall whether I looked at khash in particular; I know I was also considering some of the other klib stuff for other uses. I did use Google's dense_hash_map for a time. For my application, the problem with implementations that use more traditional tombstone algorithms is that removing items from the table doesn't decrease the load, so that at some point the entire…
If I am right, if you delete all elements in F14, there will be no tombstone. However, if you delete some, there may still be some tombstones left. You may still need rehashing due to those remaining tombstones. In that sense, F14 is not eliminating the worst case; it makes the worst case happens less often. Then the question is how "less often". This probably depends on the access pattern. What is your access patter…
It would be nice to have a deeper understanding of how/why this works, but in practice it seems fine. Under a continuous insert and erase workload the number of chunks with an overflow fluctuates a bit but stays low enough to keep probe lengths short, so F14 never needs to rehash to clean them up. Batched adds and then removes might let you bias a bit toward having longer probes for the remaining keys, but it never gets too bad. A truly adversarial workload could make things pretty bad, but they could also just insert lots of keys that all have the same hash code.
See the steady_state_stats test at https://github.com/facebook/folly/blob/master/folly/containe...
Re: Open-sourcing F14 for memory-efficient hash tables
#30Since the hashes uses open addressing wouldn't they be susceptible to hash poisoning attacks? Java plugged that hole in HashMap in Java 8 by reallocating lists over a certain length as balanced trees. But that strategy isn't possible with open addressing. https://www.nagarro.com/en/blog/post/24/performance-improvem...
F14 supports stateful hashers, so in situations that need to be resilient to hash poisoning we can use a hasher designed for that purpose.