A product paid for in blocks

A floor under a product measured the published lower bound on sorting that constrains time and space together: $T \cdot S = \Omega(n^2)$ in a model where every read costs one, and where space counts every cell an algorithm can write, including the array it sorts in place. It built the family that meets the bound. The family never writes its input: it keeps the $S$ smallest keys not yet output in a buffer of $S$ cells, scans the whole input to fill it, emits them, and scans again, $\lceil n/S \rceil$ times. Its product came out at exactly $n^2(1 + 3/S)$, and every in-place sort, counted the way the bound counts, sat far above it. Quicksort’s comparisons times its $n$ writable cells were about fifteen times the family’s product.

Its closing section noticed something the bound says nothing about. The family’s reads are sequential — it runs through the input from one end to the other, time after time — and the sorts it was compared with are not. One access, eight kilobytes priced that difference: the same 65,536 accesses cost 1,024 block transfers in one order and 65,536 in another. So in transfers rather than reads, the family’s time should fall by a factor of the block size $B$, and heapsort’s, which sprays its accesses across the heap, should not. The section predicted that the family’s advantage would widen from fifteenfold towards $B$. It also predicted that the order among the sorts would change, since the three quicksorts sit within a factor of 1.1 of each other in reads and differ in locality.

The replay confirms half of that and moves the floor.

Replaying the sorts through a block memory #

Every sort is run on 8,192 keys in random order with its accesses recorded — each read and write of the array, in order — and the trace is replayed through the memory model the transfer pages use: a fully associative memory of $M$ cells in lines of $B$ elements, least recently used replaced. A transfer is a line fetched. The sorts are heapsort, quicksort with three pivot rules, and Shellsort, all of which work inside the array. Merge sort is left out because its buffer’s accesses are not in the traces it records, so its transfers would be undercounted. Space is what the bound counts: $n$ writable cells plus whatever a sort allocates, and for the family its buffer plus three cells of bookkeeping. The family’s scans are sequential by construction, $\lceil n/B \rceil$ transfers each, and its output is written once in order.

Counting every access as one — every read and write, where the earlier page counted comparisons — puts quicksort with a random pivot at 43 $n^2$, heapsort at 94, Shellsort at 60, and the family at 1.04. Every sort is dearer by this count than by comparisons, because each comparison comes with reads and each swap with writes.

In transfers, the family’s product falls as $1/B$ — 1.04 $n^2$ at a line of one element, 0.13 at eight, 0.016 at 64 — and quicksort’s falls alongside it, 8.2 times the family’s at $B = 8$ and 8.4 times at 64. The prediction had quicksort’s accesses as the scattered kind. They are not. A partition is a scan: two pointers walking towards each other through a contiguous range, every element of which is read once. Each line a partition fetches serves $B$ consecutive reads, exactly as the family’s scans do. So quicksort’s transfers shrink with $B$ at the same rate, and the ratio between the two stays where it was.

Heapsort is the case the prediction was built on, and it behaves as predicted. Its product falls from 10.96 $n^2$ at a line of one to 5.32 at eight and then stops, 4.59 at sixteen and 4.63 at 64. By $B = 64$ it is 285 times the family’s. Where an algorithm looks drew heapsort’s access pattern as a spray between the root and the leaves. A longer line brings in the neighbours of a heap node, which a sift-down will not visit again until it happens back that way.

What a line brings in, sort by sort #

The same numbers divided by the accesses show what locality each sort has. The family pays exactly $1/B$ a read at every $B$: it uses every element of every line once and never returns. Quicksort pays less than that. At $B = 1$ its accesses already miss only a fifth of the time, because once a range is smaller than the memory, it is partitioned to the end without fetching anything twice. At $B = 64$ a transfer serves over three hundred of its accesses. Heapsort’s cost a transfer falls to 0.049 by $B = 16$ and stays there. Past sixteen elements a line, a longer line brings heapsort nothing it uses before the line is evicted.

Shellsort does something the others do not: its cost rises again at the longest line, from 0.015 transfers an access at $B = 32$ to 0.031 at 64. With 512 cells of memory in lines of 64 there are only eight lines. A pass of Shellsort with a large gap compares elements a gap apart, and when the gap spans more lines than the memory holds, every comparison fetches. The longest line gives the least room for anything else, and Shellsort is the one sort here that needs room for several distant places at once.

The floor moves with the block #

The first plate hides the most important fact on this page, because it holds the memory fixed.

With a memory that holds the whole array, every sort’s product in transfers is exactly $n^2/B$ — 0.125 $n^2$ at $B = 8$ — against the family’s 0.130. Each line of the array is fetched once and never evicted, so the sort costs $n/B$ transfers whatever it does, and its $n$ writable cells make the product $n^2/B$. The family’s product is $(n/S)(n/B)(S + 3)$, which is $n^2/B$ plus its bookkeeping. So in transfers the floor is not $n^2$ but $n^2/B$. The counting floor under comparison sorting, which the floor under every comparison sort derived, does not move with the block at all, since a comparison is not a transfer; this floor does, because it is a floor on reading. Every algorithm on the page can reach it, the family with $S$ cells of memory and the sorts with $n$.

That changes what the family’s advantage is. In reads it was an advantage in the product itself: an in-place sort could not get under fifteen times the floor. In transfers the product alone does not separate them, because a sort whose memory holds its input is on the floor. What separates them is the memory each needs to get there. The family reaches $n^2/B$ holding 131 cells. Quicksort needs the whole array in memory to reach it. At 512 cells it is eight times above, and at 2,048 cells five times. The advantage the bound measured in reads becomes, in transfers, an advantage in how much fast memory each algorithm needs to reach the floor. That is a different resource from the $S$ in the product, and the product has no term for it.

The product also hides which algorithm is faster. At $B = 8$ and 512 cells, the family makes 66,560 transfers to sort 8,192 keys: 64 scans of the array at 1,024 transfers each, and one more to write the output. Quicksort with a random pivot makes 8,706, heapsort 43,615. By time alone, counted in transfers, quicksort is seven and a half times faster than the family and five times faster than heapsort. The family’s small product comes entirely from its small space; its time is the largest on the page. A bound on $T \cdot S$ allows exactly that trade, and the family is the algorithm that takes it to its end. A machine with memory to spare would never run it, and a machine with 131 cells would have no other choice.

Eight times at one size, and growing #

Quicksort’s distance from the family grows with $n$, from 2.9 times at 1,024 keys to 13.9 at 32,768, and it grows close to $2\log_2(n/M) + 1$. Each level of partitioning whose ranges are larger than the memory is a full scan of the array, $n/B$ transfers. There are about $\log_2(n/M)$ such levels on random input, and each level’s scan both reads and writes. The family pays one scan for each of its $\lceil n/S \rceil$ buffers’ worth, so its product is fixed near $n^2/B$ while quicksort’s grows by a scan a level. Heapsort’s distance grows much faster, from 7.7 times to 65.1. Its transfers are a fraction of its accesses that does not shrink as the heap outgrows the memory.

A transfer for each level that does not fit #

The two growth rates have simple accounts, and the traces confirm both. Quicksort’s transfers, divided by the $n/B$ of one scan of the array, come to 3.3 scans at 1,024 keys, 8.5 at 8,192 and 14.3 at 32,768. That is close to two for each level of partitioning whose range exceeds the memory, $\log_2(n/M)$ of them, plus the scan that reads the array in. Each such level reads its ranges in order and writes them back in order, and nothing below the memory’s size costs anything further.

Heapsort’s transfers, divided by the number of keys, come to 1.1 at 1,024 keys, 5.3 at 8,192 and 8.4 at 32,768 — between 1.1 and 1.4 for each level of the heap below the memory’s size. A sift-down walks from the root to a leaf, one node a level. The top levels of the heap are few enough nodes to stay in memory; below them each step lands on a node no recent step has touched, and costs a line. A line of eight holds a node’s seven neighbours at its own level, and the sift-down never wants them. A tree with nodes the size of a block found the remedy for search: make a node as wide as a transfer, so that one line carries a whole step’s choices. A heap whose nodes had $B$ children would cut the levels below memory by a factor of $\log_2 B$. Heapsort as written has two children a node, and pays a line for each of its levels.

So both products grow with the same quantity, the number of levels that do not fit. Quicksort pays a scan of the array for each level, $n/B$ transfers, and heapsort pays a transfer per key for each, $n$ transfers. The ratio between them is the block size, which is why heapsort falls behind as the line grows and quicksort does not.

Whether the order changes #

The three quicksorts stay together at the top of every column, within 3% of one another: their pivot rules change which elements are compared, not the order in which memory is walked. The prediction that locality would separate them fails. All three walk their ranges the same way, and a pivot rule changes the split points, which move the transfers by a few per cent. The random pivot is cheapest in every column, as it is in reads.

The order does change lower down. Counting every access, Shellsort’s product is well under heapsort’s, 60 against 94. In transfers with lines of one element, where only the memory’s reuse counts and not the block, heapsort’s is lower, 10.96 against 14.28. That is consistent with heapsort’s upper levels being small enough to stay in memory while Shellsort’s widely spaced passes are not. With lines of eight or more, Shellsort is ahead again, because its passes with small gaps are close to scans and gain from blocks the way quicksort’s partitions do. The count is not the time found the same reordering among sorts timed on a real machine; here it follows from a model with two parameters, $M$ and $B$, and it happens between their settings.

What the replay rests on #

One memory model. Fully associative, least recently used, one level, no prefetching. A real machine has several levels, and a hardware prefetcher would make every scan cheaper still — the family’s and quicksort’s — and would do little for heapsort. The ratio between the scans would not move. The sprayed accesses would lose further ground.

Space as the bound counts it. The product charges a sort $n$ cells for the array it overwrites and the family its buffer. The memory $M$ is a property of the machine and is not charged to anyone. Charging it as well would add $M$ to every sort’s space and $M - S$ to the family’s, and it would stop the sorts reaching the floor: their space would be at least $2n$ once $M$ is large enough to hold the array.

Fetches, not write-backs. A transfer here is a line brought into memory. A real memory must also write a changed line back when it is evicted, and every in-place sort changes most of the lines it fetches, while the family changes none of its input. Counting write-backs would add up to a second transfer for most of each sort’s fetches and nothing to the family’s scans, so it would widen every gap on this page, by at most a factor of two. It was not replayed.

Random input, one seed. Every trace is one run of 8,192 random keys; the pattern of accesses depends on the keys for the quicksorts and heapsort, and a sorted or reversed input would move quicksort with a first-element pivot a long way. What a pass costs when it is a file found the same economy for a streaming selection on a file. A pass is a read of every block, and it is cheap only when the blocks are read in order.

A floor measured, not proved. That every algorithm here sits at or above $n^2/B$ is a measurement on these sorts, of the kind a floor that holds if something else does was careful to label: a claim with evidence and no proof. The published bound is for unit-cost reads, and a proof of $T \cdot S = \Omega(n^2/B)$ in transfers would need its own argument. The measurement says only that nothing here comes under it, and that the family and every sort with a large enough memory come within 4% of it.

Still open: charging the memory the product leaves out #

The product failed to separate the family from quicksort in transfers because it charges quicksort for $n$ cells it writes and not for 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 — transfers, writable cells and fast memory — would say what the two-way product cannot: that the family is on the floor with 131 cells of fast memory, and quicksort needs 8,192 to join it.

The measurement that follows sweeps both $M$ and the family’s buffer $S$, and draws, for each algorithm, the least fast memory at which its product in transfers comes within a stated factor of $n^2/B$. The prediction is that the family’s need is its own buffer, a few hundred cells whatever $n$ is. Quicksort’s should grow as $n / 2^{c}$ for a stated factor $2^c$ above the floor, since each halving of the memory adds a level of full scans. Heapsort’s should be all of $n$, since no memory smaller than its heap keeps it within a constant of the floor. If that holds, the resource the floor under a product was implicitly trading is not space in general but writable space against fast memory. A sort that writes nothing in place needs almost no fast memory to be on the floor; a sort that writes everything in place needs all of it.