INTERACTIVE DEMO

Swiss Table Probe Visualizer

Two hash-table designs run the same lookup on the same 64-slot table. The standard design stores keys inline and memcmp's SIMD candidates; CMap — Furrballs' concurrent variant — stores only the 64-bit hash and reads under a seqlock.

16-slot groups × 4 groups · 64-bit FNV-1a (XXH3 stand-in) · SSE2 cmpeq

Watch for

· Only an EMPTY ctrl byte (0x80) ends a probe — a tombstone (0xFE) never does.
· What a false H2 match costs: string bytes for the standard table, one integer compare for CMap.
· What a racing writer does: silent corruption for the standard table, a detected retry for CMap.

Setup

Key

Concurrent writer

Speed1×

1/10

Same probe, two designs

STANDARDkey stored inline · single CAS · not thread-safe

2 live

3 live · 1 ×

1 live · 1 ×

2 live

step 1 of 7hash

Hash "ring"

h = XXH3_64("ring")

H1 = (h >> 7) % 4 = 1

H2 = h >> 57 = 0x3e

groups probed: 0H2 hits: 0memcmp: 0 keys · 0 B

CMAPfingerprint-as-key · dual-CAS + seqlock reads

2 live

3 live · 1 ×

1 live · 1 ×

2 live

step 1 of 10hash

Hash "ring"

h = XXH3_64("ring")

H1 = (h >> 7) % 4 = 1

H2 = h >> 57 = 0x3e

CMap stores no keys — the 64-bit hash is both the index source and the stored fingerprint (hash-as-key).

groups probed: 0H2 hits: 0fp compares: 0seqlock retries: 0

occupied (ctrl = h2 byte)deleted (0xFE tombstone)empty (0x80 — stops probes)H2 matchcandidate

timeline: structure H2 hit success risk / torn mutationgroups open as the probe reaches them · click a header to pin · click a slot to inspect · press ? for shortcuts

Reference

Standard design

· Slots store the full key inline — matches need a memcmp
· Insert publishes with one ctrl-byte CAS
· No concurrency protocol: a racing write corrupts reads
· Probe stops at the first EMPTY byte (0x80)
· Erase leaves a DELETED tombstone (0xFE) to keep chains alive
· Used by: Abseil, Rust std, Folly, Go maps

Concurrent design (CMap)

· No key storage — the 64-bit hash is the fingerprint
· Match = integer compare: O(1), no memcmp, no string reads
· Writes are dual-CAS: seq (even→odd) then ctrl, released by seq (odd→even)
· Reads are seqlocked: acquire → copy → verify → retry
· Fail-fast: CAS failure marks the group ABANDONED
· Used by: Furrballs cache (NUMA-aware)

Vocabulary

ctrl byte: One metadata byte per slot: the 7-bit H2 when occupied, 0x80 when empty, 0xFE when deleted.
H1 / H2: Two slices of the 64-bit hash. H1 picks the starting group; H2 is what SIMD compares, byte for byte.
probe chain: The linear walk from group g to g + 1. Only an EMPTY byte ends it.
false positive: An H2 match whose full hash differs. Both designs must reject it — at very different cost.
tombstone: A DELETED slot (0xFE). Keeps the chain behind it alive; a later insert may reuse the space.
seqlock: An even/odd counter around each CMap slot. Readers acquire → copy → verify, and retry if it moved.

Based on the Furrballs whitepaper §2.7 (CMap: Concurrent Swiss Table) and §3.8 (Hash-as-Key). CMap is a one-way port from Furrballs to StreamLine (namespace StreamLine::Containers).