Blocked and Partitioned Bloom Filters for Cache-Resident Probes

The arithmetic of a Bloom filter lookup is trivial: seven multiply-adds and seven bit tests. The cost is not arithmetic but memory. Seven positions drawn uniformly from a 1.2 MB array are seven distinct cache lines, and on a machine where an L1 hit takes a few cycles and a main-memory reference takes hundreds, the lookup is dominated by the probability that those lines are absent. A standard filter probed once per request has no reuse: each request touches seven lines that the previous request almost certainly did not. The structure is therefore memory-bound in the least favourable way, and two families of layout change — block the probes into one line, or slice the array so each probe hits a different region — attack it from different angles with different costs.

Why the naive layout is worst-case

Take a 64-byte cache line, which holds 512 bits. A filter at ten bits per key over one million keys occupies 1.25 MB, or about 20,000 lines. Seven random probes touch seven of those lines. If the filter fits in L2 the accesses are cheap but still serialised by the cache’s limited associativity; if it lives in L3 or memory, each probe is a separate miss and the misses cannot be overlapped by the hardware unless the accesses are independent enough for the out-of-order window to issue them concurrently.

There is a second, subtler effect: the probes are not only scattered but unpredictable. A prefetcher can follow a stride or a repeating pattern; seven positions derived from a hash have neither. Every probe is a demand miss on a cold line.

The obvious fix is to make the probes adjacent. If all $k$ positions for a key fall within one 64-byte line, the lookup issues one memory reference and the other six probes hit the same line. That is the blocked layout.

Blocking the probes into one line

Divide the array into blocks of $B$ bits, one per cache line, and choose a block index from the key. Within the block, derive $k$ positions from the key, reduced modulo $B$:

$$ b = h_1 \bmod \frac{m}{B}, \qquad p_i = b \cdot B + \left((h_2 + i h_3) \bmod B\right) $$

The error analysis changes less than the layout suggests, and the reason is worth working through because the intuition of “fewer bits, higher density” is misleading. A bit anywhere in the array is set by a given insertion with probability $k/m$, so after $n$ keys its occupancy is the same $1 - e^{-kn/m}$ whether or not the probes for a key are confined to one region. A lookup tests $k$ bits that are each occupied with that probability, giving

$$ \varepsilon \approx \left(1 - e^{-kn/m}\right)^{k} $$

to leading order — identical to the unblocked filter. Blocking does not shrink the effective array; it relocates the probes.

What blocking does change is that the $k$ probes are now drawn from a set of only $B$ positions instead of $m$, so two of them can coincide. When they do, the insertion sets the same bit twice, which is a no-op, and the lookup tests fewer than $k$ distinct bits. The expected number of duplicated probes is

$$ k - B\left(1 - \left(1 - 1/B\right)^{k}\right) \approx \frac{k(k-1)}{2B} $$

which for $B = 512$ and $k = 7$ is about 0.04 — a signal too small to matter. It becomes visible only when $k$ is a substantial fraction of the block: at $k = 32$ and $B = 512$ the loss is roughly one probe out of thirty-two, and the error rises in proportion. Blocked filters are therefore well matched to the probe counts that ten to sixteen bits per key imply, where the duplication term is two orders of magnitude below one probe; the design becomes a poor fit only when a very small bit budget pushes $k$ into the tens.

Block size is bounded from above by the cache line, not chosen freely. A 512-bit block already fills the 64-byte line on the common architectures, so a larger block means a second memory reference and forfeits the point of the layout. Blocks of 256 bits fit two per line and halve the duplication term, which is the usual choice when the filter is shared between threads and false sharing on a line matters more than the last fraction of a percent of error.

The gain is in references, and it is exact: an unblocked lookup touches $k$ lines, a blocked lookup touches one. At $k = 7$ that is a sevenfold reduction in cache lines per query, with no change to the asymptotic error rate.

Slicing instead of blocking

The partitioned layout takes the opposite approach. Split the array into $k$ equal slices, and derive one position per slice from the key. Each slice is $m/k$ bits, and the $i$-th probe is confined to slice $i$.

The false-positive probability is unchanged in form, because the probes are still one per slice and each slice has the same density as the whole array:

$$ \varepsilon \approx \left(1 - e^{-kn/m}\right)^{k} $$

The gain is different. The $k$ probes are now in $k$ different regions of memory rather than in one, which does not reduce the number of lines touched — it is still $k$ — but makes the accesses independent of one another, so the memory system can overlap them. Each probe has a known region and a random offset within it, which allows prefetching of the region’s base. And the slice index is a function of the probe number, not the key, so a query for a key always touches one line per slice.

The comparison is worth stating plainly. A blocked filter makes one memory reference and preserves the error rate of the unblocked design up to the duplication term. A partitioned filter makes $k$ references but they can be issued in parallel, and it also preserves the error rate. Which wins depends on whether the bottleneck is the number of misses or their latency.

Layout	Lines touched	Error at 10 bits/key	Probe parallelism
Unblocked	k (scattered)	≈0.8%	high, but unpredictable
Blocked, 512-bit	1	≈0.8%, plus k(k-1)/2B duplicate probes	none needed
Blocked, 256-bit	1 (shared)	≈0.8%, with half the duplication term	none needed
Partitioned	k (one per slice)	≈0.8%	high, predictable

The error figures follow from the formulas above at $k = 7$ and ten bits per key rather than from measurement; the leading term is the same for all four layouts, and the differences between them live in the lower-order terms and in how the accesses interact with the memory hierarchy.

Insertion, deletion, and the cost of a bigger write

Blocking changes writes as much as reads. Inserting a key dirties one cache line instead of seven scattered ones, which for a filter shared between threads means one line of contention rather than seven. That is a substantial reduction in coherence traffic when many threads insert concurrently into a large filter: the probability that two threads touch the same line falls with the block count, and the false sharing that would otherwise serialise unrelated insertions disappears.

Partitioning has the opposite effect on writes: a key dirties one line in each of $k$ slices, so the write set is as large as the unblocked case. Its advantage is that the slice for probe $i$ is determined by $i$, so two threads inserting different keys contend only when their probes coincide within a slice.

Neither layout supports deletion. Both are still bit arrays, so the counting variant is required for removal, and blocking a counting filter multiplies the per-block counter traffic by the same factor the bits were multiplied by.

Choosing the block index

The block index must be uniform over the blocks and independent of the intra-block offsets. With the two-word derivation, $h_1$ selects the block and $h_2, h_3$ generate offsets, so the constraint is the familiar one from double hashing: the values must be independent and the modulus must not share a factor with the stride.

The power-of-two block count makes the block index a mask, and the intra-block offset a mask of the low bits. Taking the low bits for the offset and the high bits for the block is the safe split; taking the low bits for the block and reusing them for the offset correlates the two and clusters probes inside blocks. A mixing step before the split costs one multiply and removes the hazard.

const BLOCK_BITS: usize = 512;

fn mix64(mut x: u64) -> u64 {
    // splitmix64 finaliser: cheap avalanche, one multiply per step
    x = (x ^ (x >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
    x = (x ^ (x >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
    x ^ (x >> 31)
}

fn probe_indices(key: u64, blocks: usize, k: usize) -> impl Iterator<Item = usize> {
    let h = mix64(key);
    let block = (h as usize) & (blocks - 1);
    let h2 = mix64(h ^ 0x9E37_79B9_7F4A_7C15) | 1;   // odd stride within the block
    let base = block * BLOCK_BITS;
    (0..k).map(move |i| base + ((h2.wrapping_mul(i as u64) as usize) & (BLOCK_BITS - 1)))
}

fn insert(bits: &mut [u64], key: u64, k: usize) {
    let blocks = bits.len() * 64 / BLOCK_BITS;
    for p in probe_indices(key, blocks, k) {
        bits[p / 64] |= 1u64 << (p % 64);
    }
}

The block is a power of two so the intra-block arithmetic is masking, and the block count is a power of two so the block index is too. The two masks use disjoint bit ranges of the mixed hash.

When the layout is the wrong lever

Blocking helps when the filter is large enough to miss cache and is queried often enough that the misses matter. A filter of a few hundred kilobytes that stays resident in L2 gains almost nothing: the reference count per query falls from $k$ to one, but those $k$ references were already L2 hits, and the duplication term is still paid on every insertion and lookup. A filter queried once per second gains nothing either: the miss latency is hidden by whatever else the program is doing, while the layout’s probe-aliasing and its extra parameter remain.

The layout also interacts with the filter’s size. A partitioned filter at $k = 7$ has seven slices; if each slice is small enough to stay in L1, the whole filter is effectively cached and the partitioning is pure overhead. The blocked filter’s advantage grows with total size, because the number of lines it saves per query is fixed at $k - 1$ while the miss probability rises toward one.

A third consideration is serialisation. Both layouts change the mapping from key to positions, so a filter written by a blocked implementation cannot be read by an unblocked one. The block size joins $m$ and $k$ as a required parameter of the on-disk format, and the format must record the probe derivation as well. The failure is silent: a mismatched reader returns negatives for present keys, and the filter has no way to detect the mismatch from its contents.