The thread: There is a floor — page 2
A bit for every bit
A grid over 3,612 points is 43,344 bits of payload. The smallest any structure can be that distinguishes one permutation of 3,612 things from another is 37,485. There is 16% to play for, and the deferral that asked for a compressed grid assumed there was much more.
The floorsThe merge that can say equal
When two sorted lists draw their keys from a few values, equal keys can go on either side of each other, so far fewer answers are needed and the counting floor falls. Merging four keys into four over four values needs only 27 answers, not 70, and the floor falls from seven comparisons to five. A merge whose comparisons answer only 'at most' still needs seven on its worst input, exactly as many as distinct keys, because it can never learn that two keys are equal. A merge whose comparisons can answer 'equal' needs five and meets the floor. Solved exactly over every input, the third answer is the whole difference, and on average it is worth more than an optimal strategy.
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.
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.
What a bound isA code word is at least one bit
A wavelet tree of plain vectors reaches the entropy by its shape, and a Huffman code word cannot be shorter than one bit. On a collection whose document array has an entropy of 1.69 the tree costs 1.98, and the gap is a floor rather than an inefficiency.
What a bound isThe 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.
What a bound isThe 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.
The other axisThe 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.
What a bound isA 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.
The index that replaces the textWhat the locating apparatus becomes
The two parts that answer "where" are half an index at a dense sampling and a fifth at a sparse one, and the fifth does not fall further. Represent the marks properly and it keeps falling, to under four per cent.
What a bound isA product paid for in blocks
The published floor under sorting puts a bound on time times space, and a read-only family that scans its input over and over meets it, while every in-place sort sits far above it. Counted in block transfers rather than reads, the floor itself moves to n²/B: the family meets it at every block size, and so does every sort once memory holds the whole array. With a memory of 512 cells, quicksort sits a fixed eight times above the family at every block size, because partitioning is itself a scan. Only heapsort's distance grows with the block, from ten times at a line of one to 285 times at 64. The prediction that the family's lead would widen towards B holds against heapsort and nothing else.
What the libraries doThe floor was the marks
A saving reported as about a sixth of a bidirectional index, falling to an eighth and levelling off. Represent one array properly and it falls to a fiftieth instead — most of what was being dropped was a badly encoded bit vector.
The other axisSparse on average, dense where it gathers
The r-index keeps one suffix-array value for every run of its transform and prices the set as Elias–Fano: on 32 exact copies of 2,048 characters that is 666 values among 65,537 positions at 9.04 bits a value, as though they were spread evenly. They are not — 663 sit in one copy. Cut into chunks of 32 values, each held by whichever of a bitmap, its own Elias–Fano or a run is cheapest, the same set costs 4.48 bits a value, under the 8.05 that any representation of an arbitrary set of that size must spend on some set. At a divergence of 0.0005 the saving is a fifth, and from one character in five hundred it is nothing but the select directory, which the chunks replace with reading. On the scattered marks of an ordinary index the partition saves only that directory too.
The index that replaces the textA count that names every point
A grid that can report the points in a rectangle can be no smaller than log₂(z!) bits, because reporting them recovers the permutation. A grid that only counts them was left open as possibly smaller. Exactly, it cannot be: counts alone decode every point, and on the phrase index's 3,612 points 42,860 count questions recover the whole permutation, so an exact counter pays the same floor of 37,485 bits. Approximately it can — and the rectangles a phrase index asks are where an approximate count is worst. They hold 2.6 points on average and a third of them hold exactly one; the wavelet grid cut to eight of its twelve levels, 8% under the floor, counts 46% of them right.
The other axisCuts that follow the gathering
Cutting an r-index's run-start values into chunks of a fixed count left chunk edges inside the places the values gather. Choosing the cuts as a shortest path through the sorted values was predicted to save a further tenth on exact copies by cutting once at each edge of the gathering. It cuts there, and saves more than a quarter: two chunks, one of them a bitmap of 664 values that a select must scan from its start. Capped at the chunk's old size, the optimum keeps the reads and saves 9% on exact copies and 15% at a divergence of 0.0005. On moderately drifted copies the uncapped optimum is smaller and cheap to read at once.
The other axisA select that starts near its answer
The cheapest partition of an r-index's run-start values held exact copies in two chunks, one a bitmap of 664 values that every select scanned from its start: 1,065 bits read a select. Capping the chunks bought the reads back by giving up the saving. A select sample every 64 values inside each chunk, its bits charged in the same shortest path, was predicted to bring the uncapped optimum under 150 bits a select for under 3.5 bits a value. It reads 111 for 3.45, where the cap that reads as little costs 3.68. And the middle divergences, predicted to be untouched because their chunks were short, lose two fifths of their reads to the same samples.
The other axisA sample that has to be found
A select sample every 64 values inside the cheapest partition of an r-index's run-start values cut a select's reads from 1,065 bits to 111 on exact copies. Samples by count bound how many values a select passes, not how many bits it reads, so samples every 128 bits of a chunk's vector were predicted to read a third less on the sparse, drifted sets at the same cost. They bound the scan as promised, but a rank sample does not say which sample a select needs, and finding it by binary search costs a select up to a third of what it reads. The two kinds of sample end up on one frontier, and the rank samples' advantage is that they come in finer steps.
The index that replaces the textA test that is the top of the search
A phrase index asked whether a pattern occurs only needs to know, split by split, whether a rectangle of its grid holds a point. Stopping the grid's descent at six of its twelve levels was predicted to turn away nine in ten of the splits that come to nothing, for half the grid's bits. It turns away three in four, and the ones it lets through sit a median of five rows from a point. The test is never wrong, but the existence query had little left for it to save: patterns that occur are settled by their first split 94% of the time, and most patterns that do not occur never reach the grid.
What a bound isThe memory a product does not charge
Time times space charges a sort for the cells it writes and not for the fast memory it needs to write them cheaply. Counted three ways, on random keys in lines of eight, a read-only family stays within a factor of eight of the floor with 32 to 256 cells of fast memory at every length, while heapsort needs all of n and quicksort an eighth of it. Quicksort's need falls far faster than predicted as the factor loosens. And the product the floor leaves out, transfers times fast memory, separates the two kinds of sort completely: no read-only sort can push it far below n²/B, and quicksort reaches a twentieth of it.
What a bound isThe lines a sort writes back
A replay that charges a transfer for every line brought into fast memory and none for a line sent back flatters every sort that writes in place. Charged for its write-backs, quicksort's transfers rise by 1.9 at every memory short of n, as predicted, and heapsort's by 1.8, not the predicted three, because no line can go back more often than it came in. The cost that changes the account is the last one: at n itself every in-place sort pays two reads of its array, so none of them can come within a factor of two of the floor, while the read-only family reaches 1.07.