The room the lines lend

A reserve sized for the spill pooled the room of a blocked filter’s threshold table. The table stores one bit a block for whether its threshold closed and a four-bit value for each block that did, packed into 512-bit lines that a lookup reads in one go. Each line was given room for the mean number of closed blocks, and each group of 64 lines a reserve of value slots for its lines’ excess. Sized for the group’s expected spill rather than for a deviation of its total, the reserve put the table under the curve the ungrouped line draws, by two to three hundredths of a bit a block, the first layout on this table to get under it.

Its closing section noticed what the reserve did not use. A line sized for the mean is under its room about half the time, and its empty slots are inside its own 512 bits, already paid for. A group of 64 lines leaves, on average, about as many empty slots in its under-filled lines as its over-filled lines spill, some 145 each way. The reserve is bought because those slots cannot be reached: a line’s extra values have nowhere in the lines to go. They could have somewhere. A line over its room could pass its extra values to the next line with empty slots, carried forward in order, and a lookup whose value moved would read its own line and walk forward to the one that holds it.

It predicted that nearly every spill would find room within one or two lines, and that with no reserve at all the table would cost about 3.12 bits a block for about 2.012 lines a lookup, six hundredths under the spill-sized reserve. It named the way that could fail: lines over their room come in runs, and a value carried past a run of full lines costs a lookup one line for every line it passes.

The bits came out where predicted. The lines did not, and the runs are the reason, though not for the reason the closing section gave.

Lines that lend their empty slots #

The filter, keys and accounting are the earlier essays’: 64-bit blocks, 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. Each line holds room for the mean number of closed blocks among its blocks plus $z$ standard deviations of that number, computed from the binomial distribution of a line’s closed blocks, and $z$ is swept from nought to one and a half.

There is no reserve and no group. The table is built in one pass, line by line. A line keeps its own values up to its room. If it has slots left over, it fills them, oldest first, from a queue of values that earlier lines could not hold. If it has more values than room, its extra values join the end of the queue. Each line records, in a few bits, how many values were waiting in the queue when its own extras joined, so a lookup of a carried value knows how many earlier values stand ahead of it. A lookup reads its line; if its value is there, it is done. If not, it walks forward one line at a time, reading each line’s bit vector to count its free slots, until it reaches the line where its value landed. Anything still waiting at the end of the table goes to a small overflow area.

The arrangement is linear probing, played out at the scale of lines rather than slots. The probe nobody waits for found that in a linear-probing table the order of arrival cannot change the total distance keys travel from home, only how it is shared; that total is set by how full the table is. The same is true here: how far carried values travel, all together, is set by how much room each line has over what it is asked to hold.

Bits as predicted, lines far past it #

At room for the mean, carrying spills forward costs 3.113 bits a block, the prediction’s 3.12, and 2.183 lines a lookup, where the prediction said 2.012. The table is as small as predicted, smaller than any table on this curve so far, because it holds no reserve, no group offsets and almost nothing in an overflow area. Every slot it pays for is inside a line, and nearly every one is used. What it costs is the walk. A lookup that lands on a closed block whose value was carried reads its own line and then every line the value passed, and at room for the mean that is a long way.

At a quarter of a deviation of room the lines fall to 2.052, still worse than any point the ungrouped line reaches. At half a deviation the carried table costs 3.190 bits for 2.0187 lines, the same bits as the spill-sized reserve at those lines, to a thousandth. From there it goes under. At three quarters of a deviation it costs 3.215 bits for 2.0098 lines, where the reserve, read at the same lines, costs 3.225; at one deviation 3.282 for 2.0047, against 3.292. At a deviation and a half it reaches 3.346 bits for 2.0012 lines, where the fitted ungrouped line costs 3.393 and the reserve has no point.

A queue with nothing to spare #

At room for the mean a carried value passes 12.8 lines on average before it lands, and the queue of waiting values grows past 63 at once, so each line’s count of it needs 7 bits. At a quarter of a deviation of room the walk is 4.7 lines, at half a deviation 2.6, at three quarters 1.9, at one deviation 1.5, and at a deviation and a half 1.1. The share of lookups on a closed block whose value was carried falls more slowly, from 2.8% at the mean to 0.2% at a deviation and a half. Most of what changes with room is how far a carried value goes, not how many are carried.

The closing section expected the runs to come from the filter: the share of blocks that close drifts along the filter, so lines over their room would cluster. That may contribute, and nothing here separates it out. But the walk at room for the mean needs no drift to explain it. A line sized for the mean holds on average what it is asked to hold, so the queue gains, on average, exactly what it loses at each line. A queue whose arrivals and departures balance does not settle: it wanders, as a random walk does, and its length grows with the square root of how far it has gone. Linear probing at a load of one behaves the same way, and it is the reason no hash table is run full. The values that join the queue at the top of one of its long wanders wait behind everything already in it, and pass every line it takes to clear.

The room for the mean is not quite the mean, since a line’s room is rounded up to a whole value, and that rounding is the only slack the queue has. Any room over the mean gives the queue a margin, and a queue with a margin drains: its length settles, and the distance a value waits falls roughly as one over the margin, until it nears the single line every carried value has to pass. Half a deviation of room is about three slots a line over the mean, and the walk falls from 12.8 lines to 2.6. That is the mechanism the plate shows, and it is the one the prediction left out. “One or two lines” is the right walk for a table with slack, and room for the mean has none.

Under both curves, and by how much #

Carried forward with three quarters of a deviation of room, the table lies 0.034 bits a block under the fitted ungrouped line and 0.010 under the spill-sized reserve at the same lines a lookup; at one deviation, 0.029 and 0.010. At half a deviation it is 0.012 under the ungrouped line and level with the reserve. At a deviation and a half it is 0.047 under the ungrouped line, at a number of lines the reserve was not measured at. A hundredth of a bit a block is about a third of a percent of the table, small, and it holds at both rooms where the two can be compared.

The saving comes from where the slots are. The reserve holds the group’s spill in slots of its own, outside the lines, and it is sized for the expected spill plus a margin, so on average a fifth of it sits empty. The carried table holds the same spill in slots the lines already had, emptied by the lines under their room. It pays for its margin in the lines instead, as extra room in every line, and that margin is what keeps the walk short. At three quarters of a deviation the margin in the lines costs less than the reserve and the group offsets together, and the lookup that moves pays about the same either way, one or two lines more than the one it would read anyway.

Two kinds of slack #

The two layouts buy their slack in different places, and the comparison shows what each is for. The reserve keeps the lines at the mean and puts all the slack in one place for each group, which is the cheapest way to cover a sum of independent spills, as the earlier essay found: the group’s spill varies by a fifth of its mean. The carried table spreads the slack over every line, which is the dearer way to buy it, but it also reuses the slack the lines already had by chance, the slots of lines under their room, which the reserve throws away.

At room for the mean the carried table buys no slack at all and reuses only chance slack, and the queue shows that chance slack alone is not enough to carry the spill a short way. At three quarters of a deviation it buys enough that the reused slots take the rest, and that combination is worth a hundredth of a bit over buying all the slack in a reserve. The table that would win outright would combine them, and that is where the next measurement goes.

An offset that only has to reach its neighbours found that the address of a moved value can be made short by pooling it over neighbours. The same idea now reaches the room itself. The worst of more lines sized every line for its worst case and paid for it in every line; a bit for whether it closed made a line’s contents a count of closed blocks, which is why a line’s spare slots can be counted from its own bits. And a code that has to fit its worst line was the first to find that the table is priced by its worst lines rather than its typical one. Carrying values forward is the first layout in which a line’s luck, a few blocks fewer than expected, is worth something to a neighbour.

The filter itself met the same question one level down. Two blocks and the chances they add sent each key to the emptier of two 512-bit blocks, so that a block’s spare capacity was offered to keys that would otherwise crowd a fuller one, and the loads flattened, though a lookup then had to ask both blocks and the filter’s error rate rose. Lending a line’s empty slots is the table’s version of that, with one difference that decides everything: a key choosing between two blocks looks at both before it lands, while a carried value has no choice, only a queue, and a queue with no margin gives the walk its length. The 512-bit line that both arrangements respect is there because positions confined to one line made a lookup cost one read of memory, and every walk counted here is measured against that one read.

What the prediction got right #

The closing section predicted that, carried forward with no reserve, nearly every spill would find room within one or two lines and the table would cost about 3.12 bits a block for 2.012 lines a lookup. The bits are 3.113. The lines are 2.183, because a carried value passes 12.8 lines on average. It named runs of full lines as the way the prediction could fail, and runs are what failed it, though their source is the queue’s lack of slack, not a drift in the filter.

It asked whether the room the lines already have can be shared among them or only the room a group adds. It can be shared, with a margin: given three quarters of a deviation of room or more, the lines lend their empty slots to their neighbours’ spills, a carried value passes under two lines, and the table lies about a hundredth of a bit under the reserve that pooled only the room a group added.

What the walk leaves out #

A lookup is charged one line for every line it walks. A real walk reads each line’s bit vector to count its free slots, and consecutive lines sit next to each other in memory, where a processor’s prefetcher reads ahead. A walk of two lines may cost much less than two separate lines, which would favour the carried table; this accounting does not credit it.

One filter design, two seeds. The earlier essays’ filter at one size. The differences under the reserve are a hundredth of a bit a block, and they hold at both rooms compared; a different closed share changes how much a line spills.

The order is first in, first out. A value carried forward waits behind every earlier one. Placing the values that have waited longest last, or the reverse, would leave the total distance the same, as linear probing does, and change only how it is shared among lookups.

Still open: a walk that stops #

The carried table is cheapest in bits at room for the mean and loses only through its longest walks, the values that join a long queue and pass a dozen lines. A walk can be capped. Let a value be carried forward at most two lines, and send any value that would go further to a shared overflow area, which costs a lookup three lines as it does for the ungrouped table: the long walks become overflow lookups, and the short ones stay in the lines.

The measurement that follows caps the walk at one, two and four lines at room of nought, a quarter and half a deviation, and reports bits a block against lines a lookup beside the carried table and the reserve. The prediction is that a cap of two lines at room for the mean keeps most of the carried table’s bits, about 3.13 a block, for under 2.02 lines a lookup, and lies at least two hundredths under the spill-sized reserve there, since it pays for neither a reserve nor a margin in every line. It could fail on the overflow: 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. The question is whether a line’s luck can be lent a short way and its misfortune sent somewhere else.