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.

The cliff is at the cache’s capacity, and the cache has two parameters. Moving either should move the cliff and nothing else about the shape.

Doubling the line rather than the count of lines is the other way to the same capacity, and the model should not be able to tell them apart.

So the two factorings of one capacity are the check rather than the finding, and the plate this page already drew at 128 lines of 8 is the other half of it: the same 1,024 elements, the same curve. Anything that did differ there would be a defect in the model rather than a property of a cache.

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 cliff the model cannot show #

The model here is fully associative: any line of data may live in any of the cache’s lines, and eviction is by least recent use. That is a deliberate simplification, and it has a consequence that is easy to demonstrate and worth demonstrating, because it is the one place where this essay’s own argument has a hole in it.

A fully associative model is smooth in its capacity. Heapsort on 2,048 elements, with a line of 8:

Going from 63 lines to 64 to 65 changes the miss count by about one and a half percent each step, monotonically, with nothing special happening at the power of two. On real hardware something very special happens at the power of two, and it goes the other way: a cache that is 8-way set associative with 64 lines has 8 sets, an access pattern whose stride is a multiple of the set count maps every one of its addresses into the same set, and a program with nine such streams thrashes a cache that has room for five hundred and twelve lines’ worth of data. Capacity stops being the thing that determines whether the data fits.

The reason this matters here rather than being a footnote is the claim made two sections above: that every simplification in the model applies to all the algorithms equally, so the ordering survives even though the counts do not. Conflict misses do not apply equally. They are worst for strides that are powers of two, and heapsort’s access pattern is built from the indices $2i+1$ and $2i+2$ — its strides are powers of two by construction, at every level of the heap. Merge sort’s are unit strides through contiguous runs, which are the pattern conflict misses trouble least.

So the model is likely to flatter heapsort relative to merge sort, and heapsort is already the worst algorithm in this field by the modelled count. The direction of the error is knowable even though its size is not, and it points the same way as the measurement rather than against it — which is the most that can be said for a simplification, and is worth saying out loud rather than leaving as a caveat about associativity that a reader has to decode.

The uniform curve is a lower envelope, not a prediction #

The associativity table above varies the capacity with the data fixed, and the hero figure varies the data with the capacity fixed. They look like the same curve reflected, and reading them as such gives a number that does not fit.

Heapsort on 2,048 elements through a cache of 64 lines is working on four times what the cache holds, and it misses 2.9% of its accesses. The hero figure’s uniform random walk at four times capacity is missing a large fraction of its accesses, and by eight times it is past sixty per cent. Same model, same line size, comparable ratio, and two orders of magnitude between the answers.

The difference is the access distribution. A uniformly random walk touches every line equally, so nothing is ever worth keeping and the hit rate is essentially the fraction of the data that fits. A heap’s accesses are nothing like uniform: every sift-down starts at the root, so the top few levels are touched on every operation while the bottom level — which is half the array — is touched once each. A cache serving a distribution that concentrated keeps the hot part resident and misses only on the cold tail, and the cold tail is where the compulsory misses were going to be anyway.

So the cliff is a property of the access distribution and not of the data size, and the uniform curve is the lower envelope: the worst any algorithm can do at a given ratio, achieved only by an algorithm with no locality whatever. Every real algorithm sits above it, and how far above is the whole of what where an algorithm looks is measuring.

That reframes the figures on this page in a way worth stating plainly. The hero figure is not a prediction of what any program will do at a given working-set ratio; it is the reference against which a program’s locality is a distance. Heapsort, the worst-behaved sort in this collection by every locality measure it has, is fifteen or twenty times better than the reference at the same ratio — which says less about heapsort than about how bad the reference is.

Two things follow.

The first is that “does the working set fit” is the wrong question in the form usually asked. The right one is what fraction of the accesses fall inside the part that fits, and for a skewed distribution that fraction is far higher than the fraction of the data. Quoting the mean of the access distribution, or its support, in place of its shape is the error expected is not average is about, arriving in the memory hierarchy.

The second is that the last row of the capacity table is the only genuine cliff in it. From 16 lines to 128 the miss count falls by a factor of one and a half to two per doubling — a slope, not a step. From 128 to 256 it falls by 8.6, to exactly 256 misses, which is the compulsory floor of 2,048 elements at eight to a line. Nothing is evicted because nothing needs to be, and that transition is sharp because it is the point where the capacity misses reach zero rather than merely become few. Building a heap from the bottom is where that access distribution is measured directly.

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 the simplifications mostly apply to all the algorithms equally, and where they do not, as with the conflict misses above, the bias runs in the direction that would make the gap larger rather than smaller. 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.