An offset that only has to reach its neighbours

The worst of more lines sized a threshold table’s cache lines for the lines that usually occur rather than for the worst. In the blocked Bloom filter of a block the lookup can work out, every 64-bit block carries a threshold on an ordering hash, and a bit for whether it closed stored that table as a bit a block for whether the block closed and a four-bit value for each block that did, packed a fixed number of blocks to a 512-bit line. Sized for the most closed blocks any line draws, the table costs more as the filter grows, because the worst of more lines is further from the mean: 3.38 bits a block at two thousand blocks, 3.62 at a hundred and twenty thousand. Sized for the mean plus one standard deviation, with a line’s excess values moved to a shared overflow, it cost 3.38 at every size, and 0.6% of lookups on a closed block read one line more.

The predicted figure had been 3.25. The difference was the offset, the same kind of cost a code that has to fit its worst line met when it packed variable-length codes into lines: whatever says where something is must itself fit in the line. A line whose values overflow must say where in the overflow they begin, and an offset that can point anywhere needed nineteen bits at a hundred and twenty thousand blocks, an eighth of a bit for every block in the line. That page’s closing section proposed an offset that only has to reach its neighbours. Lines would be grouped, sixty-four to a group, each group’s spills kept together; each line would store only where its spills begin within its group’s part, about nine bits; and the group’s own position in the overflow would be held once a group in a separate array, read only by a lookup whose value moved. It predicted 3.31 bits a block at one standard deviation and the largest table, and lines a lookup rising from 2.0032 to about 2.0064. It asked whether the last eighth of a bit is worth a second extra line on six lookups in a thousand.

Three offsets #

Everything but the offset is the earlier page’s: a filter of 16 bits a key in 64-bit blocks, four-bit threshold values, two filters a seed and two seeds, 100,000 absent queries a filter, and every table charged as if it were a whole number of lines plus its overflow. A line holds $C$ blocks’ closed-or-not bits, its offset, and room for the values of the mean number of closed blocks among $C$ plus $z$ standard deviations; $C$ is the largest that fits 512 bits.

The grouped line’s offset is the fewest bits that address the largest part any group of the filter’s lines spills. The width depends on how the lines are cut, which depends on the width, so it is found by trying widths from one upward until a layout fits its own offsets. Each group’s position is held in a separate array, one entry a group. A lookup whose value stayed in its line reads its line, as before; a lookup whose value moved reads its line, the group array’s line, and the overflow line or two that hold its value.

Measuring that design exposed a confound in the comparison the proposal set up. The earlier page’s offset was nineteen bits because it was sized to address an overflow holding every value the table could move, four bits for each of a hundred and twenty thousand blocks. The overflow this table actually has is about sixteen hundred bits. A table built once knows its overflow’s size, and an ungrouped line could carry an offset sized for that, found by the same search from one bit upward. Without it, grouping would be credited with what any table can do without groups. So a third layout was added: the ungrouped line with its offset sized for the overflow it has.

Where the eighth of a bit went #

Most of the offset’s eighth of a bit was an offset sized for a table of moved values: sized for the overflow the table actually has, the ungrouped line costs 3.299, 3.292 and 3.337 bits a block at the three sizes, against 3.354, 3.374 and 3.382, with no change to how a lookup reads. Grouping in 64 lines costs 3.305, 3.295 and 3.301. At the two smaller tables grouping saves nothing over the fitted offset; at the largest it saves three hundredths of a bit a block, because there even the fitted offset has grown to eleven bits.

The proposal’s prediction holds to the hundredth. The grouped table at 124,488 blocks costs 3.301 bits a block against the predicted 3.31, and reads 2.0060 lines a lookup against the predicted 2.0064. The arithmetic behind it was right: about ten bits saved a line, spread over about 155 blocks, is six hundredths of a bit a block, and the group array costs almost nothing. What the prediction did not account for was that eight of those ten bits were available without grouping, to any table willing to size its offset by the overflow it built.

The fitted offset still grows with the table: six bits at two thousand blocks, eight at fifteen thousand, eleven at a hundred and twenty thousand, because the overflow grows in proportion to the table and its address in proportion to the logarithm. The grouped offset does not: seven or eight bits at every size. That is the one thing grouping does that nothing else here does, and at these sizes it is worth three hundredths of a bit.

At equal lines a lookup #

At 124,488 blocks the fitted offset moves the whole curve of bits against lines down, and grouping moves the bits down again by less than its extra line costs: at one standard deviation the fitted ungrouped line costs 3.337 bits a block for 2.0031 lines a lookup and the grouped line 3.303 for 2.0062. Read at equal lines a lookup, the grouped table is dearer than the fitted one by a hundredth to nine hundredths of a bit. That is the comparison the earlier page’s question asked for. A table that will spend lines can spend them two ways: on grouping, which adds a line to every moved lookup in exchange for a narrower offset, or on a smaller room, which moves more values to the overflow in exchange for fewer bits of room in every line. At this size the second is cheaper. The fitted line at half a standard deviation of room costs 3.265 bits a block for 2.0075 lines, fewer bits than the grouped line at one standard deviation for about the same lines.

Every point on the grouped curve lies to the right of the fitted curve at about the same height, which is the extra line moved lookups pay, and the fitted curve passes below every one of them. So the answer to the earlier page’s question is no. The last eighth of a bit was not worth a second extra line, because most of it was not the price of reaching the overflow but the price of an offset sized for an overflow the table never has; and what remained, three hundredths of a bit, is cheaper to buy by shrinking the room than by grouping.

Is a fitted offset fair? #

Sizing the offset by the overflow the table has is a decision made when the table is built, and it is fair only to a table that is built once. The threshold table here is built with its filter: every key is inserted, every block’s threshold settles, the lines are cut and the overflow is laid out, and from then on the table answers lookups and nothing moves. Such a table knows exactly how many bits its overflow holds, and an offset wider than that address is space spent on overflows that cannot occur. The earlier page’s nineteen bits were the right width for a table whose overflow could grow to hold every value — a table that accepted insertions after it was built — and the wrong width for the table it measured.

A filter that grows after it is built would face a different choice. Each insertion can close a block and push a value into the overflow, the overflow grows, and a fitted offset would eventually be too narrow, forcing a rebuild of every line’s offset at once. A grouped offset grows more gracefully: a group whose part outgrows its width rebuilds only its own lines, and the group array’s absolute entries are wide enough for any table. A filter that grows by moving a bit built a filter meant to grow in place, and for a table like that the comparison here would be the wrong one: there the grouped offset’s advantage is the cost of the rebuilds it avoids, which nothing on these plates measures.

A lookup’s work inside its line is the same in all three layouts: it counts the ones before its block in the closed-or-not bits to find its value’s rank, the one operation rank is the only thing it does found a compressed structure spends its time on, and compares that rank with the line’s room to learn whether the value moved. Only what happens after a value has moved differs, and on six lookups in a thousand.

Every group size #

A line’s offset needs nineteen bits to address a table of moved values, eleven to address the overflow this table has, and seven to eleven to address its group’s part at groups of 4 to 1,024 lines. The least table is at groups of 16 to 64, 3.303 and 3.301 bits a block. Small groups make the group array dearer — at groups of four it holds an entry for every four lines — and large groups make the line’s offset wider, until at groups of 1,024 the line’s offset is as wide as the fitted one and the group array is pure cost.

The widths describe the overflow itself. A group of 64 lines spills fewer than 256 bits on this filter, under one four-bit value a line even in the group that spills most. The overflow is a thin layer spread across every group, which is what one standard deviation of room was chosen to produce. An offset into a thin layer is cheap however it is sized, which is why fitting it to the layer’s real size recovered most of the eighth of a bit and grouping recovered only a little more.

Which lookups pay #

At the same room about the same share of lookups find their value moved in all three layouts — 0.62%, 0.60% and 0.60% of lookups on a closed block at one standard deviation — and only the grouped lookups read one more line for it, the group’s position, which is how 2.0031 lines a lookup becomes 2.0062. The narrower offsets let a line pack a few more blocks, 154 or 156 against 152, and give it room for a value or two more, so the overflow is about equally thin in all three. The cost of grouping is entirely in what a moved lookup must read first.

A design could fold the group’s position into the group’s first line, so that lookups in that line get it free. It would save one read in sixty-four of those lookups and cost the first line of every group nineteen bits of its room, which is the trade the grouping exists to avoid. Kept apart, the group’s position is charged only to the six lookups in a thousand that need it — and at this size even that charge is more than the bits it saves are worth.

Where the bits go #

Per block, the offset costs 0.125 bits sized for a table of moved values, 0.071 sized for the overflow the table has, and 0.051 within a group of 64 lines plus 0.002 for the groups’ positions; everything else — the bit a block and the room for values — is the same to the hundredth in all three. The table is about 3.3 bits a block, of which 3.23 are the bit and the room, and those are set by the filter’s own closing distribution, not by the layout. What the layouts compete over is a twentieth of the table.

Positions confined to one line built the blocked filter so that a lookup reads one line of bits, and one access, eight kilobytes is the measurement of why a line is the unit worth defending. The threshold table spends a second line on every lookup and a third on a few. These plates price that third line in bits: at this size, a third line on six lookups in a thousand is worth more than three hundredths of a bit a block, because the same lines spent on a smaller room save more.

What one filter cannot say #

One filter design. Every table is the one-threshold blocked filter at 16 bits a key with four-bit values. A filter with more bits a key closes fewer blocks, and its table’s room and overflow would both be smaller, which makes the offset a larger share of what is left.

Three sizes. At 124,488 blocks the fitted offset is eleven bits and the grouped seven or eight. Each doubling of the table adds about one bit to the fitted offset and nothing to the grouped one, because a group’s part of the overflow grows with the group’s own sixteen lines and not with the table. The fitted offset grows with the logarithm of the table, so a table a thousand times larger would need a fitted offset of about twenty bits and a grouped one of about the same seven or eight; there grouping would save several times what it saves here, and whether that would then beat shrinking the room was not measured.

Two seeds. Every point is two seeds of two filters each. The differences between group sizes of 16 and 64 are smaller than the spread between seeds and are not a ranking.

Still open: room that depends on the line’s neighbours #

Every line is given the same room, the mean plus some standard deviations, because every line’s number of closed blocks is drawn from the same distribution. What the plates say is that room is the part of the table worth trading, and that the line is the right place to spend a read. A group of lines could pool its room as it pooled its offsets: give each line room only for the mean, and give each group a reserve for its lines’ total excess, which varies much less in proportion than one line’s excess does — by the square root of the group’s size.

The measurement that follows sizes each line for the mean, gives each group of 64 lines a reserve at one standard deviation of the group’s total, stores a group’s spills first in its reserve and only then in the shared overflow, and compares the table against the fitted ungrouped line at equal lines a lookup. The prediction is that the table falls to about 3.24 bits a block for about 2.006 lines a lookup, below the fitted line’s curve, because a group of 64 needs an eighth of the per-line room for the same chance of spilling past its reserve. It could fail on where the reserve lives: a reserve beside the group’s lines is a line of its own, read by every lookup that spills, and if the reserves are partly empty the table pays for unused lines. The question is whether room, unlike an offset, can be pooled across neighbours, or whether room has to sit in the line its lookups already read.