btym

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