Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Open-sourcing F14 for memory-efficient hash tables

code.fb.com

Post reply on HN
Print view View original

31–40 of 50 posts

Re: Open-sourcing F14 for memory-efficient hash tables

#31

Post by daxterspeed »

necovek wrote: post #24

It'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 sma…

I 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.

Re: Open-sourcing F14 for memory-efficient hash tables

#32

Post by neptvn »

pcwalton wrote: post #26
ngbronson wrote: post #19

Earlier quoted context omitted.

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.)

Is `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.

Re: Open-sourcing F14 for memory-efficient hash tables

#33

Post by bjourne »

ngbronson wrote: post #30
bjourne wrote: post #22

Since 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.

I 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.

Re: Open-sourcing F14 for memory-efficient hash tables

#34

Post by ngbronson »

bjourne wrote: post #33
ngbronson wrote: post #30

Earlier quoted context omitted.

F14 supports stateful hashers, so in situations that need to be resilient to hash poisoning we can use a hasher designed for that purpose.

I 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.

I 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/r...

Re: Open-sourcing F14 for memory-efficient hash tables

#35

Post by greg7mdp »

woadwarrior01 wrote: post #11
stochastic_monk wrote: post #9

Earlier 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.

Comparing to ska::flat_hash_map or khash wouldn't be fair, because the F14 hash tables use SIMD intrinsics to lookup 14 buckets at once (and thus the name) whilst the former two don't have that advantage. A fairer comparison would be against Swiss tables[1] from Google's abseil library, which uses the same trick. Also, std::unordered_map is slow because its interface requires a chaining based collision resolution str…

You may want to try my version of the Abseil hash tables (I updated the code to make them header-only) at https://github.com/greg7mdp/parallel-hashmap.

Re: Open-sourcing F14 for memory-efficient hash tables

#37

Post by anderskaseorg »

neptvn wrote: post #32
pcwalton wrote: post #26

Earlier quoted context omitted.

Which has been recently upstreamed to the standard library, replacing the old hash map implementation. (This sped up rustc a noticeable amount, incidentally.)

Is `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.

Yes, as of a couple of days ago in nightly (pre-1.36): https://github.com/rust-lang/rust/pull/58623

Re: Open-sourcing F14 for memory-efficient hash tables

#38

Post by bjourne »

ngbronson wrote: post #34
bjourne wrote: post #33

Earlier quoted context omitted.

I 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.

I 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/r...

Afaik, 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... It appears that SipHash would be enough (for now) to prevent hash poisoning. Most open addressing hash implementations doesn't yet use SipHash though.

Re: Open-sourcing F14 for memory-efficient hash tables

#40

Post by ngbronson »

dkural wrote: post #39

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.

sparsehash 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.
Post reply on HN