The thread: Measured, not assumed — page 8
The record measured where it would run
A table of every pair selection sort has compared saves half its comparisons at 1,024 keys, and priced in word operations it was the better record at every size. Replayed through a 32 KB cache it misses 477,824 times to save 258,290 comparisons — nearly two misses for every comparison it removes — while a cache of 1,024 pairs misses 192. The table's size is not the problem. Its layout is: it looks up and writes each question at [key][minimum], a new row every time. Indexed by the ordered pair instead, the same bits miss 3,079 times, and that repair works only for a sort whose smaller operand stays put.
The floorsThe repeats a context cannot see past
Sorting rotations by their first k characters stops losing to the full Burrows–Wheeler transform at four or five characters on four sources and at about ten on a corpus of technical writing. The count proposed to explain the exception — how much a context spanning a word boundary says about the letter before it — cannot be read off its own estimate, which falls on words drawn independently where there is nothing to find. Measured against each text's own shuffled twin, the information the word order carries is real, but it has all arrived by four or five characters, and at eight, twelve and sixteen the two corpora are indistinguishable. What does separate them is repetition. Stream by stream, the share of positions inside a repeated sixteen-character string predicts the technical corpus's loss with a correlation of 0.98.
One pass, and no roomThe slope the slow counter already shows
A burst detector built from a fast and a slow decayed counter reads a steady rise in its background as an offset in their difference, β(R − 1)H/ln 2, and alarms on it. Every repair so far waited the offset out. This one subtracts it: the slow counter's own change over one slow half-life is a reading of the slope, and the offset follows from it. At R = 16 the corrected detector alarms on 5.5% to 7.8% of readings on rises that make the held scale alarm on 11% to 63%, and it costs a burst at most 3.7 seconds of detection. The estimate has to be quick: four times slower, it has recovered only 71% of the offset when alarms start to count.
The data that is not a numberThe shape of a real history's depth
Four essays here are about capping how far an extraction follows a chain of copies, and every number in them came from a generated collection. Here is the depth histogram of a real version history, which is a bell, and of twelve unrelated essays, which is nearly the same bell.
Two parametersA placement after the traffic moved
Four landmarks fitted to twenty queries that all end at one cell expand two thirds of the corners' cells there. Move the destination ten cells and the advantage is gone; move it thirty and the fitted placement expands nearly twice the corners' cells. Choosing again costs 317,000 cells of search — the saving of 8,600 queries — so on streams whose destination drifts, a policy that refits on a counter never beats fitting once and keeping the result, and past a drift of about ten cells nothing fitted beats the corners.
When it does not fitA reach that follows the stream
A full B+-tree leaf that passes keys along its siblings wants a short reach on random insertion and the whole parent on a nearly ordered stream, and a tree is never told which it is receiving. Let the reach double after every 64 overflows whose walks averaged two siblings or less and halve otherwise, and it finds the whole parent on every ordered stream. On random keys it lands on the fixed reaches' own frontier. On a stream that turns from random to ordered halfway it beats every fixed reach, by 57 leaves at the same writes. It notices a turn to random in 62 insertions and a turn to order in 779. Below a target of 1.75 siblings it thrashes on ordered keys.
When the algorithm flips a coinThe day a filter cannot grow
A fingerprint table dies when its quotient reaches its shortest fingerprint, and a filter cannot lengthen a fingerprint because it does not keep its keys. The store it filters does. Rebuilt from that store whenever its own count says its rate has passed 1%, a table grown a thousandfold never exceeds 1.05% and ends holding exactly what a reserve of ten bits holds — 18.9 bits a key — having read the store 1.34 times over. The reserve paid its bits early: 34.8 a key at four times the forecast, where the rebuilt table held 18.4. Which one is cheaper depends on whether the growth arrives.
CountingThe digit a pass chooses for itself
A radix sort's digit width trades passes against the streams each pass scatters into, and the best width depends on the keys and the cache together: 8 bits for uniform keys through 32 KB, 11 through 256 KB, 16 for keys with few distinct values. A digit widened because the previous pass's counts were concentrated cannot find it, since in a least-significant-first sort one digit's counts say nothing about the next. One read that counts every byte at once, and a sample to size each field, can. Charged for both, the resulting plan is never worse than 1.23 times the best fixed width on any keys or cache measured. The best single fixed width reaches 1.50, and 11 bits reaches 3.61.
The floorsThe deepening the sort was already doing
A sort of rotations by their first k characters loses to the full Burrows–Wheeler transform where a longer string repeats, and a sort deepened only inside the ranges where contexts repeat was proposed to recover those bits at a fraction of the transform's reading. It recovers the bits: on sixteen streams every one lands within 0.006 bits a symbol of the transform, and the most repetitive goes from 0.129 bits worse to 0.001. It reads more characters than the transform, not fewer — 74.5 a symbol against 69.4 on technical writing — because a comparison sort of rotations already reads deep only where rotations agree. The transform was the adaptive sort. The characters a sort by k characters saves are exactly the ones the repeats needed.
One pass, and no roomThe rise the correction kept subtracting
A burst detector that subtracts a rising background's offset, read off its own slow counter, goes on subtracting it after the rise has stopped. The prediction was a deficit for about one slow half-life that would cost bursts of 300 arrivals. Measured, the deficit is deeper and longer: down to 1.46 spreads below zero, below half a spread for seventeen minutes after a 40% rise. Bursts of 300 are never missed. What the deficit costs is small bursts — 30 arrivals caught 27% of the time where the rise saw 77% — and a fifth of a large burst's visible time.
What is taught wronglyThe measure that cannot see the alphabet
Take a Fibonacci word of 4,181 characters and transform it with a before b — six runs. Transform the same word with b before a — nineteen. The parse gives eighteen phrases either way, and the gap between the two run counts grows with every word in the family.
StructuresOne revision, one level
The cap ladder assumed depth is generations of copying. On a real file it is exactly that — one more revision, one more level, nine times running — plus eight levels the first revision already had before any history existed.
The data that is not a numberThe cell nobody filled
Every structure here was measured either on one long repetitive text or on prose cut into short documents. The collection that is both is a two-by-two with one empty corner, and what is in it is not the product of its margins.
Two parametersA refit that changes one landmark
Choosing four landmarks again after traffic moves costs hundreds of thousands of cells of search, and on drifting streams it never paid. Keeping three and re-choosing the fourth costs a fifth as much — 0.19 of a full selection, not the twelfth the earlier page guessed. On drifting streams, refitting on the counter goes from a loss of up to 13% to within 2% of fitting once, and it wins where the destination moves six cells. When the destination jumps, it is the cheapest policy measured, 12% under the corners at one jump in 10,000 queries — unless the jumps come as often as one in 2,500.
When the algorithm flips a coinA penalty set by the block
A blocked Bloom filter pays a penalty for its uneven block loads, and a threshold that lets a lookup work out its block repays about a third of it — measured on 2,048 keys, with a prediction that larger filters would widen the gain. From 2,048 keys to 131,072 nothing moves: one block holds 0.086% to 0.090% against a computed 0.086%, and the threshold design 0.060% to 0.065%. The busiest block grows and the rate does not follow it. What sets both the penalty and the repair is the keys a block holds. A threshold turns out to be worth one doubling of the block's width, and its advantage shrinks from 40% at sixteen keys a block to between 5% and 13% at 128.
When it does not fitThe small levels' share of a range filter
Prefix filters on a four-level store were proposed a prefix length each, on the reasoning that one length is a compromise between levels whose densities differ 43-fold. Each level does want its own length, 18 to 22 bits, and that recovers a quarter of the gap to a perfect range filter. The gap is mostly not about length. Three fifths of it is false positives. Moving filter bits from the largest level to the small ones — 12, 12, 8 and 3 bits a key instead of 5 each — recovers more than half of it at the same memory, and matches one shared length given twice the memory.
CountingA record the size of a pass's minima
Selection sort's table of every pair it has compared is 256 KB at 1,024 keys, and indexed by the ordered pair it lives almost entirely in the rows of the current minima. Keep only those rows — a ring of r rows, the least recently used given up — and 12 rows, 3 KB, catch 99% of the comparisons the whole table skips, with no misses beyond the first touch of each row. The ring beats the cache of 1,024 pairs on both axes at once. The rows it needs grow with the logarithm of the input, a few more than the minima one pass passes through, and which row it gives up matters as much as how many it has.
The floorsThe order the column cannot see
A sort of rotations by their first four characters leaves ranges that agree on those four, and the full Burrows–Wheeler transform reads deeper to order them. Given a budget of characters below the transform's, spending it on the ranges whose rotations are preceded by the most different characters was predicted to reach within a hundredth of a bit at two thirds of the transform's reading — and spending it on the longest agreements, as the transform does, to waste it. The price was impossible: the four-character sort alone reads 76% of what the transform reads. The ranking was right on average, and right for a reason that makes the budget unnecessary: a range whose rotations are all preceded by one character writes the same run into the output in any order. Skipping every such range writes the transform's column exactly, on all sixteen streams, and reads 11% less on technical writing — up to 19% on the stream with the longest repeats.
One pass, and no roomA share of a list of equals
Estimating the third frequency moment by finding the heavy keys first and sampling the rest works best with one counted candidate on steep streams and sixteen at Zipf 0.5, and a system that does not know its stream's skew has to pick. Keeping a long list and counting a candidate only if it holds a stated share of the list's own moment was predicted to come within a few per cent of the best fixed list on every exponent. The share does choose: at 3% it keeps one candidate at Zipf 2, three at Zipf 1, five at Zipf 0.5. But a list the stream shortens is not a short list. Its sixty-four candidates cost 192 words on every stream, four times the whole of the best estimator on the steep ones. On a flat stream every candidate is a near-equal share of a list of equals, and no share can tell that none of them is heavy. No list length and share comes within 10% everywhere; at Zipf 0.5 alone, the chosen list beats every fixed one.
What is taught wronglyThe threshold that reaches zero
At q = 5 and four errors on a twenty-four-character pattern the filter demands zero shared q-grams, proposes all 2,977 windows, and computes 986,266 table cells where filling the whole table would have cost 96,000. The failure is arithmetic and is knowable before a character is read.
What is taught wronglyThe deepest text is punctuation
Eight source files reach depth 78 in a parse, on a collection with no version history in it at all. The positions between depth 20 and depth 72 are the same 48 characters at every level, and every one of them is a dash in a comment separator.
The data that is not a numberWhat repetition is worth once the logarithm is gone
On prose, nearly three quarters of the fall in phrases per character with size is arithmetic that any text pays. On a collection built of copies it is a fifth, and what is left is a factor of three that is genuinely the arrangement.
Two parametersThe candidates near where the queries end
Re-choosing one landmark after the traffic moves tried every candidate as the replacement, and most of them could not win. Tried only on the four candidates nearest the new destination, the refit costs 0.085 of a full selection — the twelfth an earlier page guessed — against 0.236, and its placements serve fresh queries within 3% as well. Where the full search's winner lies further away, the refit was barely worth making. A refit that cheap still cannot follow a destination that jumps every 2,500 queries; what holds the counter back was never the refit's price.
When the algorithm flips a coinThe bits a second threshold costs
A blocked Bloom filter whose first block carries a threshold was proposed a second threshold on each key's second block, with a third block for keys both refuse. It does what it was meant to: at 512-bit blocks it removes nearly a third of the load spread the first threshold left. And the rate does not fall — 0.066% against 0.062% — because the second table, paid for in blocks, raises the rate the filter would have with no spread at all by more than the narrower spread saves. The threshold was stored in more bits than it needs: at four to six bits, one threshold beats the eight-bit design by about a tenth on one run, and a second threshold of the best width ties it at 512-bit blocks.
CountingA record of stretches, not pairs
Selection sort asks many of its comparisons again, and a record of past answers can skip them. A table of every pair skips them all in 256 KB at 1,024 keys, and a ring of the recent minima's rows in 3 KB. The questions a pass repeats have more structure than rows record: each minimum of the previous pass was compared with one contiguous stretch of positions. Kept as a list of stretches — each minimum's position, where its stretch began, and where the key that beat it stood — the previous pass's chain answers 99.3% of what the table would, in 312 bytes. The failure predicted for it, a key the swap moves into a stretch, costs 0.04%. What the chain cannot do is stay small on every input: on reversed keys it needs a link for every key.
When it does not fitThe 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.
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.