Measuring what an algorithm keeps

The instrumented array this site is built on counts four things: reads, writes, comparisons and swaps. Every claim on the site descends from those four, and there is a whole class of true statements about algorithms that none of them can express.

Take merge sort and heapsort at $n = 4{,}096$ on random input. Merge sort makes 43,976 comparisons, heapsort makes 85,733; merge sort makes 49,152 writes, heapsort makes 91,158. Four counters, four numbers each, and by all eight of them merge sort is the better algorithm and heapsort is the one with the worse constants.

Merge sort also needs a second array of 4,096 elements and heapsort needs nothing. That is not a small difference — it decides whether either of them can be run at all on a machine with the input and a little slack — and it appears in none of the eight numbers.

This is a gap in the instrument, not in the coverage. No amount of measuring more carefully with the existing counters produces it, because nothing that merge sort does to its buffer goes through them.

Two primitives #

The counted array gains two pairs of operations, and each pair exists because one specific thing was invisible.

alloc(k) and free(k). Scratch space taken and given back. Merge sort’s buffer is now a line of code that costs something rather than a new Array(n) that costs nothing. The counters record both the live total and the running sum, for reasons the next section is about.

enter() and leave(). A call entered and returned from. This is the one that matters more, and it is worth being clear about why: a call stack is auxiliary space. Quicksort allocates nothing, touches no scratch array, and holds a frame per level of recursion for the duration of the run. Every account of the algorithm calls it in-place; the recursion is real memory, it is proportional to the depth, and no counter that watches the array will ever see it because the stack is not in the array.

Both pairs charge in slots — one array element, or one stack frame. That is a cost model and it is the wrong one for any particular machine: a frame holding four locals and a return address is not the same size as one element of an array of 200-byte records. It is the right one for comparing algorithms, because it is the only unit that does not depend on the element type, and every figure that reports these numbers says what it is counting.

One further decision, small and load-bearing. The call into the algorithm is itself charged as a frame, so an in-place sort’s peak is 1 rather than 0. Reporting zero would be defensible and would make the constant class unfittable — a ratio of $0/1$ is not a constant, it is a missing measurement — and with the outer frame charged, heapsort’s peak is 1 at every $n$ and the class fits exactly.

Peak and total are different questions #

The counters keep two numbers where one would have been simpler, and the reason is that they answer different questions and neither answers the other’s.

Peak is the most held at one moment. It is the number a memory limit is about: a program that peaks at 2 GB needs 2 GB, whatever it did before or after.

Total is everything ever taken. It is the number an allocator’s workload is about, and a garbage collector’s, and anything charging per allocation.

They can differ by any factor. The site carries two merge sorts to make this concrete — one allocating a single buffer at the start, one allocating a buffer per merge and freeing it — and they have byte-identical comparison, read and write counts. At $n = 16{,}384$:

The peaks agree to within the depth of the recursion. The totals are a factor of 14 apart, and 14 is $\log_2 16{,}384$.

This is the amortised-versus-worst-case distinction one level down, applied to a resource rather than to an operation. A single number called “space complexity” answers whichever of the two questions its author had in mind, and the reader has no way to tell which.

What the measurement immediately shows #

With the instrument built, the sorts fall into three bands, and the bands are not what the vocabulary suggests.

The classes are fitted, not asserted. Peak auxiliary space is put through the same ratio test the comparison counts get: across $n$ from 128 to 32,768, heapsort’s peak ÷ 1 has a spread of 1.00, quicksort’s peak ÷ $\log n$ has a spread of 1.20, and merge sort’s peak ÷ $n$ has a spread of 1.07. An algorithm whose space claim failed would stop the build in exactly the way one whose time claim failed does — and one of them does fail, on one input.

The middle band is the interesting one, because it has no name. The vocabulary offers “in place” and “not in place”, and the three quicksorts are neither. They allocate nothing and hold a stack of about $\log_2 n$ frames, which is 22 slots at $n = 4{,}096$ and 4,097 slots on an input that makes the recursion go badly. Calling that Θ(1) is the standard description and it is wrong; calling it Θ(n) would also be wrong; there is no third word.

The same instrument, on a graph #

Sorting is the easy case for a space instrument, because a sort’s auxiliary space is a buffer and a stack and both are countable at the point they are taken. A traversal is harder, and it is where the instrument earns its place rather than merely working.

Breadth-first and depth-first search over the same graph perform identical counted work — the same adjacency scans, the same visits, exactly. Every counter this site had before this phase reports them as one algorithm. What separates them is how many vertices are held at once, and on a 32 × 32 grid that is 32 for breadth-first against 496 for depth-first: a factor of fifteen, in a quantity that had no instrument.

Two things about that measurement are worth carrying back to the sorting case.

It is not a peak of allocations, it is a peak of a data structure’s occupancy. Nothing here calls alloc; the queue and the stack are ordinary arrays that grow and shrink. Counting their occupancy needs the algorithm to report it, which the traversals do, and that is a different instrument from alloc/free even though it measures the same resource.

It is a property of the graph as much as of the algorithm. On a random sparse graph of 1,024 vertices the two frontiers are 569 and 553 — indistinguishable. The grid’s factor of fifteen comes from the grid’s shape: a small frontier and a large diameter, which is exactly the combination that separates the two traversals. The received advice that breadth-first search uses more memory than depth-first is true on a grid, false on a random graph, and stated about neither.

The general lesson is the one this whole field is an instance of: a resource that nothing measures is a resource about which the folklore is unchecked. Space was not measured here before this phase, and the two claims the measurement immediately contradicted — that quicksort sorts in place, and that depth-first search is the memory-frugal traversal — were both things everybody knew.

The naming problem, recorded because it nearly caused a bug #

The plan for this phase called the recursion primitive frame(). That name was already taken: the counted array has had a frame() method since the foundation, which records a snapshot of the array for the trace figures, and every step-by-step picture on the site depends on it.

Two meanings of “frame” — a stack frame and a frame of animation — in one class, one of them about to be added silently. Adding it would not have failed to compile. It would have overwritten the snapshot method, and every trace figure would have started producing empty panels while every space measurement worked perfectly.

The pair is enter/leave for that reason, and the collision is worth recording rather than quietly avoiding, because it is the shape of mistake this whole site is organised against: a change that breaks something silently and elsewhere.

Why the counters are in the array #

A design decision worth stating, because the alternative is more obvious and is wrong.

The space counters could have lived outside the algorithms — a wrapper that inspects memory before and after, or a profiler that samples. Instead they are methods on the counted array, and every algorithm that wants scratch has to ask for it by calling alloc.

That is intrusive. It means merge sort’s implementation contains a line whose only purpose is to be counted, and it means an algorithm can lie by allocating without saying so.

It is the right trade for the same reason the operation counters are inside the array rather than beside it. A measurement taken from outside is a measurement of the runtime — of V8’s heap, of this machine’s allocator, of whatever the garbage collector felt like doing — and would change between builds and between machines. A measurement taken at the point of use is a property of the algorithm and the input, exact and identical everywhere.

The lying is handled the way it is everywhere else here: not by preventing it, which is impossible, but by cross-checking. assertPeakAndTotalAreIndependent requires the two merge sorts to agree in every time-flavoured count and to differ by exactly $\log_2 n$ in total allocation. An implementation that forgot an alloc would fail that, because the ratio would be wrong.

What this cannot say #

Four limits, and the third is the one that most affects how the numbers should be read.

A slot is not a byte. Everything here counts slots. Comparing merge sort’s $n$ buffer slots against quicksort’s $\log n$ stack slots as though they were the same unit is a simplification, and on a real machine a stack frame for a two-argument recursive call is perhaps five to ten words while an element might be one word or fifty. The direction of the error is knowable: it understates the stack relative to the buffer, so quicksort’s disadvantage against heapsort is a little larger than these figures show.

Auxiliary means auxiliary. None of these numbers includes the input. That is the standard convention and it is the right one for comparing algorithms, and it means an in-place sort of $n$ elements is not using one slot of memory, it is using $n+1$. When the question is “will this fit”, the input is most of the answer and the auxiliary space is the part that decides whether the answer is nearly.

The allocator is not modelled. Real allocations have headers, alignment and fragmentation, and a program that takes 229,376 slots in 16,383 separate allocations is doing something quite different from one that takes them in a hundred. The total column counts slots and not allocations, and the two rankings would not agree.

Nothing here is a duration. As everywhere on this site, the count is not the time, and space is if anything further from time than the operation counts are — a large buffer is free if it is written once sequentially and ruinous if it competes for cache with the array being sorted. The interaction between the two axes is real and neither instrument sees it.

There is a third number, and its ratio is a thousand times the second’s #

The limit stated above — that the total column counts slots rather than allocations, and that the two rankings would not agree — can be filled in from the same pair of merge sorts, and the result is sharper than the caution suggests.

A merge sort’s recursion over $n$ elements has $n$ leaves and $n-1$ internal nodes, and the per-merge version takes a buffer at each internal node. So at $n = 16{,}384$ it makes 16,383 allocations where the one-buffer version makes one. The slots are the same 229,376 either way, spread over those calls at a mean of fourteen slots each — which is $\log_2 n$, and is the same logarithm arriving for the third time in this comparison.

Set the three ratios beside each other. Peak: 1.001. Total slots: 14. Allocation count: 16,383. Three quantities describing the same difference between the same two implementations, spanning four orders of magnitude, and all three are covered by the phrase space complexity $\Theta(n)$.

Which of the three is the cost depends entirely on what is underneath, and the three runtimes want three different answers.

A bump allocator — a pointer moved forward, freed all at once — makes an allocation nearly free, so the count is irrelevant and the total slots are the cost, paid in the cache lines that have to be touched and zeroed.

A general-purpose allocator puts a header on every block, walks a free list and may take a lock. Sixteen thousand allocations of fourteen slots is the case it is worst at: two words of header against fourteen of payload is a fourteen per cent overhead at this size, and at $n = 128$ the mean allocation is seven slots and the overhead is twenty-nine per cent. Here the count is the cost and the slots barely matter.

A garbage collector charges by what survives and by how much has been allocated since the last collection, so the total slots drive the collection frequency and the count drives nothing. Here the middle number is the one.

So the three numbers are not a refinement of each other. Each is the right measurement for a different implementation of the same primitive, and an algorithm that is a factor of fourteen worse on one and a factor of sixteen thousand worse on another is not “worse on space” in any single sense.

The pair of merge sorts is therefore a better instrument than it looked. It was built to show that peak and total are independent; it also shows that total slots and allocation count are independent, in the same direction and by a much larger factor. And it is the same shape of question choosing a growth factor asks of a dynamic array from the other side — there the algorithm decides how often it allocates and how much it wastes, and the answer depends on which of those the runtime charges for.

None of which changes the amortised argument. Both implementations move the same data the same number of times, and the extra 229,375 allocations buy nothing at all — which is what amortised means applied to a resource: the total is what an allocator sees, and the per-operation figure is what hides it.

Why the axis was worth adding #

Three things become sayable that were not, and each has an essay.

“Sorts in place” becomes a claim that can fail. It fails for quicksort, in a specific and measurable way, and most spectacularly on the input everybody tests with.

The recursion becomes visible. A stack is not free, it has a size limit that is not a soft one, and an algorithm can be killed by its auxiliary space rather than slowed by it.

“Which sorting algorithm” gets an honest answer. Comparisons on one axis and peak space on the other gives a Pareto frontier, and the frontier has four or five algorithms on it and five below it. The ones below it are dominated — beaten on both counts at once — which is a much stronger statement than being slower.

The profile at four settings #

The instrument is a peak over one run, so the useful thing is to run it on four of them.

The two below hold the size fixed and change only the order, which is the parameter no description of an algorithm’s space ever mentions.

The pattern this is an instance of #

The site’s other fields arrived at the same place from different directions, and it is worth naming the pattern because it is now the third time.

The comparison count was the only measurement, and it turned out to be one of four — reads, writes, comparisons and swaps rank the same algorithms in different orders. Then the four operation counts turned out to be one side of a second quantity, because modelled cache misses disagree with all of them. Now all five turn out to be measurements of one resource, and there is a second resource that none of them touches.

Each step has the same shape: a number that seemed complete, a second number that is independent of it, and a ranking that changes. There is no reason to expect this to be the last one, and the honest reading of the site’s whole cost model is not “here are the numbers that matter” but “here are the numbers that have been found so far, and each of the last three was invisible from inside the previous one”.

What it cost to add #

Two methods on a class, a few alloc calls in three algorithms, and a decision about what a slot is. The instrument is smaller than any of the arguments it makes possible, which is the usual proportion here: the counted array is a hundred lines and the counting field is four essays long.

What the additions bought is the ability to say a number where the vocabulary previously offered a phrase, and the first three numbers it produced all disagreed with something everybody knew.