A code that has to fit its worst line

A threshold knows only its own block tried to shrink a blocked Bloom filter’s table of thresholds by sharing one among several blocks, and found it lost at every group size. Its closing section pointed at another way to save the same bits. The table’s values are not uniform. Many blocks never close at all, and the rest close in the upper half of the ordering hash’s range, so a code built from the filter’s own distribution of closing values should hold the table in about two thirds of its four bits a block. The section predicted that a coded table would match the four-bit table’s false-positive rate on under three bits, and asked the question that decides whether the idea is usable. A threshold design exists so that a lookup reads one threshold and one block, two cache lines. Can a variable-length table still be read in one line?

Two hashes that shared their low bits had to come first. The filter’s rate was unstable between seeds by a factor of three at some widths, because its block and ordering hashes were dependent through their low bits. Read from their top bits, the filter’s rate now holds within a few per cent from one seed to the next, which is what a saving this small needs. Every filter here reads its hashes that way.

The filter and four tables #

The filter is the one-threshold design at sixteen bits a key. A key goes to its first block while its ordering value, a sixteen-level hash, is below that block’s threshold, and to a second block otherwise. A threshold closes at the first ordering value whose first-choice keys would overflow the block. The filter is sized to about two thousand blocks at each width — 8,192 keys at 64-bit blocks up to 65,536 at 512 — so that its table spans many cache lines and a layout’s per-line costs are averaged rather than rounded. Every table is paid for in blocks: the filter’s bits are divided among blocks and table, and a table that needs more bits leaves fewer blocks.

Four tables are compared. Four bits each is the published design, and three bits each the coarser one the bits a second threshold costs found slightly worse. Coded, with an index stores each threshold as a Huffman code word built from the closing distribution of a pilot build of the same filter. The Huffman code words are packed end to end, and a separate index gives the bit position of every sixty-fourth threshold, so a lookup reads the index, then the table from that position, decoding forward to its own threshold. Coded, a line each packs a fixed number of code words into each 512-bit line, as many as every line of the table can hold. Block $i$’s threshold is then in line $\lfloor i / C \rfloor$, found with no index at all. A variant of it adds, at the head of each line, the bit offset of every sixteenth threshold, so a lookup decodes at most fifteen code words before its own.

Where thresholds close #

On the top-bit filter, 47% of thresholds never close at 64-bit blocks and 39% at 512-bit blocks, and those that close crowd into the upper values: an entropy of 2.79 bits at 64-bit blocks and 2.36 at 512. A block never closes when its first-choice keys never overflow it, which happens for any block that happened to be named first by fewer keys than it holds. When one does close, it closes late, since a block fills from its first-choice keys in increasing order of the ordering value and reaches capacity only near the top of the range. Wider blocks hold more keys, so their load varies less as a share of capacity and their closings bunch more tightly near the top. That is why the entropy falls from 2.79 bits to 2.36 as the block widens.

The Huffman code follows the distribution. “Never” gets a one-bit code word at every width. The four most common closing values get three or four bits, and values that almost no block closes at get eleven to thirteen. A value that the pilot build never produced still gets a code word, one bit longer than the longest, so that a block closing there can still be stored.

Bits a block, and what one line costs #

Packed end to end with an index, the coded table costs 3.03 bits a block at 64-bit blocks and 2.65 at 512. The Huffman code words themselves average about 2.75 and 2.40 bits, a few hundredths from the entropy. The rest is the index: a word-sized bit position for every sixty-four thresholds, about a quarter of a bit a threshold, and the Huffman code’s own table of lengths. The prediction said under three bits. That holds from 256-bit blocks up and misses by three hundredths at 64.

Packed a fixed count to a line, the table costs 3.19 bits a block at 64-bit blocks and 2.80 at 512. It needs no index, and it still costs more than the indexed table, by 0.16 and 0.15 bits. The fixed count is the problem. Every line must hold the same number of code words, and that number is set by the line whose code words happen to be longest. At 64-bit blocks a line holds about 160 thresholds, and across a dozen lines the one with the most rare closing values needs about a sixth more room than the average line. Every other line pays for that space, as padding. The entropy sets what the Huffman code words cost on average, and the worst line sets what the table costs.

With offsets at the head of each line, the table costs 4.02 bits a block at 64-bit blocks — more than the plain table — and 3.31 at 512. An offset is nine bits, one for every sixteen thresholds, which is more than half a bit a threshold. That erases the saving at every width but the widest, where the Huffman code words are shortest.

The worst line does not average out #

A padding set by the worst of a dozen lines might be expected to shrink as the table grows, since a larger table’s lines are a larger sample of the same distribution. It does not, because a larger table also has more lines, and the count a line can hold is set by the worst of them. At 64-bit blocks, a filter of 2,048 keys has a table of four lines and costs 3.30 bits a block packed a line each, much of that the last line’s rounding. At 8,192 keys the table is thirteen lines and costs 3.19; at 32,768 keys, 48 lines and 3.10; at 131,072 keys, 196 lines and 3.20. The mean code word stays between 2.76 and 2.78 bits throughout, and the indexed table between 3.01 and 3.14. The line-packed table’s excess over the Huffman code words hovers near 0.4 bits a block at every size.

The reason is arithmetic about maxima. A line of about 160 code words has a total length whose spread, from one line to the next, is roughly the square root of 160 times a code word’s own spread — several code words’ worth. The largest of many such totals sits a few of those spreads above the mean, and it moves up slowly as the number of lines grows. A table of two hundred lines is bound by a line that is a little worse than the worst of thirteen. A code whose lines could vary in count, or could borrow room from a neighbour, would not pay this. That is a variable-length layout again, and finding a threshold in it needs an index, which is the other layout.

A block, a class and an offset met the same trade in a compressed bit vector. Each block there is stored as its count of ones and its arrangement, the arrangement’s length varies with the count, and finding a block needs a sampled pointer every so many blocks. The pointer is this page’s index. That structure kept it because the blocks it saves are large. Here the saving is a fraction of a bit a threshold, and an index of a quarter of a bit a threshold is a large share of it.

What a lookup reads and decodes #

The indexed table costs every lookup a third cache line: 3.13 lines on average against 2.00. The index is a separate array, so reading it is one line, and the chunk of code words it points into sometimes straddles two lines of the table. That is the second read the threshold design was built to avoid. A block the lookup can work out put the threshold design ahead of reading two blocks precisely because a lookup reads one block and one threshold. An indexed code puts the third line back.

The line-packed table is read in two lines, as the plain table is, and decodes 83 code words on average to reach the key’s own. A lookup knows which line holds its threshold but not where in the line, so it decodes from the line’s start. Eighty-three code words is several times the work of the lookup it serves, which tests eleven bits in one block. The Huffman code words before a key’s own average about 230 bits. A decoder that consumes a byte at a step, decoding every complete code word in it at once, would cross that in about thirty steps. That is the obvious repair, and it is arithmetic from the layout rather than a count made here. The offsets bring the decoding down to 7.4 code words and take the saving with them. So each layout gives up one of the three things the section wanted. The indexed table gives up the single read. The line-packed table keeps the read and gives up either the decoding or the bits.

What the saved bits buy #

At 64-bit blocks the indexed code’s filter has a false-positive rate 11% below the plain table’s, 0.284% against 0.321%, and the line-packed code’s is 5% below. Both matched the four-bit rate, as the prediction said, and both did better than match it. The indexed code returns 1.4% of the filter’s memory to its blocks, 1,955 blocks against 1,927. Each block then holds fewer keys, and on a narrow block holding about four keys that lowers the rate sharply. The three-bit plain table lowers the rate by 3% with none of the costs. It frees as many bits as the Huffman code does and reads in one line with nothing to decode, but it closes its thresholds more coarsely, which takes back most of what the freed bit buys.

At 512-bit blocks no layout differs from the plain table by more than 2%, which four seeds do not resolve. The saving is real in bits and invisible in false positives. The section expected a small gain there, and the gain is smaller than the measurement.

The prize shrinks with the block #

The table’s share of the filter is four bits over the block’s width plus four, so it halves each time the block doubles. At 64-bit blocks the four-bit table is 5.9% of the filter, and the indexed code returns 1.43% of it to the blocks; at 512-bit blocks the table is 0.78% and the Huffman code returns 0.26%. The section framed the prize at 512 bits, where it is a quarter of a per cent of the filter and moves the rate by less than one seed differs from the next. A floor on the bits put a membership structure’s cost at a logarithm of its false-positive rate, and a quarter of a per cent of the memory moves that logarithm by too little to see.

The narrow blocks are where coding the table pays, and they are where each layout’s cost weighs most. A third cache line on a lookup that otherwise reads one 64-bit block and one threshold line is half as much again. Eighty-three code words decoded is many times the eleven bit tests the block probe makes. At 64-bit blocks the plain three-bit table is the only change here that frees bits without costing the lookup anything. It frees as many as the Huffman code, and turns them into a quarter of the Huffman code’s gain.

The distribution was the easy part #

The prediction had the distribution right. Thresholds are skewed exactly as the section said, the entropy is well under four bits, and a Huffman code gets within a few hundredths of it. None of that was in doubt. What decided the result is the layout, and the prediction’s own question about it — whether a threshold can be found in one line — has a precise answer. Yes, if every line holds the same count of code words, and then the table costs what its worst line costs and a lookup decodes half a line.

A code word is at least one bit found a coded structure’s size set by a floor below its entropy, the one-bit minimum of a code word. Here the size is set by a ceiling above it, the room the worst line needs. Both are the same lesson from opposite sides: the entropy is what a code approaches over many symbols, and a structure that is read in fixed-size pieces pays for its pieces, not for its average.

Where the measurement stops #

A Huffman code from a pilot build. The Huffman code is built once from four pilot filters of the same design and used for every measured filter, so the Huffman code words fit the design’s distribution and not each filter’s own. A code rebuilt for each filter would sit a little closer to its entropy and would have to be stored with it; at these sizes the Huffman code’s own table is 68 bits.

No faster decoding. Decoding here is one code word at a time. A table-driven decoder that consumes eight or sixteen bits at a step would decode the line-packed table’s 83 code words in far fewer steps, and it is the obvious repair to the decoding cost; it was not built or counted.

One index spacing. The index holds a position for every sixty-four thresholds. A sparser index costs fewer bits and more decoding, and a denser one the reverse, and neither was measured.

Four seeds. The rate differences at 64-bit blocks, 5% and 11%, are several times the seeds’ spread. The differences at 256 and 512 bits are within it.

Still open: a threshold stored as whether it closed #

Almost half the table’s entropy is one question: did this block close at all? At 64-bit blocks 47% of thresholds never close, and the Huffman code spends one bit on each of those. A table could store that answer as a bit vector, one bit a block, and store a closing value only for the blocks that closed, in a second array indexed by the rank of the block among the closed ones. A rank on a bit vector is one of the cheapest operations there is. Rank is the only thing it does measured directories that answer it in a few word reads for a few per cent of the vector.

The measurement that follows stores the table that way — a bit a block, plus four bits, or fewer, for each closed block — and counts bits a block, lines a lookup and the rate, at 64 to 512 bits. The prediction is about 1 + 0.53 × 4 ≈ 3.1 bits a block at 64-bit blocks with a plain four-bit value for each closed block, and under three with a three-bit one. Both would be read in two lines when the bit vector, its rank directory and the closed values share a line, which at 64-bit blocks they can for about a hundred blocks at a time. What could fail is the rank. A lookup that needs a rank to find its threshold is doing arithmetic the plain table never did, and the question is whether a bit vector’s rank is cheap enough to beat both the indexed code’s third line and the line-packed code’s eighty-three decodes.