A bit for whether it closed

A code that has to fit its worst line tried to shrink the table a blocked Bloom filter keeps beside its blocks. Each key has two candidate blocks, and each block carries a threshold on an ordering hash, the design a block the lookup can work out introduced: a key below its first block’s threshold is stored there, and the rest go to their second block. A lookup reads the threshold and knows which block to read. The thresholds are four bits a block in the plain design, and their values are far from uniform. About half the blocks never close, and the rest close in the upper part of the hash’s range. A Huffman code from the filter’s own distribution sat at the entropy, about 2.75 bits a block at 64-bit blocks. Packed a fixed number of thresholds to a cache line, so that a lookup needed no index, it cost 3.19 bits, because every line had to hold its worst run of long code words, and a lookup decoded 83 code words to reach its own.

Its closing section noticed that almost half of the table’s entropy is a single question. Did this block close at all? The Huffman code spent one bit on each block that never closed, and it spent that bit inside a variable-length stream that a lookup had to walk. The section proposed answering the question separately: a bit vector with one bit a block, and a value only for the blocks that closed, stored in a second array and found by the block’s rank among the closed ones. A rank on a bit vector is one of the cheapest operations there is. It predicted about $1 + 0.53 \times 4 \approx 3.1$ bits a block at 64-bit blocks with four-bit values, under three with three-bit values, and two lines a lookup. It asked whether counting ones would beat both the indexed code’s third line and the line-packed code’s 83 decodes.

The rank is cheap: one word counted, in the same line. The bits are where the prediction fails, and they fail the way the Huffman code’s did.

Two tables that answer one question first #

The filter is the earlier page’s: 16 bits a key, about two thousand blocks at every width (8,192 keys at 64-bit blocks up to 65,536 at 512), every hash read from its top bits, the threshold table paid for in blocks given up. Every rate is the mean of four seeds, a quarter of a million absent keys a filter.

The split table is laid out two ways. Packed a line at a time, each 512-bit line covers a fixed run of $C$ blocks: first their $C$ bits of “closed or not”, then the closing values of the closed ones among them, in order. A lookup reads that one line. If its block’s bit is zero, the block never closed and the key goes to its first block. If the bit is one, the lookup counts the ones before it in the line’s vector, a popcount on one or two 64-bit words, and reads that many values along. $C$ is the largest run for which every line of the filter fits, and that is the part a prediction from the average cannot see.

Packed end to end, the vector is one long array and the values another. Each 512-bit line of the vector gives up a few bits at its head to the count of ones before it, so a block’s rank is that count plus a popcount inside one line. A lookup reads the vector’s line. A block that closed sends it on to the value’s line, a second table read before the block.

The prediction, met in one layout #

At 64-bit blocks, where 52% of thresholds close, the split table packed end to end costs 3.15 bits a block, against a predicted 3.09; packed a line at a time it costs 3.64. The prediction was arithmetic about the average, one bit a block and four more for each block that closes, and the end-to-end table is the average plus a few bits a line for the running counts. The line-packed table is the average plus something else.

The three-bit values behave the same way. A bit and three, a line each, costs 2.88 bits a block at 64-bit blocks, under three as predicted. But its mean is 2.51, so it too pays a third of a bit beyond what its contents need.

Against the line-packed code, the split loses on bits at every width. The Huffman code costs 3.19 at 64-bit blocks and 2.80 at 512, falling as blocks widen, while the split rises from 3.64 to 3.91. The Huffman code captures both halves of the closing distribution, the mass at “never” and the shape of the rest. The split captures only the first, and the first shrinks as blocks widen.

The busiest line sets the price #

Packed a line at a time, the split table pays 0.4 to 0.5 bits a block more than its contents at every width. At 64-bit blocks a line covers about 141 blocks, and on average 74 of them close. A line has room for $512 - 141 = 371$ bits of values, which is 92 four-bit values. The average line needs 74. The table pays for 18 values a line that most lines never use, because a line is a fixed run of blocks and which blocks close is decided by the keys.

The number of closings in a run of 141 independent blocks is close to a binomial count, with a standard deviation of about six. A filter has fourteen such lines, and every seed builds four filters, and every line of every filter must fit, since a lookup computes a block’s line from its index alone and cannot be sent elsewhere. So $C$ is set by the busiest run the filters happen to draw, and the busiest of some fifty draws sits two or three standard deviations above the mean. That is 12 to 18 values, 48 to 72 bits a line, and about half a bit a block.

The Huffman code paid for the same thing. A code that has to fit its worst line found its line-packed table at 3.19 bits where the Huffman code’s mean was 2.75, 0.44 bits of headroom, because its code words vary in length and a line must hold its longest run of long ones. The split’s headroom is the same size for a different reason. Its entries are of two fixed sizes, one bit or five, but which size a block takes is still a coin toss, and a line holds a sum of coin tosses. Any layout that puts a fixed run of variable-sized entries in a fixed-size line pays for the variance, whatever the entries encode. Removing the variability from the code words did not remove it from the line.

One word counted instead of eighty-three code words #

Where the split wins is the lookup: packed a line at a time, it reads two lines like the plain table and counts 0.89 words of its bit vector on average, where the line-packed code reads two lines and decodes 82 code words. A block that never closed needs no count at all, since its bit is the whole answer. A block that closed needs the ones before it in the line, and with 141 blocks to a line that is a popcount on at most three words, one or two on average.

Rank is the only thing it does measured rank directories over long vectors, where the cost of a rank is set by how often a directory samples the count and how many words lie between samples. Here the vector is never longer than a line, so the directory is the line’s own start, and a rank is a count over at most 512 bits. The question the earlier essay posed, whether a rank would be cheap enough to beat 83 decodes, has the answer the arithmetic suggests: it is two orders of magnitude cheaper, and it needs no table of code words.

End to end, the split pays for its smaller table in lines. It reads 2.51 lines a lookup, the extra half line being the value’s line for the half of the blocks that closed, and counts 2.23 words, since a vector line holds about 500 blocks rather than 141. The indexed code read about 3.1 lines and decoded 31 code words for about three bits. The end-to-end split is a tenth of a bit larger and reads 0.6 lines fewer.

Rates the seeds cannot rank #

What the saved bits buy is a few per cent at 64-bit blocks, and four seeds cannot order the tables that save them. Against the plain four-bit table’s 0.321%, the end-to-end split measures 0.300%, the line-packed code 0.304% and the line-packed split 0.306%, gains of 4.6 to 6.3%. The seeds behind a single table spread over 5 to 8% of its mean. The plain table’s four seeds run from 0.311% to 0.328%, the line-packed split’s from 0.297% to 0.321%. The direction is clear, since every table smaller than four bits a block measures below it on the mean. Which smaller table does best is not, and the plate shows each seed so that the overlap is visible.

One reading the plate does support is that the gains are about the size the bits predict. At 64-bit blocks the four-bit table takes 5.9% of the filter’s memory. Saving 0.36 to 0.85 bits a block returns 0.5 to 1.3% of the memory to the blocks, ten to twenty more blocks among two thousand, and a Bloom filter’s rate falls by several per cent for each per cent of memory added at sixteen bits a key. The three-bit split, the smallest table of all at 2.88 bits, measures 0.321%, level with the plain four-bit table. Its thresholds have only eight levels, as the plain three-bit table’s do, and that table measures 0.312%. Whether the 3% between two tables of nearly the same size is the split’s doing or the seeds’ is beyond what four seeds resolve.

Why it stops paying as blocks widen #

The split saves 0.36 bits a block on the four-bit table at 64-bit blocks and 0.09 at 512, because the share of thresholds that close rises from 52% to 61% as blocks widen. The saving is all in the blocks that never close: each spends one bit where the plain table spent four. At 512-bit blocks only 39% of blocks never close, and the vector’s bit, paid by every block, outweighs what those 39% save once the worst line has taken its half bit. With three-bit values the split is already larger than the plain three-bit table from 128-bit blocks up.

The share that close rises with width for a reason the threshold design has met before. A block closes when the keys that name it first exceed its capacity. That number is close to a Poisson count with mean equal to the capacity, and a Poisson count stays at or under its own mean with probability falling towards one half as the mean grows. At 64-bit blocks the capacity is four keys, and a Poisson count with mean four stays at or under four 63% of the time; at 512-bit blocks the capacity is 32 and the chance is 55%. Overflow from other blocks closes some of the rest. The measured shares that never close, 48% and 39%, follow the same direction. A threshold knows only its own block used that Poisson argument for the 512-bit case, and here it says where the split can work: on narrow blocks, where most thresholds stay open.

Narrow blocks are also where the table matters. A four-bit table is 5.9% of the filter’s memory at 64-bit blocks and 0.8% at 512. The split saves bits only where they are worth saving, and the Huffman code, which saves more at 512 bits than at 64, saves them where they matter least. A penalty set by the block found a threshold worth most on narrow blocks for a different reason, that the load spread it repairs is widest there. Both arguments point at the same corner of the design.

What the vector is worth #

The comparison the earlier essay asked for comes out in two parts. On the lookup, the bit vector wins outright: two lines and one word counted, against two lines and 82 code words, or three lines and 31. On the bits, it loses to the Huffman code it was meant to improve: 3.64 against 3.19 at 64-bit blocks, packed the way that keeps a lookup at two lines.

The simplest table measured is three bits a block, plain, at 3.00 bits, two lines and no work at all. The line-packed code, at 3.19 bits, is larger than it, and the line-packed split with four-bit values, at 3.64, larger still. A designer who wanted the table small and the lookup simple would choose three plain bits. One who needed a four-bit threshold’s resolution and wanted the table smaller would choose the end-to-end split, 3.15 bits for half a line more on half the lookups. The line-packed split sits between the two on bits and has no lookup cost to speak of, which makes it the right design only where that half line matters more than half a bit.

Both line-packed tables lost about half a bit a block to the same thing, and neither the Huffman code nor the vector was the cause. Two hashes that shared their low bits found a measurement unstable because of how a value was brought into range; this one is stable, and what it measures is a layout paying for a variance it fixed in advance. The obvious next move is a layout that does not fix it.

Where the measurement stops #

Four seeds, one density. Every point is 16 bits a key with about two thousand blocks, and every rate a mean of four seeds whose spread is reported beside it. The bits a block are exact for each filter built and vary by under 0.1 between seeds.

Lookups counted, not timed. Lines are distinct 512-bit lines read, the cost positions confined to one line set out to minimise; words are 64-bit words counted for a rank; code words are code words decoded. One access, eight kilobytes is why a line of the threshold table, read on every lookup, is likely to be cached on a real machine, which would make the end-to-end split’s extra half line cheaper than it counts here.

A static filter. Every table is built once from a known key set, in order of the ordering hash, as in the earlier essays. A filter that took insertions would change its thresholds, and a line-packed table would then need room for closings that had not happened yet.

The values are stored plain. Each closed block’s value is four or three bits regardless of how often it occurs. A code over the closed values alone, inside the split, was not built.

Still open: a line sized for the average, with a place for the overflow #

Half a bit a block of the line-packed split’s cost is headroom for the busiest line. A line could instead be sized for a typical run of closings, with $C$ chosen so that the average line fits with a standard deviation to spare, and a line that draws more closings than it has room for could move its last few values to a small overflow area shared by the whole table. A lookup whose value has moved reads one more line. A lookup whose block never closed, or whose value stayed home, reads what it reads now.

The measurement that follows sizes the line for its mean plus one standard deviation of closed values and counts the share of lookups that must read the overflow, the bits a block, and the rate, at 64- to 512-bit blocks. The prediction is that the table falls from 3.64 bits a block to about 3.25 at 64-bit blocks, and that under one closed lookup in a hundred reads an overflow line, since a line that overflows its mean by more than a standard deviation does so by a value or two. A lookup would then read 2.005 lines on average. It could fail if the overflow area itself needs an index. A moved value must be found, and if finding it costs a rank over the overflowing lines, the extra read becomes two, and the half bit is paid for in lines on exactly the lookups the design was built to keep at two.