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

11–20 of 50 posts

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

#11

Post by woadwarrior01 »

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.

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

[1]: https://abseil.io/blog/20180927-swisstables

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

#12

Post by ipsum2 »

alexhutcheson wrote: post #7

Hasn't this been open-sourced since at least last March? https://github.com/facebook/folly/commit/93d49bcf9a44d6b2d9c...

The blog post is dated April 25, 2019, so I suspect this is a higher level overview on how it works/benchmark results/etc.

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

#13

Post by layoutIfNeeded »

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…

Does it beat judy arrays?

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

#14

Post by nwallin »

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.

They 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 It's super interesting.

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

#15

Post by ngbronson »

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.

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

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

#16

Post by ngbronson »

usefulcat wrote: post #10
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.

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…

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

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

#19

Post by ngbronson »

tracker1 wrote: post #18

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