GBF — Beating Bloom Filters in 24 Hours

Overview

I spent one weekend trying to build a membership filter that beats Bloom and Xor at their own game in C++. I ended up with something that genuinely does, on the machine I had to test on. This is what actually happened — eight ideas, seven of them failed, one of them shipped, and the path between them turned out to be the interesting part.

Final Results (Apple M2, 1M random keys)

Filter	bits/key	build (ms)	query (ns)	FP rate
GBF v1.0 (this work)	8.520	30	8.4	0.78%
Blocked Bloom (8.26 bpk)	8.260	5	16.4	2.90%
Blocked Bloom (12 bpk)	12.000	4	14.8	1.97%
Naive Bloom (k=6)	8.500	7	17.6	1.69%

At near-equal memory, GBF is ~2× faster on query and ~3.7× better on false positive rate than a competent Blocked Bloom. The remaining honest weakness: build is ~6× slower than Bloom.

The Brief

"We're trying to beat industry-standard data structures at their own game, from scratch, in C++. Target: a membership filter that beats Bloom (used by Redis, RocksDB, Chrome) and the Xor filter (used by Cloudflare). Target metrics: <9 bits/key, 2–3 hashes, >250M ops/sec, zero false negatives. Pure C++17. No dependencies. Must compile in <100 ms for 1M keys. Pick a target. We'll build it."

The starting hypothesis: instead of storing fingerprints, encode each block as a system of GF(2) linear equations, solved at build time via Gaussian elimination. At query time you compute v · P (mod 2) — a couple of parity checks against the block's payload — and compare against an 8-bit fingerprint. This is called a Ribbon Filter (Dillinger & Walzer 2021); I didn't know that at the start. I would learn.

Development Journey

v0.1 — Broken in a Way That Looked Great

The first benchmark numbers were a dream:

build: 246 ms
query: 14.8 ns
memory: 85 bits/key
false negatives: 992,079 / 1,000,000

99% of member keys were being reported as not present. Everything was broken. Two bugs:

The cuckoo BuildBlock struct had a 512-byte temporary array inline. With alignas(64) padding, that turned 65-byte logical blocks into 128-byte physical ones. Hence the 10× memory blow-up.
The hash used during Gaussian elimination didn't match the hash used at query time. Each key got placed into the matrix with one seed pattern, but queried with a different one. Hence 99% false negatives.

v0.2 → v0.4 — Actually Competitive

v0.2: Moved temporary build state out of the persistent struct, introduced Structure-of-Arrays layout. 8.67 bits/key, 0 false negatives, 267 ms build.

v0.3: Parallelized the build via lock-free sharding. Build dropped to 103 ms.

v0.4: The big query-side win. Replaced every % num_blocks modulo in the hot path with a bitmask by rounding partition sizes to powers of two. Added explicit prefetch. Query latency dropped from 17 ns to 11.6 ns.

At v0.4 the filter was honestly competitive: ~11 ns query, 8.52 bits/key, 0.78% FP.

v0.5 — The Honesty Pass

Added three pieces of real infrastructure:

libFuzzer harness — 176,379 executions in 46 seconds, 0 crashes
GitHub Actions CI — gcc + clang on real x86, full test + bench suite
FastFilter-compatible C API — five functions matching Lemire's xor8_* naming

v0.6 — Stacked Filters (Failed)

Tried putting a tiny Bloom in front of GBF to short-circuit negative queries. Didn't work:

50/50 mixed: 18.5 ns (GBF) → 14.0 ns (Stacked) but +24% is branch prediction artifact
5/95 negative-heavy: 10.2 ns (GBF) → 10.8 ns (Stacked) — net loss

GBF's existing prefetch already overlaps the cache-line fetches with hash computation. No miss latency left to hide.

v0.7 — Bumping (Failed)

Tried using the bumping technique from BuRR (Sanders et al.) to push block load factors higher. Measured results:

GBF<2>:       8.520 bpk, 28 ms build, 10.2 ns query
GBF-Bump<2>:  8.651 bpk, 27 ms build, 13.5 ns query

Worse on every axis. The power-of-2 partition sizing from v0.4 and the bumping idea are structurally incompatible — you can't have both without giving up the 5–10 ns query speedup that came from removing the modulo.

v0.8 — The Wild Idea Bag (1 out of 3)

Three cross-disciplinary attempts in parallel:

A. Gray-Code Cuckoo Placement

Failed. Constraining h2 to a 6-bit Hamming neighborhood of h1 clustered keys too tightly. Cuckoo placement broke at TARGET_LOAD=62 and had to fall back to 56, which doubled blocks_per_part.

B. NEON SIMD Parity Verification

Worked. Replaced the 8-iteration parity loop with explicit NEON intrinsics:

100% positive:     8.1 ns → 6.5 ns   (−20%)
50/50 mixed:       21.8 ns → 20.2 ns  (−7%)
5/95 negative-heavy: 12.1 ns → 9.2 ns (−24%)

Same memory, same FP rate, zero false negatives. Stable across runs.

C. IBLT Auxiliary Structure

Failed. IBLTs measured 9.3% FP rate vs target 0.78%. IBLTs are set-reconciliation structures; pure membership is the wrong workload.

Final v1.0 Metrics

Metric	Value
bits/key	8.520
build (1M keys, 10 threads)	~30 ms
query latency	8.4 ns
batch query (prefetch)	9.2 ns
false-positive rate	0.78%
false negatives	0

Beats a competent Blocked Bloom on the same hardware on both query latency (~2× faster) and FP rate (~3.7× better) at near-equal memory.

What I Learned

Most Ideas Fail

I tried 8 algorithmic improvements past v0.4: stacked filters, paired-XOR, bumping, Gray-code cuckoo, IBLT aux, polynomial verification, holographic reduced representations, NEON parity. Seven failed. One worked. That's a hit rate of ~12%, which is actually pretty normal for systems-level optimization.

Cross-Disciplinary Borrows Usually Fail at the Interface

The 1-in-8 win came from a borrow that didn't directly apply but pointed me at something the compiler was doing suboptimally. Borrows don't deliver the win themselves; they're prompts that make you look in places you wouldn't have.

The Contribution is Engineering

This is not a new algorithm. It's Ribbon-Filter math from 2021, broken into cache-line-sized local matrices (engineering choice), parallelized via lock-free sharding (engineering), accelerated via NEON SIMD (engineering). Every interesting decision happens at the interface between math and hardware.

Failed Experiments Are the Content

v0.6 stacked filters and v0.7 bumping both sounded right and both failed measurably, for non-obvious reasons that only became clear after running the benchmark. The failures are more informative than the success.

What I Will NOT Claim

This is not novel algorithmic science. It is engineering on top of the Ribbon Filter (Dillinger & Walzer 2021).
These numbers are Apple M2 only. I do not own x86 hardware. CI runs on GitHub's ubuntu-latest x86 runners (compile + test only); I have not measured x86 query latency or build throughput from any machine I control.
The bumping technique (v0.7) didn't work here. It may well work in a Ribbon variant without power-of-2 partition sizing. That's a different experiment.
This took 24 hours of wall clock — heavily AI-assisted (Claude wrote most of the C++ under my direction). It is what one person + a strong LLM can produce in a focused weekend.

Numbers I Will Defend

Claim	Where to Verify
8.520 bits/key on M2, 1M keys	`./build/gbf_bench`
8.4 ns single-query, 9.2 ns batch	`./build/gbf_bench`
0 false negatives over 1M random keys	`./build/gbf_test` (24 tests)
Beats Blocked Bloom on query + FP at same memory	`./build/bench_vs`
176,379 fuzz executions, 0 crashes	`./build-fuzz/fuzz_gbf`
Code compiles on linux/amd64	`./scripts/x86-build-check.sh`

If any of those don't reproduce on the same hardware, the writeup is wrong and I want to know.