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

1–10 of 50 posts

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

#4

Post by jhalstead »

dclusin wrote: post #3

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

This thread has some info: 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.

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

#5

Post by usefulcat »

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

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

#6

Post by saagarjha »

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

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

#9

Post by stochastic_monk »

usefulcat wrote: post #5

I'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…

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.

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

#10

Post by usefulcat »

stochastic_monk wrote: post #9
usefulcat wrote: post #5

I'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…

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

Post reply on HN