When the algorithm flips a coin

A guess that costs more than the walk

A blocked filter's threshold table placed its slack lines where the queue of carried values was long, and read a directory of marks to find a block's line; read from memory, the directory cost a line and the design lost to every other. Giving each group of 64 lines a fixed budget of slack lines, placed where the queue asks, makes a group's first block arithmetic again, and a lookup can guess its line as if every earlier line were ordinary. The guess is wrong for 41% of lookups at the queue's own budget of fifteen, not a third of a minority; the count each line must carry costs 0.037 bits a block, not under a hundredth; and the queue's demand varies so much between groups that the budget refuses it six lines a group, so walks run to 29 lines again. The design reads 2.45 lines a lookup where fixed spacing reads 2.03 at the same bits, because everything the queue's placement saves is a few thousandths of a line of walking.

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 BB 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 ii computes its group, ii 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 ii 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, and the fixed spacing, which reaches 2.03 lines at the same bits; no budget or threshold measured gets within a fifth of a line of itSplit threshold tables over 124,900 blocks, two filters each: lines a lookup against bits a block for slack lines placed by the queue (Q = 8) on a budget of B lines in every group of 64, B = 10, 13, 15, 17, 20, 24: 10: 3.170 bits, 2.443 lines; 13: 3.175 bits, 2.507 lines; 15: 3.187 bits, 2.450 lines; 17: 3.195 bits, 2.409 lines; 20: 3.194 bits, 2.423 lines; 24: 3.208 bits, 2.434 lines; at Q = 4 and 16 with B = 15: 3.188 bits, 2.596 lines and 3.186 bits, 2.286 lines. Fixed spacing every 4, 8 or 16 lines with one or two deviations: 3.118, 2.132; 3.123, 2.103; 3.132, 2.099; 3.141, 2.062; 3.142, 2.054; 3.180, 2.032. The free placement: 3.150 bits, 2.027 lines with its directory resident, 3.027 with its read charged a line.22.252.502.7533.123.143.163.183.20bits a blocklines a lookupfree, directory readbudgets, Q = 8Q = 4 and 16, B = 15fixed spacingfree, resident124,900 blocks, 16 bits a keylines a lookup
Fig. 1 Lines a lookup against bits a block. Slack placed by the queue at Q = 8 on budgets of 10, 13, 15, 17, 20 and 24 slack lines a group of 64: 3.170 bits for 2.443 lines, 3.175 for 2.508, 3.187 for 2.450, 3.195 for 2.409, 3.194 for 2.423 and 3.208 for 2.434. At a budget of 15, Q = 4 gives 3.188 and 2.596, Q = 16 gives 3.186 and 2.286. Fixed spacing every 4, 8 or 16 lines with one or two deviations of extra room runs from 3.118 bits for 2.132 lines to 3.180 for 2.032. The free placement: 3.150 bits for 2.027 lines with its directory in cache, 3.027 lines with the directory’s read charged.

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.041Lines a lookup split into the two every lookup reads (its filter block and its table line), the extra reads to find the table line, and the walk to a carried value or the overflow. fixed every 4, two deviations: 2 + 0.000 + 0.032 = 2.032; free, directory resident: 2 + 0.000 + 0.027 = 2.027; free, directory read: 2 + 1.000 + 0.027 = 3.027; budget of 10: 2 + 0.368 + 0.075 = 2.443; budget of 15: 2 + 0.408 + 0.041 = 2.450; budget of 24: 2 + 0.411 + 0.023 = 2.434.block and linefinding the linewalklines a lookup (axis from 1.5)fixed every 4, two deviations2.032free, directory resident2.027free, directory read3.027budget of 102.443budget of 152.450budget of 242.434124,900 blockslines a lookup
Fig. 2 Lines a lookup, part by part: the filter block and the table line every lookup reads, the extra reads to find the table line, and the walk to a carried value or the overflow. Fixed every four lines, two deviations: 2 + 0 + 0.032 = 2.032. The free placement with its directory in cache: 2 + 0 + 0.027 = 2.027; with the directory’s read charged: 2 + 1 + 0.027 = 3.027. Budgets of 10, 15 and 24: 2 + 0.37 + 0.07, 2 + 0.41 + 0.04 and 2 + 0.41 + 0.03.

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 itShare of lookups whose first guess, the line their block would occupy if every earlier line of its group were ordinary, is not their block's line, with the slack lines' share of all lines: Q = 8, B = 10: wrong 37%, slack 16%; Q = 8, B = 13: wrong 44%, slack 21%; Q = 8, B = 15: wrong 41%, slack 24%; Q = 8, B = 17: wrong 37%, slack 27%; Q = 8, B = 20: wrong 40%, slack 31%; Q = 8, B = 24: wrong 41%, slack 37%; Q = 4, B = 15: wrong 54%, slack 24%; Q = 16, B = 15: wrong 25%, slack 23%.guess wrongslack share of linesQ = 8, B = 1037% · 16%Q = 8, B = 1344% · 21%Q = 8, B = 1541% · 24%Q = 8, B = 1737% · 27%Q = 8, B = 2040% · 31%Q = 8, B = 2441% · 37%Q = 4, B = 1554% · 24%Q = 16, B = 1525% · 23%124,900 blocksshare of lookups
Fig. 3 Share of lookups whose first guess is not their block’s line, with the slack lines’ share of all lines. At Q = 8: budgets of 10, 13, 15, 17, 20 and 24 are wrong 37%, 44%, 41%, 37%, 40% and 41% of the time, with slack 16% to 37% of lines. At a budget of 15, Q = 4 is wrong 54% of the time and Q = 16 25%.

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 Q=16Q = 16 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 Q=4Q = 4 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 5.92 lines a group and 2.10 more are placed where it did not ask, because the queue's demand varies from group to group about the 23% it averagesFor each budget B, slack lines a filter of about 13 groups, at Q = 8: placed where the queue asked, placed at a group's end to fill the budget, and asked for by the queue but refused because the group's budget was spent. B 10: asked 121.25, forced 2.00, refused 227.50; B 13: asked 154.00, forced 5.25, refused 161.50; B 15: asked 156.75, forced 27.25, refused 77.00; B 17: asked 154.00, forced 52.75, refused 34.75; B 20: asked 156.50, forced 87.50, refused 17.50; B 24: asked 152.25, forced 140.25, refused 1.00. The free placement makes 23% of its lines slack.where the queue askedforced at the endrefusedslack lines a filterB = 10121 · 2 · 228B = 13154 · 5 · 162B = 15157 · 27 · 77B = 17154 · 53 · 35B = 20157 · 88 · 18B = 24152 · 140 · 1Q = 8, a filter of 124,900 blocksslack lines a filter
Fig. 4 For each budget, slack lines a filter of about twelve groups at Q = 8: placed where the queue asked, placed at a group’s end to fill the budget, and asked for but refused because the group’s budget was spent. Budget of 10: 121, 2 and 228. Of 13: 154, 5 and 162. Of 15: 157, 27 and 77. Of 17: 154, 53 and 35. Of 20: 157, 88 and 18. Of 24: 152, 140 and 1. The free placement makes 23% of its lines slack.

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 eightThe longest walk of a carried value, in lines, over two filters: budget of 10: 33; budget of 13: 39; budget of 15: 29; budget of 17: 36; budget of 20: 13; budget of 24: 9; free placement: 8; fixed every 4: 21; fixed every 8: 33; fixed every 16: 43. Budgets at Q = 8; fixed spacing with one deviation of extra room.longest walk, linesbudget of 1033budget of 1339budget of 1529budget of 1736budget of 2013budget of 249free placement8fixed every 421fixed every 833fixed every 1643two filters of 124,900 blockslongest walk
Fig. 5 The longest walk of a carried value, in lines, over two filters. Budgets of 10, 13, 15, 17, 20 and 24 at Q = 8: 33, 39, 29, 36, 13 and 9 lines. The free placement: 8. Fixed spacing every 4, 8 and 16 lines with one deviation: 21, 33 and 43.

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 5 bits out of each line, and the slack lines a budget forces where the queue did not ask hold fewer blocks for nothingBits a block, Q = 8, by budget: 10: 3.170 (5 bits of count a line, 163 blocks an ordinary line, 155 a slack line); 13: 3.175 (5 bits of count a line, 163 blocks an ordinary line, 155 a slack line); 15: 3.187 (5 bits of count a line, 163 blocks an ordinary line, 155 a slack line); 17: 3.195 (6 bits of count a line, 162 blocks an ordinary line, 154 a slack line); 20: 3.194 (6 bits of count a line, 163 blocks an ordinary line, 155 a slack line); 24: 3.208 (6 bits of count a line, 163 blocks an ordinary line, 155 a slack line). The free placement: 3.150 bits with its directory, 165 and 157 blocks a line.3.143.163.183.203.22101315172024slack lines budgeted a group of 64bits a blockfree placementa hundredth overbudgetedQ = 8, 124,900 blocksbits a block
Fig. 6 Bits a block at Q = 8 by budget: 10, 3.170 (five bits of count a line, 163 blocks an ordinary line, 155 a slack line); 13, 3.175; 15, 3.187; 17, 3.195 (six bits, 162 and 154); 20, 3.194; 24, 3.208. The free placement: 3.150 bits with its directory, 165 and 157 blocks a line. The faint line is a hundredth of a bit above it.

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.

The objects this essay names

Each one links to every other essay that touches it.

Blocked filterCache lineDesign parameterPredictionRankThresholdVariance