Blocked filter — where it appears
Named by 15 essays across one field — each of them below, with the objects they name alongside it.
Positions confined to one line
A Bloom filter lookup reads 5.55 cache lines because its six positions are scattered across the whole filter. Confining them to a 512-bit block makes it exactly one, and costs 7% more false positives at eight bits a key. At sixteen bits a key the same block costs 91%, and the two-value trick that is free across a whole filter costs another 135% inside one — because a block is a small filter, and small filters are where the penalty lives.
Two blocks and the chances they add
Send each key to the emptier of two 512-bit blocks and the busiest block of a filter at sixteen bits a key holds 35 keys instead of 51. The false-positive rate gets worse: 0.0997% against 0.0854%. At eight bits a key it nearly doubles. A lookup cannot tell which block a key went to, so it has to ask both, and asking twice is two chances to be wrong. At every density a filter is commonly built at, the repair that tames a hash table's worst bucket buys a filter nothing that a block twice as wide does not.
A block the lookup can work out
Sending each key to the emptier of two blocks flattens the load and doubles the chance of a false positive, because a lookup cannot know which block was chosen. Give each block a threshold on a hash of the key instead and the lookup can work it out: one block read, one chance, and 46% of the load balance kept. At sixteen bits a key that is 0.0618% against one block's 0.0854% and two blocks' 0.0997%. The threshold costs 1.5% of the budget and two bits of it are nearly as good as sixteen.
A penalty set by the block
A blocked Bloom filter pays a penalty for its uneven block loads, and a threshold that lets a lookup work out its block repays about a third of it — measured on 2,048 keys, with a prediction that larger filters would widen the gain. From 2,048 keys to 131,072 nothing moves: one block holds 0.086% to 0.090% against a computed 0.086%, and the threshold design 0.060% to 0.065%. The busiest block grows and the rate does not follow it. What sets both the penalty and the repair is the keys a block holds. A threshold turns out to be worth one doubling of the block's width, and its advantage shrinks from 40% at sixteen keys a block to between 5% and 13% at 128.
The bits a second threshold costs
A blocked Bloom filter whose first block carries a threshold was proposed a second threshold on each key's second block, with a third block for keys both refuse. It does what it was meant to: at 512-bit blocks it removes nearly a third of the load spread the first threshold left. And the rate does not fall — 0.066% against 0.062% — because the second table, paid for in blocks, raises the rate the filter would have with no spread at all by more than the narrower spread saves. The threshold was stored in more bits than it needs: at four to six bits, one threshold beats the eight-bit design by about a tenth on one run, and a second threshold of the best width ties it at 512-bit blocks.
A threshold knows only its own block
A blocked Bloom filter that gives each block a threshold on a hash of the key lets a lookup work out which of two blocks a key went to, and it spends a small table to do it. Sharing one threshold among a group of blocks would shrink the table, and was proposed as the next saving. It is a loss at every group size. With one four-bit threshold a block, 512-bit blocks reach a false-positive rate of 0.061%; shared by a pair, 0.071%; shared by sixteen, 0.100%, worse than no threshold at all. Neighbouring blocks fill at unrelated moments, so a shared threshold closes when the first of its group does, and every key it turns away lands in a second block chosen at random.
Two hashes that shared their low bits
Two pages on blocked Bloom filters with thresholds each recorded an instability they could not explain: a false-positive rate that collapsed on one seed at 256-bit blocks, and a pair of four-bit thresholds measuring 0.169% where its neighbours measured 0.08%. Both came from how a hash was brought into range. Every filter took its block and its ordering value as a modulo of a multiply-shift hash, and the low bits of such a hash depend only on the low bits of the key, so the two values were dependent whenever the block count had a factor of two to spare. At 992 blocks the threshold filter measures anything from 0.185% to 0.645%; read from the hash's top bits, 0.126% to 0.133%.
A code that has to fit its worst line
A blocked Bloom filter's four-bit thresholds are far from uniform: two blocks in five never close, and the rest crowd into the upper values, an entropy of 2.4 to 2.8 bits. A table coded from that distribution was predicted to match the four-bit rate on under three bits a block. Packed end to end it does, at 2.65 to 3.03 bits, and it costs every lookup a second read for the index. Packed a fixed number to a cache line it needs no index, but every line must hold its worst run of long code words, which costs 3.19 bits at 64-bit blocks and eighty-three code words decoded a lookup. Where the table is large enough for the saving to show, a plain three-bit table gets part of it with none of the costs.
A bit for whether it closed
Almost half of a blocked filter's threshold table says one thing: this block never closed. Store that answer as a bit a block, and a closing value only for the blocks that did, found by counting the ones before it. At 64-bit blocks the prediction was 3.1 bits a block and two cache lines. Packed end to end it lands at 3.15 bits and 2.5 lines; packed a line at a time it reads two lines and counts one word, and costs 3.64 bits, because every line must hold the most closings any line happens to draw. At 512-bit blocks, where three blocks in five close, it saves under a tenth of a bit.
The worst of more lines
A blocked Bloom filter's threshold table, stored as a bit for whether each block closed and a value for each block that did, packed a fixed number of blocks to a cache line, costs 3.64 bits a block at 64-bit blocks because every line must hold the most closed blocks any line draws. Sizing the line for the mean plus one standard deviation, and moving a line's excess values to a shared overflow, was predicted to cost about 3.25 bits and send under one closed lookup in a hundred to a third line. The lookups behave as predicted: 0.6% read the overflow, 2.003 lines a lookup. The bits land at 3.38, because every line must carry the offset where its moved values begin. What the measurement found instead is that the worst line is a property of how many lines there are: 3.38 bits at two thousand blocks and 3.62 at a hundred and twenty thousand, while the line sized for the usual line costs the same at every size.
An offset that only has to reach its neighbours
A blocked Bloom filter's threshold table, its cache lines sized for the mean number of closed blocks plus one standard deviation and their excess values moved to a shared overflow, cost 3.38 bits a block where 3.25 was predicted, because every line carries a nineteen-bit offset into the overflow. Grouping lines, each line's offset reaching only its group's part and each group's position held once in an array of its own, was predicted to cost 3.31 bits a block for 2.0064 lines a lookup. It costs 3.301 for 2.0060, as predicted. But the nineteen bits were mostly an offset sized to address a table of moved values, when the overflow this table has needs eleven: sized for the overflow it has, the ungrouped line costs 3.337 for no extra line at all. Grouping's further three hundredths cost a line a moved lookup, and spent on room instead, that line buys more. At equal lines a lookup the grouped table is the dearer, by a hundredth to nine hundredths of a bit.
A reserve sized for the spill
A split threshold table gives every line the same room, the mean number of closed blocks plus some standard deviations. Giving each line room for the mean and each group of 64 lines a shared reserve at one standard deviation of the group's total was predicted to cost about 3.24 bits a block for 2.006 lines a lookup, under the best ungrouped line. The reserve it predicts holds 52 values where the group's lines spill 145: it is full in every group, the spills go on to a third line, and the table lands on the ungrouped curve. Sized for the spill instead, the reserve puts the table under that curve at every room, by two to three hundredths of a bit a block.
The room the lines lend
A blocked filter's threshold table gives each 512-bit line room for its closed blocks' values, and a group reserve sized for the spill had just put it under the ungrouped curve. A line under its room leaves slots empty that are already paid for, so its neighbours' spills could be carried forward into them, with no reserve at all: predicted at about 3.12 bits a block for 2.012 lines a lookup. The bits are right and the lines are not. At room for the mean a carried value passes 12.8 lines before it finds a slot, because a run of lines that is room-for-the-mean on average is a queue with nothing to spare. Given three quarters of a deviation of room, the walk falls under two lines and the carried table lands a hundredth of a bit under the reserve.
A walk that stops at two lines
A blocked filter's threshold table, its lines sized for the mean number of closed blocks and each line's surplus carried forward into the next lines' empty slots, was cheapest in bits — 3.113 a block — and dear in lines, 2.183 a lookup, because a carried value joins a queue with no slack and walks 12.8 lines. Capping the walk was predicted to keep most of the bits, about 3.13, for under 2.02 lines, two hundredths under a reserve sized for the spill. Capped at two lines, the walk sends 53% of its carried values to overflow, and the table costs 3.180 bits a block for 2.027 lines. That is a hundredth under the spill-sized reserve at the same lines and a few thousandths under the uncarried line's curve: at room for the mean most of what joins the queue would wait more than two lines, so the overflow becomes the reserve by another name. With room to spare, every cap loses to the reserve.
A queue that drains at intervals
A blocked filter's threshold table, its lines sized for the mean number of closed blocks and each line's surplus carried into the next lines' free slots, is cheapest in bits and dear in lines, because at room for the mean the queue of carried values never drains. Capping the walk turned the cap into an overflow. Giving every eighth line a deviation of extra room was predicted to empty the queue there, bound every walk by eight lines, and cost about 3.15 bits a block for under 2.02 lines a lookup. It costs 3.123 bits for 2.103 lines. After a slack line the queue is empty a third of the time, walks reach 33 lines, and the reason is arithmetic: one line's deviation of room is not room for eight lines' wander, which grows as the square root of eight. The slack lines do buy something — a hundredth or two of a bit a block under spreading the same room evenly, at five of the six spacings — but they buy it at lines no other design here would accept.
Named alongside it
The objects these essays reach for when they reach for this one.
Design parameterThresholdFalse-positive rateBloom filterCache lineBit vectorBalls in binsTwo choicesLoad balancingPredictionCacheLocality