Where an algorithm looks

The instrumented array records more than counters. It records the complete sequence of indices touched, in order.

That sequence is a much richer object than any count derived from it. Plotted as index against time it becomes a picture, and the pictures for different algorithms are so distinct that a sorting algorithm can be identified from its trace at a glance — which is a strange thing to be able to say about a quantity that every complexity analysis discards entirely.

Reading the pictures #

Merge sort produces bands. Each merge sweeps two ascending runs and writes an ascending output, so within a merge the accesses climb steadily. The bands get wider and fewer as the recursion unwinds: many short sweeps at the bottom, a single full-length one at the top. The whole picture is made of straight ascending strokes.

Heapsort produces a spray with a descending upper edge. The sift-down operation walks from a node to a child at roughly twice the index, so a single sift-down jumps by a doubling sequence — a scatter across the whole array in $\log n$ steps. The descending edge is the sorted region growing at the top as elements are extracted, one per iteration.

Quicksort produces a narrowing triangle. Each partition sweeps two pointers towards each other across a contiguous range, and each recursive call halves the range. The picture is a nested set of sweeps, each half the width of its parent, with the widest at the start.

Insertion sort produces a diagonal band. The outer loop advances one element at a time and the inner loop walks backwards a short distance, so the trace hugs the diagonal with a small vertical thickness that is the average displacement.

These shapes are not decoration. Each one is a direct statement about how the algorithm will behave against a memory hierarchy, and they say things the counts do not.

Sequentiality, and what it misses #

The single-number summary of a trace used on this site is sequentiality: the fraction of consecutive accesses that go to the same element or the next one. It is the pattern a prefetcher can follow.

The bottom row is the measure failing, and it is worth understanding why rather than quietly dropping it.

Selection sort’s inner loop compares each element against the running minimum. The comparison primitive records two accesses — the candidate at index $j$ and the minimum at index $m$ — so the trace alternates $j, m, j{+}1, m, j{+}2, m, \ldots$. No consecutive pair is adjacent, so the measure reports zero, while the algorithm is in fact walking straight through the array and touching one fixed extra location. Its real locality is excellent.

The measure is looking at consecutive pairs and the algorithm’s structure is a stride-two pattern with a stationary component. A better measure would consider a window rather than a pair. The site keeps the simple one and reports the miss count alongside, because the miss count does not have this blind spot: selection sort’s misses are high for a different and genuine reason, which is that it makes twice as many accesses as anything else quadratic.

The general lesson is one this site keeps running into: a summary statistic has a shape it cannot see, and the way to find out is to look at the thing it summarises. That is what the trace pictures are for.

Why recursion is good for locality #

The divide-and-conquer algorithms have an advantage that is not in their operation counts and is visible in their traces.

After a few levels of recursion, the subproblem being worked on is small. Once it is smaller than the cache, everything below that level runs entirely at cache speed — and most of the work is below that level, because each level does the same total work and there are many more small subproblems than large ones.

The striking part is that this happens without the algorithm knowing anything about the cache. A recursive algorithm that halves its problem passes through every scale on the way down, so whatever the cache’s capacity is, some level of the recursion matches it. This is the idea behind cache-oblivious algorithms: structure the recursion so that it is automatically efficient at every level of a memory hierarchy whose parameters are never learned. Merge sort gets it for free.

Heapsort cannot. Its working set is the entire heap from the first operation to the last, and there is no level at which it becomes small. That is why its miss count is 3.7 times merge sort’s on 1.9 times the comparisons, and it is a structural property of maintaining one global structure rather than a fixable inefficiency — the same structural cost that an unbalanced tree pays on every lookup.

Insertion sort’s compensation #

The trace explains something the comparison count makes look absurd.

Insertion sort at n = 2,048 performs 1,058,128 comparisons against merge sort’s 19,919 — 53 times as many. It is a bad algorithm by that measure and the measure is not wrong.

But 67% of its accesses are sequential, and its working set at any moment is a handful of adjacent elements. Every access is to the element beside the last one. In a cache-line model this is nearly free: eight elements arrive per fetch and all eight are used before the next fetch.

So insertion sort converts a large comparison count into a small number of expensive events, which is exactly the trade modern hardware rewards. On small arrays this is enough to make it the fastest thing available despite doing far more nominal work — and the crossover is measurable, though not in the count everyone assumes.

Bubble sort has the best sequentiality of anything here, at 75%, and it is still a bad algorithm, because it combines good locality with 2,091,472 comparisons and 62,563 swaps. Locality is a multiplier on the cost of an operation, not a substitute for doing fewer of them.

The trace and the count, side by side #

The most direct way to see what a trace adds is to put it next to the count it is not.

Insertion sort and bubble sort at $n = 2{,}048$ perform 1,058,128 and 2,091,472 comparisons — bubble sort does about twice the work by that measure, and both are quadratic. Their traces are nearly the same picture: both hug the diagonal, both have high sequentiality (67% and 75%), and their modelled miss counts are 103,343 and 246,592, which is the same factor of two the comparison count gave.

So for these two algorithms the trace adds nothing. The counts and the locality agree, the ratio is the same by either measure, and a comparison count would have said everything.

Merge sort and heapsort are the opposite. 19,919 comparisons against 38,765 — a factor of 1.9 — and 1,277 misses against 4,677, a factor of 3.7. The trace is carrying something the count is not, and that something is worth about twice again.

The general rule that falls out: the trace matters when the algorithms differ in structure and not when they differ only in constant. Two nested loops over an array look alike whatever the loops do. A recursion and a heap traversal do not.

What a trace is for #

Three uses beyond producing pretty pictures.

Feeding the cache model. The trace is the input to the miss count, which is the second independent quantity this site carries. Without the trace there is only one number and no way to notice that it is insufficient.

Diagnosing where an algorithm is slow. A trace shows which phase of an algorithm scatters. If merge sort were slower than expected, the trace would say whether the problem is in the merges or in the copy back from the buffer, and it says so by where on the picture the scattering is rather than by a summary number that mixes them.

Making the invisible visible. The strongest argument for these pictures is that nobody who has seen the heapsort trace beside the merge sort trace goes on believing that “both are $\Theta(n \log n)$” is a complete description. The classification is true and it is missing this, and there is no way to convey what it is missing except by drawing it.

The locality a trace shows is a property of the algorithm and the input, and two more panels separate them.

What the pictures do not show #

Three limitations worth stating, since a picture is more persuasive than a number and deserves more scepticism.

The traces are at n = 256. At that size the entire array fits comfortably in any real cache, so a real machine would show none of the effects these pictures are used to explain. The pictures are illustrating a structure that persists at every size, and the structure is what the cache model at larger sizes actually measures.

The vertical axis is an array index, not an address. Two adjacent indices are adjacent in memory only for a contiguous array of fixed-size elements. For an array of pointers to objects — which is what sorting objects in most languages means — the indices are adjacent and the objects are wherever the allocator put them, and every comparison chases a pointer to somewhere unrelated. The pictures describe the index trace and the hardware sees the address trace, and for a pointer array the two have very little to do with each other.

One run, one seed. Each picture is a single execution on a single input, and a single run is not a distribution. For the deterministic algorithms that is the whole story; for randomised quicksort it is one draw, and a different seed gives a visibly different triangle. The site’s figures state their seeds for this reason.

The horizontal axis is an order, not a clock #

There is a fourth limitation, and it is separate from the other three because it is about what the picture implies rather than about what it leaves out.

Every trace on this page is drawn with access number running left to right, and a reader takes that axis for time. It is not time. It is an ordinal: the sequence in which the algorithm asked for things. Two neighbouring dots may be one cycle apart or three hundred, depending on whether the second access hit in cache, and the picture gives them equal width.

That would be a minor complaint if the widths were merely unequal. What makes it substantive is that on a real processor the order is not preserved either. A modern core issues several loads at once and continues past one that has missed, as long as nothing downstream needs the result yet. Two misses that overlap cost roughly what one costs. Two misses that must happen in sequence — because the address of the second was computed from the value returned by the first — cost the full penalty twice.

This is memory-level parallelism, and it splits the traces on this page in a way the miss count does not.

Merge sort’s misses are independent. It is walking two runs forwards. The address of the next line is known long before the current one arrives, so the hardware can have half a dozen in flight, and the prefetcher can have several more. A count of, say, a thousand misses on a merge phase is a thousand latencies overlapped into far fewer stalls.

Heapsort’s misses are dependent. Sifting down computes the index of the next node from the comparison of the two children of the current one. Nothing about the next address is known until the current one has arrived. Its misses queue up end to end, and a thousand of them is close to a thousand full latencies.

So the two algorithms differ not only in how many misses they take — which the model measures, and which already favours merge sort — but in how much each miss actually costs, which the model does not measure at all and which favours merge sort again.

This is the second place in this collection where a simplification turns out not to be neutral between the algorithms, and it points the same way as the conflict misses the cache model cannot see. A model that is optimistic about everything is fine; a model that is optimistic about the loser is worth flagging. Both of these are, and the honest statement is that the measured gap between the sweeping algorithms and the scattering ones is a lower bound on the real one.

The line the pictures could draw and do not #

The first limitation above is that the traces are drawn at 256 elements, where everything fits in any cache and none of the effects being explained would occur. The defence is that the structure persists at every size — and there is one feature of that structure which does not, and drawing it would turn these pictures from illustrations into measurements.

The level at which the recursion becomes cache-resident. A divide-and-conquer algorithm’s advantage is that some level of its recursion has a working set smaller than the cache, and everything below that level runs at cache speed. Which level that is depends on the capacity, and it is a specific place on the trace: the point at which the width of a sweep drops below the number of elements the cache holds.

A trace annotated with the cache’s capacity — a horizontal band showing how much of the index range fits — would show that transition directly, and it would show each algorithm’s relationship to it:

Merge sort would cross it once, part way down the recursion, and everything to the left of the crossing in each band would be resident. The picture would divide into a small number of expensive top-level sweeps and a great many free ones.

Quicksort would cross it at the corresponding depth of its narrowing triangle, and the triangle would visibly become free below the line.

Heapsort would never cross it. Its sifts span the whole array at every step, so no band of the picture is ever narrower than the array, and the annotation would be a line the trace simply ignores — which is the essay’s structural claim made visible rather than argued.

Insertion sort would be entirely below it at every size, because its working set is a handful of adjacent elements throughout.

That is worth more than a redrawing at a larger $n$, and it is the reason to prefer it. A trace at sixty-five thousand elements is a smear; a trace at 256 with the capacity marked shows where the boundary would fall and lets a reader see which side of it each part of the algorithm lives on. The interesting quantity is not the size of the picture but the position of the line in it, and the position is computable from the same two parameters the cache model already prints.

The measure that would be better #

Since the sequentiality measure has a known blind spot, it is worth saying what would replace it.

The quantity that actually predicts cache behaviour is reuse distance: for each access, how many distinct lines were touched since that line was last touched. If the reuse distance is smaller than the cache’s capacity in lines, the access hits; otherwise it misses. That is not an approximation — it is exactly what a fully associative LRU cache does, so a reuse-distance histogram determines the miss count at every possible cache size at once.

The site computes miss counts directly by simulating, which is equivalent and simpler to implement, and reports sequentiality alongside because it captures a different thing: whether a prefetcher could help. Two accesses can both hit and still differ in whether the hardware fetched them ahead of time.

The two measures answering different questions is the same pattern as comparisons and misses answering different questions, one level down. There is no single number, and every level of the analysis discovers this again.