The worst of more lines

A bit for whether it closed shrank the threshold table of a blocked Bloom filter by asking one question of each block first. In the design a block the lookup can work out introduced, every block carries a threshold on an ordering hash. A key below its first block’s threshold is stored there and the rest go to their second block, so a lookup reads the threshold and knows which block to read. About half the blocks never close, and their threshold is a single fact. So the table became a bit a block for whether it closed, and a four-bit value only for the blocks that did, found by counting the ones before it in the bit vector. Packed a fixed number of blocks to a 512-bit cache line, a lookup reads its threshold’s line and its block’s line, two lines, as the plain table does. Two is the number the whole design defends. Positions confined to one line built the blocked filter to read one line of bits where a plain Bloom filter reads five, because a line is what the machine charges for, as one access, eight kilobytes measured; the threshold table costs the second, and any design that adds a third is spending what the blocks were built to save.

The cost of the fixed count was the worst line. Every line holds the same number of blocks, so every line must have room for as many closed values as the busiest line happens to draw. At 64-bit blocks the mean need was 3.09 bits a block and the table paid 3.64. That essay’s closing section proposed paying for the usual line instead. Size each line for the mean number of closed blocks plus one standard deviation. A line that draws more moves its last few values to a small overflow area shared by the whole table, and a lookup whose value moved reads one more line. It predicted about 3.25 bits a block at 64-bit blocks, and that under one closed lookup in a hundred would read the overflow, about 2.005 lines a lookup on average. It named the failure: if finding a moved value needs an index of its own, the extra read becomes two, and the half bit is paid back in lines on exactly the lookups the design was built to keep at two.

The line, the overflow, and the offset that joins them #

A line holds $C$ blocks: their $C$ bits of the vector, and room for $R$ four-bit values. $R$ is the mean number of closed blocks among $C$, $Cp$ for the filter’s own share $p$ of closing blocks, plus $z$ standard deviations of the binomial count, $z\sqrt{Cp(1-p)}$, rounded up. A line that draws more than $R$ closed blocks keeps the first $R$ values and moves the rest, in order, to an overflow area packed end to end after the last line.

The failure the proposal named is avoided by construction. Each line carries one more field: the bit offset in the overflow area where its moved values begin. A lookup reads its line, counts the closed blocks before its own as the earlier table did, a rank inside one line of the kind rank is the only thing it does priced at a popcount a word, and if its rank is $R$ or more, reads the overflow at the line’s offset plus four bits for each rank past $R$. That is one more line, or two when the value straddles a line boundary, and no index. The offset must address the whole overflow, so it costs $\lceil\log_2(\text{overflow bits})\rceil$ bits a line: 13 at two thousand blocks, 19 at a hundred and twenty thousand. $C$ is then the most blocks for which $C$ bits of vector, the offset and $R$ values fit in 512.

Every table is paid for out of the filter’s sixteen bits a key, so a smaller table leaves more blocks; that is how the table’s size reaches the false-positive rate. One more thing is reported differently from the earlier pages, and it matters here. A table of two thousand blocks fills thirteen lines, and its last line is partly empty; the earlier pages charged that padding to the table, up to a thirteenth of it. Here each table’s bits a block are reported as if it filled a whole number of lines, $512/C$ plus the overflow, which is the design’s own cost.

The worst line depends on the table #

Sized for its worst line, the table costs 3.38 bits a block at two thousand blocks and 3.62 at a hundred and twenty thousand; sized for the mean plus one standard deviation it costs 3.35 to 3.38 at every size. The comparison the proposal was asking for changes with the table it is asked of.

The reason is the arithmetic of maxima. A line of about 150 blocks at 64-bit blocks holds about 79 closed blocks on average, with a standard deviation of about six. The worst of thirteen such lines lies about 1.7 standard deviations above the mean; the worst of 870 lies about three. The worst-line table must make every line as large as that maximum, and the maximum grows with the logarithm of the number of lines. At two thousand blocks the worst line asked for little more than a standard deviation, which is why the overflow saves only three hundredths of a bit there. At a hundred and twenty thousand blocks it asks for more than three, and the overflow saves a quarter of a bit.

The earlier essay’s 3.64 at two thousand blocks was a different number from this plate’s 3.38. It included the last line’s padding, which is a fixed cost spread over a small table, and it took the worst of four filters’ tables. At a hundred and twenty thousand blocks the padding is negligible and the worst line’s own cost has grown to 3.62. The two measurements meet by coincidence of two effects of size, one shrinking and one growing.

The line sized for the usual line is indifferent to size because it never pays for the maximum. Its room is set by the mean and the spread of one line, which are the same however many lines there are. What grows with the table is only the offset, by a bit for every doubling of the overflow, a few thousandths of a bit a block.

What each standard deviation buys #

At a hundred and twenty thousand blocks each standard deviation of room costs a block between an eighth and a fifth of a bit, and taking it away sends more lookups to a third line: from 0.0003 extra lines a lookup with two standard deviations of room to 0.015 with none. Room for the mean plus one deviation costs 3.38 bits a block and 2.0032 lines a lookup, close to the 2.005 the proposal expected. Room for the mean alone costs 3.25 bits, the proposal’s own number, at 2.015 lines.

Every point on that curve is cheaper in bits than the worst line, including the one with two standard deviations of room, which almost never reads a third line. That is the plainest way to state the finding. The worst line at this size is about three standard deviations above the mean, so a table that sizes for two and moves the rare excess is smaller and reads a third line on three lookups in ten thousand.

Between the points the choice is a price. Going from one standard deviation of room to none saves 0.13 bits a block, about sixteen thousand bits, two kilobytes, on a filter of a hundred and twenty thousand blocks. It adds 0.012 lines a lookup, a third line on one lookup in eighty-three. A filter asked a million questions a second would read twelve thousand more lines a second to keep two kilobytes. Whether that is worth it depends on the machine and on what else wants the memory, and no plate here can decide it; what the plate does decide is that every point on the curve is a better trade than the worst line.

How many lookups move #

With one standard deviation of room, 0.62% of lookups whose block closed read the overflow, under the one in a hundred the proposal predicted; with none, 2.98%. The share is set by the room and hardly at all by the table’s size, as it should be if neighbouring blocks close at unrelated moments, which a threshold knows only its own block found they do. It is a property of one line’s count: how often a binomial count of closed blocks exceeds its mean by a given number of deviations, and by how many values when it does.

A lookup reads the overflow only if its own block’s value was among those moved, and the moved values are the last closed blocks in a line that overflowed. With one deviation of room, about one line in eight overflows at two thousand blocks, and an overflowing line moves only the values beyond its room, usually a few of its 85. That is why the share of lookups is so much smaller than the share of lines that spill.

Where a block’s bits go #

Of the 0.53 bits a block the worst line spends above the mean, a line sized for one standard deviation keeps 0.15 as room and spends 0.13 on its offset; the offset is why the measurement lands at 3.38 and not the 3.25 the proposal predicted. The prediction priced the room and the overflow and left out the field that finds the overflow. Nineteen bits a line, among 152 blocks, is an eighth of a bit a block, almost as much as the standard deviation of room it accompanies.

The proposal worried about the opposite failure, that finding a moved value would need an index and a second extra line. Putting the offset in the line removes that failure and replaces it with a cost in bits. The cost is paid by every line, including the seven in eight that never spill, which is the price of being able to find a spill without reading anything else.

Every block width, at two thousand blocks #

At two thousand blocks the overflow line saves little at any width, and at 256-bit blocks the line sized for one standard deviation costs two hundredths of a bit more than the worst line. This is the small-table end of the first plate repeated at every width: thirteen lines’ worst is barely above one deviation, and the offset costs more than the room it saves. Wider blocks close more often, 52% of them at 64 bits and 61% at 512, so every split table grows with the width and the advantage of splitting off the blocks that never close shrinks, as the earlier essay measured. Why wider blocks close more often was not measured here; a penalty set by the block measured how the blocks’ loads behave as they widen, and the closing share is a consequence of those loads that this table only records.

The plain three-bit table sits under all of them at 3.00 bits a block. A code that has to fit its worst line found the same: a threshold with eight levels instead of sixteen gives up resolution, and the earlier pages measured that loss as small. The split tables keep sixteen levels for a third of a bit more.

What the bits buy #

The rates of the three split tables differ by three thousandths of a percentage point, inside the spread of their own four seeds; every one of them measures about 5% below the plain four-bit table. At sixteen bits a key and 64-bit blocks, the threshold table takes about 6% of the memory, and each tenth of a bit a block it saves returns a seventh of a per cent of the memory to blocks. A Bloom filter’s rate falls by several per cent for each per cent of memory, the slope the formula everybody sizes filters with gives and these filters follow closely on hashed keys, so a tenth of a bit is worth about half a per cent of the rate, far below what four seeds resolve.

So the choice among the split tables is not made on the rate at this size. It is made on bits, which the plates above measure exactly, and on lines, where the overflow table pays a third line on 0.3% of lookups at one standard deviation. At a hundred and twenty thousand blocks the bits saved are a quarter of a bit a block, about a twentieth of the table, and the rate would follow them by a few tenths of a per cent; that was not measured to a resolution that could show it.

What the counts depend on #

Two seeds at the larger sizes, four at two thousand blocks. The bits a block are exact for each built table and vary little between seeds; the rates are sampled from 100,000 to 250,000 queries a filter and are reported only at two thousand blocks.

A line read is a line. The lookup’s cost is counted in lines, and a value straddling two overflow lines counts both. The popcount over the line’s vector, the earlier essay’s half a word on average, is unchanged by the overflow and not repeated here.

A binomial count. The room assumes the closed blocks in a line are a binomial count. At two thousand blocks with one standard deviation of room, 13% of lines spill, where a normal count would spill on about 16%; the real count is a little narrower than the binomial, so one deviation of room is slightly more than one deviation of the real spread. Why it is narrower was not measured. One candidate is that a key turned away by one block’s threshold lands in another, so closings are not quite independent.

Room set from this filter’s own share. $R$ uses the share of closing blocks measured on the filter being stored. A table built before the filter’s thresholds were known would have to assume the share, and a wrong assumption costs either bits or spills.

Still open: an offset that only has to reach its neighbours #

The overflow line missed the predicted 3.25 by the cost of its offset, an eighth of a bit a block at a hundred and twenty thousand blocks, and that cost grows with the logarithm of the table. But an offset does not need to address the whole overflow. Lines could be grouped, sixty-four to a group, with the group’s spills kept together and one absolute offset for the group stored where the lookup can find it. Each line would then store only where its spills begin within its group’s part of the overflow: about nine bits instead of nineteen.

The group’s absolute offset must be read from somewhere, and that is where this can fail. If it sits in a separate array, a lookup whose value moved reads three extra lines’ worth rather than one, which is the failure the earlier essay’s proposal named. If it is folded into the first line of each group, only lookups in that line get it for nothing. The measurement that follows stores the group offset in a separate array read only by lookups whose value moved, sized at one word a group, and prices the bits and the lines at groups of 16, 64 and 256 lines and at the three table sizes. The prediction is that at a hundred and twenty thousand blocks and one standard deviation of room the table falls from 3.38 to about 3.31 bits a block, and the lines a lookup reads rise from 2.0032 to about 2.0064, since every moved value now needs the group’s offset first. The question is whether the last eighth of a bit is worth a second extra line on six lookups in a thousand, or whether a table this close to its mean has nothing left that is cheaper to remove than the room itself.