4 ms·

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 o

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.

jhalstead 7y ago
This 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 ago
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 https://www.youtube.com/watch?v=ncHmEUmJZf4 It's super interesting.
ngbronson 7y ago
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/ 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 ago
https://news.ycombinator.com/item?id=17176713 https://news.ycombinator.com/item?id=17176713 perhaps?

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.

jhalstead 7y ago

This 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 ago

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 https://www.youtube.com/watch?v=ncHmEUmJZf4 It's super interesting.

ngbronson 7y ago

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/ 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 ago

https://news.ycombinator.com/item?id=17176713 https://news.ycombinator.com/item?id=17176713 perhaps?