The thread: Measured, not assumed — page 9
The resolution a range filter can afford
A prefix filter on each level of a log-structured store answers a range by asking one question for every prefix the range touches, and each can be wrong. A filter holding prefixes at every length from 16 to 24 bits could ask each range at the resolution it needs, and was proposed as the repair. At the store's five bits a key it costs 5.69 transfers a range query where one length a level costs 4.32, because a short range is asked only at the finest length, and that filter now holds a fraction of the memory. Asked at every length it recovers most of that, and seems to overtake the single length at twelve bits a key — but only a single length chosen for five bits. Chosen again for each memory, one length a level beats every multi-resolution design at every memory measured, because the resolution a level can afford is itself set by its memory.
The floorsThe runs a short list cannot have
A merge whose comparator can say 'equal' meets the counting floor on lists of repeated values, but it takes the gain only when one list's head happens to meet an equal head in the other. Comparing keys inside a list would find runs of equal keys on purpose, and was predicted to leave the worst case alone and help a great deal on average when the values are few. Solved exactly at four keys a list, it leaves the worst case alone and helps by under a hundredth of a comparison: a list of four has no run worth finding, and an equal answer already places two keys at once. On long lists the same idea, galloping over each run before comparing across again, does pay — a twenty-sixth of the textbook merge's comparisons with one value at 1,024 keys a list — and at every length it stops paying at the same place: when a value's run averages fewer than about thirty-two keys a list.
One pass, and no roomA list that gives back its places
An estimator of the third frequency moment keeps a list of candidate heavy keys beside a Count-Sketch and samples the rest, and cutting a long list at the end of the pass to the candidates that hold a share of its moment picked the right keys and paid for the whole list. Dropping a candidate during the pass, as soon as it falls below that share, was predicted to make the list's memory follow the stream: under four candidates on steep streams, within a fifth of the best fixed list, and about ten on Zipf 0.5 with most of the earlier win kept. The list ends the pass the right length — three candidates on Zipf 1 — but its memory is its peak, and the peak is set by the twenty-fifth arrival, before any key has stood out: nineteen candidates on Zipf 1, and on flatter streams the most a share θ allows, one over θ. Charged its peak, it beats the end-of-pass cut on every stream from Zipf 0.75 up, 208 words against 364 at Zipf 1, and never reaches the best fixed list, 159.
What the libraries doThe cap that would ship
The published sweep put the knee at four to eight. On four real collections it is at nine to twelve, a cap of one costs forty-eight times the free parse rather than twenty-one, and the number a system should actually set is none of those.
The data that is not a numberThe array is the length distribution
The document array holds each document once per character it contributed, so its symbol distribution is the collection's length distribution exactly. On equal-length documents its entropy is log d and no coding saves anything.
Two parametersStarting from the corners
A landmark search that refits one landmark when its traffic moves lost to the fixed corners when the destination jumped often, and the accounting blamed the one full selection every refitting policy makes at the start. Starting from the corners instead, and never selecting in full, closes 82% of that gap at one jump in 2,500 queries and is the cheapest policy of all at one in 5,000. It gives the full selection back its advantage when jumps are rare, and on traffic that drifts a step at a time it gives up fitting altogether. Its counter fires when the cost rises, and from the corners concentrated traffic raises nothing: the corners are no worse for it, only no better.
When the algorithm flips a coinA threshold knows only its own block
A blocked Bloom filter that gives each block a threshold on a hash of the key lets a lookup work out which of two blocks a key went to, and it spends a small table to do it. Sharing one threshold among a group of blocks would shrink the table, and was proposed as the next saving. It is a loss at every group size. With one four-bit threshold a block, 512-bit blocks reach a false-positive rate of 0.061%; shared by a pair, 0.071%; shared by sixteen, 0.100%, worse than no threshold at all. Neighbouring blocks fill at unrelated moments, so a shared threshold closes when the first of its group does, and every key it turns away lands in a second block chosen at random.
CountingTwo swaps a pass, and the stretches hold
Bidirectional selection sort finds the smallest and the largest key in one scan and places both, so a record of its past answers has to keep two chains, and each pass makes two swaps that land where the other chain reaches. The prediction was that the second swap would break stretches at a rate of whole per cent. It does not. Each chain answers its own side's repeats as the one-sided chain does — 99.1% and 99.2% at 1,024 keys — and a swap spoils about a tenth of a question whichever sort makes it, so the broken share falls as 1/n for both. What the second chain changes is the input that makes a record long: sorted keys, which the one-sided sort never repeats a question on, cost the two-ended record a link a key.
When it does not fitOne length for the gaps and the clusters
On uniform keys one prefix length a level, chosen for its memory, beat a filter holding every length from 12 to 24 bits. Clustering the keys was predicted to reverse that, because coarse prefixes between clusters are empty and a coarse filter can then say no to a long range in one question. Clustering alone does not: whether ranges fall in the gaps or at the keys, one length re-chosen for that workload still wins, since it moves coarse for the gaps and fine for the keys. The multi-resolution filter wins only where a clustered store is asked both — by 0.17 transfers a query at ten bits a key on sixteen clusters — and it wins on short ranges inside the clusters, not on long ones between them.
The floorsA merge that decides per run whether to gallop
Merging two sorted lists of repeated values, a merge that gallops along every equal run beats the textbook merge while the runs average more than about thirty keys a list and loses below, a rule about the whole input. A merge that learns the runs as it goes was predicted to match the better of the two on uniform values and beat both on skewed ones. The proposal's rule — gallop when the last few runs averaged long — cannot learn a run that has not ended: at one, two or four values it walks every key. Timsort's own rule, applied to equal answers — walk until a bar of consecutive equal answers, then gallop, the bar moving by one as galloping pays or fails — does what was predicted. On uniform values it stays within a hundredth of a comparison a key of the better merge; under Zipf 1, at 4,096 keys a list and 1,024 values, it makes 0.447 comparisons a key against 0.595 walking and 0.594 galloping, a quarter under both.
One pass, and no roomA check as slow as what it checks
A burst detector that subtracts a rising background's offset goes on subtracting it after the rise ends, and loses small bursts in the trough that opens. Capping the subtraction by what the difference itself shows, averaged over one slow half-life, was predicted to close the trough to under half a spread. It lifts it from 1.46 spreads to 1.24, because that average is as late as the estimate it checks. Averaged over a quarter of the time it lifts it to 0.70 and catches small bursts in the trough more often than any other design but the one that alarms on a fifth of its readings. Neither cap helps after a large burst, which every slope correction reads as a rise.
What is taught wronglyWhat the approximation gives up
Compared at every one of the 3,736 decisions a search could ask about, the published shift rules and the exact ones agree at all of them on a set of 128 patterns. At two patterns they differ at five of 84, by up to four positions — and the run reads 6.3% more characters.
The index that replaces the textThe half that is never asked where
A bidirectional index is two indexes and one interval. One of them is asked for ranks several hundred times a search and for a position never — and the parts that answer "where" are two of the five it is made of.
Two parametersA refit priced before it is made
A landmark placement that starts at a maze's corners and refits one landmark when a counter sees recent queries getting dearer closed most of its gap on traffic that jumps — and on traffic that drifts it never fired, because from the corners concentrated traffic raises no cost. The chance it missed is cost that could fall. Pricing that chance directly — the current placement on the last twenty queries against four nearby candidates, every two thousand queries, refitting when the estimated saving pays for the refit — costs 120.5 cells a query at one jump in 2,500 against the counter's 128.9 and the corners' 126.8, and 107.4 on a slow drift against 103.3 for a full selection fitted once. It fails where jumps come every thousand queries, and on one stream it stops firing after its placement has aged.
CountingA run answers what nobody asked
Bidirectional selection sort remembers its past comparisons in two chains, and on sorted or reversed keys the chains need a link for every key. Keeping instead what is known about adjacent positions — which of each neighbouring pair is larger, forgotten when a swap moves either — turns a monotone stretch into a single run with a direction. On reversed keys one run replaces 1,025 links. On sorted keys the run does more than remember: it answers 260,610 questions the sort had never asked, from two keys' positions alone, and the sort makes 2,045 comparisons at 1,024 keys where the chains leave 263,167. On organ-pipe keys it cuts a quarter of the comparisons; on random keys, nothing.
When the algorithm flips a coinTwo hashes that shared their low bits
Two pages on blocked Bloom filters with thresholds each recorded an instability they could not explain: a false-positive rate that collapsed on one seed at 256-bit blocks, and a pair of four-bit thresholds measuring 0.169% where its neighbours measured 0.08%. Both came from how a hash was brought into range. Every filter took its block and its ordering value as a modulo of a multiply-shift hash, and the low bits of such a hash depend only on the low bits of the key, so the two values were dependent whenever the block count had a factor of two to spare. At 992 blocks the threshold filter measures anything from 0.185% to 0.645%; read from the hash's top bits, 0.126% to 0.133%.
The data that is not a numberThe part every saving left alone
A bidirectional index was made smaller three times, one part at a time, and every change left the largest part untouched: the wavelet trees, whose levels are two thirds of the structure. Coding every level in blocks of 63 bits — how many ones a block holds and which arrangement it is — takes that protein index from 210,934 bits to 167,707, a larger step than the two before it together. On English words it takes the same structure from 210,872 bits to 76,054, and an ordered tree, coded, ends up smaller than an unordered Huffman tree, plain. Every rank then reads 1.4 times as many entries, and a smaller superblock buys the reads back for part of the bits.
When it does not fitTwo lengths that do the work of eleven
On keys that cluster, asked both between the clusters and at them, a prefix filter holding every length from 12 to 24 bits beat one length a level by 0.17 transfers a range query, and a pair of lengths — one coarse, one fine — was proposed to recover nearly all of that. It recovers more than all of it: 0.23 transfers at ten bits a key, and at four bits, where the eleven lengths lose to one, the pair still saves 0.18. The coarse filter takes under 2% of a level's memory, and the eleven-length filter was leaving its finest length as little as 14% and cannot give it more without starving the lengths its descent passes through. The store predicted to defeat a pair, with gaps at two scales, does not. The saving is bought in questions: the pair asks its filters more often than the eleven lengths do.
The floorsThe question asked at every split
A range of rotations preceded throughout by one character writes the same run into the Burrows–Wheeler column in any order, and a sort that asked that once, of the ranges four characters leave, read 11% less than the transform. Asked at every split of a sort that partitions on one character at a time, it was predicted to read a fifth less on technical writing and an eighth less on the essays. It reads four fifths less — and nearly all of that is the change of sort, which the prediction expected to cost reading rather than save it. The question's own share, measured against the same sort without it, is 29% on technical writing and 14% on the essays.
One pass, and no roomA variance that had seen one hash
A budget of 40,960 bits split between a HyperLogLog and a bottom-k sample answers an intersection best by weighting the two estimates by their variances, except in one corner: a sample of 160 hashes asked about sets sharing one key in a thousand, where the weighting's worst regret was 4.46. The sample was said to see nothing, report a variance of nought and be believed completely. Its variance was never nought — it was taken at one shared hash whenever none was seen — and it was believed too little, not too much. Half a shared hash in the variance gives the sample more weight and cuts the corner's regret to 3.08, not under the 2.5 predicted; half a hash in the estimate too gives 3.74 there, and 1.61 at five eighths of the budget in registers, the lowest worst regret any split and rule has reached. No weighting measured gets the corner under the sample's own 2.30: 160 hashes expecting a sixth of a shared one is a limit, not a formula.
What is taught wronglyThe operations a candidate count leaves out
The grid examines 33 candidates where the scan examines 4,355 — a factor of 132. Counted in the operations each of them performs, the same query is 2,471 against 4,355, and the factor is 1.8.
The other axisAn index that cannot locate
Take an FM-index, remove the sampled positions and the bit vector marking them, and refuse every request for a position. What is left still counts, still extends intervals, still runs a whole search — and is a third smaller.
When the algorithm flips a coinA code that has to fit its worst line
A blocked Bloom filter's four-bit thresholds are far from uniform: two blocks in five never close, and the rest crowd into the upper values, an entropy of 2.4 to 2.8 bits. A table coded from that distribution was predicted to match the four-bit rate on under three bits a block. Packed end to end it does, at 2.65 to 3.03 bits, and it costs every lookup a second read for the index. Packed a fixed number to a cache line it needs no index, but every line must hold its worst run of long code words, which costs 3.19 bits at 64-bit blocks and eighty-three code words decoded a lookup. Where the table is large enough for the saving to show, a plain three-bit table gets part of it with none of the costs.
Two parametersA horizon the stream can supply
A watch that refits a landmark placement when an estimated saving pays lost where traffic jumped every thousand queries, because its estimate assumed each saving would last a whole window. The horizon proposed to correct it, learned from the intervals between the watch's own refits, is the window every time: the watch looks once a window, so its refits are never closer together than one. A horizon learned from the traffic instead — how long it stays within ten cells of one destination — is safe on every stream and saves 3.4% at one jump in 2,500. At one in 1,000 it reaches 150.7 cells a query against the corners' 142.7, and a horizon read from the future only ties them. At that pace the looking costs what the refits save.
The data that is not a numberSix bits a class
Coding a bidirectional index's wavelet-tree levels in blocks left a part that did not shrink: six bits a block for the block's class, its count of ones, which on English words became a quarter of the levels. Coding the classes by their runs was predicted to halve them. It takes a third off, 0.480 bits a character to 0.323, because two thirds of the blocks are uniform but they come in stretches of about two. One entropy code over the classes does about as well, and on the repetitive collection better. Runs also cut the reads a rank makes by 15%. On random letters runs make the classes larger, and the pointer a variable-length stream needs at every superblock eats most of what an entropy code saves.
CountingA pass repaid by the scans after it
Give the two-ended selection sort one pass between neighbours before it starts, n − 1 comparisons, and sorted and reversed keys cost exactly that pass. The pass was predicted to be repaid in the first scan, and almost none of it is. On organ-pipe keys it saves 43,776 comparisons at 1,024 keys, 97% of them in the scans after the first. On random keys it costs 236, not 1,023, because later scans use the short runs it found. It breaks even on runs of four keys at every size — and the sort stays quadratic on every input that is not one run.
When it does not fitThe filter rebuilt with every write
A log-structured store chooses a range filter's two prefix lengths when it writes a level, and a filling store's small levels hold only the keys that arrived last. Choosing at every write was predicted to keep the lead a pair chosen once on the full store has, except where keys arrive a cluster at a time and a small level's choice goes stale when the next batch lands elsewhere. It cannot go stale: a levelled store changes a level's keys only by rewriting it, and rewriting it rebuilds the filter. Choosing at every write and choosing once then differ by at most 2.3% of what a perfect filter saves, on both arrival orders, at two bits a key and at ten, and choosing costs twenty-eight times the hashing. What the order of arrival changes is the store: filled a cluster at a time, its small levels hold one cluster each, and at two bits a key the same filter captures 94% of a perfect filter's saving against 68% shuffled.
The floorsA sort that infers the order
A radix quicksort that stops at every group of rotations preceded by one character reads about fourteen characters of a text for every symbol of its Burrows–Wheeler transform. Induced sorting, which reads the order of a third of the suffixes and derives the rest, was predicted to read three. It reads 6.1 on all sixteen streams, within 0.14 of each other, and the same at every length from a thousand characters to thirty-two thousand. The question the quicksort asks saves it nothing, as predicted, for a reason the prediction did not give: its last two passes read the transform's column itself, one character for every rotation, in order to sort.
What is taught wronglyThe cap that binds on one text and not another
A periodic text looks like the one made of chains and pays 1.11 times the phrases for a cap of four. A text that repeats itself pays 2.96. The guess is backwards, and the reason is that depth measures nesting rather than repetition.
What is taught wronglyA sixth of what, exactly
The saving from a counting-only reverse half is 30.5% at one sampled position in four and 14.0% at one in a hundred and twenty-eight. A number quoted without its sampling rate is a number about a setting somebody chose.