search

cockroachdb / swiss

Go port of Google's Swiss Table hash table
Apache License 2.0
317 stars 12 forks source link

swiss: remove sentinel #24

Closed petermattis closed 8 months ago

petermattis commented 8 months ago

Remove usage of the the sentinel control byte which was not serving any purpose. Abseil uses the sentinel control byte to terminate iteration (or claims to), but in this implementation iteration is terminated by iterating over all of the groups exactly once. Mentions that probing are terminated by reaching an empty control byte or the sentinel were erroneous. We only terminate probing by reaching an empty slot which implies that the map always needs at least 1 empty slot for correct operation.

cockroach-teamcity commented 8 months ago

This change is Reviewable

RaduBerinde commented 8 months ago

map.go line 40 at r1 (raw file):

Previously, RaduBerinde wrote…
Was the N-1 thing in the Google's layout or was that only an Abseil thing?

Ah, Abseil is Google's implementation, I thought it's a separate one.