A buffer that does not shift its tail

The memory a product does not charge replayed every sort’s accesses through an LRU memory of $M$ cells, in lines of eight, and charged a transfer for every line brought in. One family of sorts did well on that account in a way no in-place sort could: the read-only family, which never writes its input. It scans the input once for each batch, keeping in a buffer the smallest values greater than the last one output, and when the scan ends it writes the buffer out in order. A buffer of $S$ cells costs about $n/S$ scans, so the family trades memory for reading at a fixed exchange, and at its best memory its transfers times fast memory came to 1.29 of $n^2/B$, the floor such a product has for sorting.

The lines a sort writes back charged the other half of the traffic, every dirty line evicted back to slow memory, and the family lost its advantage there. The family’s input is never written and its output is written once, in order; its buffer is the problem. A sorted array of the smallest values seen 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. The family’s least product rose from 1.29 to 1.87, and the whole rise was the buffer.

That essay’s closing section noticed that the buffer does not have to be sorted while it fills. A max-heap of the smallest values seen does the same job: each input value is compared with the heap’s root, the largest value kept, as the sorted buffer compares with its last entry; a value that belongs replaces the root and is sifted 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. The prediction was that below its buffer the heap would write 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 product would fall from 1.87 back towards 1.29. It named the risk: 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 might fetch more lines and lose on misses what it saves on write-backs.

The heap, traced as the sorted buffer was #

The keys, buffers and charges are the earlier essay’s: 8,192 random keys, buffers of 16, 64 and 256 cells, every access recorded with whether it writes, and the trace replayed through LRU with write-allocate and write-back in lines of eight cells — a miss fetches the line whatever the access, a write marks it dirty, evicting a dirty line costs a second transfer, and lines still dirty at the end are written back too. The heap’s trace is built the same way as the sorted buffer’s: the input and a bookkeeping cell read at every value, the root read to compare, every cell a sift-up or sift-down reads or writes, the in-place heapsort at the end of each scan read and written cell by cell, and the output written once in order. The heap family outputs the keys in order, which the trace checks.

A third written back, as predicted #

With a buffer of 64 cells, the heap writes back 33% of the lines it brings in at 32 cells of fast memory and 23% at 64, where the sorted buffer writes back 45% and 40%: a sift-down writes one path, not a tail. At 32 cells, the memory where both buffers’ products are least, the prediction’s third is exact. At 64 cells — the memory that holds the buffer and nothing else — the heap’s share is under a quarter, because its root and the first levels below it, which every sift-down touches, stay resident while the deep levels are written only by the sifts that reach them. The sorted buffer’s writes spread over its whole length on every insertion, and at 64 cells it still sends back two lines in five.

Below 32 cells both buffers’ write-back shares fall, because at 16 cells of fast memory the buffer cannot stay resident at all and almost every transfer is a fresh read of the input or the buffer. Above the buffer’s size the shares fall for the other reason: the buffer stays resident, and what goes back dirty is mostly the output, a line for every eight keys written.

A product that falls, but not to the floor #

The heap buffer’s least transfers × fast memory, with write-backs charged, is 1.71 of $n^2/B$ at 32 cells against the sorted buffer’s 1.87 — down by 8%, not to the 1.29 both reach on reads alone: at that memory the heap still writes back a third of what it reads. The prediction’s share was right and its conclusion did not follow from it. A product counted in transfers rises with write-backs in proportion to their share of reads: at a share of 45% the sorted buffer’s product was 1.29 × 1.45, about 1.87, and at a share of 33% the heap’s is 1.29 × 1.33, about 1.71. To bring the product “towards 1.29” the write-backs would have had to fall towards nothing, and a buffer that changes while the scan runs, smaller than the memory that holds it, writes some of its lines back on every scan whatever its shape.

The reads are the same for both at this buffer: the least read-side products are 1.288 for each, at the same memory, because at 32 cells of fast memory the misses are mostly the input’s and the input is read the same way by both. The heap’s read pattern, the risk the proposal named, costs nothing here.

Three buffers #

By buffer: with write-backs charged, the heap brings the family’s least product from 2.30, 1.87 and 2.39 to 2.35, 1.71 and 1.62 of $n^2/B$ at buffers of 16, 64 and 256 cells — no help at 16, where a shift is short, 8% at 64, and 32% at 256, where it comes within 0.05 of the sorted buffer’s product on reads alone. At 16 cells a shift moves on average eight entries, a line, and a sift-down crosses four levels in two lines; there is nothing for the heap to save, and its extra reads at the end of each scan cost it two hundredths. At 256 cells the heap’s least product with write-backs, 1.62, is within 0.05 of what the sorted buffer of that size reached with no write-backs charged at all, 1.58 — and the heap’s own reads-alone product is 1.04, a figure no buffer reached on the earlier charge, where the floor was said to be 1.29.

That last number needs care. The “floor” of 1.29 was the best the sorted family reached; it was a measurement, not a bound, and the heap moves it. At 256 cells the heap family’s reads alone come to 1.04 of $n^2/B$ at 32 cells of fast memory, a quarter under the sorted family’s best, because the sorted buffer was paying for its shifts in reads as well as in write-backs, and at a large buffer that was most of what it read.

What the shifts were costing #

The heap also does less: at a buffer of 256 cells the family makes 6,936,087 accesses with a sorted buffer, 3,160,844 of them writes, and 1,470,607 with a heap, 417,955 writes — the shifts were most of the sorted buffer’s work, and at 16 cells, where a shift is short, the two do the same. Both buffers make the same 32 scans at 256 cells and read the input the same 262,144 times. The difference is entirely inside the buffer: a sorted buffer of 256 takes each new value with a shift of up to 256 entries, every one read and written, while a heap’s sift-down is eight levels with two reads and two writes a level, and most values do not enter the buffer at all once it has filled with small ones.

So the earlier essay’s account of the family was right about where its write-backs came from and understated what the buffer cost. Its shifts were a quadratic piece of work inside a linear scan, and at small buffers they were cheap enough to hide; at 256 cells they were five times the rest of the family’s accesses combined. The writes nobody counted found the same kind of thing in sorts that were called read-only: a structure that holds the answer while it is built pays for building it.

The risk that did not arrive #

The risk named for the heap — reads that jump between lines — does not appear: with a buffer of 256, at 64 cells of fast memory the heap misses 174,827 times against the sorted buffer’s 462,204, and at 128 cells 90,719 against 378,099; its write-backs fall further, so its transfers are under the sorted buffer’s at every memory below the buffer. A sift-down does jump between lines, and at small memories each jump is a miss; but it makes eight of them where a shift makes a hundred-cell sweep, and a sweep across lines that are not resident is a miss per line too. Above the buffer, at 512 cells of fast memory, the heap pays slightly more, 47,330 transfers against 40,431, because its end-of-scan heapsort reads the resident buffer in a scattered order and touches lines the sorted buffer, already in order, does not need to touch again.

So the proposal’s risk was the right kind of worry — a heap’s access pattern is worse than an array’s — and the wrong size. The pattern’s cost is set by how many accesses there are as well as by how they jump, and the heap’s are a fifth as many.

Why a third is what a resident root pays for #

The heap’s third at 32 cells of fast memory has a shape that follows from the memory, not from the heap. Thirty-two cells are four lines. The input is read sequentially and occupies one of them at a time; the bookkeeping cell and the output line take two more, roughly; and what is left is about one line for the buffer, which a 64-cell heap spans eight times over. Every sift-down that goes below the root’s line fetches a line, modifies it and, at the next sift that goes elsewhere, evicts it dirty. A third written back is the share of fetches that come from those sift-downs rather than from the input, and it would be the same for any buffer shape whose writes cannot stay resident between insertions. The cliff where the data stops fitting found the same arithmetic for whole arrays: below the memory that holds the working set, the cost is set by how often the working set is revisited, not by how it is laid out.

At 64 cells the heap’s root and the levels just below it, the cells every sift-down touches, stay resident, and the share falls to under a quarter, while the sorted buffer, whose writes reach every line of its length on most insertions, still writes back two lines in five. That is the difference between the two shapes that the replay can see: a heap concentrates its writes where they are cheapest to keep, a sorted array spreads them evenly. One access, eight kilobytes put the same point in other units: what a structure costs in transfers depends on how many of its accesses share a line, and a heap’s upper levels share one far more often than a sorted array’s tail does.

The model a bound was quoted in is the reminder that applies to every number above: they are LRU transfers in lines of eight cells, a model that charges a scattered access and a sequential one the same once both miss. On hardware that prefetches sequential lines, the sorted buffer’s sweeps would be cheaper than this replay says, and the heap’s advantage at large buffers smaller.

A floor that was a measurement #

The closing question was whether the read-only family’s best point on this product was a property of reading its input only, or of the structure it kept its buffer in. It was mostly the structure. The family’s input is still read once a scan and never written, and that is what keeps its write-backs low at memories above its buffer; but below the buffer, which is where its products are least, the buffer decided both the write-backs and, at 256 cells, the reads. A floor under a product derived a lower bound for this kind of product, and the 1.29 the sorted family reached was a measurement above that bound; the heap family’s 1.04 on reads is another measurement, nearer it.

None of this brings the family near the in-place sorts. Quicksort’s least product with write-backs is 0.095 of $n^2/B$ at 16 cells of fast memory, seventeen times under the heap family’s best, because it needs almost no fast memory to sort, and a product with fast memory as a factor rewards that. The family is the right design for a different question: what a sort costs when its input must not be written, which in place is a claim asked of every sort on the site.

What the replay does not count #

One machine model. LRU with write-allocate in lines of eight cells. A memory that did not allocate on a write, or one whose write-backs were buffered and coalesced, would charge the sorted buffer’s sweeping writes less than this replay does.

Comparisons are free. The product counts transfers, not the work of comparing. The heap family makes fewer accesses, so it would also be faster on a model that charged work, but that was not measured separately.

One size of input. 8,192 keys. The family’s scans grow as $n/S$, and the buffer’s share of the work grows with $S$, so the gap between the buffers at 256 cells would widen with larger buffers on larger inputs.

Still open: a heap that keeps its upper levels in a line #

The heap’s write-backs at its best memory are still a third of its reads, and the plate showing them says where: the deep levels, which a sift-down reaches on only some insertions and which are evicted dirty between them. A heap laid out so that each subtree of three levels — seven cells, with a spare — sits in one line of eight would make a sift-down’s path cross a line only every three levels, about a third as many lines as the plain array heap, whose children of cell $i$ are at $2i + 1$ and $2i + 2$ and leave the line after the first level.

The measurement that follows lays the buffer out that way, a blocked heap with the same comparisons and moves, and replays it at the same buffers and memories. The prediction is that at a buffer of 64 cells the write-back share at 32 cells of fast memory falls from 33% to about 15%, and the family’s least product from 1.71 to about 1.5. It could fail on the end-of-scan heapsort, whose extractions sift through every level and would then dominate the writes, or on the blocked layout’s own arithmetic — its parent and child cells take more computing, which the replay does not charge, so a gain would be a gain in transfers only. The question is whether the family’s product can be brought to its read-side figure by arranging what it writes, or whether a buffer that changes inside a scan always pays some fixed share to the memory that cannot hold it.