The thread: Space is the other axis — page 3
Two 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.
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.
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.
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.
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 the algorithm flips a coinA 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.
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.
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.
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.
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.
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.
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.
When the algorithm flips a coinThe room the lines lend
A blocked filter's threshold table gives each 512-bit line room for its closed blocks' values, and a group reserve sized for the spill had just put it under the ungrouped curve. A line under its room leaves slots empty that are already paid for, so its neighbours' spills could be carried forward into them, with no reserve at all: predicted at about 3.12 bits a block for 2.012 lines a lookup. The bits are right and the lines are not. At room for the mean a carried value passes 12.8 lines before it finds a slot, because a run of lines that is room-for-the-mean on average is a queue with nothing to spare. Given three quarters of a deviation of room, the walk falls under two lines and the carried table lands a hundredth of a bit under the reserve.
CountingA register kept through a confirmation
Two registers beside a two-ended selection sort's extremes, holding where the run of known order from each one ends, read 53.5 words a question on a sorted array of 1,024 keys, more than reading the record plainly — because 263,167 times a neighbour's question, answered by the previous scan's chains, rewrote a pair at the value it already held, and each rewrite dropped a register. Kept through such a confirmation and dropped only when a pair is forgotten or turns round, the registers read 0.347 words a question on that array, a 154th, and 0.345 on 4,096 keys: the reading stops growing with n. They become the cheapest record at every run length, 49 to 73 times under the next on runs and 5.75 times under the run list's search on the sorted array, and the price of a saved comparison now falls as runs lengthen, from 3.97 word reads at runs of four to 0.35. The dearest saving is now the short run's, and it is still above the 3.1 at which a table of compared pairs breaks even.
The other axisWhat 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.
What the libraries doThe 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.
StructuresThe 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.