3 ms·
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 secon
by nwallin 8y 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.