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.
Open-sourcing F14 for memory-efficient hash tables
41–50 of 50 posts
Re: Open-sourcing F14 for memory-efficient hash tables
#42how 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/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 table_;
the implementation class F14Table - https://github.com/facebook/folly/blob/master/folly/containe...
Re: Open-sourcing F14 for memory-efficient hash tables
#43Facebook is evil.
Re: Open-sourcing F14 for memory-efficient hash tables
#44Curious how this compares to brownhash, which is on its way to stable Rust on July 4th.
Re: Open-sourcing F14 for memory-efficient hash tables
#45Can this easily be ported to Rust?
Fb probably open sourced the work after the engineers realized that hashbrown is superior to it. Just a hunch. Need to see benchmarks..
Re: Open-sourcing F14 for memory-efficient hash tables
#46Re: Open-sourcing F14 for memory-efficient hash tables
#47how 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/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 table_; the implementation class F14Table - https://github.com/facebook/fol…
That's a fallback implementation for platforms without SIMD. The real code is lower down.
Re: Open-sourcing F14 for memory-efficient hash tables
#48Earlier 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…
> What is your access pattern? Are insertions and deletions frequently interleaved?
It's basically random, but generally they are very interleaved and most of the time the number of insertions and deletions are approximately equal over some period of time (~seconds). This is for keeping track of orders while processing a depth of book feed, in case you're familiar with that sort of thing.
F14 is using some kind of reference counting scheme for tombstones, described in the article. I don't fully understand it, but it definitely seems different than the standard tombstone-based algorithm, which I do understand. In any case, when using something like dense_hash_map, I see huge spikes in processing time (due to rehashing) that I don't see when using F14. I also resize the hash tables up front to avoid having to do so later on, but of course for my use case that doesn't help with implementations that use a traditional tombstone algorithm unless I use ridiculously large initial sizes.
Re: Open-sourcing F14 for memory-efficient hash tables
#49Someone 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.
Re: Open-sourcing F14 for memory-efficient hash tables
#50I'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 know it's late, but I finally got around to trying ska::flat_hash_map. For my application (lots of insertions and deletions) it's not quite as fast as F14, but the difference is fairly small. It's also much easier to incorporate than folly, since the entire thing is in a single header file.