Positions confined to one line

Two hash values and the keys they copy measured what it costs a Bloom filter to make its $k$ positions from two hash values as $h_1 + i\,h_2$ rather than from $k$ independent ones. The penalty is real and it is a finite-size effect: 2.6 times the independent rate on a filter of 64 bits, 1.13 times at $k = 7$ on 1,024 bits, and nothing worth measuring on a filter of any practical size. It ended by observing that there is a common design which makes every filter small from a key’s point of view.

A blocked Bloom filter uses a first hash to choose one block — 512 bits, a cache line’s worth — and puts all $k$ positions inside it. A lookup then reads one line instead of $k$ scattered words, which is the same locality argument the bucket that fits a line made for a hash table’s probe sequence. And the penalty a key’s copies cause is now counted against 512 bits rather than against the whole filter, so a construction that was free everywhere becomes a question again.

This page measures the block’s own cost, the two-value penalty inside it, and whether the cubic repair still works there.

What a block buys, in lines #

The quantity a block exists to reduce is easy to count and rarely counted.

5.55 rather than six, because six positions drawn from thirty-two lines occasionally repeat one. The blocked filter reads one, by construction, and the two points at the right of the plate say what “by construction” means: a block of 1,024 bits spans two lines and reads 1.97 of them, and a block of 2,048 spans four and reads 3.29. The largest block that guarantees one line is one line, and every block smaller than that reads one line too and costs more rate. So the design has exactly one sensible setting for the block, and the rest of this page is about what that setting costs.

The rate paid for it is 2.329% against 2.171% — seven per cent more false positives in exchange for a fifth of the memory traffic. Whether that is a good trade is not a question this page can settle, because it compares a rate with a count of cache lines and nothing here converts one into the other. What it can do is say how the seven per cent behaves, because it is not a constant.

It is also worth being concrete about what the two quantities buy, because they are paid by different parts of a system. The lines are paid on every lookup, positive or negative. The rate is paid only on a negative that answers yes, and what it costs then is whatever the filter was standing in front of: the filter each run carries measured a log-structured store where a false positive is a block read from a level that does not hold the key, and the filter that feeds the table one where it is a wasted probe into a hash table. A false positive against a disk read is worth thousands of cache lines; a false positive against an in-memory probe is worth one or two. So the same 0.158 percentage points is a good trade in one system and a bad one in the next, and a filter’s own plates cannot say which — which is why this page reports the two costs separately rather than combining them into a figure of merit nobody could use.

The block’s own cost, against the block’s size #

The block’s cost falls steadily as the block grows and is already small at 512 bits. The mechanism is the one a reader may guess and it is worth stating exactly, because it is the only thing on this page that is not about hashing.

A whole filter of 16,384 bits holding 2,048 keys holds exactly 2,048 keys. A filter divided into thirty-two blocks holds, in each block, however many of the 2,048 keys happened to choose it.

A block that received 77 keys is a filter twenty per cent over its design load, and the false-positive rate is steeply convex in the load — at eight bits a key and six positions, twenty per cent more keys is about forty per cent more false positives. The nineteen blocks below the mean save less than the thirteen above cost, and the difference is the whole of a block’s penalty. It shrinks as the blocks grow because the relative spread of a count like this falls as its mean rises: at 2,048-bit blocks the mean is 256 and the spread about sixteen, six per cent rather than twelve, and the measured penalty is 1% rather than 7%.

Nothing about hashing is involved in that, which is worth being clear about before the next section, where everything is.

That also predicts where the penalty is largest, and the prediction is checkable.

At four bits a key a 512-bit block costs nothing measurable. At sixteen it costs 91%, nearly doubling the rate. The reason is the convexity again: a rate of 14.7% cannot rise much, and a rate of 0.049% has almost everywhere to go. A blocked filter is close to free when it is loose and expensive when it is tight, which is the opposite of what a designer choosing “one cache line per lookup” would expect from a decision that looks purely architectural.

That is the first practical finding and it inverts the usual reasoning. Blocking is sold as a locality optimisation with a small constant penalty. It is a locality optimisation whose penalty is set by how precise the filter is being asked to be, and the filters where precision matters most are the ones where blocking costs most.

Two hash values, inside a block #

Now the question the earlier page left. Across a filter of 16,384 bits the three position schemes are indistinguishable: 2.171% from independent hashes, 2.132% with an odd-stepped $h_1 + i\,h_2$, 2.184% with the cubic term. Inside a block they are not.

The shape transfers exactly. The earlier page’s account says the penalty comes from a query whose start-and-step pair copies a stored key’s whole progression, or copies it in all but a few positions, and that the number of such pairs over the number of pairs available gives a penalty of about $12n/m^2$. Evaluated with the block’s bits and the block’s keys, that account predicts the penalty halving at every doubling of the block — and it does, four times over, which is what a flat quotient means.

The constant does not transfer, and it is out by a factor of about 2.1 in a direction the account itself explains. Its twelve counts two pairs that copy a stored key exactly and four more for each number of positions missed. A query that copies a stored key in all but one position is a false positive only if that remaining position happens to be set by some other key — and at the optimal number of positions a Bloom filter’s bits are set half the time, by construction. Weighting the near-copies by the chance their remaining bits are set turns 12 into about 6, and the measurement reads 5.6. The earlier page found the same account overstating by about a fifth on a whole small filter and said so; inside a block, where the near-copy terms matter more, it overstates by rather more.

What this costs a real filter is on the density plate above. At eight bits a key the two-value scheme adds 9% on top of the block’s 7%; at sixteen bits a key it adds 135% on top of the block’s 91%, taking a filter that would have answered 0.049% of absent keys yes to one that answers 0.219%. A blocked filter at high precision is exactly the case the earlier page’s penalty was measured on, because a 512-bit block is a small filter, and the construction that is free across a filter of any size is not free inside one of its blocks.

Whether the cubic term still repairs it #

It does, and mostly.

Across the block sizes on the second plate, the cubic term — positions at $h_1 + i\,h_2 + (i^3 - i)/6$ — recovers most of the two-value penalty at every size. In blocks of 64 bits it takes 4.717% back to 3.893% against 3.791% for independent hashes, closing 89% of the gap. At 512 bits it takes 2.546% back to 2.392% against 2.329%, closing 71%. At 1,024 and 2,048 bits it lands slightly below the independent scheme, which is within the measurement’s spread rather than a finding.

Setting that plate beside the block sweep answers a question it would be easy to get wrong. A whole filter of 512 bits pays 1.23× for an odd-stepped two-value scheme; a 512-bit block pays 1.061×. The block looks kinder and is not. It holds 64 keys where the standalone filter holds 50.7, so its absolute penalty is larger — 0.143 points against 0.18 — and the multiplier is smaller only because the block’s base rate is 2.35% where the standalone filter’s is 0.80%. A multiplier is a statement about its denominator, and the denominator here is how precise the filter was being asked to be, which is the same variable the block’s own penalty turned on.

So the practical arrangement is unchanged by blocking: two hash values, a cubic correction, and the penalty is a few per cent rather than tens of per cent. The cost of the correction is two multiplications and a division by six per position, which is nothing beside a cache miss — and the whole reason for a blocked filter is that it has fewer cache misses to hide behind.

What a designer chooses, and in what order #

The plates above have three settings in them and they are not independent, so the order of the decisions matters.

The block size is not a free parameter. The hero plate says a block smaller than a cache line reads one line and costs more, and a block larger than one reads more than one line. So a blocked filter’s block is a cache line, always, and there is nothing to sweep. Every other page on these filters has found the opposite — the threshold somebody chose swept four constants written into real code and found none of them at an optimum — and it is worth noticing when a constant genuinely has only one sensible value.

The bits a key is where the decision actually is. Blocking costs nothing at four bits a key and nearly doubles the rate at sixteen, so the question “should this filter be blocked” cannot be answered without the target rate. A filter at 1% is blocked for free; a filter at 0.05% is not, and a designer who blocks it has quietly moved it to 0.09% — still a small number, and twice what was asked for.

And the two-value construction is decided after both. Its penalty inside a block is $5.6n/m^2$, which at 512 bits and 64 keys is a seventh of a percentage point and at sixteen bits a key is more than the block’s own cost. The cubic term removes most of it for two multiplications, so the honest default is to use it and stop thinking about the question — which is the conclusion the earlier page reached about whole filters and which blocking does not overturn.

The reason this ordering is worth writing down is that all three decisions look architectural and only one of them is. The block size is a fact about the machine. The bits a key is a fact about what the caller will accept. And the position scheme is a fact about the hash, which is where a reader would expect the whole page to be and where almost none of it turned out to be.

What this says about where a filter’s rate comes from #

Three of the plates on this page are the same fact in three coordinates, and it is worth naming because it governs every filter design measured here.

A filter’s false-positive rate is set by its bits per key and its load, and both of those are properties of the smallest independently-addressed piece of it. A whole filter’s mean load is not what decides its rate if its keys are divided into blocks that each have their own; a fingerprint table’s mean fingerprint length is not what decides its life if its generations have their own, which is what the bits given to the wrong keys measured; and a stack of filters has a rate that is the sum of its layers’ rather than the rate of any of them.

The general form is that dividing a structure into pieces makes the pieces’ variation part of its cost, and a design that divides for locality is paying that cost whether or not it is measured. Seven per cent at eight bits a key is a price worth paying for a fifth of the memory traffic. Ninety-one per cent at sixteen bits a key is a different decision, and it is made by the same line of code.

What is not measured here #

Cache lines counted, not cache misses. The hero plate counts distinct 512-bit lines a lookup’s positions fall in. A real lookup misses on however many of those are not already resident, which depends on the filter’s size against the cache, on what else is running, and on the prefetcher. The block that is not a block is the argument that this model is a model; the count here is the best case for the scattered filter and the exact case for the blocked one, so the gap measured is a lower bound on the gap in misses.

One filter size. Every measurement holds 2,048 keys. The block penalty depends on the keys per block rather than on the filter’s size, so a larger filter at the same bits a key and the same block size should show the same penalty; that is an argument rather than a sweep.

No SIMD. The practical argument for a blocked filter includes setting and testing all $k$ bits of a block with vector instructions, which changes the time and not the rate. Nothing here is timed.

One number of positions per density. The load plate sets $k$ to the optimum for each bits-a-key, which is the right comparison for a designer and the wrong one for isolating a mechanism: the block penalty and the $k$ both move between points. A sweep at fixed $k$ would separate them and is not drawn. The threshold somebody chose is the general warning — a plate that moves two settings at once reports their sum.

Blocks chosen uniformly. The first hash spreads keys over blocks as evenly as a random assignment does, which is what makes the block’s penalty a balls-in-bins effect. A filter whose keys arrive with structure the block hash does not destroy would be worse, and by an amount no plate here bounds.

One correction, at one load. The cubic term is the only repair measured, and the weighting that turns twelve into six assumes the filter is at the load where half its bits are set. A filter deliberately run under its optimal load sets fewer, and the account’s constant would move.

Still open: a block that is chosen twice #

Every key on this page chooses its block once, and a block that receives more keys than its share stays overloaded for the filter’s life. That is a balls-in-bins problem with a standard repair, and the repair has already been measured in another structure: the second choice found that offering each key two buckets and taking the emptier one lowers the maximum load from a logarithm to a logarithm of a logarithm.

A filter cannot quite do that, because a lookup must know which block to read without knowing how full either was. But it can do half of it: choose two candidate blocks, insert into the emptier, and at lookup read both. That costs a second line on every lookup — half the saving the block was for — and should flatten the block-occupancy spread that this page’s whole penalty comes from.

The measurement that follows builds that filter at each density on the load plate and asks three things: how much of the block penalty the second choice removes, whether what it removes is worth reading a second line at eight bits a key and at sixteen, and whether a rule that reads the second block only when the first says no — which is free on a true negative and costs nothing on a true positive — keeps the rate of reading both while costing closer to one.