5 ms·
Open-sourcing F14 for memory-efficient hash tables
- deleted 7y ago[deleted]
- dclusin 7y agoThere 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.
- jhalstead 7y agoThis thread has some info: https://groups.google.com/forum/m/#!topic/hashtable-benchmarks/-nT-3fESXq8 https://groups.google.com/forum/m/#!topic/hashtable-benchmar.... Edit: Or at least I think that's relevant to this announcement. I don't know enough about it to say for sure.
- nwallin 7y agoThey are very, very similar. The hashes are two level: one is fairly traditional. You take the first k bits from the hash and look that up in a table. The second layer is 128 bit blocks. (one SSE/NEON register) This block contains 14 8 bit blocks, where the top bit is a tombstone marker, and the bottom 7 bits are the k+1 though k+7 bit from the hash. (or the top 7 bits? not sure. it's 7 bits from the hash that aren't used in the top layer) It uses SSE instructions to identify which of the 14 blocks to do a full key compare with. Both of them have two variants, one which guarantees that references to keys and values will remain valid even if iterators are invalidated, and another which is faster but iterator invalidation invalidates references to keys or values. IMHO it looks like the Folly team saw the Abseil presentation last year and said, "That's a good idea, we should do that." abseil presentation: https://www.youtube.com/watch?v=ncHmEUmJZf4 https://www.youtube.com/watch?v=ncHmEUmJZf4 It's super interesting.
- ngbronson 7y agoI'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/ https://github.com/google/hashtable-benchmarks/), which shows that the algorithms have slightly different tradeoffs but neither dominates the other.
- deleted 7y ago[deleted]
- mappu 7y agohttps://news.ycombinator.com/item?id=17176713 https://news.ycombinator.com/item?id=17176713 perhaps?
- usefulcat 7y agoI've recently started using Folly's F14 hash map implementation (specifically, F14ValueMap--my keys and values are relatively compact) and it's the fastest unordered associative container I've yet found. This is for an application that repeatedly adds to and removes from the map. In particular, it's faster than a custom solution using open addressing that I had written that is pretty much optimal for this particular application (for an open addressing implementation, that is). I do wish it could be used header-only out of the box, but still a great library.
- stochastic_monk 7y agoHave 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.
- usefulcat 7y agoI 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 table has to be recreated. For my application, worst case performance is far more important than average performance. dense_hash_map definitely behaves as described above, and (from a quick look at the code) I believe khash does as well. I haven't looked at ska::flat_hash_map but thanks for the tip.
- ngbronson 7y agoNon-SIMD algorithms work better in some cases, for example if you look up the same key over and over (so the control flow is predictable) or when all of the data is in the L1. The SIMD approach tends to be more robust inside a larger program where there's less chance for branch prediction and caching to help you.
- saagarjha 7y ago> Those options are slow, risky (clients can change the key), incompatible (maybe we can try again after proxy iterators work), and ugly, respectively. After careful deliberation, we chose ugly, using const_cast to make the key mutable just prior to its destruction during rehash. You can't win them all, I guess… Also, TIL that invalidating iterators does not actually invalidate references to keys and values: > The standard guarantees reference stability: References and pointers to the keys and values in the hash table must remain valid until the corresponding key is removed.
- alexhutcheson 7y agoHasn't this been open-sourced since at least last March? https://github.com/facebook/folly/commit/93d49bcf9a44d6b2d9ce2c0a1f309457b6132709#diff-01399ee4f56d48b1e6847210ecf4c80b https://github.com/facebook/folly/commit/93d49bcf9a44d6b2d9c...
- adamnemecek 7y agoCan we stop posting fb links to Hn? Hasn’t the company done enough fucked up stuff?
- tracker1 7y agoI'm curious what Rust's implementation looks like in comparison now...
- ngbronson 7y agohttps://github.com/rust-lang/hashbrown 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.
- pcwalton 7y agoWhich has been recently upstreamed to the standard library, replacing the old hash map implementation. (This sped up rustc a noticeable amount, incidentally.)
- neptvn 7y agoIs `hashbrown::HashMap` now completely ported/identical with `std::collections::HashMap`? I just compared their performance (on yesterday's beta channel) on a hashmap with over 200k keys and didn't notice any relevant speedup.
- anderskaseorg 7y agoYes, as of a couple of days ago in nightly (pre-1.36): https://github.com/rust-lang/rust/pull/58623 https://github.com/rust-lang/rust/pull/58623
- mlindner 7y agoCan this easily be ported to Rust?
- pcwalton 7y agoRust'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. :)
- Dowwie 7y agoFb probably open sourced the work after the engineers realized that hashbrown is superior to it. Just a hunch. Need to see benchmarks..
- Shish2k 7y agoF14 has been open source for over a year already...
- kevingadd 7y agoThis 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.
- bjourne 7y agoSince 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-improvement-for-hashmap-in-java-8 https://www.nagarro.com/en/blog/post/24/performance-improvem...
- rurban 7y agoThey 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.
- ngbronson 7y agoF14 supports stateful hashers, so in situations that need to be resilient to hash poisoning we can use a hasher designed for that purpose.
- bjourne 7y agoI recall that that was what was suggested for Java's HashMap too, but they found it to be insufficient. By careful analysis, an attacker could still figure out how to cause hash collisions.
- ngbronson 7y agoI haven't seen those discussions, but is it possible that they were trying to rehash the results of Object.hashCode rather than pass all of the bytes of the original value through a new hash algorithm? If you haven't seen it before you will appreciate https://accidentallyquadratic.tumblr.com/post/153545455987/rust-hash-iteration-reinsertion https://accidentallyquadratic.tumblr.com/post/153545455987/r...
- bjourne 7y agoAfaik, they augmented the hash function with a random seed, which didn't work out. See: http://emboss.github.io/blog/2012/12/14/breaking-murmur-hash-flooding-dos-reloaded/ http://emboss.github.io/blog/2012/12/14/breaking-murmur-hash... It appears that SipHash would be enough (for now) to prevent hash poisoning. Most open addressing hash implementations doesn't yet use SipHash though.
- necovek 7y agoIt'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.
- daxterspeed 7y agoI realized that I misunderstood this comment (I assumed same fortnight meant "same fortnight number in a year" - when it should be same 14 day span) but I thought it was worth calculating this example anyway. The oldest person alive was born in 1903. Since then 3035 fortnights have passed. Assuming an even distribution of birth fortnights, there'd be a 3.4058% chance of two people having the same birth fortnight (1 - (P(3035,15)) / (3035^15), where P is for Permutations). It's still fairly likely, but far from the ~1 in 10^23 odds of having NO shared birthdays between 180 people.
- greg7mdp 7y agoPerformance is very similar to my header-only version of the Abseil's hash tables available at https://github.com/greg7mdp/parallel-hashmap https://github.com/greg7mdp/parallel-hashmap.
- dkural 7y agohttps://github.com/sparsehash/sparsehash https://github.com/sparsehash/sparsehash was for a decade+ hands down the most memory efficient map implementation, originally written by Craig Silverstein of Google. I am not sure how the more recent SIMD stuff impacts it.
- ngbronson 7y agosparsehash is still more memory efficient, but it is quite slow in comparison. Also, in practice it doesn't reach the ultra-low space overheads claimed by the documentation. It allocates memory blocks of many different sizes, so the dominant space overhead becomes internal fragmentation in the allocator. For sparsehash using JEMalloc's default allocation classes (spaced about a factor of 1.2 apart) the memory used relative to useful data varies from about 1.3 for small values to 1.1 for large values.
- MichaelMoser123 7y agohow comes that F14BasicMap (the base class of F14FastMap F14ValueMap and all the others) is extending std::unordered_map ? https://github.com/facebook/folly/blob/master/folly/container/F14Map.h https://github.com/facebook/folly/blob/master/folly/containe... they seem to be calling the table_ member for every method in the book. Still weird by they are deriving from std::unordered_map in the first place. F14Table<Policy> table_; the implementation class F14Table - https://github.com/facebook/folly/blob/master/folly/container/detail/F14Table.h https://github.com/facebook/folly/blob/master/folly/containe...
- ngbronson 7y agoThat's a fallback implementation for platforms without SIMD. The real code is lower down.
- yotamoron 7y agoFacebook is evil.
- Dowwie 7y agoCurious how this compares to brownhash, which is on its way to stable Rust on July 4th.
- Zelizz 7y agoSomeone should port this to C and add it to the next version of Lua, given that Lua's main datatype is pretty much a hashtable with some extra magic.