A queue that drains at intervals

A threshold filter splits its keys between two blocks and records, for each block, the threshold at which it closed to new keys; a lookup reads the block’s threshold before it reads the block. The thresholds live in a table packed into 512-bit lines, and most of the essays on this filter have been about the table. A bit for whether it closed stored one bit for every block and a four-bit value only for the blocks that closed, which is about half of them, so each line holds a run of blocks and room for the values of those that closed. The room has to be sized in advance, and the number of closed blocks in a line varies.

The room the lines lend sized every line for the mean and let a line’s surplus — the closed blocks it has no room for — carry forward, in order, into the next lines’ free slots. A lookup of a carried value reads its own line, then walks forward, reading each line’s free slots from its own count, until it reaches the line that holds the value. At room for the mean that table was the cheapest in bits measured, 3.113 bits a block, and dear in lines, 2.183 a lookup against the two of a table that never carries: a carried value joined a queue with no slack and walked 12.8 lines on average. A walk that stops at two lines capped the walk and sent anything that would go further to a shared overflow, and found that at room for the mean 53% of carried values went to overflow; the cap became an ungrouped overflow by another name.

That essay’s closing section diagnosed the walk. At room for the mean, free slots and surplus balance on average, so the queue’s length is a random walk with no drift — it wanders, and most of the time it is long. A queue that drains needs room somewhere, and the proposal was to put the room at intervals rather than everywhere: every $k$-th line sized for a deviation more than the mean, so that the queue empties into it, and no carried value walks past the next slack line. The prediction was that a slack line every eighth line, with a deviation of extra room, would cost about 3.15 bits a block for under 2.02 lines a lookup, two hundredths of a bit under the reserve sized for the spill. The named risk was a queue that had grown since the last slack line longer than any deviation of room.

A line that holds fewer blocks #

A line is 512 bits whatever it holds, so room is bought with blocks. An ordinary line here holds 165 blocks and room for 85 closed values, which is the mean number of closed blocks among 165 rounded up, plus the bits for each block’s closed flag and the count of values waiting. A slack line sized for one deviation more than the mean holds 156 or 157 blocks and room for 87 values; for two deviations, 148 or 149 blocks and room for 89. Every other line is ordinary, at room for the mean, and there is no cap on the walk: a value waits until some line has a free slot for it, and the few still waiting at the end of the table go to an overflow area.

The layout repeats every $k$ lines, so a block’s line is arithmetic and a lookup needs no index — the property positions confined to one line made the starting point of this whole filter, where a lookup’s positions were confined to one block so that it reads one line. Everything else is the earlier essays’: a split threshold filter of 524,288 keys in 64-bit blocks, sixteen bits a key, four-bit threshold values, two filters a seed and two seeds, a hundred thousand absent lookups a filter, every stored key checked to be found. Lines a lookup counts the threshold table’s lines read plus the block’s own line.

What a slack line holds #

A line is 512 bits whatever it holds, so a slack line buys its room with blocks: an ordinary line holds 165 blocks and 85 slots, a slack line at one deviation 157 blocks and 87, at two deviations 149 blocks and 89 — the extra room is a handful of slots beyond the share an ordinary line gives the same blocks. The plate is the cost side of the proposal. A slack line at one deviation gives up eight blocks to buy two more slots, and since its 157 blocks fill about 80 of its 87 slots on average, it has about seven slots to spare for the queue. At two deviations it gives up sixteen blocks and has about thirteen to spare. Those spare slots are all the draining any slack line can do.

The other cost is the table’s length. A table with one line in eight holding eight fewer blocks needs about 0.6% more lines, which is the bits the proposal expected to spend. What it did not expect is how little draining eight slots buy.

The frontier #

A slack line every eighth line, with a deviation of extra room, costs 3.123 bits a block for 2.103 lines a lookup — cheaper in bits than the predicted 3.15 and five times further over two lines than the predicted under 2.02 — and five of the six slack spacings land a hundredth to two hundredths of a bit under the uncapped walk at the same lines. The prediction fails in the direction that matters. The design is cheaper in bits than expected because a slack line’s extra room costs little, and much dearer in lines because that room does not do what it was for: a lookup that reads 2.103 lines is carrying a tenth of a line of walking on average, five times the two hundredths the proposal allowed.

The six slack designs make a curve of their own, and it is a real improvement on one thing. The uncapped walk with its room raised evenly across every line — a quarter of a deviation, then a half — runs from 3.113 bits for 2.183 lines to 3.190 for 2.019. Five of the six slack designs sit under that curve, by between 0.012 and 0.020 bits a block; the sixth, a slack line every fourth line at two deviations, sits on it. Room placed at intervals is cheaper than the same room spread out, as the proposal argued. But the slack curve stops where the others start. The closest it comes to two lines is a slack line every fourth line at two deviations, 3.180 bits for 2.032 lines, and there it lies on top of the cap-two walk and the ungrouped line, 3.180 and 3.182. Under 2.03 lines, where the reserve and the ungrouped line live, no slack spacing measured reaches at all.

A queue that does not drain #

The queue does not drain: after a slack line every eighth line with a deviation of extra room, the queue is empty 32% of the time; two deviations raise it to 62%, and a slack line every fourth to 74%. The named risk is the common case. Two times in three, a queue that reaches a slack line is longer than the slack line’s spare slots, and the values left over walk on to the next one. The slack line still takes what it can — about five values at that spacing — so it shortens the queue, but it does not reset it.

The pattern across the plate is the one the risk implied. More room per slack line drains more often. Closer slack lines drain more often, because the queue has had less time to grow. A slack line every sixteenth line at one deviation drains barely more than a quarter of the time, so most of the time it is just a slightly roomier line in a queue that runs past it.

How far the values walk #

No walk stops at the next slack line: with one every eighth line and a deviation of extra room a carried value walks 7.34 lines on average and up to 33, past four slack lines; at every spacing measured the longest walk is between 2.3 and 5.3 spacings long. The proposal’s bound — no carried value walks more than $k$ lines — would hold if every slack line drained, and the previous plate says most do not. The mean walk falls from the uncapped table’s 12.8 to between 2.6 and 9.6, which is the gain, and the longest walks stretch across several slack lines.

A capped walk had the opposite profile. The cap bounded every walk at two lines by construction and paid for it with an overflow that held half the carried values, three lines a lookup each. Slack lines keep every carried value in the table, and pay with walks that are shorter on average than the uncapped table’s and unbounded in the tail. Neither shape reaches two lines a lookup at room for the mean, for the same reason, which the next plate makes into arithmetic.

Room for one line, wander over eight #

Why the queue does not drain: an ordinary line of 165 blocks spills with a standard deviation of about 6.4 values, so over $k$ lines the queue wanders by about $6.4\sqrt{k}$ — 12.8, 18.1 and 25.6 at $k$ = 4, 8 and 16 — while a slack line’s spare slots are about seven at one deviation and thirteen at two. The proposal sized the slack line’s extra room in the deviations of one line, and the quantity it had to absorb was the deviation of $k$ lines’ surplus summed. Sums of independent deviations add in square, so eight lines’ surplus spreads $\sqrt{8}$, nearly three times, as wide as one line’s. A slack line with one line’s deviation of extra room is outwalked by the queue it was built for whenever that queue has had a moderately unlucky eight lines.

The arithmetic also says what spacing and room would drain. To absorb the queue’s wander most of the time, a slack line needs room for a couple of deviations of $k$ lines’ surplus, about $2 \times 6.4\sqrt{k}$ slots. At $k = 4$ that is about 26 spare slots, nearly twice what two deviations of one line give; at $k = 8$ about 36. And the cost of that room scales the same way: spare slots are bought with blocks, at about four blocks for every three slots. Slack lines trade a bit-cost that grows as $\sqrt{k}$ against a walk that shrinks as $k$ — there is no spacing at which both are small. The worst of more lines met the same arithmetic from the other side: a table that sizes every line for its own deviation pays for the worst line of many, and one that pools lines pays for the spread of their sum, which grows more slowly than the sum of their spreads. Here the square root works against the design, because the surplus a slack line must absorb is a sum it was sized as if it were one term.

What the walk costs a lookup #

A carried value’s walk is paid only by lookups that need it, and most lookups do not. A lookup of an absent key reads its block’s threshold first, and the threshold is in the block’s own line unless the block closed and its value was carried; at room for the mean between 2.4% and 2.7% of the lookups that land on a closed block find its value carried, and closed blocks are about half of all blocks. So the tenth of a line that the slack design adds over two is the walk of about one lookup in seventy-five, each walking several lines — 7.3 on average at a slack line every eighth line — and a lookup that is not carried reads exactly two.

That is why a few long walks move the mean so little and why the mean is a poor summary of the design. The share carried is set by how much room the ordinary lines have, which is the mean, and no spacing of slack lines changes it; the slack lines change only how far the carried values go. A design that wanted to bring the mean lines down further would have to carry fewer values, which means more room on every line, which is the uncapped walk at higher room — the curve the slack lines sit a hundredth under.

Room at intervals, room everywhere #

The plates leave the proposal’s central intuition standing in a reduced form. Room placed where the queue drains is cheaper than room placed everywhere: at equal lines a lookup, every slack design is a hundredth or two cheaper in bits than raising every line’s room. That is the same economy an offset that only has to reach its neighbours found for the overflow’s addressing — spend where the variance is absorbed, not everywhere it might arise.

What the intuition missed is that “where the queue drains” is not a place the table can choose in advance. The queue’s length at any line depends on every line since it last emptied, and a fixed spacing of slack lines meets the queue at whatever length chance has given it. A reserve sized for the spill sized a shared reserve for the expected spill of a group of lines, which is the same arithmetic done in advance: a group’s spill has a mean and a spread, and a reserve sized for them absorbs it whatever its order. The reserve reaches 2.014 lines at 3.192 bits; the slack lines’ best near that, 3.180 for 2.032, reads two hundredths of a line more.

The probe nobody waits for is the reminder about the tail: there, Robin Hood hashing left the mean probe count exactly where it was and moved the worst case from 114 slots to 19. A lookup’s cost here is a mean too, and slack lines leave a longer tail than any design with a hard bound on its walk; a system that cared about its slowest lookups would weigh the 33-line walks differently from this plate.

What the measurement leaves out #

One table size. 524,288 keys, about 8,200 blocks a filter and fifty lines. The overflow at the end of the table holds the queue left over after the last line; on a longer table it would be the same few values over more lines.

Fixed spacing. Slack lines every $k$ lines exactly. A table that placed its slack where its own queue was long at build time — which it knows, since it builds the queue — would be a different design, measured next.

Mean lines. Lines a lookup is the mean over absent lookups; the plates on walks show how wide the tail is but do not price it.

Still open: slack placed where the queue is long #

The slack lines fail because their room is fixed in advance and the queue’s length is not. But the table is built, not grown: when its lines are laid out, every line’s surplus is known, and so is the queue’s length at every line. A table could place its slack where the queue is long instead of at fixed intervals. Lay the lines out at room for the mean, compute the queue line by line, and whenever it passes a length $Q$, make the next line a slack line with room for the queue’s excess; record, in a few bits a line, which lines are slack, so a lookup can still find its block’s line.

The measurement that follows sweeps $Q$ from four to thirty-two values on the same filters, charging the slack lines’ blocks and the bits that mark them. The prediction is that at $Q$ of about eight it reaches 3.15 bits a block for 2.03 lines a lookup — a hundredth of a line under the fixed spacing at the same bits — and bounds every walk at about eight lines, since no queue is allowed to grow past what one slack line drains. It could fail on the marking: a lookup now has to know how many slack lines precede its block, which is a rank over the marks, and a rank that costs a second line read would cost more than every walk it shortens. The question is whether room can be put where the variance lands once the table knows where that is, or whether any design that keeps every value in its own region must pay the square root of the region’s length.