The cliff where the data stops fitting

Take a fixed number of random accesses — twenty thousand, say — into an array of $n$ elements, and vary $n$. The number of accesses does not change. The algorithm does not change. Only the size of the region being touched changes.

The miss rate goes from essentially zero to essentially one, and it does so over about a factor of eight in $n$.

What the cliff is #

The mechanism is not subtle. A cache holds some fixed amount of data. If the set of things a program is actively using — its working set — fits, then after the first pass everything is already there and every subsequent access hits. If the working set does not fit, then by the time the program comes back to something, it has been evicted to make room for everything else, and the access misses.

There is no middle ground to speak of, because eviction is all-or-nothing per line and the accesses are spread uniformly. Slightly over capacity means slightly more than half the lines get evicted before reuse; well over capacity means essentially all of them do.

The practical shape of this: an algorithm can be fast at one size and slow at twice the size, with no change whatsoever in its operation count per element. Every count on this site would report the second run as costing exactly twice the first. A clock would report considerably more than twice.

Why it makes complexity classes misleading #

A complexity class is a statement about how the operation count grows. It carries an implicit assumption that operations cost about the same as each other, and across a cliff they do not.

Consider an $O(n)$ algorithm — one pass over an array, constant work per element. Double $n$ and the operation count doubles, so the class predicts a doubling of cost. If the doubling crosses the cache capacity, the actual cost can grow by considerably more, because the per-operation cost changed at the same time as the count.

The effect is bounded — the ratio between a hit and a miss is large but finite, so the whole thing is a constant factor and the class survives. But it is a constant factor of ten or more that switches on somewhere in the middle of the range that matters, and “asymptotically it’s still linear” is not much comfort to somebody whose job just got ten times slower.

This is one of the more concrete instances of the general problem with asymptotic reasoning: the notation describes behaviour past some threshold and is silent about where the threshold is. Here the threshold is a hardware parameter that the algorithm’s author never saw.

Two kinds of miss #

Not all misses are avoidable, and separating them matters when deciding whether an algorithm can be improved.

Compulsory misses. The first time a cache line is touched, it must be fetched. Nothing can prevent this, and the count is simply the number of distinct lines the algorithm touches. For a single pass over an array of $n$ elements at eight elements per line, that is $n/8$, and no algorithm reading all the data can do better.

Capacity misses. Everything else — a line that was fetched, evicted, and needed again. These are the ones an algorithm can avoid, by arranging to finish with data before it gets pushed out.

The site’s model asserts the distinction directly: with a cache larger than the data, the measured miss count must equal the compulsory floor exactly. If it were higher, the model would be inventing evictions that cannot happen; if it were lower, it would be inventing hits.

The distinction also identifies when optimisation is pointless. An algorithm whose misses are nearly all compulsory has nothing left to gain from better locality, and effort should go elsewhere. One whose misses are mostly capacity misses can potentially be restructured — and the standard restructuring is blocking: process the data in chunks that fit in cache, finishing entirely with each chunk before moving on. That is exactly what an insertion-sort cutoff does to merge sort’s recursion, and it is most of why the cutoff exists.

Backwards is as cheap as forwards #

One row of that figure deserves attention because it contradicts a common intuition.

Reading an array from the last element to the first produces exactly the same number of misses as reading it from first to last. Both touch every line once and each line is used eight times.

The intuition that backwards should be worse comes from thinking about prefetching rather than caching, and it is half right: some older hardware prefetchers only detected ascending strides, so a descending walk got no help. Modern ones handle both directions. The site’s model has no prefetcher at all, so the two are exactly equal in it, and on real hardware they are close.

What the model does capture is the thing that is genuinely fatal: stepping by the line size or more. Stepping by 8 elements when a line holds 8 touches a new line every single time, so a walk of $n$ accesses costs $n$ misses instead of $n/8$. A factor of eight, from an access pattern that looks perfectly regular and is.

This is why the notorious cache pathologies involve strides that are powers of two — they interact badly with both line size and set indexing, and the resulting slowdowns look inexplicable from the source code.

What the cliff does to a complexity comparison #

The most common way the cliff produces a wrong conclusion is in an informal benchmark, and the mechanism is worth spelling out because it is easy to fall into.

Suppose two algorithms are compared at $n = 10{,}000$ and one is 30% faster, and the conclusion drawn is that it is the better algorithm. Now suppose the faster one’s working set at that size fits in the last-level cache and the slower one’s does not, because it keeps a buffer. At $n = 1{,}000{,}000$ neither fits, both are paying full price for every access, and the comparison count reasserts itself as the thing that matters — possibly reversing the verdict.

The reverse also happens. An algorithm that looks bad at small $n$ because of a fixed setup cost can win decisively at large $n$, and an algorithm that looks good at small $n$ because everything fits in cache can lose.

There is no way to detect this from a single measurement, and the fix is not subtle: measure across a range, and plot it. A curve that bends where a curve should be straight is the cliff announcing itself, and it is invisible in any single number.

This site’s fits run over three orders of magnitude for exactly this reason, and the one case where the fitted class changed when the range was extended is the same lesson arriving from the other direction.

Where the cliff puts the sorting algorithms #

The cliff explains a specific and otherwise puzzling observation: recursive divide-and-conquer algorithms have an advantage on large data that has nothing to do with their operation counts.

Merge sort and quicksort both split the problem repeatedly. After a few levels of recursion, the subproblem they are working on fits in cache, and everything below that level runs entirely at cache speed. The top few levels cost misses; the bottom many levels cost almost none.

Heapsort does the opposite. It maintains one structure the size of the whole input and jumps around inside it from the first operation to the last. There is no point at which its working set becomes small. That is why its modelled miss count at n = 2,048 is 4,677 against merge sort’s 1,277 — 3.7 times, on only 1.9 times the comparisons.

This is the property that made cache-oblivious algorithms an interesting idea: a recursive algorithm that halves its problem automatically becomes cache-friendly at every level of a hierarchy it knows nothing about, because at some level of the recursion each cache size is matched. Merge sort gets this for free by being recursive.

Two sizes, and a third that is often forgotten #

The cliff described here is one transition, and a real machine has several — one per level of the hierarchy. A program’s working set can fit in L2 and not L1, fit in L3 and not L2, or fit in memory and not in L3, and each boundary has its own cliff with its own height.

The site’s model has one level, so it shows one cliff. That is a simplification and it is the right one for the argument being made: the shape is identical at every level and only the capacity and the penalty change.

There is a third transition, further out, that behaves differently enough to be worth naming. When the working set exceeds physical memory the operating system starts paging to disk, and the penalty is not a factor of a hundred but a factor of ten thousand or more. Every effect on this page becomes correspondingly more dramatic, and an algorithm’s access pattern stops being an optimisation and becomes the entire question. The external-memory algorithms literature exists for exactly this regime, and its cost model counts block transfers rather than operations — which is the same move this site makes with modelled misses, taken seriously.

What this means for measurement #

Three practical consequences, and they are the reason this essay exists in a site that never publishes a timing.

A benchmark at one size measures one side of the cliff. Timing a sort on ten thousand elements and concluding anything about a million is extrapolating across a transition. This is the most common single mistake in informal benchmarking, and it can reverse the conclusion.

The cliff moves between machines. Capacity is a hardware parameter, so where the transition falls depends on the processor. A result obtained on a machine with a large last-level cache may not hold on one with a small one, even at identical $n$. A comparison-count result holds everywhere.

The model has to state its parameters or its numbers mean nothing. A miss count without a line size and a capacity is not a measurement. Every figure on this site that reports one prints them, for exactly this reason: the number is only interpretable against the model that produced it, and the model is a choice.

The honest limit #

Everything above is measured through a model with no prefetcher, one level, and no associativity conflicts. The cliff it shows is real and the shape is right; the exact miss counts are not what a real processor would produce.

What survives the modelling assumptions is the ordering — that a strided walk is much worse than a sequential one, that heapsort is much worse than merge sort, that the transition is sharp — because every simplification in the model applies to all the algorithms equally. What does not survive is any attempt to turn these numbers into predicted times, and no essay here makes one.

The cliff is the reason operation counts and running times diverge, and knowing where it falls for a particular workload is worth more than knowing that workload’s complexity class — because which side of the cliff a program sits on is usually changeable, and the class rarely is.