A walk that stops at two lines

A blocked filter puts every key’s bits in one 64-bit block, and a split threshold filter gives each key two candidate blocks and a rule for choosing between them: a key goes to its first block while a per-block threshold on an ordering hash says it may. The thresholds are a table, four bits a block, and most of it never closes; a bit for whether it closed split the table into a bit a block saying whether its threshold closed and a packed list of the closed blocks’ values, so that a lookup reads its block’s line of the table and, for a closed block, the value beside it. Lines hold a fixed number of blocks, and a code that has to fit its worst line found that sizing every line for its worst draw of closed blocks wastes most of the table.

So the lines have been sized for the usual draw, and the surplus a line cannot hold has gone somewhere. To one shared overflow area, which an offset that only has to reach its neighbours priced; to a reserve kept for each group of 64 lines, which a reserve sized for the spill found cheapest once sized for the spill rather than for the group’s total; and, last, into the lines after it. The room the lines lend carried each line’s surplus forward into the empty slots of the following lines, with no reserve and no overflow at all. At room for the mean the table was the cheapest yet in bits, 3.113 a block, and the dearest in lines, 2.183 a lookup: a line with no slack lends nothing, so a carried value joins a queue and walks 12.8 lines on average before it finds a slot.

That essay’s closing section proposed capping the walk. A value carried forward at most two lines, and any that would go further sent to a shared overflow area at three lines a lookup, as for the ungrouped table: the long walks become overflow lookups and the short ones stay in the lines. The prediction was that a cap of two at room for the mean would keep most of the carried table’s bits, about 3.13 a block, for under 2.02 lines a lookup, and lie at least two hundredths of a bit under the spill-sized reserve there. It named the risk: at room for the mean the queue is long most of the time, and if most carried values are past two lines the overflow becomes a reserve by another name, outside the lines and three lines away.

Carried, then capped #

The filter, the keys and the charges are the earlier essays’: 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, and every layout charged both its bits a block — counted as whole lines, plus whatever lies outside them — and the lines a lookup reads.

The capped table is the carried table with one change. A line keeps its own closed values up to its room and puts the rest in a queue; free slots in each following line are filled from the front of the queue; and before a line takes from the queue, any value that has already walked its cap of lines is sent to overflow instead. A lookup of a carried value reads its own line, which holds how many values are waiting ahead of its own, and walks forward to the line that holds it. A lookup of a value sent to overflow reads its line, a small array holding each group of 64 lines’ start in the overflow, and the overflow’s line — and its own line carries one more count, how many values of its group went to overflow before its own, so that the lookup can find its value there. Caps of one, two and four lines were run at room for the mean and a quarter and a half of a deviation above it.

A hundredth under the reserve, and not the predicted point #

Capped at two lines, the carried table at room for the mean costs 3.180 bits a block for 2.0267 lines a lookup — not the predicted 3.13 for under 2.02 — and lies within a few thousandths of the ungrouped line’s 3.182 at the same lines: a capped walk is an ungrouped overflow with a short walk in front of it. Against the spill-sized reserve the cap does gain, at the one place they meet: the reserve at a line room of half a deviation below the mean costs 3.191 bits a block for 2.0261 lines, and the capped walk 3.180 for 2.0267, a hundredth less. The prediction asked for two hundredths and a lookup cost under 2.02; it got half the saving at a lookup cost above 2.02.

With more room the order reverses. At a quarter of a deviation the capped walk costs 3.217 bits for 2.0161 lines, where the reserve costs about 3.191 at the same lines, and at half a deviation 3.245 for 2.0115 against the reserve’s 3.21 or so. The caps make lines cheaper to read by sending long walks away, and the extra room makes the walks short already; the reserve, which does not walk at all, wins there.

Most of the queue goes to overflow #

The named risk is the case: at room for the mean, a cap of two lines sends 53% of the carried values to overflow, a cap of one 70% and a cap of four 34% — the queue is long most of the time, and most of what joins it would wait more than two lines. The uncapped walk’s 12.8 lines on average was not a few long walks among many short ones. At room for the mean a line has, on average, exactly as many free slots as it has surplus, so the queue does not drain; it drifts, like a random walk with no pull toward zero, and spends most of the table long. A value that joins a long queue waits for every value ahead of it, and a cap of two lets through only the values that join when the queue is nearly empty.

So at room for the mean the capped table holds about half its surplus in the lines and half in an overflow area three lines away, which is what the ungrouped table does with all of it. Its bits are the carried table’s lines plus that overflow, and its lookups are the overflow table’s cost on half the values plus a short walk on the other half: a mixture of two designs the earlier essays had already priced, and its point on the plate lies on the line between them.

Read at equal lines #

Read at equal lines a lookup, a capped walk costs more than the spill-sized reserve until lookups are allowed to be dearest: at 2.016 lines the reserve costs 3.191 bits a block, the uncapped walk 3.198, and walks capped at one, two and four lines 3.226, 3.218 and 3.232; only at 2.026 does a cap of two come under the reserve, 3.183 against 3.191. The plate is the same finding in another shape. Between 2.012 and 2.02 lines a lookup the reserve costs 3.19 to 3.21 bits a block, and every capped walk three to four hundredths more; the uncapped walk, given room, matches the reserve at 2.02 lines, 3.189 against 3.191. At 2.026 lines, the dearest lookups any capped table offers, the cap of two reaches 3.183 and the ungrouped line 3.182. The only region where a cap pays is where lookups are allowed to cost most, and there it pays eight thousandths over the reserve and nothing over the plain ungrouped line.

The four designs on the plate are four ways of putting a line’s surplus somewhere, and their curves lie within about three hundredths of a bit of each other across the lookup costs any of them reaches. Two blocks and the chances they add found the filter’s rate set by its blocks, and positions confined to one line its lookups by its lines; the table that records which block a key went to is a few bits a block, and how its surplus is placed now decides the third decimal of those bits.

How fast room shortens the walk #

The uncapped walk’s own numbers show why the cap had so little to work with. At room for the mean a carried value walks 12.8 lines; at a quarter of a deviation more room, 4.7; at half a deviation, 2.6; at three quarters, 1.9; at a full deviation, 1.5. A quarter of a deviation of room in a line of a few hundred blocks is a slot or two, and those few slots take the walk from a dozen lines to under five, because they give the queue a slight pull toward empty: with room just above the mean, a line on average has a little more free space than surplus, and the queue drains between the lines that overflow.

A cap does something different from room. Room shortens every walk by draining the queue; a cap shortens only the walks that would have been long, by removing their values, and leaves the queue as long as before for everything behind them. At room for the mean the two values ahead of a newly spilled one have usually been waiting long already, so a cap of two removes most of the queue’s traffic and keeps the short walks of the few values that arrive when it happens to be empty. At a quarter of a deviation the queue is shorter and the cap of two sends 37% away instead of 53%, but the room has already bought most of what the cap was for: the uncapped walk at that room walks 4.7 lines, and the cap of two cuts that to 1.4 by sending more than a third of the surplus three lines away, so that its lookups trade a long walk for a short one on most values and a three-line overflow read on the rest.

What the overflow costs to find #

A capped table has to say where its overflow values are, and that is part of why it lands on the ungrouped line. Each line holds two counts: the values waiting from earlier lines, five bits on this table, as the uncapped walk does; and how many values of its group have already gone to overflow, so that a lookup of a value sent there can find its place in the group’s part of the overflow. A group array holds each group’s start in the overflow, about twenty bits for every sixty-four lines, and is read only by lookups that go there. The ungrouped table pays for its overflow the same way — an offset in every line and a separate area — and the capped table, with half its surplus in overflow, pays about half that apparatus as well as the carried table’s count.

That apparatus is a few bits a line, a few hundredths of a bit a block, and together with the overflow’s own values — stored once each in a packed area outside the lines, where the uncapped walk kept them in slots the lines had anyway — it is why the capped table at room for the mean costs 3.180 bits a block rather than something nearer the uncapped walk’s 3.113. How the 0.067 divides between the values and the counts that find them was not separated.

Why a walk cannot be both short and cheap #

A walk is cheap in bits because it needs no reserve: every slot it fills is a slot the lines had anyway. It is short only where the lines have slack, and slack costs bits, because a line given room for the mean plus a quarter of a deviation holds a few more slots than it fills on average. The capped walk tried to get the first without the second, by sending away the values whose walks would have been long; but at room for the mean those are most of the values, and sending them away is paying for an overflow area of about half the surplus.

There is no free point between the two, and the measurement shows the cost of each. At room for the mean the walk is cheapest in bits, 3.113, and dearest in lines, 2.183. A cap of two moves it to 3.180 and 2.027, close to the ungrouped line. Room of three quarters of a deviation with no cap moves it to 3.215 and 2.010. A reserve sized for the spill offers 3.191 bits for 2.014 lines, which no walk at any cap or room measured here beats at that lookup cost. The worst of more lines found the same kind of floor when a lookup’s extra lines were priced: they are rare, and a design that makes them rarer pays in bits for the difference.

What the table does not show #

One size of table. Every number is the table of 524,288 keys, two seeds of two filters; the queue’s drift and the share of carried values that overflow depend on how many lines there are, and a smaller table has fewer long queues.

Lines, not time. A lookup is charged the lines it reads. A walk of two lines reads consecutive lines, which a machine fetches faster than the scattered lines of an overflow lookup; on hardware that prefetches the next line the capped walks would look better than this plate draws them, and the reserve, which reads a separate line, worse.

Three caps and three rooms. A cap of three, or a room of an eighth of a deviation, was not run, and the plate’s curves between the measured points are straight lines.

Still open: a queue that drains #

The capped walk fails because at room for the mean the queue does not drain: free slots and surplus balance on average, so the queue drifts and is long most of the time. A table can make it drain without giving every line slack, by giving slack to only some: every eighth line, say, sized with room for a deviation more than the mean, so that the queue empties into it at regular intervals. Between the slack lines the queue grows as before; at each slack line it is cut back, and no carried value can walk more than eight lines.

The measurement that follows sizes every $k$-th line with extra room, for $k$ of 4, 8 and 16 and extra room of one and two deviations, with the other lines at room for the mean and no cap, and charges the same bits and lines. The prediction is that at $k = 8$ with a deviation of extra room the table costs about 3.15 bits a block for under 2.02 lines a lookup, under the spill-sized reserve’s curve by two hundredths, because the extra slots are spent only where the queue needs them and every walk is bounded by the distance to the next slack line. It could fail on the slack lines themselves: their extra room is fixed in advance, and a queue that has grown long since the last one may be longer than any deviation of room, leaving values to walk on past it. The question is whether a line’s surplus can be absorbed by room placed at intervals, or whether any room that is not where the surplus arises is paid for twice — once in the bits that hold it and once in the lines walked to reach it.