SwissTable Control Bytes and Group-Wise Probing

A hash table lookup costs one memory access to find the slot and one comparison to confirm the key. On a machine where a cache line is 64 bytes and a memory access is a hundred or more cycles, the second part is the expensive one when it misses. Group-wise probing attacks this by separating the question “could this slot hold the key” from “does this slot hold the key”, and answering the first for a whole group of slots at once.

Metadata in a parallel array

The layout keeps the slot array contiguous, holding keys and values, and adds a parallel array of control bytes, one byte per slot. Each byte is either empty, deleted, or a 7-bit fragment of the key’s hash, called the tag. The eighth bit distinguishes the special states from a tag, so the tag space is 128 values and the special values occupy the remaining bit patterns.

A lookup hashes the key, derives the tag from the hash’s high bits, and computes the home group. It then loads the control bytes for the group, compares all of them against the tag in one operation, and obtains a bitmask of candidate slots. Only those candidates are checked against the actual key. Because the tag is 7 bits, a candidate matches by coincidence with probability about 1/128, so the key comparison runs rarely.

The reason the metadata is separate is memory traffic. A lookup that must touch the key array to discover that a slot is empty pays for a full key-sized access; a lookup that can rule out sixteen slots by reading sixteen bytes pays for a fraction of a line. The control array is dense, so a group of sixteen control bytes fits in a quarter of a 64-byte line, and the whole group’s state is available in a single load.

Groups of sixteen and the SIMD comparison

The group size is chosen to match the vector width. On x86 with SSE2 the natural width is 16 bytes, and the comparison is a single instruction that produces a mask of equal bytes. The implementation broadcasts the tag into all 16 lanes, compares against the loaded control bytes, and extracts the mask. Each set bit in the mask names a slot to examine.

The mask is also used for the negative case. Emptiness is encoded as a specific byte value, so a second comparison against the empty marker yields a mask of empty slots in the group. If the group contains an empty slot and no candidate matched the tag, the lookup terminates: the probe sequence would have stopped there. If the group is entirely full and no candidate matched, the lookup advances to the next group.

/* One probe step: 16 control bytes, two 16-bit masks, no key touched yet.
   Low half = tag matches (candidates), high half = empty slots (stop markers).
   A zero result means the group is full and holds no candidate: advance. */
static inline uint32_t group_probe(const uint8_t *ctrl, uint8_t tag, size_t start)
{
    __m128i bytes = _mm_loadu_si128((const __m128i *)(ctrl + start));
    uint32_t match = (uint32_t)_mm_movemask_epi8(
                         _mm_cmpeq_epi8(bytes, _mm_set1_epi8((char)tag)));
    uint32_t empty = (uint32_t)_mm_movemask_epi8(
                         _mm_cmpeq_epi8(bytes, _mm_set1_epi8((char)0x80)));
    return (match & 0xFFFF) | (empty << 16);
}

The caller walks the low sixteen bits as candidate slots and consults the high sixteen to decide whether the search may continue past this group. Because both masks come from single instructions, the cost of ruling out sixteen slots is close to the cost of ruling out one.

Advancing is where the layout differs from classic linear probing. The probe sequence is not slot-by-slot but group-by-group: within a group the sixteen slots are examined at once, and the next group begins at the next group-sized boundary, so that ctr is a whole number of groups ahead of the home position. Probing within a group is free in the sense that the SIMD comparison covers all sixteen slots simultaneously, so the effective probe granularity is sixteen slots rather than one. This is what reduces the number of probe iterations relative to scalar linear probing.

In the Abseil implementation the sequence comes from an odd group increment that grows by the group size on each step, step += width, with offset = (offset + step) mod capacity, applied in slot units so that wrap-around lands on a group boundary. Adding an odd multiple of the width each time makes the group offsets a permutation of the groups only when the number of groups is a power of two, which is one reason the capacity is restricted to 2^k - 1 slots.

Capacity, the sentinel, and the mirrored control byte

The control array has one byte per slot plus a small number of duplicates after it. The duplicates mirror the first bytes of the array, which lets a group that straddles the end of the array be loaded as one contiguous 16-byte vector instead of being split across two loads. This is why the allocated array is longer than the slot array, and why the capacity is restricted to values where the group arithmetic works out: capacities are 2^k - 1 slots, so the table always sits one slot short of a group boundary.

The 2^k - 1 capacities have a second effect. The slot count is one less than a multiple of the group size, so the table never ends flush with a group boundary, and the mirrored bytes plus a small number of unoccupied control bytes keep the group that straddles the end loadable and unambiguous. This is also why insertion can assume the table always has at least one EMPTY or DELETED slot: the load factor is capped below 1, and growth is triggered before the cap is reached. That guarantee is what makes a lookup terminate: the probe sequence will encounter a group containing a visible empty slot, and the empty-slot mask detects it.

Deletion uses the same two special values. A deleted slot is marked with a distinct byte, which the candidate comparison ignores but the emptiness check does not treat as empty. Growth is triggered when the count of occupied plus deleted slots exceeds the capacity threshold, and rehashing rebuilds the control array from scratch. Some implementations also rebuild when deleted slots dominate, exactly as in open addressing with tombstones.

Iteration and the cost of the parallel array

Iteration must skip empty and deleted slots, which the control bytes make cheap: a scan reads sixteen control bytes, finds the occupied ones by comparing against the special values, and visits only those slots. The keys and values are never touched for empty slots, so iteration over a sparse table costs time proportional to capacity in control-byte reads but proportional to the live entries in key reads.

The trade is that every insertion writes two locations, the slot and its control byte, and the two are in different arrays. That is two cache lines touched instead of one for a table that fits in cache, and it is the reason small tables sometimes favour a simpler layout with the metadata packed into the slot. The advantage appears when the table exceeds cache: the control array stays resident while the key array streams, so the working set for lookups shrinks by the ratio of the control byte to the slot size.

For a table with 8-byte keys and 8-byte values, the slot is 16 bytes and the control byte is 1, so the metadata adds about six percent to the footprint. For a table with large values stored inline, the ratio is far smaller, and the absolute saving is proportionally larger. Implementations that store values indirectly, or that split the table into a key array and a value array, exploit this further.

Limits of the approach

Group-wise probing inherits the load-factor sensitivity of open addressing. The maximum load is typically set around 0.875, above which the probe sequences lengthen and the SIMD advantage is eaten by the number of groups examined. The number is higher than the 0.5 to 0.75 range of scalar linear probing because a group of sixteen behaves like a single probe unit, and the clustering analysis applies per group rather than per slot.

The design assumes a vector unit. On architectures without one, the group comparison becomes a sequence of scalar comparisons, and the advantage narrows to the metadata separation alone, which is still real but smaller. Portable implementations either select a code path at compile time or use a word-at-a-time comparison that processes eight control bytes per 64-bit load.

The tag width is a fixed compromise. Seven bits give a false-positive rate of 1/128 per candidate slot, which is negligible when the candidate count is small but not when a lookup scans many groups. A wider tag would reduce false positives at the cost of fewer special values and a larger control byte; an 8-bit control array with a 7-bit tag is the point where the arithmetic is most convenient.

Finally, the layout does not remove the need for a good hash. The tag comes from the hash’s high bits, and if those bits are poorly distributed, slots in a group match the query’s tag far more often than chance allows and the key comparison runs on most of them. The mixing requirements are the same as for any table hash, described in hash functions for table indexing, and they are more visible here because a weak hash degrades the group filter before it degrades the probe count.

The technique is a memory-hierarchy optimization rather than an algorithmic one. The probe sequence is still open addressing, the expected probe count is still governed by the load factor, and the asymptotic bounds are unchanged. What changes is the constant: fewer lines touched per probe, fewer candidates compared per line, and a lookup that spends its cycles on the one comparison that matters.