The thread: Measured, not assumed — page 10
A bit for whether it closed
Almost half of a blocked filter's threshold table says one thing: this block never closed. Store that answer as a bit a block, and a closing value only for the blocks that did, found by counting the ones before it. At 64-bit blocks the prediction was 3.1 bits a block and two cache lines. Packed end to end it lands at 3.15 bits and 2.5 lines; packed a line at a time it reads two lines and counts one word, and costs 3.64 bits, because every line must hold the most closings any line happens to draw. At 512-bit blocks, where three blocks in five close, it saves under a tenth of a bit.
The data that is not a numberA flag for the blocks that change once
A coded wavelet-tree level stores each mixed 63-bit block as the index of its arrangement, as if every arrangement were equally likely. Coding it instead as the gaps between its value changes was predicted to take a third off the offsets on English words. Alone it adds 4%: a third of the mixed blocks change value once, as predicted, but most of the rest change twenty times or more. A one-bit flag that lets each block take the shorter code takes 21% off, and the levels fall from 1.72 bits a character to 1.45. On the repetitive collection the offsets halve.
Two parametersA watch that looks less
A landmark watch that refits when an estimated saving pays loses to the plain corners when traffic jumps every thousand queries, because its looking costs more than its refits save. Using its learned horizon to look less often there — doubling the interval when the horizon falls below half of it, halving it when the horizon comes back — was predicted to tie the corners at that pace and cost nothing elsewhere. It ties nothing: 150.5 cells a query against the corners' 142.7, since the looks it skips are the looks that found the chances. And at one jump in 2,500, where the watch had won, it loses by twenty cells, because the rule cannot come back down. Halving needs a horizon as long as the stretched interval, and at 8,000 queries no stream here supplies one. A two-state rule that can come back does better and still loses at both paces. The looking was never the waste; at one jump in 1,000 there is nothing to watch for.
CountingThe runs too short to drop
A pass between neighbours leaves the two-ended selection sort a record of 674 runs on 1,024 random keys, and the scans after it use them to repay three quarters of the pass. Keeping only runs of three keys or more was predicted to cut the record by two thirds and give back under a tenth of what it repaid. It cuts the record by 63%, and gives back 69%: runs of two keys answer half of everything the record answers, because three quarters of its answers are about two neighbouring positions — the question a scan asks about the key beside the extreme it has just found. The record's cost was never in its short runs. It was in writing each run as three words: every neighbouring pair at two bits a pair is 64 words, a thirty-second of the run list, and keeps all of them.
When it does not fitOne bit a key, divided
A levelled store of a million clustered keys, each level's range filter a pair of prefix lengths chosen when the level is written, captures 68% of a perfect filter's saving at two bits a key spread evenly when its keys arrive shuffled, and 94% when they arrive a cluster at a time. The proposal was to divide the memory by what each level's filter saves per bit, and it predicted the memory would leave the small levels, whose keys the arrival order had already sorted out. It goes the other way, as it did for single prefix lengths, and much further: the small levels take twelve to sixteen bits a key, the deepest level one, and the store captures 99% of a perfect filter's saving on both orders while leaving part of the budget unspent. Divided, one bit a key on average does what four bits spread evenly cannot.
The floorsA bar that wins rarely meet
A merge of two sorted lists of repeated values saves most of a textbook merge's comparisons by galloping along a run of equal answers once a bar of them have come in a row, with the bar lowered after a gallop that pays and raised after one that does not. Timsort keeps the same kind of bar for the other kind of stretch, one list winning repeatedly, and a merge of repeated values meets both. One count and one bar for either kind was predicted to save a further tenth under Zipf 1 and change nothing on uniform values. It saves at most 1.0% under Zipf 1, costs up to 1.3% on uniform values, and two separate bars do no better. In two lists drawn from the same distribution a stretch of wins long enough to gallop over is rare: under Zipf 1 at most 18% of the shared bar's gallops are over wins, and where wins dominate the gallops, at a thousand uniform values, the runs of either kind are too short for any gallop to pay.
What is taught wronglyThe pruning that loses an occurrence
Two versions of the same lower-bound pruning, each one character away from correct. Both return only real occurrences, both return fewer of them, and no check that asks whether the answers are right can tell either from the truth.
What the libraries doThe saving, spent
A bidirectional index whose reverse half cannot locate is a sixth smaller. Give that sixth back to the half that does locate, and the same total size answers a locate five times faster.
When the algorithm flips a coinThe worst of more lines
A blocked Bloom filter's threshold table, stored as a bit for whether each block closed and a value for each block that did, packed a fixed number of blocks to a cache line, costs 3.64 bits a block at 64-bit blocks because every line must hold the most closed blocks any line draws. Sizing the line for the mean plus one standard deviation, and moving a line's excess values to a shared overflow, was predicted to cost about 3.25 bits and send under one closed lookup in a hundred to a third line. The lookups behave as predicted: 0.6% read the overflow, 2.003 lines a lookup. The bits land at 3.38, because every line must carry the offset where its moved values begin. What the measurement found instead is that the worst line is a property of how many lines there are: 3.38 bits at two thousand blocks and 3.62 at a hundred and twenty thousand, while the line sized for the usual line costs the same at every size.
The data that is not a numberThe optimum the flag took away
A bidirectional index's wavelet-tree levels were coded in blocks of 63 bits because a sweep found 63 the best length: shorter blocks pay for more classes, longer ones for offsets that approach the block's own length. Then the classes were coded as runs and each offset given a flag to choose a code of its value changes instead. Lengthening the blocks to 127 bits was predicted to save on English words and the repetitive collection and to change nothing on random letters. It saves on all four texts, and there is no best length short of 1,023 bits on three of them: English words fall from 1.431 bits a character at 63 to 1.304 at 1,023. Under the codings the optimum came from, the same levels cost 3.728 at 1,023. The flag turned a long block's offset into the cost of its change points, which no block length moves, and left the length to be set by the one thing still growing with it: the work of a rank.
When it does not fitA division chosen before the queries arrive
A levelled store's range-filter memory, divided among its levels by trying every assignment against the store's own queries, captures 99% of a perfect filter's saving on both arrival orders, with the small levels at twelve to sixteen bits a key and the deepest at one. A store writing a level cannot try every assignment, but it knows its levels' sizes, and a rule giving each level δ more bits a key for every factor of four it is smaller was predicted to match the fitted division on the shuffled store and to land near the even split's 94% on the store filled a cluster at a time. It matches the fitted division on both: 97.2% to 99.0% shuffled and 99.7% to 99.9% filled a cluster at a time from one bit a key up, with δ chosen on a sample of queries and charged on others. One δ of four, set before any query, is within a point and a half everywhere from one bit a key up. The rule fails exactly where the proposal said: a δ of six or more at one bit a key gives the deepest level nothing, and the shuffled store falls from 97.2% to 73.9%.
CountingWhat it costs to consult two bits a pair
The two-ended selection sort's record of adjacent order can be kept as two bits a neighbouring pair or as a list of runs, and the page that compared them counted both as free to read. Priced, the bits read 1.09 words a question on 1,024 random keys — under the two predicted — and a binary search of the run list takes 8.8 steps, because the pass leaves 503 runs to search. The run list was predicted to win from runs of sixteen keys; it wins only from runs of 512. Both prices are small and neither is small enough. Asked every question the sort makes, the bits spend 201 word reads for every comparison the record saves on runs of four keys, 764 at 4,096 keys, where a table of compared pairs broke even at three. The record repays its reading only on long runs, and the pass that finds them is also the cheapest place to decide whether to consult at all.
Two parametersA watch that switches itself off
A landmark watch that cannot beat the plain corners by looking less was given a switch instead: at every look it prices the corners on the same twenty queries, and when the corners would have been cheaper over its last four looks it goes back to them and stops looking for 8,000 queries. At one jump in 1,000 it works — 145.5 cells a query comparing search costs, 144.4 charging the watch for its own looking and refits, against the corners' 142.7 and the watch's 150.7. At one jump in 2,500, where watching pays, both switches give the watch's advantage away, 125.3 and 126.1 against 116.4, and the charging switch is off for 60% of the stream, as much as at the fast pace. What a look reads is the same at both paces: 12,249 cells a window at one, 11,257 at the other, with a spread of sixty thousand. The watch's value arrives in a few large looks after jumps, and four looks at any pace are mostly the others.
What is taught wronglyThe ratio that was an implementation
This collection published a factor of forty-two between two shift rules' preprocessing. Sixty-nine per cent of the denominator was a table the published rule never reads, and the numerator was a definition rather than a construction. The corrected ratio is 1.6.
The index that replaces the textEvery child at once
A bidirectional extension counts the occurrences of every symbol smaller than the one being added, and this collection did it with one rank per symbol — 139.7 operations an extension on a twenty-six-letter alphabet. One walk down the tree gives the same number.
The data that is not a numberA flag that weighs the work as well as the bits
A wavelet-tree level's mixed blocks are each coded by their arrangement's index or by the gaps between their value changes, a flag choosing the shorter, and longer blocks then save bits on every text at the price of more work a rank. Charging the flag for decoding work as well as bits was predicted to reach the same curve as shortening the block, and to beat it by no more than a hundredth of a bit a character. On English words, DNA and protein it reaches nothing below that curve. On the repetitive collection it reaches 0.156 bits a character below it: 1,023-bit blocks with a price on work cost 0.458 bits a character for less work a rank than 63-bit blocks do at 0.607. The difference is in which blocks the flag codes by their arrangement — on English words blocks that change value ninety-six times, on the repetitive collection blocks holding one short run of ones in two hundred and fifty-five bits.
When the algorithm flips a coinAn offset that only has to reach its neighbours
A blocked Bloom filter's threshold table, its cache lines sized for the mean number of closed blocks plus one standard deviation and their excess values moved to a shared overflow, cost 3.38 bits a block where 3.25 was predicted, because every line carries a nineteen-bit offset into the overflow. Grouping lines, each line's offset reaching only its group's part and each group's position held once in an array of its own, was predicted to cost 3.31 bits a block for 2.0064 lines a lookup. It costs 3.301 for 2.0060, as predicted. But the nineteen bits were mostly an offset sized to address a table of moved values, when the overflow this table has needs eleven: sized for the overflow it has, the ungrouped line costs 3.337 for no extra line at all. Grouping's further three hundredths cost a line a moved lookup, and spent on room instead, that line buys more. At equal lines a lookup the grouped table is the dearer, by a hundredth to nine hundredths of a bit.
Two parametersA switch that counts the jumps
A landmark watch whose switch read its own costs could not tell fast traffic from slow, because what a look reads has the same mean at both paces. A switch that reads the traffic instead — the mean spacing of the last ten times the destination moved more than ten cells — was predicted to reach the corners at one jump in 1,000 and keep the watch at every slower pace. It separates the paces where costs could not: 146.6 cells a query at one jump in 1,000 against the watch's 150.7, and on drifting traffic it never switches off at all. But a count of k events is a reading with a delay of k events and a noise of one part in √k, and no k has both: three stretch ends reach the corners' 142.7 at the fast pace and are off 38% of the slower stream; twenty never misfire and save nothing. And when traffic slows, the events that would show it stop arriving, so the count keeps its fast reading and the switch stays off: 135.8 cells a query on a stream that slows halfway, worse than the corners or the watch.
CountingA filter that reads the word it saves
A selection sort's record of adjacent order, two bits a neighbouring pair, costs 1.09 word reads a question and spends 201 of them for every comparison it saves on 1,024 keys in short runs, because it is asked everything and answers almost nothing. A filter bit beside each pair, set only where a run could start, was predicted to turn away three quarters of the questions and cut that price to under sixty. It turns away two thirds and cuts the price to 185. The questions it turns away were already refused in the first word, the filter is read in that same word, and one read a question is a floor no filter can go under.
When it does not fitThe sizes a store passes through
A levelled store's range-filter memory can be divided by its levels' sizes alone, a few more bits a key for every factor of four a level is smaller than the deepest, and on the full store that rule matched the division fitted to the store's own queries at every budget. Through the fill it does not. At a bit a key or less it falls up to 17 points of a perfect filter's saving behind on the shuffled store and 26 on the store filled a cluster at a time, and every large loss has the same cause: part way through the fill the deepest level is a smaller share of the store, and the rule gives it nothing.
What is taught wronglyThe occurrences a join invents
Eight documents run together hold forty-nine eight-character windows that span a join, twenty-three of which occur in no document at all. Every index built over the concatenation reports them, and five essays of this collection paid that cost silently.
What the machine doesThe count that was already there
A bit vector's rank of one is the position minus its rank of zero. Every walk down a wavelet tree computes one of them at every level, and this collection asked for the other separately for years.
The data that is not a numberA price the levels share
A bidirectional index's wavelet-tree levels code each mixed block by its arrangement or by its gaps, and a flag that charges each code for the work a rank costs inside it reached below the curve the block lengths draw on one text of four. Setting that price separately for each level of the tree was predicted to find a few hundredths of a bit on English words, where the deep levels hold runs. It finds nothing on any text: under a ten-thousandth of a bit beyond one shared price. The price a block wants is set by the text, not by the depth of the node it sits in, and every level holds a fifth of the index.
CountingA run end kept in a register
A selection sort's record of adjacent order spends about a word read on every question it is asked, and on short runs it is asked 184 questions for every comparison it saves, so no filter read in that word can make it pay. Every question starts from one of the sort's two current extremes, and what the record can say about all of them is one number: where the run from that extreme ends. Kept in a register beside each extreme and refreshed only when it changes, that number cuts the reading to a forty-fifth on 1,024 keys in runs of four, and the price of a saved comparison from 201 word reads to 4.5, where it stops growing with the input.
When it does not fitA floor under every level
A levelled store's filter memory divided by its levels' sizes lost up to 26 points of a perfect filter's saving part way through its fill, every large loss a level given no filter at all. A floor of half a bit a key under every level was predicted to close every gap above five points at one bit a key and cost nothing at two and four. It closes them: the worst gap at one bit falls from 17 points to 4 on the shuffled store and from 25 to under 1 on the clustered one, and nothing moves at two bits and up. At half a bit a key the floor is the whole budget and the rule becomes the even split, which the clustered store wants half way through and the shuffled store, at the same sizes, loses 35 points by.
When the algorithm flips a coinA reserve sized for the spill
A split threshold table gives every line the same room, the mean number of closed blocks plus some standard deviations. Giving each line room for the mean and each group of 64 lines a shared reserve at one standard deviation of the group's total was predicted to cost about 3.24 bits a block for 2.006 lines a lookup, under the best ungrouped line. The reserve it predicts holds 52 values where the group's lines spill 145: it is full in every group, the spills go on to a third line, and the table lands on the ungrouped curve. Sized for the spill instead, the reserve puts the table under that curve at every room, by two to three hundredths of a bit a block.
What is taught wronglyA schedule nobody writes down
A search scheme is valid when its searches between them cover every way the errors can fall — ten cases at two errors, enumerable in a line. A scheme missing one of them finds seven occurrences of eight, all real, at the right error counts, and reports nothing wrong.
StructuresThe tree the operation insists on
The compound walk means "everything that went left is smaller", which is true only if the leaves are in the alphabet's order. Huffman's tree is the smallest and its leaves are in frequency order, so the operation that makes a bidirectional search affordable costs the shape that makes an index small.
What the machine doesA node costs two ranks
The left child's interval is the position minus the right child's. A descent that calls rank on both children returns exactly the same symbols at twice the cost, and nothing about the answer can see it.
The data that is not a numberThe blocks the searches ask for
A flag that codes each block of an index's wavelet-tree levels as an arrangement or a gap code, charged for the work a rank does inside the block, was priced as if ranks landed on every position equally, and a price for each level found nothing that one price did not. Pattern searches do not ask evenly: on English words the busiest tenth of the blocks takes 22% of their ranks, and 35% when common patterns are asked more. Priced by the work of the ranks that actually land in each block, chosen on one sample of searches and charged on another, the flag reaches 0.11 to 0.16 bits a character below the old pricing at the same work on English, and 0.03 on the repetitive collection.