The memory a product does not charge

A floor under a product measured the published bound that time times space for sorting is at least $n^2$, in a model where a sort reads its input but may write only in $S$ cells of its own. A read-only family meets it with equality: keep the $S$ smallest values above the last one emitted, emit them, and scan the input again, $\lceil n/S \rceil$ times. Every sort that writes into its input sits far above the bound, because the array it overwrites counts as working memory. A product paid for in blocks then charged the reads in block transfers through a memory of $M$ cells in lines of $B$. The family’s reads are sequential, so its product fell to about $n^2/B$. The quicksorts, whose reads are mostly sequential too, fell alongside it once $M$ was large, while heapsort’s scattered reads kept it far above.

Its closing section found the gap in the account. The product charges quicksort for the $n$ cells it writes and says nothing about the $M$ cells of fast memory it needs to write them cheaply. The family needs almost no fast memory at all. A three-way account of transfers, writable cells and fast memory would separate what the two-way product cannot. It proposed sweeping $M$ and drawing, for each algorithm, the least fast memory at which its product comes within a stated factor of $n^2/B$. The prediction was that the family’s need is its own buffer, a few hundred cells whatever $n$ is. Quicksort’s should be $n/2^c$ for a factor $2^c$, since each halving of memory adds a level of scans. Heapsort’s should be all of $n$.

The first and third parts hold. The second holds in shape and fails in rate. And the account turns up a fourth product the bound never takes, which separates the two kinds of sort more cleanly than either of the products before it.

Every trace replayed at every memory #

Each sort runs on random keys and records every array access it makes. The traces are the earlier essay’s, for heapsort, Shellsort and quicksort with a random pivot and with a median-of-three pivot. The family is traced too this time, not charged by formula. Every read of its input is recorded, along with every touch of its sorted buffer (the comparison with its largest entry and the shifts of each insertion), the two bookkeeping cells it reads on every step, and each value of its output as it is written. Every address is separate, so a memory too small for the buffer is charged for it. Each trace is replayed through an LRU memory of $M$ cells in lines of eight, the block model one access, eight kilobytes introduced to charge an access by the line it lands on, for every $M$ on a doubling grid from 16 cells to $n$, at $n$ = 2,048, 4,096 and 8,192. When the memory holds the whole array, every sort pays one read of it, which is the floor for anything that must see every key.

The product is transfers times writable cells over $n^2/B$. A sort’s writable cells are its $n$ array cells plus whatever it allocates; the family’s are its buffer and three bookkeeping cells. With room for the buffer but not the input, the family’s transfers come out at its scans over lines plus one pass of output, the formula the earlier essay charged, which is the check that the trace and the formula describe the same algorithm.

What each sort pays as memory shrinks #

At n = 8,192, quicksort pays 2.7 reads of its array in transfers with half of n in fast memory and 8.5 with 512 cells; heapsort pays 8.7 and 43. Both pay exactly one read once the whole array fits. Below that the curves part by locality, as the earlier essay found by varying the line. Quicksort’s partitions are sequential sweeps, and each halving of memory adds about 1.8 reads of the array, because one more level of the recursion no longer fits. Heapsort’s sift-downs jump across the array, and below half of $n$ almost every step down the heap is a transfer.

The family’s curves are flat and high. With 16 cells it pays about 516 reads of the array at any memory of 64 cells or more, because it scans the whole input for every 16 values it emits, and no amount of fast memory beyond its buffer changes that. With 256 cells it pays 33 reads, a sixteenth as many. Below its buffer the family falls off a cliff: with 16 cells of memory and a buffer of 16 it pays 6,461 reads, because its buffer, its bookkeeping and the line it is scanning no longer fit together.

The family needs its buffer and a few lines #

The family is on the floor as soon as its buffer fits: with 256 cells its product is 11.7 times $n^2/B$ in 128 cells of fast memory, 3.73 in 256 and 1.13 in 512, and the same holds at every length. That is the prediction’s first part. The family’s need for fast memory is its own buffer plus the few lines its scan, its output and its bookkeeping occupy, and it does not grow with $n$.

The curves show one refinement. A buffer does not have to fit entirely to be nearly free. With 64 cells of buffer and only 32 cells of fast memory, the product is 2.70 times the floor, not ten or fifteen. Between insertions the family touches only the buffer’s last entry, the largest value it is keeping, and late in each scan insertions are rare, because a value small enough to enter a full buffer of the smallest values becomes harder to find as the scan proceeds. The working set of the buffer is its end, most of the time. The cliff comes where even that working set stops fitting, which for a buffer of 256 is between 128 and 256 cells.

Heapsort needs all of n, quicksort an eighth #

Within a factor of eight of the floor, heapsort and Shellsort need all of $n$ in fast memory at every length, quicksort needs an eighth of $n$, and the family needs 32 to 256 cells whatever $n$ is. The plate’s three slopes are the three predictions. The family’s need is flat. Quicksort’s and heapsort’s grow in proportion to $n$, with quicksort’s an eighth of heapsort’s.

The flat line is the plate’s argument. A product within a factor of eight of $n^2/B$ is, for the earlier essays, the same verdict for all of these algorithms: each is near the floor. The memory each needs to reach it ranges from 32 cells to 8,192. Doubling $n$ doubles what quicksort and heapsort require and leaves the family’s requirement where it was. Any account of time and space that leaves fast memory out describes these algorithms as equals, and the plate shows they are not.

Heapsort’s need is all of $n$ for the reason the cliff where the data stops fitting gave for a random access pattern: below the size of the working set, LRU misses on nearly every access, and heapsort’s working set is the whole heap. Shellsort behaves the same way at this factor because its long gaps make the same kind of jumps. The two pay one read of the array at $M = n$ and 8.7 and 12 reads at $n/2$, so a factor of eight is crossed just short of fitting the whole array.

Each factor of two buys a sixteenth #

At n = 8,192, quicksort’s need for fast memory falls from 8,192 cells within a factor of two to 4,096 within four, 1,024 within eight and 64 within sixteen. The prediction said each extra factor of two would halve it. It does far more than halve: the step from four to eight divides it by four, and the step from eight to sixteen by sixteen.

The transfers plate says why. Each halving of memory adds about 1.8 reads of the array to quicksort’s bill, a constant amount, while the factor allowed above the floor is a multiple. Allowing twice the factor allows roughly twice as many extra reads, and each extra 1.8 reads buys a halving of memory. So the memory quicksort needs falls exponentially in the factor, roughly as $n \cdot 2^{-(f-1)/1.8}$: about $n/3$ at a factor of four, $n/15$ at eight and $n/300$ at sixteen, against the grid’s $n/2$, $n/8$ and $n/128$. The prediction’s $n/2^c$ treated the factor as the number of levels; it is the number of levels times the cost of a level, and the cost of a level for a partition sort is about two reads of the array. That is the external-memory picture sorting what will not fit measured for merge sort, where transfers grow with the logarithm of the data’s size over the memory’s, so that a memory many times smaller costs only a few more passes.

Heapsort barely moves: all of $n$ within eight, half of $n$ within sixteen. Its transfers at half of $n$ are 8.7 reads and at a quarter 18, so its bill doubles with each halving of memory, and a factor that doubles buys back only one halving. The difference between the two sorts is the difference between a cost that grows additively as memory shrinks and one that grows multiplicatively.

The product the floor does not take #

Transfers times fast memory never falls below 1.29 times $n^2/B$ for the read-only family at any memory or buffer measured, and for quicksort it falls to 0.05 at 16 cells of memory. This is the product the closing section’s three-way account implied and did not name. It separates the two kinds of sort completely, where transfers times writable cells put them side by side.

The family’s floor here has a one-line reason. A sort that may not write into its input carries information from one scan to the next only in the memory it holds, and it cannot usefully hold more than $M$ values in $M$ cells of fast memory, so each scan emits at most about $M$ values. It needs at least $n/M$ scans of $n/B$ transfers each, and transfers times $M$ is at least $n^2/B$. It is the published argument with the fast memory in the place of $S$: for a read-only sort, the cells it writes and the cells it holds fast are the same cells.

Quicksort escapes that argument because it writes into its input. The arrangement of the array after a partition is information carried between scans, stored in slow memory, and a sort that can store its progress there needs only enough fast memory to keep its current sweeps efficient. Its transfers grow as the logarithm of $n/M$ while $M$ shrinks geometrically, so the product of the two keeps falling, from 1.27 at 2,048 cells to 0.05 at 16. Its partitions never consult $M$ at all; like the layout the layout that is told nothing measured, a sweep that is sequential at every scale is efficient at every memory without being told which one it has. Heapsort writes into its input too and gets the same escape at small memories, 0.26 at 16 cells, though its transfers grow too fast for the product to stay low as memory grows.

That is the trade the closing section was reaching for, now stated as two products. Transfers times writable cells has a floor of $n^2/B$ that every sort here can reach, given enough fast memory. Transfers times fast memory has the same floor for any sort that does not write into its input, and no floor at that level for one that does. A sort can save writable cells or fast memory, and the read-only family and quicksort are the two extremes: one writes almost nothing and needs fast memory in proportion to the progress it makes each scan, the other writes everything and needs almost no fast memory at all.

The three-way account #

All three algorithms are within a factor of four of the floor at n = 8,192, and their bills differ by a factor of 430 in writable cells, 256 in fast memory and 560 in transfers. Heapsort writes all 8,193 cells, needs all 8,192 in fast memory and pays 1,024 transfers, one read of its array. Quicksort writes 8,221, needs 4,096 and pays 2,725. The family with a buffer of 16 writes 19 cells, needs 32 and pays 572,132 transfers. With a buffer of 256 it writes 259, needs 256 and pays 120,788.

No single product ranks these. The two-way product calls them equal. Transfers alone favour heapsort with all of $n$ in fast memory, which is the case where sorting is cheap anyway. Fast memory alone favours the family, at the price of five hundred passes. The account the closing section asked for is three numbers, and which algorithm is best depends on which resource is scarce. The model a bound was quoted in drew the same lesson from the accuracy guarantees of streaming summaries: a guarantee holds in the model it was stated in, and one assumption more is enough to change which structure wins.

What the prediction got right #

The closing section predicted that the family’s need is its own buffer, a few hundred cells whatever $n$ is. It is its buffer, and slightly less, since the buffer’s working set is its end, and it does not move with $n$. It predicted heapsort needs all of $n$, and within a factor of eight it does at every length. It predicted quicksort’s need would be $n/2^c$ for a factor $2^c$. The need is proportional to $n$, as predicted, but it falls with the factor much faster than halving, because a level of quicksort’s recursion costs about 1.8 reads of the array, not one.

What it could not have predicted is the product of transfers and fast memory, and that turns out to be the cleanest statement of the trade. The bound on time times writable space was proved for sorts that read their input and write elsewhere. Read with fast memory in place of writable space, the same argument holds for exactly those sorts and fails for every sort that writes in place. In-place sorting is a way of using slow memory as storage for progress, and the published bound charges that storage as if it were free.

What the replay assumes #

LRU on one level. Every transfer is a miss in a fully associative LRU memory of $M$ cells. A real cache is set-associative and a real memory hierarchy has several levels; the block that is not a block listed what such a model leaves out. Within the model the comparisons are exact, and the cliff and slopes are the shapes LRU gives every scan and every random walk.

Reads only. A transfer is charged when a line is brought in. A line a sort has written must also be written back when it is evicted, and quicksort dirties every line it partitions while the family dirties only its output. Write-backs were not charged.

Random keys. Every trace is on a random permutation. Quicksort’s need for memory depends on its partitions being balanced, and the median-of-three pivot, which needed all of $n$ within a factor of four at n = 8,192 against the random pivot’s half, shows that the need moves with the pivot rule on the same input.

Still open: the lines a sort writes back #

The replay charged a transfer for every line brought into fast memory and none for a line written out. That is fair to the family, which writes only its output, once, in order. It flatters every sort that writes in place, since each line a partition or a sift-down modifies must eventually go back to slow memory, and under LRU it goes back each time it is evicted dirty.

The measurement that follows replays the same traces with every eviction of a modified line charged as a second transfer, and draws the same two products again: transfers times writable cells against $n^2/B$, and transfers times fast memory. The prediction is that write-backs roughly double quicksort’s transfers at small memories, since a partition writes nearly every line it reads, and nearly triple heapsort’s, whose sift-downs modify lines they leave quickly. The family’s transfers should not move. On transfers times fast memory, quicksort’s least value should rise from 0.05 to about 0.1, still far below the family’s 1.29. The question is whether charging the writes moves the in-place sorts back towards the floor the read-only family cannot get under, or whether storing progress in slow memory stays cheap once its true price is paid.