SIMD within a register, usually shortened to SWAR, is a family of techniques that treats an ordinary machine word as several smaller lanes. Instead of loading data into explicit SIMD vector registers, a program packs multiple fixed-width values into a 32-bit or 64-bit scalar register and uses integer arithmetic, bitwise logic, shifts, and masks to operate on all lanes at once.
A compact hash-table bucket is a natural fit for this pattern. Cuckoo filters, quotient filters, compact open-addressing tables, parsers, and token scanners often store tiny values such as 8-bit fingerprints. A four-slot bucket of 8-bit fingerprints fits exactly in one 32-bit word. A conventional lookup reads each byte, branches on equality, and exits when it finds a match. A SWAR lookup compares all four byte lanes in parallel with a handful of scalar operations.
The key trick is to turn equality into zero detection. If a bucket word is XORed with a word that repeats the searched byte in every lane, any equal lane becomes zero. A classic zero-byte test, ((v - 0x01010101) & ~v & 0x80808080), then reports whether any lane became zero. The result is a branch-free, loop-free membership test for a fixed-size bucket.
This topic is useful far beyond one C# Cuckoo filter implementation. It teaches a reusable optimization pattern: when a hot path repeatedly scans a small fixed-width group, pack the group into a scalar word, broadcast the query value, transform the predicate into a zero-byte test, and benchmark whether fewer branches and loads outweigh the loss of readability.
SWAR starts by assigning subfields inside an ordinary word. In the common byte-lane case, a 32-bit unsigned integer contains four independent 8-bit values and a 64-bit unsigned integer contains eight. The CPU still executes scalar integer instructions, but those instructions manipulate all packed lanes because the data layout makes each byte position meaningful.
Bitwise operations are especially friendly to this representation. AND, OR, XOR, and NOT operate independently on each bit, so they naturally preserve lane boundaries. Arithmetic operations need more care because carry and borrow can cross from one byte into the next. SWAR algorithms either prove that cross-lane effects are harmless, mask them away, or deliberately exploit a predictable high-bit marker.
To compare every byte lane with one target byte, repeat that byte across the whole word. For a 32-bit word, multiplying an 8-bit value by 0x01010101 builds a repeated-byte mask: 0x56 * 0x01010101 = 0x56565656. For a 64-bit word the equivalent constant is 0x0101010101010101.
XOR then performs the comparison setup in parallel. In each byte lane, a ^ b equals zero exactly when a == b. After XORing the packed bucket with the repeated target mask, a matching lane becomes 0x00, while non-matching lanes become non-zero bytes.
The classic zero-byte test marks the high bit of any byte that was zero before the test. The expression subtracts one from every byte lane using a word-wide subtract, inverts the original value, and intersects the result with the high bit of each byte. For zero bytes, the subtract produces a lane whose high bit is set and the inverted input also has the high bit set. For non-zero bytes below 0x80, the conjunction does not survive; for bytes above 0x80, the inverted high bit removes false positives.
A packed lookup becomes simple when equality is converted into zero. Broadcast the searched value, XOR it with the packed bucket, and run a zero-byte detector. The detector does not need to know which lane matched unless the caller needs the slot index.
A straightforward four-slot bucket lookup scans four bytes. This is clear, flexible, and often fast enough, but it still performs repeated indexing and usually emits branches or conditional moves. In a filter lookup path that executes millions of times, the fixed bucket size makes the loop overhead visible.
public bool Contains(byte fingerprint, uint bucketIdx)
{
var offset = bucketIdx * 4;
for (var i = offset; i < offset + 4; i++)
{
if (_table[i] == fingerprint) return true;
}
return false;
}The first optimization is representational: make each bucket one 32-bit word. That removes the multiply-by-bucket-size offset and lets the lookup load one aligned value instead of four separate bytes. Field-level access can still be preserved with an explicit layout that overlays byte fields and a full-word field.
[StructLayout(LayoutKind.Explicit, Size = 4)]
private struct Bucket
{
[FieldOffset(0)] public uint All;
[FieldOffset(0)] public byte Fp0;
[FieldOffset(1)] public byte Fp1;
[FieldOffset(2)] public byte Fp2;
[FieldOffset(3)] public byte Fp3;
}The SWAR lookup broadcasts the requested fingerprint, XORs it with the packed bucket, and checks whether the result contains any zero byte. The method returns a boolean membership result without branching over the four slots.
private static bool HasZeroByte(uint v)
{
return ((v - 0x01010101U) & ~v & 0x80808080U) != 0;
}
public bool Contains(byte fingerprint, uint bucketIdx)
{
ref readonly var bucket = ref _table[bucketIdx];
uint mask = fingerprint * 0x01010101U;
uint xored = bucket.All ^ mask;
return HasZeroByte(xored);
}If the bucket contains 0x12 0x34 0x56 0x78 and the query is 0x56, the broadcast mask is 0x56565656. XOR transforms the matching lane to 0x00. The zero-byte test sees that lane and returns true. If the bucket already contains an empty zero slot and the query is non-zero, XOR changes that zero slot to a non-zero byte, so the zero-byte detector still reports only actual matches.
Cuckoo filters store compact fingerprints rather than full keys. A lookup checks two candidate buckets and succeeds when either bucket contains the fingerprint. Since buckets are small and fixed-width, SWAR can accelerate the inner membership test without changing the higher-level filter algorithm.
The source benchmark used four 8-bit slots per bucket. Compared with the original byte-array loop, the packed integer version was more than 40% faster for positive lookups and more than twice as fast for negative lookups in the reported benchmark set. Negative lookups benefit strongly because the branchy version must inspect every slot before returning false, while the packed version always follows the same short instruction sequence.
Many high-performance hash tables store small metadata bytes beside keys: fingerprints, occupancy markers, control bytes, tombstones, or probe sequence markers. SWAR is a scalar alternative when explicit SIMD intrinsics are not available, when the metadata group is smaller than a vector register, or when a managed runtime makes vector intrinsics inconvenient.
Text parsers often search for delimiter bytes such as comma, quote, newline, brace, or zero terminator. The same broadcast-XOR-zero-test structure can scan several bytes at once inside a word. Production parsers typically scale the idea to 64-bit words or explicit SIMD vectors, but the reasoning is the same: compare many lanes with one value, collapse the lane result into a bit mask, and branch only on the aggregate result.
The easiest way to make this optimization maintainable is to hide the packed word behind a bucket type. Callers should not know that four logical slots share one integer. The bucket type owns layout, insertion, deletion, matching, and slot extraction. That keeps bit tricks out of the rest of the table implementation.
private readonly Bucket[] _buckets;
public bool Contains(byte fingerprint, uint primary, uint alternate)
{
return ContainsInBucket(fingerprint, primary) ||
ContainsInBucket(fingerprint, alternate);
}
private bool ContainsInBucket(byte fingerprint, uint bucketIdx)
{
uint word = _buckets[bucketIdx].All;
uint repeated = fingerprint * 0x01010101U;
uint candidate = word ^ repeated;
return ((candidate - 0x01010101U) & ~candidate & 0x80808080U) != 0;
}The same idea extends to 64-bit buckets with eight byte lanes. The constants change, but the structure is identical. Wider buckets increase per-lookup parallelism, but they can also change cache behavior, table load factor, collision probability, and insertion complexity. Treat the lane width as a data-structure decision, not just a micro-optimization.
private static bool HasZeroByte(ulong v)
{
return ((v - 0x0101010101010101UL) & ~v & 0x8080808080808080UL) != 0;
}Do not benchmark only successful lookups. Filters and hash tables often spend much of their time proving that an item is absent. A branch-free packed lookup may shine on misses because it avoids repeated conditional exits, but the result depends on runtime, CPU, memory layout, inlining, and whether the surrounding algorithm is cache-bound.