The lines a sort writes back

The memory a product does not charge replayed every sort’s array accesses through an LRU memory of $M$ cells in lines of eight and read three numbers off the replay: the transfers a sort pays, the cells it writes, and the fast memory it needs. A read-only family that rescans its input for every buffer of values it emits needs almost no fast memory and stays near the floor of $n^2/B$ on transfers times writable cells. Quicksort writes into its array and needs an eighth of $n$ in fast memory to stay within a factor of eight of that floor. And transfers times fast memory, the product the published bound never takes, separated the two kinds of sort completely: the family never fell below 1.29 times $n^2/B$, and quicksort reached 0.05.

That replay charged a transfer when a line came into fast memory and nothing when one went out. Its closing section named whom that flatters. The family writes only its output, once, in order. Every sort that writes in place modifies the lines it reads, and a modified line must go back to slow memory before its slot can be reused. It predicted that charging those write-backs would roughly double quicksort’s transfers at small memories and nearly triple heapsort’s, whose sift-downs modify lines and leave them quickly, and that the family’s transfers would not move. On transfers times fast memory it predicted quicksort’s least value would rise from 0.05 to about 0.1, still far below the family’s 1.29.

Two of those predictions hold, one is impossible, and one fails in a way that exposes something the family was getting for free.

Every access marked as a read or a write #

The sorts are the earlier page’s, on the same random keys: heapsort, Shellsort, and quicksort with a random pivot, with a median-of-three pivot and with the first element as pivot. Each runs on a counted array that now records, beside every address it touches, whether the touch wrote. A comparison reads two cells, a swap reads two and writes two, and a store writes one. The family is traced the same way. Its scans read the input and the largest entry of its buffer, its insertions and the shifts that make room for them write the buffer, its output is written once in order, and the cell holding the last value emitted is written each time a value goes out.

Each trace is replayed through LRU with the two rules a real write-back cache uses. A miss fetches the line whether the access that missed reads or writes, which is write-allocate. A write marks the line dirty, and evicting a dirty line costs a second transfer. When the run ends, every line still dirty is written back too, because an array that is sorted in fast memory is not yet sorted where anyone else can read it. The replay’s misses are checked against the earlier simulator’s on the same traces and agree exactly, so the read side of every number here is the earlier page’s. One access, eight kilobytes introduced this way of charging an access by the line it lands on; this is the same model with the line’s return trip added.

One fact settles part of the prediction before any trace runs. A line comes in once each time it misses and goes out at most once each time it is evicted, so the write-backs over a whole run can never exceed the misses plus the lines left dirty at the end. Charging write-backs can at most double a sort’s transfers. Heapsort cannot triple.

Nine lines in ten come back dirty #

Of the lines quicksort brings into fast memory, 89% to 93% go back dirty at every memory from 16 cells to a quarter of $n$, and of heapsort’s, 79% to 86%. A partition reads a line, swaps some of its keys with keys from the other end of the range, and moves on. On random keys almost every line it crosses holds a key on the wrong side, so almost every line it reads it also writes. The share does not depend on how much fast memory there is, because a partition’s sweep reads and dirties each line once per level of the recursion whatever $M$ is; memory decides how many of those levels fit, which changes how many lines come in, not what happens to each one.

Heapsort’s share is lower and steadier. A sift-down compares a key with its two children and swaps it with the larger, level by level, until it is larger than both. Every line on that path is written except the last, where the comparison found nothing to move, and the stop at the bottom of each sift-down leaves a line or two read and clean. That reason is the likeliest one; the replay counts the lines and not which comparison touched them last. Shellsort at 16 cells writes back only 53% of what it reads, the likeliest reason being that with two lines of fast memory its long-gap comparisons fetch lines it then does not modify; above that its share climbs towards one as its gaps shrink and its passes become near-sequential insertion sorts that move a key on almost every line.

The family is the other extreme, and each of its curves is two curves joined at its buffer. Once the buffer fits, what comes back dirty is mostly its output, about one line for every line of output, against the 33 to 513 reads of the array its scans make, so the share is a few lines in a hundred or less. Where a buffer of 64 cells must share 32 cells of fast memory, 45% of the lines it brings in go back dirty; where a buffer of 256 shares 128, 85%. The family writes in two places, and only its output is cheap to write.

Never more than double, and two at the end #

Charged for its write-backs, quicksort pays 1.92 times its read transfers at 16 cells and between 1.89 and 1.96 at every other memory short of $n$; heapsort pays 1.79 times at 16 cells and never more than 1.86. The first is the prediction’s “roughly double”. The second is not “nearly triple”, and the plate shows why the prediction could not have held: a sort’s transfers with write-backs charged are its misses times one plus its share, and the share is a fraction. The worst ratio at any memory short of $n$, for any sort here, is 1.98, Shellsort’s at 4,096 cells, where nearly every line it reads is modified on the same pass.

What the prediction did not mention is the right-hand end. With the whole array in fast memory, every in-place sort pays one read of its array to bring it in, and on the old account that was the whole bill. Charged for its write-backs, it pays a second read’s worth to send the sorted array back out, because on random keys every line has had some key move. That makes the cheapest an in-place sort can possibly be, in any memory, two reads of its array. It is the floor of permuting is sorting here, seen from the other side: a sort that rearranges $n$ keys in place has written every line of them, and writing a line to slow memory costs what reading it did.

A factor of two out of reach #

With write-backs charged, no in-place sort’s transfers times writable cells comes within a factor of two of $n^2/B$ at any memory: heapsort and quicksort reach 2.00 and 2.01, and only with all of $n$ in fast memory. The read-only family reaches 1.07 with a buffer of 64 and 1.19 with 16. The earlier page’s verdict on this product was that every sort here can reach the floor given enough fast memory, and that the product therefore calls them equals. On the honest account, the in-place sorts’ floor is twice the family’s.

The arithmetic is short. An in-place sort’s writable cells are its $n$ array cells, and its transfers can never fall below the two reads of its array the last plate found, $2n/B$. The product is at least $2n^2/B$. The family writes only $S$ cells, and its transfers are its $n/S$ scans of $n/B$ each plus its output, so its product is $n^2/B$ plus terms that shrink as $S$ grows and as $n/S$ does. Its output costs it a read of the array to write as well, since an output line is fetched before it is written and written back after; but that read is one more scan among the hundreds the family already makes, a few per cent of its bill, where for an in-place sort with all of $n$ in fast memory it is half.

A floor under a product found the published bound easy to beat by four hundred times when the input may be written, and the earlier pages put the in-place sorts back near it by counting the array as writable memory and charging transfers instead of reads. With write-backs charged, the bound’s model and the block model now agree on a direction: writing into the input is a cost, and the read-only family is the cheapest way to sort that either model measures, by a factor of nearly two on this product even when fast memory is unlimited.

What every factor now costs in fast memory #

At n = 8,192, quicksort with a random pivot now needs all of $n$ in fast memory to come within a factor of four of the floor, half of $n$ within eight, and an eighth within sixteen, where on reads alone it needed half, an eighth and a 128th. Each requirement has moved up by one to four doublings, and within a factor of two there is no memory at which any in-place sort qualifies. Heapsort, which needed half of $n$ within sixteen, now needs all of it within every factor it can reach.

The size of each move follows from the earlier page’s arithmetic. There, each halving of fast memory added about 1.8 reads of the array to quicksort’s bill, and the memory it needed fell exponentially in the factor allowed. Write-backs nearly double every one of those additions, to about 3.5 reads of the array a halving, and they double the starting point too, from one read of the array to two. A factor of sixteen allows about sixteen reads of the array. On reads alone quicksort starts at one and has room for about eight halvings at 1.8 each; charged, it starts at two and has room for about four at 3.5. The grid measures seven and three: 64 cells against 1,024.

The family’s requirements mostly stay where they were. A buffer of 16 needs exactly what it needed at every factor, a buffer of 64 needs 128 cells instead of 64 to come within a factor of two, and a buffer of 256 needs 512 instead of 256 within four. The one large move is the loosest factor on the largest buffer: within sixteen, a buffer of 256 needed only 32 cells of fast memory on reads alone, an eighth of itself, and charged it needs all 256. On reads alone it could afford to let most of its buffer live in slow memory; charged for the buffer’s write-backs, which the plate after next isolates, it cannot. The cliff where the data stops fitting is the same shape at the family’s scale: a working set that fits pays almost nothing, and one that nearly fits pays almost everything.

The product the floor does not take, repriced #

Charged for its write-backs, quicksort’s least transfers times fast memory rises from 0.049 of $n^2/B$ to 0.095, at the same 16 cells, and the family’s least, over all three buffers, rises from 1.29 to 1.87. The first is the prediction exactly: about 0.1. The second is the prediction’s one outright failure. The family’s transfers were supposed not to move, and at its best point they move by 45%.

The best point is where the move is. The family’s least memory product was always found just below its buffer, 32 cells of fast memory holding the end of a 64-cell buffer, because transfers times $M$ rewards the smallest $M$ that does not fall off the cliff. That is exactly the configuration in which the buffer does not fit and its insertions dirty lines that are then evicted. On the read-only account those lines were free to throw away; on the honest one each costs a transfer. So the family’s floor on this product was partly an artefact of not charging the family for writing its own buffer.

The separation survives. The family’s least is still twenty times quicksort’s, against twenty-six before, and the earlier page’s argument for why the family cannot go below $n^2/B$ on this product is untouched: a sort that does not write into its input carries its progress between scans only in what it holds fast, so it needs about $n/M$ scans. Quicksort’s escape from that argument was storing its progress in slow memory, and the repricing says what that storage costs: one write-back for about nine of every ten lines it reads, which is a factor under two on a product it beats the family on by twenty.

The family’s buffer was never free #

Where its buffer fits, the family’s write-backs are its output and almost nothing else: a buffer of 256 pays 34.1 reads of the array where it paid 33.1, at every memory from 1,024 cells. Where the buffer does not fit, a buffer of 256 at 128 cells pays 681.4 reads where it paid 369.2. The prediction that the family would not move was a prediction about the first regime, and there it is right to within one read of the array. Its output is written in order, so each output line is fetched once, filled, and written back once, and that is the whole of the change.

Below the buffer the family has a second written structure, and it is a bad one to write. An insertion into a sorted buffer shifts every larger entry one place, so a new value near the front of a 256-cell buffer dirties all thirty-two of its lines. While the buffer fits, those lines stay in fast memory and are written back once, at the end. When it does not, the scan’s input lines push the buffer’s lines out between insertions and every shift sends a line back. The earlier page found the buffer’s working set was mostly its end, which is why a buffer that did not fit was still cheap to read. Its write set is not its end: every insertion writes from the insertion point to the end, and on random keys early in a scan the insertion point is anywhere.

So the honest account adds one condition to the family’s claim on fast memory. The family needs its buffer to fit, not merely its buffer’s end, and its advantage is cleanest at the memory where that happens rather than just below it. The writes nobody counted found a B-tree writing forty-nine elements’ worth of blocks for every key it stored because each update rewrote a whole node; a sorted buffer that does not fit is the same structure at a smaller scale, rewriting its tail to place one value.

The gap grows with n #

Quicksort’s least memory product, write-backs charged, falls from 0.301 of $n^2/B$ at $n$ = 2,048 to 0.174 at 4,096 and 0.095 at 8,192, nearly halving with each doubling of $n$ exactly as it did on reads alone, while the family’s best stays between 1.87 and 2.68. The ratio between them grows from nine to twenty over a factor of four in $n$, and charging the write-backs changes the level of quicksort’s curve and not its slope.

The slope has a plain reason. Quicksort’s least product is always at the smallest memory, 16 cells, where its transfers are $n/B$ times a number of passes that grows as $\log_2(n/M)$, the levels of its recursion that do not fit, and its writes nearly double that number without changing how it grows. Transfers times $M$ over $n^2/B$ is then proportional to $M\log_2(n/M)/n$, which at fixed $M$ falls nearly as $1/n$: from 2,048 to 8,192 that expression falls by a factor of 3.1, and the measured product by 3.2. The family’s least can never go below the floor, by the scanning argument, at any $n$. So the in-place sort’s advantage on this product is not a constant to be traded against write costs; it grows with the input, and a factor of two in the cost of storing progress is small against it at any size measured here.

That puts the two products where the earlier page left them, with one correction. On transfers times writable cells, the in-place sorts were the read-only family’s equals given enough fast memory, and on the honest account they are not: their floor is twice the family’s, because a rearranged array is written once in full. On transfers times fast memory, the in-place sorts are better than any read-only sort by a margin that grows with $n$, and the honest account narrows that margin by a factor under two at every size. The model a bound was quoted in drew the same moral about streaming summaries: change what the model charges and the verdict between two structures can move by a constant, while the verdict that grows with the input survives it.

What the replay still assumes #

Write-allocate on one level. A miss on a write fetches the line before writing it. The family’s output is written in order and never read, and a cache with streaming stores would write those lines without fetching them, saving the family one read of the array. Nothing here measures that, and it would change the family’s numbers by the same few per cent its output costs it now.

Writes priced as reads. A write-back is charged one transfer, the same as a fetch. On disks and on most memories that is close to the truth. On flash and on the non-volatile memories that keep data through a power cut, a write can cost several times a read and wear the medium as well, and none of the products here would rank the sorts the same way.

Random keys, one seed a length. On random keys nearly every line holds a key out of place, so nearly every line an in-place sort reads it also writes. On input that is nearly sorted, a partition swaps little and the share of lines written back would fall; in-place is a claim has already shown how far a sort’s behaviour on such input can move from its behaviour on random keys.

Still open: a buffer that does not shift its tail #

The family’s one real loss on the honest account is its buffer. A sorted array of the smallest values seen so far takes each new value by shifting every larger entry one place, so an insertion near the front writes every line from there to the end, and below the memory that holds the whole buffer each of those lines is evicted dirty and sent back. Its least memory product, found at exactly such a memory, rose by 45% for that reason alone, while its output cost it one read of the array.

A buffer does not have to be sorted while it fills. Kept as a max-heap of the smallest values seen, it compares each input value with its root, as the sorted buffer compares with its last entry, and an insertion replaces the root and sifts the new value down one path of about $\log_2 S$ cells, rather than shifting a tail of up to $S$. The heap is sorted once, in place, when the scan ends, which writes every line of the buffer once a scan, as the sorted buffer’s emptying already reads them. The measurement that follows gives the family that buffer, at the same three sizes, and replays it with write-backs charged at every memory. The prediction is that below its buffer the heap writes back about a third of the lines it brings in rather than 45% to 85%, since a sift-down’s path crosses about three of a 64-cell buffer’s eight lines where a shift crosses half of them on average, and that the family’s least memory product falls from 1.87 back towards the 1.29 it measured on reads alone. It could fail on the heap’s reads. A sift-down reads two children a level and jumps between lines a sorted buffer reads in order, so a heap that does not fit may fetch more lines than the sorted buffer did, and lose on misses what it saves on write-backs. The question is whether the read-only family’s best point on this product was a property of reading its input only, or of the particular structure it kept its buffer in.