Slack placed where the queue is long
A threshold filter sends each key to one of two blocks and records, for every block, the point at which it closed to new keys; a lookup reads that threshold before it reads the block. The thresholds live in a table packed into 512-bit lines, and the strand of essays on this filter has spent most of its length on how to pack them. A bit for whether it closed stored a bit for every block and a four-bit value only for the blocks that closed, about half of them, so each line codes a run of blocks and holds room for the values of those that closed. The room the lines lend sized that room for the mean and carried a line’s surplus forward into the following lines’ free slots. Cheapest in bits, 3.113 a block, and dear in lines, 2.183 a lookup, because at room for the mean the queue of carried values is a random walk with no drift and is long most of the time.
A queue that drains at intervals gave every eighth line a deviation of extra room so the queue would empty there. It did not: after a slack line the queue was empty a third of the time, walks reached 33 lines, and the reason was arithmetic. One line’s deviation of room is about seven spare slots; eight lines’ surplus wanders by about values. The slack lines bought a hundredth or two of a bit a block under spreading the same room evenly, at lines no other design would accept.
That essay’s closing section pointed at what a fixed spacing throws away. The table is not grown key by key; it is built once from a finished filter, so when its lines are laid out every line’s surplus is already known, and so is the queue’s length at every line. A slack line could go where the queue is long. The proposal: lay the lines out at room for the mean, follow the queue line by line, and whenever it holds at least values make the next line a slack line. The prediction was that at of about eight the table costs 3.15 bits a block for 2.03 lines a lookup — a hundredth of a line under the fixed spacing at the same bits — with every walk bounded at about eight lines. The named risk was the marking: a lookup has to find its block’s line, which now depends on how many slack lines come before it, and a count that costs a line read would cost more than every walk it shortens.
A line placed by the queue it follows
The two kinds of line are the earlier essay’s. A line is 512 bits whatever it holds, so room is bought with blocks: an ordinary line codes 165 blocks with room for 85 closed values, the mean among 165 rounded up; a slack line at one deviation more codes 157 blocks with room for 87, at two deviations 149 with room for 89. What changes is only where the slack lines go. The table is laid out from the first block, and after each line the layout counts the values still waiting; if there are or more, the next line is a slack line, otherwise an ordinary one. No walk is capped. 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, three lines a lookup.
Under a fixed spacing a lookup works out its block’s line by arithmetic, because the pattern repeats every lines — the property positions confined to one line made the point of this whole filter. Under this layout the pattern is whatever the queue made it, so the table carries a directory: one entry for every 64 lines, holding the number of the entry’s first block and a mark bit for each of its 64 lines. A lookup reads its entry, counts the marks — slack lines hold eight fewer blocks than ordinary ones — and arrives at its line. The directory’s bits are charged to the table in every number below. Whether its read is charged a line is the question the risk named, and it is answered separately, because the answer decides everything.
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. One filter of that size has 124,912 blocks and its table about 767 lines. Lines a lookup counts the threshold table’s lines read plus the block’s own line.
The hero plate is the design in one picture: the queue’s length after each of a filter’s first 120 lines, under a slack line every eighth line and under a slack line whenever the queue reaches eight. Under the fixed spacing the slack lines arrive on schedule, cut a few values off whatever the queue happens to hold, and the queue climbs to 28 between them. Under the queue’s own rule the slack lines arrive in clusters where the queue has grown, and none arrive in the long stretches where it sits at nothing.
Three hundredths under every table before it
Placed whenever the queue reaches eight, slack costs 3.150 bits a block for 2.027 lines a lookup — the prediction’s 3.15 and 2.03 — and at the same bits the fixed spacing reads 0.023 lines more, over twice the hundredth predicted. Seven of the eight queue-placed designs sit under the fixed spacing, the ungrouped line and the spill-sized reserve all at once. The eighth, a threshold of four with two deviations of room, reaches 2.015 lines at 3.197 bits, where the reserve sized for the spill reaches 2.014 at 3.192: at the fewest lines measured the two meet.
The size of the gain is easiest to read against the curves that matter. At 2.027 lines the ungrouped overflow line — the plain design with no carrying at all, room for the mean plus half a deviation in every line — costs 3.182 bits a block, and the reserve sized for the spill, the best design this strand had found, costs about 3.191 at its own nearest point. The queue-placed table at a threshold of eight is three hundredths of a bit under both. Against the uncapped walk with its room raised evenly the margin is similar: at a threshold of 32, where walks are longest and bits fewest, the queue-placed table costs 3.123 bits for 2.078 lines, and the even room reaches 2.078 lines at about 3.151.
The other half of the prediction concerned the comparison the proposal was built on, the same slack lines at fixed intervals. At every threshold the queue-placed table reads 0.017 to 0.033 lines fewer than the fixed spacing reaches at the same bits. The fixed spacing’s best near two lines, a slack line every fourth line at two deviations, was 3.180 bits for 2.032 lines; a threshold of eight with one deviation beats it on both axes at once, three hundredths cheaper and five thousandths quicker. Placement is the whole difference. The two designs have the same lines, the same room on each kind of line, the same filters and the same lookups; one puts its slack lines on a schedule and the other where its own queue says.
Walks that stop near the threshold
At a threshold of eight a carried value walks 2.16 lines on average and never more than eight, where a slack line every eighth line let values walk 7.34 lines on average and up to 33; at every threshold the longest walk is between six and seventeen lines, about the threshold or a little over. The bound the fixed spacing promised and could not keep is kept here, and for the reason the proposal gave. A value that joins the queue joins behind at most others plus its own line’s surplus, and once the queue reaches the next line drains some of it. A slack line at one deviation has about seven spare slots on average, so a queue held near eight is cut back by most of a slack line each time it reaches the threshold, and a value at the back of it waits for one or two such lines.
The plate also shows where the bound is loose. At a threshold of four with one deviation, the longest walk is nine lines, longer than at a threshold of eight. A low threshold puts slack lines down often, but each drains only its seven slots, and a run of unlucky lines can push the queue past four by more than one slack line can take; the queue then stays at or above the threshold for several lines running, and every one of those lines is a slack line. That is the reason the gaps plate below shows so many slack lines back to back. With two deviations of room the slack lines drain more, and the longest walks fall to six and eight lines.
The contrast with a walk that stops at two lines is the same contrast as before, made sharper. The cap bounded every walk at two lines by construction, and paid by sending more than half the carried values to an overflow three lines away. The queue-placed table bounds walks by spending room where they would have grown, keeps every carried value inside the table — the overflow takes six in ten thousand at a threshold of eight — and pays for the slack lines in bits it would otherwise have spread across all of them.
Slack in runs, not at intervals
Placed by the queue, 42% of slack lines come straight after another slack line and 64% within three lines of one, while the longest stretch with none is 29 lines; the mean spacing is 4.23 lines, about half the fixed spacing it beats. The slack goes in runs. A queue reaches the threshold after an unlucky stretch, and the lines that follow it are no luckier on average than any others, so the queue usually needs two or three slack lines in a row before it falls back below eight; then, if the following lines happen to have closed few blocks, the queue drains through ordinary lines’ free slots and no slack line is placed for twenty lines or more.
That is the shape the earlier essay’s arithmetic asked for. Its wander plate said that a queue’s growth over lines spreads as and that a slack line’s room, sized in one line’s deviations, cannot absorb it. A fixed spacing asks a single slack line to absorb whatever lines produced; the queue-placed table asks as many slack lines as the growth needs, one after another, and none when there was no growth. The room spent is roughly what the queue’s excess was, line by line, which is exactly the quantity a fixed spacing had to guess in advance.
Spending it this way costs more slack lines in all, which the next plate counts. At a threshold of eight, 23% of lines are slack lines, nearly twice the one in eight of the fixed spacing it is compared with. That should make the table dearer, since every slack line holds eight fewer blocks than an ordinary one, and the frontier says it does not: the slack lines that a fixed spacing places into an empty queue are wasted, and those are the ones this layout never places.
A queue cut back, not emptied
Placed by the queue, slack drains less often than the fixed spacing did — after 26% of slack lines at a threshold of eight, against 32% for a slack line every eighth line — and is placed nearly twice as often, 23% of lines against 13%; a slack line here is placed to cut a long queue back below the threshold, not to empty it. The earlier essay read its 32% as failure, because the fixed spacing’s promise depended on the queue emptying at each slack line. The queue-placed table makes no such promise. Its slack lines are judged by whether the queue stays near , and a slack line that takes its seven spare slots’ worth off a queue of twelve has done its job even though five values are still waiting.
The threshold sets how often that happens. At 32 the queue is allowed to grow long before any slack line appears, 6% of lines are slack and no slack line ever empties the queue; at four, 35% of lines are slack. Two deviations of room drain more at each threshold and need fewer slack lines to do it — 18% of lines at a threshold of eight against 23% — but each such line gives up sixteen blocks rather than eight, and the frontier shows the two settings of room tracing nearly the same curve, each threshold-and-room pair a different point on it.
The pairs together say what the threshold actually buys. Across the eight settings, from a threshold of 32 with one deviation of room to a threshold of four with two, lines a lookup fall from 2.078 to 2.015 and bits a block rise from 3.123 to 3.197. The threshold is a dial on one trade, mean walk against room spent, and the queue-placed table draws that trade at every setting about three hundredths of a bit under where any of the earlier tables drew it.
Two cache lines of marks
The marks cost 972 bits for a table of 124,912 blocks — under a hundredth of a bit a block, and under two cache lines for the whole directory — and the design stands or falls on where those two lines live: kept in cache, a threshold of eight reads 2.027 lines a lookup; read from memory with every lookup, 3.027, a line more than any design this strand has measured. The risk the proposal named turned out to be all or nothing, and the plate shows why. Every lookup needs its block’s line, so every lookup consults the directory. There is no partial charge: either the directory is where the lookup already is, or it is one more line.
The measured gain over the fixed spacing is about two hundredths of a line, and the directory’s read, if charged, is a whole line, fifty times that. No threshold changes the comparison, since the directory’s size hardly moves with — 972 or 1,053 bits at every setting, the second where the layout grows a few lines longer and needs another entry. The frontier plate is drawn with the directory in cache, and that is the condition attached to every number on it.
Whether the condition holds is a fact about the machine, not about the table, and this measurement does not model a cache. What it can say is how small the thing to be kept is. The directory of a filter of half a million keys is two lines of 512 bits, touched by every lookup, beside a table of 767 lines and a filter of 124,912 blocks touched at random. Any cache that keeps anything keeps the lines every lookup reads, which is the argument rank is the only thing it does makes about a rank directory’s top level and the reason such directories are sized to be tiny. It is not a measurement, and a filter shared by many structures competing for a small cache, or a cold lookup after a long gap, would pay the line. The fixed spacing and the reserve need no such assumption: their line is arithmetic, and that is the one advantage over this design they keep.
What the threshold cannot be told
The queue-placed table has a property none of the earlier designs had, and it is worth stating plainly, because it is why the gain is as large as it is. Every earlier table decided its room before it saw its own filter: a margin on every line, a reserve on every group, an offset sized for the neighbours it had to reach, a slack line on every -th line. Each was sized for a distribution — the mean and spread of closed blocks a line — and paid, somewhere, for the lines that drew from the distribution’s tail. The queue-placed table decides its room from the filter itself. It still uses a rule, the threshold, but the rule reads the one quantity that says where room is needed.
That is possible here only because the table is static. The day a filter cannot grow dealt with a fingerprint table that has to absorb keys as they arrive, and a threshold table rebuilt whenever its filter is rebuilt can be laid out with the whole filter in view. A table that had to accept insertions after it was built — a block closing that had been open, a value joining a line in the middle of a long run — would find its slack lines in the places the old queue needed them, and the new surplus would walk as it did under the fixed spacing until a rebuild.
There is a second limit, in what the queue measures. The queue’s length is the backlog of values without a slot, not the number of lookups that will wait for them. A lookup of an absent key touches a closed block’s value about half the time and a carried value about once in eighty lookups, so the walks the plates count are paid by a small share of lookups, and the mean lines a lookup is what the frontier reports. A design that wanted to bound the slowest lookup rather than the mean would want the longest walk, and on that axis the queue-placed table is the first in the strand whose longest walk is small enough to state: eight lines at a threshold of eight, against 33 for the fixed spacing and 12.8 on average, unbounded, for the uncapped walk. The probe nobody waits for is the reminder that a mean and a worst case answer different questions, and here, unusually, both improved together.
What the measurement leaves out
One table size and one filter design. 524,288 keys in 64-bit blocks at sixteen bits a key, as in the earlier essays; the threshold table’s line count, and so the directory’s share, would change with the filter’s size, though the directory stays one entry per 64 lines.
No cache. Lines a lookup counts lines read, as everywhere in this strand. Whether the directory’s two lines are resident is stated as a condition and both charges are printed; neither is measured on a machine.
A static table. The layout is computed once from a finished filter, and no insertion after it was measured.
Two settings of a slack line’s room, one and two deviations, with four thresholds each. A slack line sized from the queue’s actual excess, rather than in one of two fixed sizes, would make the line’s block count variable too, and the directory would need more than a mark to find it.
Still open: marks a lookup can count without a directory
The design’s whole gain rests on a directory that every lookup must read. The way to remove it is to make the slack lines’ positions partly arithmetic again without giving up placement by the queue. Fix the number of slack lines in every group of 64 lines — at a threshold of eight about fifteen of them, close to the 23% the queue chose — and let the layout place that many inside each group where its queue is longest, carrying the queue across the boundary as before. A group’s first block is then arithmetic, and a lookup can guess its line inside the group as if every line before it were ordinary. The guess is late by the number of slack lines before it times eight blocks, so it is off by at most one line; each line stores, in a few bits, how many slack lines precede it in its group, and a lookup whose guess is wrong reads the line before.
The measurement that follows sets the budget at the share the queue-placed table chose and at a little above and below it, and charges every lookup that reads its guessed line and then the right one. The prediction is that the budget costs under a hundredth of a bit a block over the free placement, since the queue rarely asks for more than the budget inside one group, and that the guesses go wrong for about a third of the lookups that land on a closed block whose line has a slack line before it in its group. It could fail on that third: if wrong guesses cost more than the fixed spacing’s walks, the directory, kept in cache, remains the cheaper answer and the budget is a worse design that merely needs no assumption. The question is whether a layout chosen by its own data can be found by a lookup that knows only the data’s position, or whether anything placed by the data has to be looked up.
What this makes readable
Essays that name this one as a prerequisite.
Named alongside this one
Essays reaching for the same objects. Nobody chose these; they are what the concept index makes visible.
- A code that has to fit its worst line blocked filter · cache line · design parameter · threshold
- A block the lookup can work out blocked filter · design parameter · threshold
- A penalty set by the block blocked filter · design parameter · threshold
- A threshold knows only its own block blocked filter · design parameter · threshold
- The bits a second threshold costs blocked filter · design parameter · threshold
- Two hashes that shared their low bits blocked filter · design parameter · threshold
What links here
Every essay whose body links to this one.
The objects this essay names
Each one links to every other essay that touches it.
Blocked filterCache lineDesign parameterPredictionRankThresholdVariance