[btym]

>And so our "two loops" are usually just "do two simple SIMD operations". Not quite so offensive when you say it like that!

No, it's not quite so offensive, but this doesn't explain why it's the best option. Is there no equally-fast way to write the first-tombstone implementation with SIMD instructions? The answer seems to be in the sketch of the implementation, which I'm having trouble understanding.

EDIT: I'm watching the original SwissTable talk now... would it really have been worse to use 2 bits for empty/tombstone/full/sentinel, and 6 bits for hash prefix?

EDIT 2: More implementation info. Tombstones are actually rare, because if any element in your 16-wide chunk is empty, you don't have to create a tombstone. In the very best case (a perfectly distributed hash function), your hashmap has to be ~94% full before it's even possible to fail this. Because tombstones are so rare, it's better to save the single bit for extra confidence in the hash prefix.

So, here is my understanding of the implementation and its rationale:

* Every bucket in the backing array has a corresponding byte in a metadata array

* 1 bit of this byte stores whether the bucket is empty, the other 7 bits are for a hash prefix

* SIMD instructions search 16 bytes at a time, checking: this bucket is not empty, this bucket's key matches the first 7 bits of my key

* Since 16 buckets are checked for emptiness at the same time, you can avoid creating a tombstone for a bucket if any of the other 15 buckets are empty (just set it to empty, i.e. set the first bit to 0)

* This means that tombstones are very unlikely- you'll probably rehash before you get to the load factor where you start seeing tombstones

* Since tombstones are so unlikely, it's more valuable to add an extra bit to the hash prefix than it is to quickly find tombstones

My question remains: why can't the first search return the offset of the first empty bucket? In this loop, why is there not an else that saves the offset?: https://github.com/abseil/abseil-cpp/blob/256be563447a315f2a...

[btym]

Ok, I got it. They're exactly the same. Either way you'd need to do a second search, because you're trying to differentiate between 3 states: "probably a match", "empty", or "deleted". A much better way than stealing a bit from the hash prefix is using a special value that represents "empty or deleted", and that's exactly what SwissTable does: https://github.com/abseil/abseil-cpp/blob/256be563447a315f2a...