A guess that costs more than the walk
A threshold filter sends each key to one of two 64-bit blocks and keeps, for every block, a four-bit value saying when it closed to new keys. A lookup reads that value before it reads the block, so the values live in a table packed into 512-bit lines, and how the table is packed decides how many lines a lookup costs. A bit for whether it closed stored a bit for every block and a value only for the blocks that closed; the room the lines lend sized each line’s room for the mean number of closed blocks and carried a line’s surplus forward into later lines’ free slots. A carried value is found by walking forward from its block’s line, and how far it walks is the price.
A walk that stops at two lines capped how far a carried value may walk, and a queue that drains at intervals gave every eighth line extra room and found that one line’s slack cannot drain eight lines’ wander. Slack placed where the queue is long used the fact that the table is built once, from a finished filter: it laid the lines out at room for the mean and made the next line a slack line whenever eight or more values were waiting. That table costs 3.150 bits a block for 2.027 lines a lookup, and no walk is longer than eight lines. At the same bits, slack every few lines reads about two hundredths of a line more.
All of that depended on a directory. A slack line holds fewer blocks than an ordinary one, so once the slack lines go wherever the queue put them, a block’s line can no longer be worked out from its number. That essay stored a mark bit for every line, grouped 64 to an entry with the entry’s first block, and a lookup counted the marks before its line. The directory is small, 972 bits for the whole table, but a lookup has to read it. If it is in cache the design wins; read from memory it costs a whole line, and at 3.03 lines a lookup the design loses to every other.
Its closing section proposed taking the directory away. Fix the number of slack lines in every group of 64 lines, at about the share the queue chose, and let the layout place that many inside each group where its queue is longest. A group then holds a fixed number of blocks, so its first block is arithmetic again. A lookup can guess its line as if every earlier line of its group were ordinary; the guess is late by the slack lines before it, eight blocks each, so it is off by at most one line; and each line stores in a few bits how many of its group’s slack lines precede it, so a lookup whose guess is wrong knows exactly where to go next. The prediction was that the budget would cost under a hundredth of a bit a block over the free placement, and that the guess would be wrong for about a third of the lookups that land on a closed block with a slack line before it in its group. The risk was that wrong guesses would cost more than the walks the placement shortens.
The table, as built
A group is 64 lines and holds exactly slack lines. The layout goes line by line as before and makes the next line a slack line whenever eight or more values are waiting, while the group’s budget lasts. When the budget is spent, the queue’s further requests in that group are refused and the lines stay ordinary. When a group nears its end with slack lines still unspent, the remaining lines are made slack so the count comes out exactly, whether the queue asked or not. The queue carries across a group boundary as it did across any line.
Every line now stores, beside its blocks’ bits, how many of its group’s slack lines come before it and whether it is slack itself: five bits at a budget of fifteen, six above sixteen. A lookup for block computes its group, divided by the group’s fixed block count, and its offset within the group, and guesses the line that offset would fall in if every line of the group held the ordinary 163 blocks. It reads that line. The line’s count says where the line’s first block really is, and if block is not among the line’s blocks the lookup moves forward as many lines as the shortfall needs, assuming the lines in between are ordinary, and reads again.
Everything else is the earlier essays’: a split threshold filter of 524,288 keys in 64-bit blocks, sixteen bits a key, two filters a seed and two seeds, a hundred thousand absent lookups a filter, every stored key checked to be found. One filter has 124,912 blocks and its table about twelve groups. Lines a lookup are the threshold table’s lines read, including any wrong guess, plus the block’s own line.
Between the directory and the fixed spacing
With no directory, a budget of fifteen slack lines a group costs 3.187 bits a block for 2.45 lines a lookup — between the free placement read through its directory, 3.03 lines, and the fixed spacing, which reaches 2.03 lines at the same bits. No budget and no threshold measured gets within a fifth of a line of the fixed spacing. The best, a threshold of sixteen, reads 2.29.
The design does what it set out to do in one respect: it removes the directory’s whole line. A lookup that guesses right reads exactly the lines it would read under fixed spacing, and the plate’s dots sit 0.6 lines under the directory’s. But the line it saves is not the comparison that matters, because a design that stores no marks at all, slack every fourth line with two deviations of room, already reads 2.03 lines at these bits. The budget had to beat that and it misses by more than four tenths of a line.
Two of the proposal’s numbers went wrong, and the plate’s horizontal axis carries one of them. Every budgeted design sits at 3.17 to 3.21 bits a block, two to six hundredths over the free placement’s 3.150, where under a hundredth was predicted. The vertical axis carries the other, and it is the larger.
The guess is the bill
Everything the queue’s placement can save is in the walk, and the walk is 0.032 lines a lookup under fixed spacing and 0.027 under the free placement; a budget of fifteen pays 0.41 lines to find its line, and then walks 0.04. The plate puts the whole argument of the slack lines in its pale ends. Under every design here, a lookup reads two lines it cannot avoid, its block and its table line. The walk is what the designs compete on, and at these bits the competition is over a few hundredths of a line, because the room was sized so that walking is rare.
That reframes the earlier essay’s result. Slack placed by the queue beat the fixed spacing by about two hundredths of a line at the same bits, which was real and was all there was to win. Any way of finding a line that costs more than two hundredths of a line on average loses the design its whole advantage. The directory cost a line; the guess costs four tenths; a design that guessed right nineteen times in twenty would still cost five hundredths and lose.
The budget’s own walks are no shorter than the fixed spacing’s. A budget of fifteen walks 0.04 lines, longer than either design it was meant to sit between, for a reason the walk plate shows. It is the second way the budget gives back what the free placement had.
Wrong four times in ten
The guess is wrong for 25% to 54% of lookups — 41% at the queue’s own budget of fifteen — because every slack line before a block in its group puts the block 8 blocks further on than the guess, and a block with half its group’s fifteen behind it sits about 60 blocks into a 163-block line from where the guess put it. The proposal expected a third of a minority, the closed blocks with a slack line before them. The plate is counting every lookup, open blocks and closed, and it is wrong for four in ten of them.
The arithmetic is short once the shift is seen as cumulative. An ordinary line holds 163 blocks and a slack line 155, so each slack line before a block moves the block eight blocks later than the arithmetic says. A block near the start of its group has few slack lines behind it and is guessed right. A block near the end has nearly all fifteen behind it, a shift of about 120 blocks, and is guessed right only if it sits in the last 43 blocks of its line. Averaged over a group, the shift is about 60 blocks, and a block is guessed wrong when its offset within its true line is less than the shift’s remainder, which is a little over a third of the time. That the guess is never more than one line out was right: 120 blocks is less than a line, so a second read always lands.
The threshold moves the share because it moves where the slack lines sit. At the queue asks late, so most of a group’s budget is spent at its end, where the layout forces the unspent lines, and a block early in the group has none behind it: 25% wrong. At the queue asks early and often, the budget is spent in the group’s first lines, and nearly every block has most of the slack behind it: 54%.
A budget the queue does not keep
No budget fits the queue: at fifteen slack lines a group the queue is refused about six lines a group and two more are placed where it did not ask, because its demand varies from group to group about the 23% it averages. The free placement made 23.5% of its lines slack, fifteen of 64. A budget of exactly that share is right on average and wrong in almost every group, because the queue is a random walk, and how many times it reaches eight inside 64 lines varies as much as the walk does.
The plate shows the two failures trading. A tight budget refuses many requests, 228 a filter at ten; a loose one forces many slack lines nobody asked for, 140 at 24, each holding eight fewer blocks than an ordinary line would and buying room in a place with no queue to use it. Nothing in between avoids both, because the variation is between groups and the budget is the same for all of them. A budget of 17 refuses 35 and forces 53, about as balanced as the two get, and it still reads 2.41 lines.
The bound that went with the directory
The budget gives back the bound the free placement bought: the longest walk is 8 lines when slack goes wherever the queue asks, 29 on a budget of fifteen and 33 on ten, as long as fixed spacing every eight. The free placement’s one unconditional promise was that no value walks farther than the queue’s threshold allows, because a queue of eight always gets its slack line next. A refused request breaks that promise at once: the queue grows past eight, the next line is ordinary, and the walk lengthens until the next group’s budget arrives.
Only the two largest budgets restore something near the bound, 13 lines at twenty and 9 at twenty-four, because they refuse almost nothing. They pay for it in forced slack, which costs bits, and in a worse guess, since more slack lines behind a block shift it further. A budget large enough to keep the bound is a budget that spends a third of its lines on slack, which was never the design.
A long walk is rare — the worst of more lines found a table’s worst line far from its typical one — so the mean walk barely shows it; the parts plate’s walks moved by hundredths. The bound mattered to the earlier essay as a guarantee: a lookup’s worst case is what a table built for a hardware path has to plan for, and the budget gives up the guarantee without buying anything for the average.
Five bits a line, every line
The budget costs 0.037 bits a block over the free placement at fifteen, not under a hundredth: the count every line now carries takes five bits out of each line, and the slack lines a budget forces where the queue did not ask hold fewer blocks for nothing. The proposal priced the count as “a few bits a line” and treated a few bits as free. On a 512-bit line that holds 165 blocks, five bits is two blocks: an ordinary line drops from 165 to 163, and every block in the table pays its share. That alone is about 0.038 bits a block; the directory it replaces had cost 0.008, so the count is nearly all of the gap, and the forced slack lines the rest.
The directory it replaced cost less. One entry of 64 mark bits and a block number for every 64 lines is about 81 bits for 64 lines, 1.3 bits a line, a quarter of what the count costs. It is the lesson a code that has to fit its worst line learned about the threshold values themselves: a field every line must carry is paid for by every line. Storing the count in every line is the price of being able to correct a guess from the line itself, and it is four times the price of the marks the guess was meant to make unnecessary.
Anything placed by the data must be looked up
The proposal asked whether a layout chosen by its own data can be found by a lookup that knows only the data’s position. The measurement says it can, at a price, and that on this table the price is larger than anything the layout could earn. The guess finds every line within two reads and needs no structure outside the line, which is what was asked. It costs four tenths of a line on average because the data moved the lines by more than a guess can absorb, and the same data, varying between groups, made any fixed budget wrong in one direction or the other.
The deeper reason is the size of the prize. At room for the mean the table’s walks are short, a few hundredths of a line, because the room the lines lend sized lines so that most surplus is absorbed at once. The queue’s placement improved a quantity that was already small. Positions confined to one line made arithmetic addressing the point of this filter, and it is worth what it saves: every design that keeps a block’s line computable from its number reads its table line in one go. A design that gives that up for two hundredths of a line has to find the line again for less than two hundredths, and nothing measured here, in cache or out of it, does.
The same arithmetic applies wherever data-dependent placement meets a lookup that must find it. A block the lookup can work out built this filter on the same principle: a key’s second block was chosen by a threshold the lookup could compute, because a choice the lookup cannot work out is paid for at every lookup — there, as a doubled false-positive rate from reading both blocks. A layout chosen by the data needs either an index to the choices or a search that recovers them, and the gain from the choices has to exceed the price of whichever the lookup pays. When the gain is a refinement of something already close to optimal, it rarely does.
What the comparison assumes
Room for the mean. Every table here is sized at room for the mean number of closed blocks, where walks are short. At less room the fixed spacing’s walks grow fast, and the gain a placement by the queue can earn grows with them; the comparison was not made there. The lines-against-bits plate would look different, and the conclusion might too.
A line is a line. Every read is charged one line, whether it is the guessed line, the corrected one or the next line of a walk. On hardware that fetches pairs of adjacent lines, a wrong guess one line early often costs nothing extra, since the corrected line is the one already fetched. That would cut the guess’s price, and it was not modelled.
Uniform lookups. Absent keys are drawn uniformly, so every block is asked equally often. The guess is right more often at the start of a group, so a workload that favoured early blocks would see fewer wrong guesses.
One threshold, one room for the slack. The slack lines carry one deviation of extra room throughout. A slack line with two deviations holds 149 blocks, sixteen fewer than ordinary, which doubles the shift per slack line and would make the guess worse.
Still open: room below the mean
The budget lost because the walks it competes on were a few hundredths of a line, and finding a line it placed cost four tenths. Sized below the mean, the trade changes. At half a deviation below the mean, slack every eight lines with one deviation reads 4.17 lines a lookup and walks up to 432 lines, and slack every four with two deviations reads 2.23, while slack placed freely by the queue reads 2.06 at 3.118 bits with no walk over sixteen lines. There the queue’s placement saves nearly a fifth of a line, not two hundredths, and a guess costing four tenths is within reach of it.
The measurement that follows sizes the lines at half a deviation and a full deviation below the mean, gives each group a budget at the share the free placement chooses there, about 54% of its lines at half a deviation below, and charges every lookup its guess, its correction and its walk, against fixed spacing at the same bits. The prediction is that at half a deviation below, a budget of 35 slack lines a group reads under the best fixed spacing’s 2.23 lines at the same bits, because the walks it shortens are now worth more than the guesses it gets wrong. It could fail on the guess itself: with more than half the lines slack, a block deep in its group could sit more than a line’s worth of blocks from where the arithmetic puts it, so a wrong guess would cost two extra reads rather than one. The question is whether there is any room at which a layout chosen by its own data earns more than it costs to find, or whether arithmetic addressing is worth more than any placement the data can choose.
Named alongside this one
Essays reaching for the same objects. Nobody chose these; they are what the concept index makes visible.
- A reserve sized for the spill blocked filter · cache line · design parameter · prediction · threshold · variance
- An offset that only has to reach its neighbours blocked filter · cache line · design parameter · prediction · rank · 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
The objects this essay names
Each one links to every other essay that touches it.
Blocked filterCache lineDesign parameterPredictionRankThresholdVariance