A reserve sized for the spill

An offset that only has to reach its neighbours worked on the table that tells a blocked filter where each block’s threshold closed. The table keeps one bit a block for whether the threshold closed and a four-bit value for each block that did, packed into 512-bit lines that a lookup reads in one go, the line a blocked filter confines its positions to. Every line is given room for the mean number of closed blocks plus some standard deviations, and the values that do not fit move to a shared overflow area that costs a lookup a second line. That essay found that grouping lines to shorten the offset into the overflow did not pay: an ungrouped offset sized for the overflow the table actually has gave a cheaper table at equal lines a lookup, and that fitted ungrouped line became the curve to beat.

Its closing section turned from the offset to the room. Every line gets the same room because every line’s count of closed blocks is drawn from the same distribution, and the room is the part of the table worth trading. A group of lines could pool its room as it had pooled its offsets: give each line room for the mean, and give each group of 64 lines a reserve for its lines’ excess, at one standard deviation of the group’s total. The total over 64 lines varies, in proportion, an eighth as much as one line’s count, so a group should need an eighth of the per-line room for the same chance of spilling past its reserve. The prediction was about 3.24 bits a block for about 2.006 lines a lookup, below the fitted line. The named risk was the reserve itself: it is a line of its own, read by every lookup that spills, and a partly empty reserve is paid for.

The arithmetic of the total is right, and the total is not what a reserve has to hold.

Lines at the mean, and a reserve a group #

The filter, the keys and the accounting are the earlier essays’: 64-bit blocks whose uneven loads the thresholds repay, 16 bits a key, four-bit threshold values, 524,288 keys in about 124,500 blocks, two filters a seed and two seeds, 100,000 absent queries a filter, and the table’s cost counted as whole lines plus everything outside them. In the pooled table each line holds room for the mean number of closed blocks among its $C$ blocks, $\lceil Cp \rceil$ values for this filter’s closed share $p$, so a line’s room is about half the time too small. Lines are grouped 64 at a time, and each group has a reserve of value slots. A line’s values beyond its room go first into its group’s reserve, in order, and only when the reserve is full into the shared overflow.

Each line carries where its spills begin in its group’s sequence of spills, in as few bits as address the largest group’s; each group carries, once, where its part of the shared overflow begins. A lookup whose value stayed in its line reads one line. One whose value is in the reserve reads its line and the reserve’s line, or two if the value straddles a boundary. One whose value went past the reserve reads its line, the group array’s line and the overflow’s. The reserve is sized two ways: as proposed, $r$ standard deviations of the group’s total of closed blocks, and for the spill, the group’s expected spill plus $r$ standard deviations of it, both computed from the binomial distribution of a line’s closed blocks.

A reserve that is always full #

A reserve of one standard deviation of a group’s total holds 52 values, the 64 lines of a group sized for the mean spill about 145, and the reserve is full in every group: 1.7% of lookups on a closed block find their value past it, in the shared overflow, three lines away. The proposed reserve is not too large, the named risk; it is a third of what it must hold.

The proposal reasoned about the group’s total. Sixty-four lines of about 164 blocks each, with about half the blocks closing, hold a total whose standard deviation is $\sqrt{64}$ times one line’s, and one line’s is about 6.3 values, so one standard deviation of the total is about 50 values. That is the right spread for the total. But a line with fewer closed blocks than its room cannot lend its empty slots to a line with more, since its slots are inside its own 512 bits. What the reserve has to hold is not the group’s total above its mean but the sum of every line’s own excess, and half the lines exceed the mean. A line’s expected excess over the mean is about 2.3 values, and 64 of them are about 145, with a spread of only about 28. The spills of a group are large and steady, which is the opposite of what the proposal’s arithmetic pictured.

Sized for that, a reserve of 144 slots, the expected spill, is 92% full and sends 0.24% of closed lookups past it; one standard deviation more, 177 slots, is 81% full and sends 0.03%. The partly empty reserve the closing section feared appears exactly where the reserve is large enough to work.

Why a group’s spill is steady #

The square root the proposal relied on is real, and it applies to the spill rather than the total. One line’s spill over the mean is zero about half the time and several values the rest: its expected size is 2.27 values and its standard deviation 3.54, so it varies by one and a half times its own mean. Summed over 64 lines, independent because the hash that places the keys is drawn at random from a family, the mean grows 64 times and the deviation eight times, so the group’s spill is 145 values give or take 28: it varies by a fifth of its mean. Pooling makes the spill eight times steadier relative to its size, which is exactly the factor the closing section named. What it does not do is make the spill smaller, and the proposal’s reserve was sized as if it did.

That difference is the whole result. A per-line room has to cover a line’s spill at the line’s own variability; to keep one line in a hundred from spilling, a line needs about two and a half deviations of room over the mean, and every line pays for them. A group reserve has to cover the group’s spill at the group’s variability; to keep one group in a hundred from overflowing, it needs about the expected spill plus two and a half of its own deviations, 215 slots, which spread over 64 lines is 3.4 values a line, against the 15 or so a line would need alone at the same chance. The saving is in the margin, not in the mean, and the mean is most of what a reserve holds.

The measured saving is far smaller than that arithmetic suggests, because the ungrouped line does not keep its lines from spilling either. It sends its spills to an overflow area and pays a second line and an offset for them, so what pooling can save over it is only what a reserve costs less than that overflow, slot for slot and line for line, and that is a few hundredths of a bit a block.

Back on the curve, and under it #

With the reserve sized for the spill, the pooled table sits under the fitted ungrouped line at every room measured: 3.192 bits a block for 2.0137 lines a lookup where the line costs 3.224 at the same lines, 3.243 for 2.0078 against 3.263, and 3.313 for 2.0034 against 3.331. The saving is two to three hundredths of a bit a block, about 1% of the table. It is the first layout on this table’s plates to get under the fitted line at equal lines a lookup, since fitting every line to its worst run of values first priced the table by its lines.

The proposed reserve lands on the curve instead. At one deviation of the total it costs 3.180 bits for 2.0231 lines, and the fitted line at 2.0231 lines costs 3.186, six thousandths more. The bits are lower than the prediction’s 3.24, because the reserve is small, and the lines are four times the predicted excess over two, because so many values go past it. The prediction’s point, 3.24 at 2.006, is almost exactly where the spill-sized reserve with lines at half a deviation over the mean sits, 3.243 at 2.0078; it was reachable, by a reserve three and a half times the size it proposed.

Below the mean the pooling stops paying. With lines half a deviation under the mean and a spill-sized reserve, the table costs 3.191 bits for 2.0261 lines, more than the fitted line there; the reserve then holds most of the values and the line is mostly offsets and empty room.

Every reserve at the mean #

Growing the proposed reserve from half a deviation of the total to two leaves the bits at 3.180 a block and only lowers the lines, from 2.0257 to 2.0183; the reserve is full at every one of those sizes, so a larger one simply keeps more of the spill out of the overflow at the same cost a slot. At four deviations of the total, 205 slots, it is larger than the spill needs, 69% full, and the bits rise to 3.203. The spill-sized reserves sit between, and the one at the expected spill alone, 144 slots, is the cheapest point under the curve: 3.184 bits for 2.0151 lines, against the fitted line’s 3.215 at 2.0150.

The plate makes the trade visible. A slot in a full reserve costs four bits and saves a value from the overflow, where it would have cost four bits too plus a third line a lookup; a slot in an empty reserve costs four bits and saves nothing. The cheapest reserve is the one that is nearly full and almost never overflows, and a reserve sized for the expected spill is that one, because the spill of 64 lines is steady enough that its mean almost bounds it.

Group size #

At groups of 16 lines the proposed reserve comes closest to the spill it must hold and lands 0.020 bits a block under the fitted line; at 64 it is 0.006 under, and at 256 it is 0.035 over. The proposed reserve grows as the square root of the group, while the spill it must hold grows in proportion to the group. At 16 lines the two are close, 26 slots against about 36 values of spill. At 64 the reserve is a third of the spill. At 256 the spill outruns the reserve in every group by hundreds of values, which go to the overflow and cost the lines, while the larger group’s offsets cost the line two more bits.

That is the same arithmetic as the reserve plate seen from the side. A group’s total varies as $\sqrt{G}$, its spill as $G$, and only the second is what a reserve holds; sized by the first, a reserve fits the spill only at the one group size where the two happen to meet.

Room and spill #

The closing section asked whether room, unlike an offset, can be pooled across neighbours, or whether room has to sit in the line its lookups already read. The measurement separates the two halves of a line’s room. The part every line uses, up to the mean, cannot be pooled: it is in the line, and a line’s unused slots cannot lend themselves to a neighbour. The part some lines need and some do not, the spill, can be pooled, and pooling it is what puts the table under the line, because a group’s spill is far steadier than any one line’s.

The worst of more lines priced the line sized for its worst case against the line sized for its usual case, and moved the excess to one overflow area; a bit for whether it closed had made the line’s contents a count of closed blocks in the first place. Each step since has asked how much of the variation between lines a table must pay for in every line. Pooling the spill pays for it once a group, at the group’s mean spill, which is the variation’s own size rather than a margin over it.

What the prediction got right #

The closing section predicted that lines at the mean with a group reserve of one standard deviation of the group’s total would cost about 3.24 bits a block for about 2.006 lines a lookup, below the fitted ungrouped line. It costs 3.180 for 2.0231, on the line rather than below it, because its reserve of 52 slots is full in every group and 1.7% of lookups on a closed block go past it. It named the risk that the reserve would be partly empty and paid for; the proposed reserve is never empty, and the reserves that are partly empty are the ones sized to work.

What the prediction rested on, that a group’s total varies an eighth as much in proportion as one line’s, is true and is not the quantity a reserve holds. Sized for the spill, the pooled table goes under the fitted line at every room, by 0.019 to 0.032 bits a block, and reaches the prediction’s own point, 3.24 bits at 2.008 lines. Room can be pooled across neighbours in the part of it that spills.

What the table leaves out #

One filter design. The earlier essays’ filter, at one size. A filter with a different closed share or block width changes how much a line spills and how steady a group’s spill is.

The reserve beside the groups. The reserves are packed together, one region for all of them, and a lookup into a reserve is charged the line it lands on. A reserve laid out next to its group’s lines would share their cache lines, which this accounting does not credit.

Two seeds. Every point is two seeds of two filters, as before, and the differences under the line are two to three hundredths of a bit a block. The ordering holds at every room measured, which is the evidence it is not noise.

Still open: a reserve inside the lines #

The reserve costs a lookup a second line because it lives outside the group’s lines. But a group of 64 lines at the mean leaves, on average, as many empty slots in its under-filled lines as its over-filled lines spill, about 145 each way, and those empty slots are already paid for. A line could hold not only its own spill’s position but a neighbour’s: when a line is over its room, its extra values could go into the next line of the group with empty slots, chained, so that a spill costs a lookup the neighbouring line rather than a reserve’s.

The measurement that follows lets each line lend its empty slots to the following lines of its group, a value carried forward until a line has room, with a count in each line of how many values it holds for lines before it, and reports bits a block against lines a lookup beside the reserve. The prediction is that nearly every spill finds room within one or two lines, so that a lookup that spills reads its line and the next one, and that with no reserve at all the table costs about 3.12 bits a block for about 2.012 lines a lookup, under the spill-sized reserve by six hundredths. It could fail on runs: lines over their room come in runs, since the closed share drifts along the filter, and a value carried forward past a run of full lines costs a lookup one line for every line it passes. The question is whether the room the lines already have can be shared among them, or only the room a group adds.