The space the model does not see

The space counters are the newest instrument on this site and every other one is a phase older. That is a reason to be more careful about them rather than less, and this essay is the account of what they do not measure — written while the gaps are still obvious, rather than after the numbers have been quoted often enough to feel like facts.

There are six limits and one abandoned result.

A slot is not a byte #

Everything here is counted in slots: one array element, or one stack frame, each charged as one.

An array element might be a 32-bit integer, a 64-bit pointer, or a 200-byte record held by value. A stack frame for a two-argument recursive call is perhaps five to ten machine words on a typical calling convention, and for a function with a dozen locals rather more. So merge sort’s 4,096 buffer slots and quicksort’s 22 stack slots are being compared in a unit that means different things on the two sides.

The direction of the error is knowable, which is the most that can be said for a simplification.

A frame is usually bigger than an element. So quicksort’s stack is undercounted relative to merge sort’s buffer, and quicksort’s space advantage is a little smaller than the figures show. At 22 slots against 4,110 that changes nothing; on a sorted input where the depth reaches 4,097, it means the two algorithms are not merely comparable but that quicksort is probably using more memory than merge sort.

An element can be enormous. Sorting 200-byte records by value, merge sort’s buffer is 800 KB for 4,096 elements and quicksort’s stack is a few hundred bytes. The ratio the figures show — 4,110 to 22, about 190 — understates the real ratio by a factor of twenty or more.

So the slot unit is right for comparing algorithms and wrong for sizing a program, in the same way that the comparison count is right for comparing algorithms and wrong for predicting a duration. It is chosen because it is the only unit that does not depend on the element type, and every figure prints what it is counting.

The input is not in any of these numbers #

“Auxiliary space” means space beyond the input, and that is the standard convention. It is also the convention that makes the whole field look more decisive than it is.

Heapsort’s peak is 1. Heapsort’s memory requirement is $n + 1$.

When the question is “which algorithm uses less memory”, the auxiliary convention is right, because the input is common to all of them and a common term cancels. When the question is “will this fit”, the input is almost all of the answer, and the difference between $n$ and $2n$ is the difference between fitting and not — which is precisely the situation in which anybody cares.

So the frontier plot’s vertical axis spans a factor of four thousand and the actual memory requirements it corresponds to span a factor of two. Both are true and they answer different questions, and only one of them is drawn.

An allocation is not a slot #

The total column counts slots taken, not allocations made. Those are very different workloads for an allocator.

The per-merge merge sort at $n = 16{,}384$ takes 229,376 slots in 16,383 separate allocations — one per merge. Plain merge sort takes 16,384 slots in one. The slot ratio is 14; the allocation ratio is 16,383.

Which of the two an allocator cares about depends on the allocator. A bump allocator with a garbage collector behind it charges almost nothing per allocation and everything per byte, so the slot count is the right measure. A general-purpose heap allocator charges a header, an alignment gap and a free-list operation per allocation, so at 16,383 allocations of an average of fourteen slots each, the overhead may exceed the payload. A pool allocator sized for the largest block charges nothing extra for either.

The counters cannot distinguish these because they do not model an allocator at all. alloc(k) records $k$ and moves on. That is a deliberate choice — modelling an allocator would mean choosing one, and the choice would be doing as much work as the measurement — and it means the total column should be read as “how much scratch is churned” rather than as a cost.

The same gap appears one level down, in the argument for a growth factor of 1.5: whether previously freed blocks can be reused depends entirely on coalescing behaviour that the site models not at all.

Where the sixteen thousand allocations actually are #

The overhead may exceed the payload is the right worry and it is two claims, one of which the arithmetic supports and one of which it does not.

The distribution is exact. A merge sort of $n$ elements performs $n/s$ merges at each size $s = 2, 4, \ldots, n$, so the allocations number $n-1$ and the slots total $n\log_2 n$ — 16,383 and 229,376 at $n = 16{,}384$, which is where the mean of fourteen comes from.

But a mean of fourteen over that distribution is misleading in the usual way. Half of the allocations are two slots long. A quarter are four. Ninety-four per cent are under thirty-two, and between them they hold 28.6% of the slots.

So the aggregate claim fails and the per-allocation one holds sharply. Total overhead is one header per allocation, so overhead over payload is $h/14$ for a header of $h$ slots — 14% at a two-slot header, 29% at four, and it would take a 112-byte header to exceed the payload in total. On the two-slot allocations, which are half of them, a two-slot header is 100%.

That distinction is worth keeping because it points at the fix. The problem is not that 229,376 slots are churned; it is that 15,000 of the requests are for a handful of slots each, and a request for two slots is dominated by whatever the allocator charges for existing.

Capping the allocations at thirty-two slots removes 94% of them and touches 29% of the bytes — the small merges are served from one reused scratch buffer and the large ones keep their own. That is one comparison in the merge routine, and it converts the allocation count from $\Theta(n)$ to $\Theta(n/32)$ while leaving the slot count exactly where it was.

It also lands on the same boundary a library merge sort already has for a different reason. Every practical implementation stops recursing at some small size and finishes with insertion sort, and the sizes it stops at are exactly the ones producing these allocations — so the cutoff that exists to save comparisons removes almost all of the allocation overhead as a side effect, and nobody credits it with that.

Which is the essay’s own point turned on the counter rather than on the algorithm. The total column reports slots, the allocation count is not in it, and the two are related by a distribution the plate does not draw — so how much scratch is churned and how many times an allocator was asked diverge by a factor that is itself a function of $n$. Measuring what an algorithm keeps charges one number and choosing a growth factor is about the other, and this is the one place on the site where both are visible in the same run.

Fragmentation, and the peak that is not the peak #

Peak auxiliary space is the maximum, over the run, of the number of slots live at once. On a real machine the number that matters is the maximum address range the process needs, and those differ whenever memory is freed and reallocated in a pattern the allocator cannot pack.

A run that alternately takes and frees blocks of 1,000 and 1,001 slots has a peak of 1,001 by this measure and may have a resident set several times that, because each freed 1,000-slot hole is one slot too small for the next request. That is fragmentation and it is invisible here.

It is worth naming because the per-merge merge sort is exactly the pattern that produces it: 16,383 allocations of every size from 2 up to $n$, in an order determined by the recursion. Its measured peak equals plain merge sort’s; its real resident set under a naive allocator would not.

The interaction with the other axis #

The most important omission is not about space at all. It is that the two axes on the frontier plot are not independent in the way the plot implies.

Merge sort’s buffer is not merely a cost. It is the reason its access pattern is a clean sequential write into scratch rather than an in-place shuffle, and the reason its modelled miss counts are the best on the site. The memory it takes is buying the locality that makes it fast.

Heapsort’s zero auxiliary space is not merely a benefit. It sifts within the array, jumping by powers of two, and its miss counts are the worst here. Taking no memory is costing it locality.

So a plot with comparisons on one axis and space on the other is drawing two quantities that trade against each other through a third the plot does not show. An algorithm that used more space might be faster because of it. Nothing in the frontier can express that, and the honest statement is that the frontier is a lower bound on the set of reasonable choices rather than a description of the trade.

One process, one thread, one moment #

Peak auxiliary space, as counted here, is the maximum over one sequential run of one algorithm. Three ordinary situations make that the wrong quantity and none of them is modelled.

Concurrency. Eight threads each running a sort with peak $S$ need $8S$ at once, and a parallel merge sort that splits the array and merges the halves needs a buffer per branch that is live simultaneously rather than sequentially. The peak of a parallel algorithm is not the peak of its sequential form, and the sequential form is what is measured here.

Nesting. Sorting inside a recursive procedure that also holds state means the sort’s peak adds to whatever the caller was already holding. That is exactly the situation in which a stack overflow arrives earlier than the measurement suggests, and it is why the real threshold moves between call sites.

The rest of the program. A peak of 4,096 slots is nothing in a program with a megabyte to spare and fatal in one already at its limit. The measurement is a property of the algorithm; whether it fits is a property of everything else.

All three are the same omission: the counters describe an algorithm in isolation, and memory is the resource for which isolation is least realistic, because it is shared with everything running at the same time in a way that a comparison count never is.

The bound that was attempted and cut #

This phase’s plan named one more thing for this field, and it is not here.

Borodin and Cook’s theorem gives, for sorting in a branching-program model with restricted workspace, a bound on the product of time and space: $TS = \Omega(n^2)$. It is a remarkable result because it is a bound on a combination rather than on either quantity — no amount of trading one for the other escapes it — and it would have been the floors field’s first bound of that kind, beside the leaf-counting one and the adversary one.

It is not here because it could not be measured honestly at this site’s scale, and the plan said in advance to cut it if it could not.

Three things stood in the way, and the third is the decisive one.

The model is restrictive in a way this instrument cannot reproduce. The bound is about branching programs with $S$ bits of workspace, where the only memory an algorithm has is those $S$ bits and the read-only input. The counted array measures how much scratch an algorithm chooses to take; it has no way to restrict an algorithm to a workspace and force it to work within one. Demonstrating the bound needs the second, not the first.

The interesting regime is unreachable. The product bound bites where $S$ is genuinely small — around $\sqrt n$ or below — and where the algorithms are the specialised space-restricted sorts designed for exactly that setting. The algorithms measured here occupy three widely-separated bands, of which one is $\Theta(1)$ and one is $\Theta(n)$, and the product $TS$ for the $\Theta(1)$ band is dominated entirely by $T$ because $S$ is literally one.

Measuring $TS$ over the existing algorithms would produce a plot that looks like a demonstration and is not. Multiply each point’s comparisons by its peak slots and a curve appears, bounded below, rising like $n^2$ — and it would prove nothing, because it is a plot of ten arbitrary algorithms rather than an exploration of the trade the theorem is about. Publishing it would be exactly the failure this site exists to avoid: a picture whose shape is suggestive and whose content is a quotation.

So the theorem is stated here, credited, and not drawn. What would be needed to draw it honestly is a space-restricted sorting algorithm — one parameterised by a workspace budget $S$, correct for every $S$ from $O(1)$ upwards, with the instrument enforcing the budget rather than reporting it — and then a sweep of $S$ showing $T$ rising as $S$ falls, with the product bounded below. That is a phase’s work rather than an essay’s, and it would be a genuinely good phase.

The output is not counted either #

There is a sixth omission that is easy to miss because the sorting field hides it: an in-place sort writes its answer over its input, and a non-comparison sort usually does not.

Counting sort on 256 values from eight distinct ones spends 520 operations, which makes it look free beside merge sort’s 1,682 comparisons. It also needs a counter array of size $d$ and an output array of size $n$, so its auxiliary space is $\Theta(n + d)$ — the same band as merge sort, and larger than everything in the constant band. Radix sort needs the same, several times over if it is not careful about buffer reuse.

The site’s space instrument would report that correctly if counting sort were implemented against the counted array, and it is not: counting sort does not compare, so it does not fit the algorithm interface that everything else here uses. Its numbers in the floors field are operation counts computed from a formula rather than from an instrumented run, and its space is not reported at all.

That is a genuine hole and it is worth naming rather than leaving as an absence. The linear-time sorts win on the axis the floors field measures and lose on the axis this field measures, and only one of the two comparisons is currently drawn.

What would make these numbers into bytes #

A recurring question about every model on this site is what it would take to close the gap, and for this one the answer is unusually concrete.

Parameterise the element. Give the counted array an element width in words and charge alloc in words rather than slots. Charge a frame at a stated width too — four words, say, printed on the figure the way the cache model’s line size is. That converts every number here into words, at the cost of one more model parameter and one more thing to state.

Model an allocator. Choose one — a size-class allocator is the common case — and charge a header and an alignment gap per allocation. That would make the allocation count matter, and it would mean the numbers describe that allocator rather than allocation in general, which is the same bargain the cache model already makes.

Track a high-water mark of the address range rather than of live slots, so fragmentation becomes visible. This is the hardest of the three and the one that would change the per-merge merge sort’s headline number.

None of those is done, and the reason is the same in each case: each adds a parameter, each parameter is a choice, and each choice makes the numbers less portable in exchange for making them more concrete. The site’s standing bargain is to prefer portable numbers with stated gaps, and this essay is the statement of the gaps rather than a promise to close them.

Peak against total, four ways #

The two numbers are different numbers, and the whole page turns on that — so it is worth showing that the gap between them is not an artefact of one input at one size.

Neither of those changes the input, and the input is the parameter a bound is least likely to mention — yet it is the one that decides how deep a recursion goes and therefore how many frames are live at the peak. The next two plates hold the size fixed and move it.

Reversed input is the last of the four, and it is the one a quicksort with a naive pivot rule is worst on — which is where a peak and a total come furthest apart.

What all of this is an instance of #

Every field on this site has arrived at the same place, and the space field arrived faster than the others because it is newer.

The comparison count is exact and machine-independent and is not a duration. The cache model is exact given its parameters and its parameters are a choice. The graph counts sum four operations of different kinds into a unit that no machine charges. And the space counts are in a unit that is neither bytes nor allocations and exclude the largest term.

In every case the instrument is honest, the numbers are exact and reproducible, and the gap between the number and the thing anybody cares about is real and is stated. What makes that a method rather than an excuse is the direction: each of these gaps has a known sign, and where the simplification favours one side of a comparison, the essays say which side.

The alternative — measuring the thing anybody cares about — means measuring a duration on a machine, and that is a different project with a different set of things it cannot say.