Theme

The thread: Measured, not assumed — page 12

Page 12 of 16, continuing the same thread in the same order.
00.2500.5000.7501share of the fillnewest level's reach ÷ largest level's⅛¼⅜½¾fullswitch at 0.5shuffledtwo clusters at a timeone cluster at a timefilled: no floor better · hollow: floored better, at half a bitratio of reach When it does not fit

A choice the fences cannot make

At half a bit a key a levelled store's range-filter memory has two good divisions, one for a store whose levels all meet the same queries and one for a store whose newest level meets few. A switch between them on the ratio of the newest level's reach to the largest's was predicted to land within three points of the fitted division on the shuffled store and ten on the others. It holds on the two stores it was shaped on and fails on a third filled two clusters at a time, 15.9 points behind, choosing the worse division at four checkpoints of six. At three quarters of a bit the floored division is within 1.7 points everywhere and the switch's premise is gone. Priced on a sample of queries instead, the same choice between the same two divisions stays within 3.6 points on every store at both budgets.

1.0%10.0%0.11fraction of characters changedper characterthe real runsthe real phrasesgenerated runsgenerated phrasesten revisions of one file · 24,580 characters2.32% against 3.24% What is taught wrongly

The dial that has no setting

The generator has one parameter. The real version history's run count asks it for 2.3% and its phrase count asks for 3.2% — and the reason is not that the dial is badly calibrated. Real edits average 7.3 characters a block and generated ones average 1.04.

range consideredminimum atC[at] < lonew document[476, 489)483 · document 4yesyes[476, 483)477 · document 1yesyes[476, 477)476 · document 0yesyes[478, 483)482 · document 2yesyes[478, 482)478 · document 0nono[484, 489)486 · document 3yesyes[484, 486)484 · document 0nono[487, 489)487 · document 2nono8 steps, 5 documents, and the two columns never differrows 476–489 · 8 documents8 steps Structures

A document already in the answer

The same walk, with the chain's test replaced by a lookup in the answer so far. It reports the same documents at the same cost, and two exchanged lines make it lose nine of seventeen without failing.

051015204060documents, which here is also the copy countbits a characterFM-indexrun-length indexphrase index8,192 characters throughout2665 runs down to 427 The index that replaces the text

The index that does not notice

Three compressed indexes over the same characters. One is flat at six and a half bits a character however many copies the collection holds; the other two fall by factors of five and six. At one copy the two that fall are the largest of the three.

05e+31e+41.5e+40246bits kept in the low partbits⌊log₂(n/m)⌋ = 2low partshigh vector2,049 marks in 16,385 positions1 bits between the two roundings What a bound is

The flat bottom of a shallow curve

The low width is chosen as the floor of log of the universe over the count. Rounding it up instead costs one bit on five thousand, because the total is m·w plus n over two to the w and the minimum is where those two are equal.

025507510000.50011.502errors permittedfactor against the published loop64.5%55.8%74.7%the walk: 11xthe descentthe label is the shareof dead extensions6 patterns · sigma 2198x to 105x What a bound is

Flat in the budget, and not

One saving is eleven times at every error budget, because it is a property of the alphabet. The other moves between ninety-eight and a hundred and five, because it follows the share of extensions that find nothing. Two savings, two shapes, and neither line crosses the other.

0.5%1%2%5%10%20%0.020.050.10.20.5share of the copies' characters touched (log scale)runs a character, r/n (log scale)scattered substitutionsblocks of 64 rewrittenblocks of 64 movedr-index = entropy-boundedidentical copies32 copies of 512 characters6 collections a point The data that is not a number

A paragraph moved costs its seams

A paragraph cut from one place in a copy and pasted at another changes no character, only where the characters sit, and both repetition measures charge it for the where. Across thirty-two copies of one text, a moved block adds about three phrases to the Lempel–Ziv parse and eleven runs to the Burrows–Wheeler transform at every length from four characters to 256 — the price of the three seams a move makes, and nothing for the text between them. A tenth of the copies moved in blocks of 64 leaves the transform at 0.030 runs a character, where the same tenth rewritten reaches 0.050; the run-length index stays smaller than the entropy-bounded one up to 9% moved against 4% rewritten, and the phrase index stays the smallest of the three at every share measured.

a slack line every 8th linea slack line whenever the queue reaches 8Q 80280line 1line 120values waiting after each line · dots: slack linesone filter When the algorithm flips a coin

Slack placed where the queue is long

A blocked filter's threshold table, its lines sized for the mean number of closed blocks and each line's surplus carried into the next lines' free slots, had been given a slack line every eighth line and found that one deviation of room cannot drain eight lines of wander. The table is built, not grown, so it knows its queue: placing a slack line whenever the queue reaches eight was predicted to cost 3.15 bits a block for 2.03 lines a lookup and to bound every walk at about eight lines. It costs 3.150 bits for 2.027 lines, the longest walk is eight lines, and at the same bits the fixed spacing reads 0.023 lines more — over twice the hundredth predicted. Every earlier table is about three hundredths of a bit dearer at the same lines. All of it depends on a directory of marks, 972 bits for the whole table, being in cache when a lookup asks it where its line is; read from memory, it costs a whole line, and the design loses to every other.

00.1000.200share of keys in runs of at least 8 (log scale)record's saving, share of the cost without it1%3%10%30%100%switch at a tenthfilled: the record pays · hollow: it does not3 word reads a comparison17 inputs Counting

A switch that reads the long runs

The two-ended selection sort's record of adjacent order pays on long runs and costs on short ones, and a switch on the mean run the pass between neighbours reads could not tell an input of even short runs from one whose keys are half in short runs and half in long. The proposal counted something chosen for what the record is worth: the share of keys the pass finds in runs of at least eight, keeping the record when it reaches a tenth. At three word reads a comparison that switch chooses right on all seventeen inputs measured, including five new ones built to defeat it, where the mean's best threshold leaves up to 0.18%. But the prediction said it would be right at every rate, and it is right only at three: at one word read a comparison it costs 1.2% on runs of eight, at four it drops the record on one run of 64 among single keys, which at that rate pays. One number from the pass is enough to decide. Which number depends on the price of a word.

floored startsingle stepssteps priced in bitsworst gap over the fill behind the fitted division, pointsshuffled, 0.534.833.90.0shuffled, 0.751.70.00.0shuffled, 14.10.00.0two clusters at a time, 0.515.915.912.4two clusters at a time, 0.750.30.00.0two clusters at a time, 12.70.00.0one cluster at a time, 0.59.19.10.0one cluster at a time, 0.750.90.30.0one cluster at a time, 10.90.10.0within two points highlighted; over ten darkpoints behind the fitted division When it does not fit

A level priced on its own sample

A levelled store chose between two divisions of its filter memory by pricing both on a sample of queries, and still divided by the size rule's shape. The proposal was to descend from the floored division instead: price each level alone on the sample at the settings either side of what it has, and move a grid step of bits from the level that saves least to the one that saves most, until no move helps. At three quarters of a bit and one bit a key the descent reaches the fitted division on all three stores in at most two moves, within a third of a point. At half a bit it does not move at all on most of the fill, as the risk named: no single step pays, because the fitted division's trade is the largest level's half bit given up for many steps on the smallest, and a grid step is not a unit of bits. Moves priced in bits instead of grid places close half a bit on two stores of three — but they price up to 60% of the filters a full search builds, and the prediction was under a quarter.

tree · suffix array2,363,886tree · text656,635tree · document array1,050,616tree · previous-occurrence chain2,363,886tree · range minimum4,727,772succinct · suffix array2,363,886succinct · text656,635succinct · document array1,050,616succinct · previous-occurrence chain2,363,886succinct · range minimum1,483,854chainless · suffix array2,363,886chainless · text656,635chainless · document array1,050,616chainless · range minimum1,483,854chainless · reported bitmap256131,327 characters · 256 documents6 parts The other axis

What the chain cost

The chain of previous occurrences is one row number per row — exactly as wide as the suffix array it sits beside, and the largest single part of a document-listing apparatus. It is now absent, and what replaces it is one bit per document.

1101000.1documentsruns of the transform, per characterprose: 1.10xcopies: 1.02x8,192 characters, cutthe control rises further What is taught wrongly

A boundary that costs nothing

A separator occurs nowhere else in the collection, so it must break a phrase that would have spanned it. Cutting a repetitive text into a hundred and twenty-eight documents raises its run count by two per cent, and cutting prose raises it by ten.

051015255075100125documentsdistinct characters the documents end with+7+52+162+293+4+-1+9+19prosecopies of one basethe label is the runsthe cut added128 documents0.15 against 2.31 runs a separator Structures

The price of a boundary is what precedes it

A separator sorts before everything, so its rows sit at the top of the suffix array and hold the documents' last characters. What a document boundary costs the transform is the entropy of the character in front of it, and nothing else.

every occurrence5610 documentsrange minimum and chain32510 documentsrange minimum, no chain9610 documentsone descent over D3810 documentsthe document arraythe document array, the chain and a range minimumthe document array, a range minimum and one bit per documentthe document array, in a wavelet tree56 occurrences in 10 documentsoperations inside the structure The index that replaces the text

The tree answers the question

The distinct documents in a range of rows are the distinct symbols of the document array in that range. A wavelet tree enumerates those in one descent, so the range minimum, the chain, the bitmap and the recursion all go at once.

110100k, the operators after the alternationstatesits DFA: 512its NFA: 30a literal's DFA: 11alphabet ab2^(k+1), exactly What a bound is

The exponential is in the expression

The subset construction on one family reaches two to the k plus one states, exactly and not approximately. A literal of the same length gives eleven. Both are regular expressions and the difference is that one of them asks the machine to remember something.

a chaina star as far aparta star of one step a copyphrases added (log scale)runs added (log scale)moved blocks934931,2854,35698355rewritten blocks3277881,5284,275335760scattered changes2,6026,5535,22013,9892,4136,22832 copies, 1 edit a stepadded over identical copies The data that is not a number

Edits a history inherits

Every collection of copies measured so far was a star — one original and every other copy an independent edit of it — and a version history is a chain, each version the one before with one more edit. Built as a chain of thirty-two versions with one moved paragraph a step, a collection adds 93 phrases to the Lempel–Ziv parse of identical copies, three a step, exactly what one move costs a star, as predicted; a star whose copies are as far from the original adds 1,285, fourteen times as many. The parse charges an inherited edit nothing. The transform does not quite: a chain of moves costs 15.9 runs a step against eleven predicted, 39% more than a star of one move a copy, while rewritten and scattered edits cost a chain within 5% of a star. And the risk — a later edit cutting an earlier seam — is the common case, nine moves in ten, and costs nothing. A history is priced by how many edits were made, not by how far its copies have drifted.

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 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 segment tree over the chain2.70x8,142,274 bitsa succinct range minimum over the chain1.62x4,898,356 bitsno chain at all0.84x2,534,726 bitsthe dashed rule is the index itself: a suffix array and the text131,327 characters · 256 documents2.70x → 0.84x What the libraries do

The apparatus that is smaller than its index

Answering "which documents hold this" at a price proportional to the answer used to cost 2.70 times the index it sits beside. Two changes later it costs 0.84, and the largest thing left is an array that says which document each row belongs to.

run together1.00xsigma 21 · 5 bitsone separator1.00xsigma 22 · 5 bitsa separator each1.20xsigma 36 · 6 bitsruns 1.00xruns 1.00xruns 1.02x16 documents of 512 characterspacked bits, against running them together The other axis

Two currencies for one separator

Giving every document its own boundary marker costs a fifth of the packed text and three per cent of the run count. Both numbers are right, they are about the same change, and which one a collection pays depends on a structure nobody named.

prose, many short documents4.31 most frequent3.07 drawn from a documentone copy per document5.75 most frequent1.81 drawn from a documentcopies cut across the boundaries5.81 most frequent1.88 drawn from a documentoccurrences per document holding the pattern16 documents · 6-character patternsall three within a tenth on the drawn pattern What is taught wrongly

One copy per document is one occurrence per document

The output-sensitive listing apparatus wins when a pattern occurs far more often than it occurs in documents. A collection of versions was supposed to be that case, and it is the one collection where the two numbers are equal by construction.

range minimum and chain838,797255.0%range minimum, no chain285,46086.8%one descent over D119,97236.5%the document array, the chain and a range minimumthe document array, a range minimum and one bit per documentthe document array, in a wavelet tree64 documents · 16,447 characters14.3% of the published apparatus Structures

The last array in the apparatus

The document-listing apparatus began as three arrays beside a suffix array. Two of them turned out to be machinery for reading the third, and both have gone. What is left is the document array, and it is the only one of the three that was information.

acdefghijklmnopqrstuvwyzroot24 of 26 symbols present54 ranks · 51 nodes The index that replaces the text

Asking about symbols that are not there

A search extends an interval by every character of the alphabet, and on a deep branch almost all of them produce an empty interval. That is a full rank walk whose entire result is the discovery that nothing was there.

4,097 rows · one in 32 marked3.1% of the rows The other axis

The array that says where is twice the samples

An index keeps one suffix-array value in every thirty-two, and a bit vector over all n rows saying which. The vector is sixteen thousand bits and the values it points at are seven thousand — the index of the samples is twice the samples.

linear probingcuckoo, two tablescuckoo, buckets of 8024680.30.450.60.750.850.95load factorentries read per lookup00.511.50.30.450.60.750.850.95load factorcache misses per lookup8,192 slots, 64 cache lines of 8a probe is an entry read; a miss is a line fetched What the machine does

The bucket that fits a line

Make each of a cuckoo table's two candidates a bucket of eight slots laid out on one cache line, and no lookup ever touches more than two lines, the table builds past a load of 0.95, and at that load it misses 1.21 times a lookup where linear probing misses 1.79. The prediction that it would lose to linear probing at low loads was wrong — it misses less at every load measured, 0.94 against 0.96 at 0.3 — because a key it holds almost never lives in its second bucket. The guarantee belongs to the alignment, not the bucket; eight slots on lines of four put a lookup on four lines.

0.010.11101001000QuicksortQuicksortQuicksortShellsortHeapsortMerge sortMerge sort with a cutoffInsertion sortBubble sortSelection sortn²time × space, as a multiple of n²n = 8,192 · light: auxiliary slots · dark: the input counted toonone under n² What a bound is

A floor under a product

Every lower bound written here so far puts a floor under one quantity. The published time–space bound for sorting puts one under a product: T·S is Ω(n²), so buying time with space and space with time cannot both be done. Measured, heapsort's product is 0.0028 n² — four hundred times under a bound nothing can beat. The bound is not wrong. It is stated in a model where the input may not be written, and every sort here writes to the input, which is where its working memory actually is.

one text16 short documentsprosecopies of one baseprose, one textr/n 0.2996z/n 0.1273prose, many short documentsr/n 0.3053z/n 0.1301copies of one base, run togetherr/n 0.0638z/n 0.0354one copy per documentr/n 0.0768z/n 0.04188,192 characters throughoutthe outlined cell is the one that was empty What the libraries do

A collection is a construction

The same characters, arranged as one copy per document or cut across the copies, give a different run count, a different boundary cost and a different answer about which structure to build. Which one a benchmark used is usually not recorded.

range minimum and chain838,797255.0%range minimum, no chain285,46086.8%one descent over D119,97236.5%the document array, the chain and a range minimumthe document array, a range minimum and one bit per documentthe document array, in a wavelet tree64 documents · 16,447 characters14.3% of the published apparatus The other axis

The apparatus, three times smaller again

Eight hundred and thirty-nine thousand bits became two hundred and eighty-five thousand, and now a hundred and twenty thousand. The listing apparatus is fourteen per cent of what it was and holds one array, which is the only part of it that was ever information.

bits heldbalanced49,593huffman41,589the answer comes backbalanced: sorted · 26 operationshuffman: sorted · 24 operations32 documents · zipf lengths83.9% of the ordered tree What the libraries do

The smaller tree hands it back unsorted

A frequency-shaped tree is sixteen per cent smaller and returns its documents in code order. A balanced one is larger and returns them sorted. The trade is d log d comparisons against a saving, which is not close — until the answer is truncated.

equal lengths5.00 bits100.0%lengths as one over rank4.15 bits83.4%a few long, many short4.31 bits86.7%one document holding most of the text1.69 bits39.5%log₂ 3232 documents · 8,192 characters100.0% to 39.5% What is taught wrongly

A saving quoted without its collection

A check asking whether a compressed document array is smaller than the plain one passes on the rounding whenever the document count is not a power of two. It would report a saving of nothing as sixteen per cent, on a collection that has no redundancy at all.

extensions attempted9,206 dead7,594 livebit-vector ranksthe loop: 168,000the descent: 24,0868 patterns · 1 error · sigma 2054.8% dead · 6.98x Structures

The branches that find nothing

An approximate search over a twenty-symbol alphabet attempts sixteen thousand eight hundred extensions and nine thousand two hundred of them produce an empty interval. That is a full rank walk whose entire result is the discovery that nothing was there.

All threads