News for hackers. Stuff that matters.
Re:Open-sourcing F14 for memory-efficient hash tables by dclusin on Friday April 26, 2019 @01:57PM (#19760168)
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.
Re:Open-sourcing F14 for memory-efficient hash tables by ngbronson on Friday April 26, 2019 @03:58PM (#19761253)
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 by nwallin on Friday April 26, 2019 @03:40PM (#19761094)
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 by jhalstead on Friday April 26, 2019 @01:59PM (#19760198)
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 by mappu on Friday April 26, 2019 @11:24PM (#19763570)