Learn Zig Series (#112) - Cuckoo Filters

avatar

Learn Zig Series (#112) - Cuckoo Filters

zig.png

What will I learn?

  • Why the cuckoo filter answers the exact question the bloom filter left dangling at the end of episode 111 -- membership testing with clean deletion -- and does it without inflating every slot into a counter;
  • What a fingerprint is, why storing a few bits of a key instead of the whole key is the trick that makes the whole thing fit, and where those bits come from;
  • The partial-key cuckoo hashing trick at the heart of it -- how a key gets two candidate buckets, and the small piece of XOR arithmetic that lets you compute the second bucket from the first without ever having the key in hand;
  • How to build a working cuckoo filter from scratch in Zig -- add, contains, and (at last) remove -- with a flat byte table, four-slot buckets, and the eviction dance that gives the structure its name;
  • Why insertion can fail where the bloom filter's never could, how Zig's error unions make that failure a value you must handle rather than a surprise, and what "the table is full" really means;
  • How to test a structure that both lies (false positives) and can legitimately refuse work (a full insert) -- separating the guarantee that must never break from the statistics that only have to land in a band;
  • Where the cuckoo filter genuinely beats the bloom filter (and where it does not), plus the rule of thumb for which one to reach for at a given false-positive target;
  • How the same design maps onto C, Rust, and Go, and why the eviction loop is the part that makes each language show its hand.

Requirements

  • A working modern computer running macOS, Windows or Ubuntu;
  • An installed Zig 0.14+ distribution (download from ziglang.org);
  • Episode 111 fresh in mind -- we built a bloom filter, watched it prove absence for free, and hit the one wall it cannot climb: you cannot delete a key without risking corruption of some other key's bits;
  • Comfort with allocators (episodes 7 and 26), bit manipulation and XOR in particular (episode 17), and a working feel for hashing from the hash-map work in episode 22;
  • The ambition to learn Zig programming.

Difficulty

  • Advanced

Curriculum (of the Learn Zig Series):

Learn Zig Series (#112) - Cuckoo Filters

I ended episode 111 with a cliffhanger and a promise. The bloom filter we built was a lovely thing -- it stored none of the keys, answered "definitely not present" with total certainty, and cost a fixed, tiny amount of memory no matter how fat the keys were. But it had one wall it could not climb, and I made a point of leaning on it: you cannot delete a key from a plain bloom filter. Clearing a key's bits might clear a bit some other key still relies on, so the honest options are "never delete" or "fatten every bit into a counter and pay for it". That second road -- the counting bloom filter from last week's exercise 3 -- buys deletion by multiplying your memory bill four-fold or eight-fold, and the counters can still overflow and corrupt the filter permanently. A workaround wearing a solution's coat, as I put it.

So I promised a structure that supports deletion natively, without inflating every slot, and that at the low false-positive rates real systems actually demand is often more space-efficient than the bloom filter, not less. That structure exists, it borrows its central trick from a hashing scheme named after a bird with famously rude nesting habits, and it is where we go today. The cuckoo filter. First though -- the debt from last week, three exercises, all with real code ;-)

Solutions to Episode 111 Exercises

Exercise 1 -- estimateCount from the bit array alone. The set bits carry enough information to estimate how many distinct keys were added, with no separate counter. Count the set bits (that is @popCount over the u64 words, the population count from episode 17), then invert the fill formula: with X bits set out of m, and k hashes, the estimate is -(m/k) * ln(1 - X/m).

fn estimateCount(self: *const Self) f64 {
    var set_bits: usize = 0;
    for (self.bits) |word| set_bits += @popCount(word); // episode 17's population count
    const m: f64 = @floatFromInt(self.num_bits);
    const k: f64 = @floatFromInt(self.num_hashes);
    const x: f64 = @floatFromInt(set_bits);
    return -(m / k) * @log(1.0 - (x / m)); // invert the "expected fraction filled" formula
}

test "estimateCount lands within a few percent of the truth" {
    var bf = try BloomFilter.init(std.testing.allocator, optimalBits(2000, 0.01), optimalHashes(optimalBits(2000, 0.01), 2000));
    defer bf.deinit();
    var buf: [24]u8 = undefined;
    var i: usize = 0;
    while (i < 1000) : (i += 1) {
        const key = try std.fmt.bufPrint(&buf, "item-{d}", .{i});
        bf.add(key);
    }
    const est = bf.estimateCount();
    try std.testing.expect(est > 950.0 and est < 1050.0); // ~1000, allow +/- 5%
}

The estimate degrades as the filter saturates because the formula divides by (1 - X/m): once nearly every bit is set, X/m creeps toward 1, ln(1 - X/m) dives toward negative infinity, and tiny sampling wobble in X swings the answer wildly. A filter you sized correctly (fill fraction around one-half at capacity) sits in the formula's well-behaved zone -- a filter you overstuffed does not.

Exercise 2 -- union of two filters. The mechanics are almost embarrassingly small: OR the two bit arrays word by word. The interesting part is the precondition, because OR-ing two filters that disagree on m or k produces silent garbage, so I refuse it with an explicit error rather than let it corrupt quietly.

fn unionWith(self: *Self, other: *const Self) error{Mismatch}!void {
    if (self.num_bits != other.num_bits or self.num_hashes != other.num_hashes)
        return error.Mismatch; // OR-ing incompatible filters is meaningless -- refuse it loudly
    for (self.bits, other.bits) |*a, b| a.* |= b; // set-union is just bitwise OR, word by word
}

You can union cheaply because "present in A OR present in B" maps exactly onto the bit-level OR -- a bit is set in the result precisely when some key set it in either input, which is what membership in the union means. Intersection does not work the same way: AND-ing the arrays gives you the bits that happened to be set in both, but a bit set in both could easily come from two different keys colliding on that position, so the AND invents members that were in neither original set. Union is exact, intersection is a lie -- that asymmetry catches quite some people out.

Exercise 3 -- the counting bloom filter. Replace each bit with a small counter so add increments and a new remove decrements, and deletion finally exists. Packed two nibbles to a byte, it looks like this:

const CountingBloom = struct {
    const Self = @This();
    counters: []u8, // one nibble per logical slot, two slots per byte
    num_slots: usize,
    num_hashes: usize,
    allocator: std.mem.Allocator,

    fn get(self: *const Self, i: usize) u4 {
        const byte = self.counters[i >> 1];
        return @intCast(if (i & 1 == 0) (byte & 0x0F) else (byte >> 4)); // low nibble / high nibble
    }
    fn set(self: *Self, i: usize, v: u4) void {
        const bi = i >> 1;
        if (i & 1 == 0)
            self.counters[bi] = (self.counters[bi] & 0xF0) | @as(u8, v)
        else
            self.counters[bi] = (self.counters[bi] & 0x0F) | (@as(u8, v) << 4);
    }
    fn add(self: *Self, key: []const u8) void {
        const h = hashPair(key);
        var j: usize = 0;
        while (j < self.num_hashes) : (j += 1) {
            const idx = (h[0] +% (@as(u64, @intCast(j)) *% h[1])) % self.num_slots;
            const c = self.get(idx);
            if (c < 15) self.set(idx, c + 1); // saturate at 15 rather than overflow to 0
        }
    }
    fn remove(self: *Self, key: []const u8) void {
        const h = hashPair(key);
        var j: usize = 0;
        while (j < self.num_hashes) : (j += 1) {
            const idx = (h[0] +% (@as(u64, @intCast(j)) *% h[1])) % self.num_slots;
            const c = self.get(idx);
            if (c > 0) self.set(idx, c - 1);
        }
    }
    fn contains(self: *const Self, key: []const u8) bool {
        const h = hashPair(key);
        var j: usize = 0;
        while (j < self.num_hashes) : (j += 1) {
            const idx = (h[0] +% (@as(u64, @intCast(j)) *% h[1])) % self.num_slots;
            if (self.get(idx) == 0) return false; // any zero counter -> definitely absent
        }
        return true;
    }
};

After add(x); add(y); remove(x), the counters that only x touched drop back to zero (so x reads absent) while every counter y needs stays positive (so y reads present) -- deletion works. The price: four bits per slot instead of one, so 4x the memory of the plain filter for the same bit count. And the catastrophe I flagged: if a 4-bit counter is pushed past 15 it wraps to 0, which then reads as "absent" and silently breaks the no-false-negative guarantee for every key sharing that slot. That saturating if (c < 15) clamp is not optional -- it trades a slow leak (a counter that never comes back down) for a hard corruption, and the slow leak is the survivable one.

That fourth-power memory tax is exactly the itch the cuckoo filter scratches. On to the bird.

The one idea: fingerprints that remember where they can live

Here is the whole cuckoo filter in one breath. Keep a flat table of buckets, each bucket a small fixed number of slots (four is the classic choice). In those slots you do not store keys -- you store fingerprints, a handful of bits (I will use one byte) derived by hashing the key. To find a key you check whether its fingerprint sits in one of its two candidate buckets. That is the entire query: hash, look in two buckets, done.

The magic -- and it is genuinely clever, worth slowing down for -- is how the two buckets relate. In an ordinary hash table with two choices you would compute both bucket indices straight from the key: i1 = hashA(key), i2 = hashB(key). But a filter never keeps the key around, so at eviction time (more on that in a moment) it would have no way to recompute where a stranded fingerprint is allowed to go. The cuckoo filter solves this with partial-key cuckoo hashing: the first bucket is i1 = hash(key), and the second is

i2 = i1 XOR hash(fingerprint)

Stare at that for a second, because the XOR is doing something sneaky. XOR is its own inverse, so i2 XOR hash(fingerprint) gives you i1 straight back. Which means: given only a bucket index and the fingerprint sitting in it, you can compute the other candidate bucket -- no key required. That is the property that lets fingerprints shuffle themselves around the table without anyone remembering which key produced them. The key is long gone; the fingerprint plus the XOR is enough.

The consequences fall right out:

  • Lookups touch exactly two buckets. No probing chain, no tree descent -- contains reads bucket i1, and if the fingerprint is not there, bucket i2, and that is the worst case, always.
  • Deletion is trivial and clean. To remove a key, find its fingerprint in one of its two buckets and erase that slot. No shared bits, no counters, no overflow -- the thing the bloom filter could never do becomes a one-line for loop.
  • Insertion can fail. This is the price. When both candidate buckets are full, the filter evicts a resident fingerprint to make room and relocates it to its own alternate bucket, which may evict another, and so on. Usually this settles in a handful of hops. Occasionally, in a filter packed near capacity, it loops -- and then insertion honestly reports that the table is full. The bloom filter never had to say "no". The cuckoo filter does, and Zig will make us handle it.

Having said that, let's build the thing and watch the eviction dance in real bytes.

Laying out the table in Zig

I'll keep the whole table as one flat []u8 -- num_buckets * bucket_size fingerprints, laid out bucket by bucket, with 0 reserved as the "empty slot" marker. A byte per fingerprint keeps the bit-twiddling out of the way for a first version (the exercises push toward tighter packing). The bucket count is a power of two on purpose: it turns the modulo in the index math into a cheap bitmask, and -- more importantly -- it keeps the XOR trick in bounds, since XOR-ing two values below 2^n always lands below 2^n.

const std = @import("std");

const CuckooFilter = struct {
    const Self = @This();
    const bucket_size = 4;   // slots per bucket -- 4 is the sweet spot in the paper
    const max_kicks = 500;   // eviction hops to try before declaring the table full

    buckets: []u8,           // num_buckets * bucket_size fingerprints; 0 == empty
    num_buckets: usize,      // ALWAYS a power of two, so "mod" becomes "& (num_buckets - 1)"
    count: usize,            // live entries, for load-factor bookkeeping
    prng: std.Random.DefaultPrng, // drives the random eviction choice
    allocator: std.mem.Allocator,

    fn init(allocator: std.mem.Allocator, capacity: usize) !Self {
        var nb: usize = 1;
        while (nb * bucket_size < capacity) nb <<= 1; // smallest power of two that fits capacity
        const buckets = try allocator.alloc(u8, nb * bucket_size);
        @memset(buckets, 0); // every slot empty -- an empty set
        return .{
            .buckets = buckets,
            .num_buckets = nb,
            .count = 0,
            .prng = std.Random.DefaultPrng.init(0x1234_5678), // fixed seed -> reproducible tests
            .allocator = allocator,
        };
    }

    fn deinit(self: *Self) void {
        self.allocator.free(self.buckets); // one flat allocation, one free -- like the bloom filter
    }

    fn bucket(self: *Self, i: usize) []u8 {
        return self.buckets[i * bucket_size .. (i + 1) * bucket_size]; // the four slots of bucket i
    }
};

Notice the family resemblance to last week: one contiguous allocation, a trivial deinit, no per-node pointer chasing. The cuckoo filter is every bit as cache-flat as the bloom filter -- the difference is entirely in how we address into that flat block.

Fingerprints and the two bucket indices

Three little pure functions carry the scheme: one to derive the fingerprint, one for the primary bucket, one for the alternate. The fingerprint must never be 0, because 0 is our empty-slot marker -- so if the hash's low byte comes out zero, I bump it to 1. That is a real correctness detail, not a nicety: a zero fingerprint would be indistinguishable from an empty slot and the whole structure would quietly rot.

fn fingerprint(key: []const u8) u8 {
    const h = std.hash.Wyhash.hash(0x9E3779B97F4A7C15, key);
    const fp: u8 = @truncate(h);      // keep the low 8 bits as the fingerprint
    return if (fp == 0) 1 else fp;    // 0 is reserved for "empty" -- never emit it
}

fn primaryIndex(self: *Self, key: []const u8) usize {
    const h = std.hash.Wyhash.hash(0xD1B54A32D192ED03, key); // a DIFFERENT seed from the fingerprint
    return @intCast(h & (self.num_buckets - 1)); // power-of-two size -> mask is exact modulo
}

// The involution: altIndex(altIndex(i, fp), fp) == i, so a stranded fingerprint can always
// find its way home with no knowledge of the original key.
fn altIndex(self: *Self, i: usize, fp: u8) usize {
    const h = std.hash.Wyhash.hash(0x2545F4914F6CDD1D, &[_]u8{fp});
    return i ^ (@as(usize, @intCast(h)) & (self.num_buckets - 1));
}

The altIndex function is the load-bearing wall of the entire structure, so let me say plainly why it works. It XORs the current bucket index with hash(fingerprint) mod num_buckets. Because XOR is self-inverse, applying it twice with the same fingerprint returns the original index -- that is the involution I keep going on about. So bucket i1 and bucket i2 are each other's alternate through the fingerprint, and crucially you can hop from either to the other holding nothing but the fingerprint that is physically sitting in the slot. Nota bene: the primary index uses a seed different from the fingerprint's, so the fingerprint and the bucket choice are independent -- reuse the same hash for both and you correlate them, which inflates the false-positive rate above what the math predicts.

Insertion: the cuckoo kicks a tenant out

Insertion tries the easy path first: is there an empty slot in either candidate bucket? If so, drop the fingerprint in and we are done. Only when both buckets are full does the namesake behaviour kick in (pun fully intended). We pick one of the two buckets, evict a random resident fingerprint, put ours in its place, and then the evicted fingerprint has to go live in its alternate bucket -- which we can compute, because we have the fingerprint and the bucket it was just kicked out of. If that alternate is full too, it evicts someone else, and the chain continues until either a slot opens up or we hit max_kicks and admit defeat.

const Error = error{TableFull};

fn insertIntoBucket(self: *Self, i: usize, fp: u8) bool {
    for (self.bucket(i)) |*slot| {
        if (slot.* == 0) { slot.* = fp; return true; } // first empty slot wins
    }
    return false;
}

fn add(self: *Self, key: []const u8) Error!void {
    var fp = fingerprint(key);
    const i1 = self.primaryIndex(key);
    const i2 = self.altIndex(i1, fp);

    // Fast path: a free slot in either candidate bucket.
    if (self.insertIntoBucket(i1, fp) or self.insertIntoBucket(i2, fp)) {
        self.count += 1;
        return;
    }

    // Both full: start kicking. Pick a starting bucket at random.
    var i = if (self.prng.random().boolean()) i1 else i2;
    var n: usize = 0;
    while (n < max_kicks) : (n += 1) {
        const slot_idx = self.prng.random().intRangeLessThan(usize, 0, bucket_size);
        const slot = &self.bucket(i)[slot_idx];
        std.mem.swap(u8, &fp, slot); // fp now holds the EVICTED fingerprint; our fp is placed
        i = self.altIndex(i, fp);    // relocate the evicted one to ITS alternate bucket
        if (self.insertIntoBucket(i, fp)) {
            self.count += 1;
            return;
        }
    }
    return error.TableFull; // ran out of patience -- the table is effectively full
}

The std.mem.swap is the elegant heart of it: in one move it plants our fingerprint in the chosen slot and hands us the one we displaced, ready to be rehomed. Then altIndex(i, fp) -- with fp now the evicted fingerprint -- computes exactly where that refugee is allowed to go. No lookup table, no back-references, no memory of any key. Just the fingerprint and one XOR. When people say cuckoo hashing is "beautiful" this swap-and-relocate loop is usually what they mean.

The error.TableFull return is the honest part. A cuckoo filter that is packed past roughly 95% load starts failing insertions not because it is truly out of physical slots but because the eviction chain cannot find a stable arrangement. That is a real, expected outcome, and the caller has to decide what to do about it -- rebuild bigger, or reject the insert. Which brings us straight to Zig's error handling.

Where Zig's type system and error handling earn their keep

The bloom filter's add could never fail -- it just set bits. The cuckoo filter's add genuinely can, and this is exactly the kind of fallible operation Zig refuses to let you paper over. The return type is Error!void, so a caller cannot silently ignore the possibility of a full table -- they must try it (propagate), catch it (handle), or explicitly discard it. There is no way to forget that insertion is fallible, because the type system makes the failure a visible part of the signature. Compare a C version returning int, where "0 means it failed" is a convention you have to remember and every caller is free to ignore.

// The caller is FORCED to reckon with a full table -- three honest choices, no silent path.
fn demonstrateHandling(filter: *CuckooFilter, key: []const u8) void {
    // 1. Propagate: bubble error.TableFull up to whoever called us.
    //    try filter.add(key);

    // 2. Handle it locally: treat "full" as a signal to grow and retry elsewhere.
    filter.add(key) catch |err| switch (err) {
        error.TableFull => std.log.warn("cuckoo table saturated -- time to resize", .{}),
    };
}

The fingerprint type pulls its weight too. By making it a u8 I have baked the fingerprint width into the type -- the compiler will not let me accidentally stuff a 16-bit value into a slot, and the false-positive rate (which depends directly on that width) is now a property of the type rather than a loose runtime constant I might mismatch between add and contains. And the 0-is-empty invariant lives in exactly one place, the fingerprint function, so there is a single line to audit for the "did we ever emit a zero fingerprint" bug. That is the recurring Zig through-line of this whole series: push the rules into the types and the compile step, and what is left at runtime is small, flat, and hard to hold wrong.

Lookup and -- finally -- deletion

After all that, the two operations that motivated the whole episode are almost anticlimactic. contains hashes the key, computes both candidate buckets, and checks whether the fingerprint is sitting in either. remove does the same search and, on a hit, zeroes the slot.

fn bucketHas(self: *Self, i: usize, fp: u8) bool {
    for (self.bucket(i)) |slot| { if (slot == fp) return true; }
    return false;
}

fn contains(self: *Self, key: []const u8) bool {
    const fp = fingerprint(key);
    const i1 = self.primaryIndex(key);
    const i2 = self.altIndex(i1, fp);
    return self.bucketHas(i1, fp) or self.bucketHas(i2, fp); // at most two bucket reads, ever
}

fn remove(self: *Self, key: []const u8) bool {
    const fp = fingerprint(key);
    const i1 = self.primaryIndex(key);
    const i2 = self.altIndex(i1, fp);
    for ([2]usize{ i1, i2 }) |i| {
        for (self.bucket(i)) |*slot| {
            if (slot.* == fp) { slot.* = 0; self.count -= 1; return true; } // erase and reclaim
        }
    }
    return false; // fingerprint not found in either candidate bucket
}

That is the deletion the bloom filter could not give us -- a single zeroed byte, no shared state, no counters to overflow. But there is one honesty caveat I have to flag, and it is the same coin the false positive is minted from. Because we match on fingerprints, not keys, remove deletes a slot holding that fingerprint, which -- with small probability -- might be a fingerprint that belongs to a different key that happens to collide. So the deletion contract is: you may only delete keys you actually inserted. Delete a key you never added and you might, rarely, evict some innocent bystander's fingerprint and hand yourself a false negative for it. Add-only-what-you-later-remove is a discipline the caller has to keep; the structure trusts you on that point the same way it hedges on membership.

Testing a structure that lies AND refuses work

The cuckoo filter is harder to test than the bloom filter for a subtle reason: it has two legitimate ways to surprise you. Like the bloom filter it lies with false positives (statistical, test with a band). Unlike it, insertion can legitimately fail (test that it succeeds up to a sane load, and does not spuriously fail early). So the suite splits into three claims: successful inserts are always findable, deletion actually removes, and the false-positive rate stays in the ballpark.

test "cuckoo: every successfully inserted key is found" {
    var cf = try CuckooFilter.init(std.testing.allocator, 4096);
    defer cf.deinit();
    var buf: [16]u8 = undefined;
    var i: usize = 0;
    while (i < 2000) : (i += 1) { // ~60% load -- comfortably below the failure cliff
        const key = try std.fmt.bufPrint(&buf, "key-{d}", .{i});
        try cf.add(key); // a TableFull here at this load would itself be a bug
    }
    i = 0;
    while (i < 2000) : (i += 1) {
        const key = try std.fmt.bufPrint(&buf, "key-{d}", .{i});
        try std.testing.expect(cf.contains(key)); // NO false negatives for inserted keys
    }
}

test "cuckoo: deletion removes the key and frees a slot" {
    var cf = try CuckooFilter.init(std.testing.allocator, 1024);
    defer cf.deinit();
    try cf.add("alpha");
    try cf.add("beta");
    try std.testing.expect(cf.remove("alpha"));   // present -> removed
    try std.testing.expect(!cf.contains("alpha")); // gone now
    try std.testing.expect(cf.contains("beta"));   // beta untouched
    try std.testing.expect(!cf.remove("alpha"));   // removing again reports "not there"
}

test "cuckoo: false-positive rate stays in the right band" {
    var cf = try CuckooFilter.init(std.testing.allocator, 8192);
    defer cf.deinit();
    var buf: [24]u8 = undefined;
    var i: usize = 0;
    while (i < 4000) : (i += 1) {
        const key = try std.fmt.bufPrint(&buf, "member-{d}", .{i});
        try cf.add(key);
    }
    var false_positives: usize = 0;
    i = 0;
    while (i < 20000) : (i += 1) { // strangers we never added
        const key = try std.fmt.bufPrint(&buf, "stranger-{d}", .{i});
        if (cf.contains(key)) false_positives += 1;
    }
    const rate = @as(f64, @floatFromInt(false_positives)) / 20000.0;
    try std.testing.expect(rate < 0.05); // 8-bit fp, b=4 -> ~3% expected, assert a loose band
}

The first test is the one I would defend hardest, exactly as with the bloom filter: successfully inserted keys must always report present. The deletion test encodes the whole reason this episode exists -- and the final !cf.remove("alpha") line quietly checks that a double-delete is reported rather than silently corrupting the count. The false-positive test is deliberately loose (assert under 5% for a ~3% design) because it samples a random process, and pinning a statistical test to an exact value is how you earn a build that flaps green-to-red for no reason. Same lesson as last week, worth repeating until it is muscle memory.

Performance and space: when the cuckoo beats the bloom

On time, the cuckoo filter is superb and beautifully flat for the two operations that matter: contains and remove each read at most two buckets, and with four slots per bucket sitting in one or two cache lines, that is a tiny, fixed cost independent of how many keys you have stored. It is even friendlier than the bloom filter on lookups in one respect -- a bloom filter does k scattered probes (five to fifteen cache-random pokes), while a cuckoo lookup touches two localized buckets. The asymmetry flips on the write side: bloom add is also just k bit-sets, but cuckoo add can trigger an eviction chain, so its worst-case insert is far spikier even though the average stays cheap. You trade steadier writes for faster, delete-capable reads.

On space, here is the headline that justifies the whole exercise. A cuckoo filter's cost per key is roughly (f + 3) / load_factor bits, where f is the fingerprint width -- with an 8-bit fingerprint and the ~95% load factor that four-slot buckets sustain, that lands near 11-12 bits per key for a false-positive rate around 3%, and dropping f to about 7 bits with a semi-sorting trick tightens it further. The crossover rule worth memorising: at false-positive rates below about 3%, the cuckoo filter uses less space than a bloom filter for the same rate and throws in deletion for free. Above 3% the plain bloom filter is still a hair leaner. So the decision is not "which is better" but "where on the error curve do you live": loose filters (bloom), tight filters or any need for deletion (cuckoo). The max_kicks constant is the one tuning knob with teeth -- too low and you fail inserts that a little more shuffling would have placed, too high and a genuinely-full table wastes 500 doomed hops before admitting it. 500 is the paper's battle-tested default and I would not move it without a benchmark forcing my hand.

How this compares to C, Rust, and Go

In C, the cuckoo filter is a malloc'd byte array and three hash calls, and the flat table means none of the pointer-teardown hazards of the tree structures -- a single free and you are done. The eviction loop is where C shows its teeth: the swap is a three-line temp-variable shuffle you write by hand, and the ever-present risk is an off-by-one in the bucket indexing that silently reads a neighbouring bucket's slots. No crash, just a quietly wrong false-positive rate -- the nastiest kind of bug, the sort valgrind will never point at because nothing is technically illegal.

In Rust, the flat Vec<u8> table is once again a structure that does not pick a fight with the borrow checker (no internal references, ownership is one buffer). The eviction loop is where Rust's mem::swap shines -- it is the idiomatic move for "put this here and give me back what was there", exactly what the algorithm wants, and the borrow checker guarantees you are not aliasing the slot you are swapping through. Crates like cuckoofilter wrap it in a tidy API, and Rust's real gift here is the same as with the bloom filter: the type system stops you mixing hash strategies between insert, lookup, and delete, which would silently shred the invariant.

In Go, it is a []byte and hash/maphash, the garbage collector owns the one allocation, and libraries (seiflotfy/cuckoofilter is the well-known one) hide the eviction loop behind Insert/Lookup/Delete. Short and safe, at Go's usual price of interface-dispatched hashing on the hot path and a panic-or-bool failure convention that is looser than Zig's error union. Our Zig version sits where it always does -- the table sized with an explicit allocator you can aim at an arena (episode 26), the fingerprint width fixed in the type, and the one operation that can fail forced into the caller's face as an error.TableFull you cannot forget. Same structure across all four languages, but only in Zig is "this insert might fail" a compile-time fact rather than a comment you hope people read ;-)

Exercises

  1. Tighten the fingerprint, measure the rate. Right now the fingerprint is a full u8. Change it to a u16 (two bytes per slot) and re-run the false-positive test from the episode. The theory says the rate should drop by a factor of roughly 256 (each extra bit of fingerprint halves it). Confirm that empirically, then write a one-paragraph comment explaining the exact space-for-accuracy trade you just made: how many more bits per key did the u16 version cost, and at what measured false-positive rate does it now sit? Which of bloom-vs-cuckoo would you now pick for a 0.01% target?

  2. Resize on error.TableFull. Wrap add in an addOrGrow method that, on catching error.TableFull, allocates a new table with num_buckets * 2, re-inserts every live fingerprint from the old table into the new one, frees the old, and retries the failed insert. The subtle part: you cannot simply copy fingerprints slot-for-slot into the bigger table, because a fingerprint's valid buckets depend on num_buckets (the mask changed!) -- so you must recompute primaryIndex/altIndex for each. But you no longer have the original keys... so work out what you can recompute from a stranded fingerprint and its old bucket alone, and explain in a comment why re-insertion is trickier for a cuckoo filter than for a bloom filter (hint: bloom filters cannot be resized this way at all -- why not?).

  3. Pack two fingerprints per three bytes. An 8-bit fingerprint wastes space if you only need ~12 bits of it. Implement a variant with a 12-bit fingerprint, packing the four slots of a bucket into 6 bytes (four 12-bit values). Write getSlot/setSlot helpers that do the nibble-and-byte arithmetic, keep 0 reserved as empty, and re-run all three episode tests against the packed version. Then answer in a comment: how much memory did you save per key versus the u8 version, and what did you pay for it in contains latency (the packed reads are no longer a single aligned byte)?

Where this is heading

Step back and look at what every structure in this recent run has quietly assumed: an allocator handed to us from outside, and a table we size once and mostly leave alone. The cuckoo filter's error.TableFull was the first real crack in that comfort -- the moment the structure itself had to say "I have run out of room, do something". Exercise 2 pushes on it directly: growing a table means allocating a new one, moving everything, and freeing the old, and suddenly how memory is carved and recycled stops being someone else's problem and becomes the whole game.

So the question the next stretch turns on is this. What if the fixed-size table is not a limitation to grow past but the entire point -- a buffer of exactly known size that you fill and drain and refill forever, handing slots back the instant you are done with them, with no allocator call on the hot path at all? What if two threads could push and pop from that buffer at the same time without ever taking a lock, relying on nothing but the atomics we met back in episode 30? Recycling memory at speed, reusing slots instead of freeing them, and doing it safely while more than one thread watches -- that is the terrain we step onto next. We have spent a hundred-odd episodes deciding what to store. Time to get serious about how we hand the memory around ;-)

Thanks for reading -- and happy nesting!

@scipio

stem stemsocial steemstem zig programming
0
0
0.000
0 comments