The count is not the time

Every number in the counting and floors fields on this site is exact and none of them is a duration.

The distance between the two is not a small correction. On modern hardware a comparison whose operands are already in the processor’s fastest cache costs well under a nanosecond; one that has to be fetched from main memory costs on the order of a hundred. Two orders of magnitude, decided not by how many operations an algorithm performs but by where in memory it performs them.

An algorithm doing half the comparisons in a worse order is routinely slower. Nothing in a comparison count reveals that, and no amount of counting comparisons more carefully will.

What is actually happening in the machine #

The relevant fact about modern hardware is that memory is not one thing. It is a hierarchy, and the levels differ by orders of magnitude in both size and speed.

Registers hold a few dozen values and are instant. The first-level cache holds tens of kilobytes and costs a few cycles. The second and third levels hold megabytes and cost tens of cycles. Main memory holds gigabytes and costs a couple of hundred. The ratios have widened steadily for four decades, because processors have got much faster and memory latency has barely moved.

Two consequences shape everything below.

Memory moves in lines, not elements. Fetching one byte from main memory fetches a whole aligned block, typically 64 bytes — eight double-precision numbers, or sixteen 32-bit integers. An algorithm that uses all of them has amortised the fetch sixteen ways. One that uses a single element and moves on has paid for sixteen and used one.

The hardware guesses. A prefetcher watches the stream of addresses and, when it detects a regular pattern, fetches ahead of the program. An algorithm walking straight through an array gets its data before it asks for it. An algorithm jumping unpredictably gets nothing.

So the property that matters is locality: does the algorithm touch memory in an order the machine can anticipate? And that property is invisible to every count in the counting field.

The model #

This site does not time anything. What it does instead is record the complete sequence of array indices each run touches — the instrumented array collects it alongside the counters — and replay that trace through an explicit cache model.

The model is deliberately simple and its parameters are printed on every figure that reports a number from it:

• fully associative — any line may live in any slot
• a stated number of lines, each holding a stated number of elements
• least-recently-used replacement

A real cache is set-associative, has several levels, has separate instruction and data paths, has write buffers, and prefetches. This model has none of that. What it does capture is the thing that explains most of the effect: whether the working set fits, and whether consecutive accesses land in the same line.

It does not produce a time and no essay here treats its output as one. The output is a count of modelled misses. It is a second exact, reproducible, machine-independent number, and its value is that it is independent of the first one.

The model is checked in both directions #

A model that reported plausible numbers without measuring anything would be worse than no model, because every comparison drawn from it would be written as though it worked.

So the gate makes four demands.

A sequential walk must miss exactly once per line. Walking 4,096 elements with eight elements per line must produce exactly 512 misses. Not approximately — exactly. If it produced more, the model would be wrong about the only access pattern hardware is unambiguously good at, and every comparison would be biased in the same direction.

A random walk over an oversized array must miss almost always. Over an array eight times the cache’s capacity, the measured miss rate is 87%. A model that reported something similar for both patterns would be measuring nothing.

Two traces of identical length must give very different miss counts. A sequential walk of 2,048 accesses produces 256 misses; a stride-97 walk of the same 2,048 accesses produces 2,048. A factor of eight. If those numbers were close, the miss count would be a restatement of the access count and this site’s two-quantity framing would be empty.

And the model must be capable of failing that test. The gate runs the independence check with a line size of one element — a cache with no spatial locality to exploit — and requires it to fail, because under that configuration the second count genuinely does stop carrying information.

What the second count says about the sorts #

At n = 2,048 on random input, with 64 lines of 8 elements:

Several things here are not visible in the comparison column.

Heapsort’s miss count is 3.7 times merge sort’s, on 1.9 times the comparisons. Heapsort’s problem on real hardware is worse than its comparison count suggests, and the reason is in the last column: 14% of its accesses go to the adjacent element, against merge sort’s 49%. Heapsort moves between a node at index $i$ and its children at $2i+1$ and $2i+2$, which for a large heap are far apart in memory. It is the least local algorithm here.

Median-of-three quicksort has the fewest misses of anything — fewer than merge sort, despite 29% more comparisons. Quicksort’s partition sweeps two pointers towards each other through a contiguous range, which is close to the best possible access pattern, and it sorts in place so there is no buffer competing for cache.

That inversion is the whole point. By comparisons, merge sort wins. By modelled misses, quicksort wins. Both numbers are exact and neither is the running time, and anyone choosing between them needs to know which resource is scarce.

Selection sort reports 0% sequential. Its inner loop does walk straight through, but every comparison is against the running minimum at a fixed index, so the trace alternates between a moving position and a stationary one and no consecutive pair is adjacent. This is a case where the sequentiality measure — defined as the fraction of consecutive accesses that go to the same or the next element — understates the locality badly. The miss count is the more trustworthy number and it is high for a different reason: selection sort makes twice as many accesses as anything else quadratic.

What a second count is for #

The value of carrying two numbers is not that the second is more accurate. It is that two numbers can disagree, and a disagreement is information that one number cannot contain.

This is the same structure as comparisons and swaps disagreeing about which quadratic sort is better, one level up. There the two counts were both about operations; here one is about operations and the other about where they happen, which makes them independent in a stronger sense.

The strongest form of the point is a case where the two counts give opposite verdicts. Merge sort and median-of-three quicksort at $n = 2{,}048$:

• merge sort does 19,919 comparisons, quicksort 25,703 — merge sort wins by 29%
• merge sort incurs 1,277 modelled misses, quicksort 1,187 — quicksort wins by 8%

Neither number is wrong and neither is a time. What they establish jointly is that the choice between these two algorithms depends on which resource is scarce, and a site reporting only the first would have declared merge sort better, full stop.

The site therefore asserts the disagreement rather than merely observing it. A figure requires that ranking by comparisons and ranking by misses give different orders, and that at least one algorithm moves two or more places between them. If the two counts ever became predictable from each other, that assertion would fail and the build would stop — which is the same must-be-able-to-fail discipline applied to a claim about the method rather than about an algorithm.

The sequential fraction and the miss count rank two algorithms oppositely #

The last column of that table is offered as an explanation of the third, and on one pair it points the other way — which is worth following, because it says what the two columns are each measuring.

Selection sort is 0% sequential and incurs 245,740 misses. Bubble sort is 75% sequential and incurs 246,592. Two algorithms three quarters of a table apart on one measure and within a third of a per cent on the other.

Divide through by the work. Bubble sort makes about $n^2/2$ accesses at $n = 2{,}048$, so its miss rate is roughly one in eight — which is exactly the line size, and exactly what an algorithm gets when it walks contiguously and reuses nothing. Selection sort makes about twice as many accesses for the same comparison count, so its rate is roughly one in seventeen, or half bubble sort’s. The algorithm reported as 0% sequential is missing half as often per access as the one reported as 75%.

Both numbers are right about different things. Bubble sort’s sweeps are contiguous, so it collects the whole spatial benefit — one miss per line rather than one per element — and it collects nothing else, because each sweep traverses an array four times the cache’s capacity and every line has been evicted before the next sweep reaches it. Selection sort’s trace alternates between a moving position and the running minimum’s fixed index, which is what makes its consecutive-access measure zero; but that fixed index is one line, permanently resident, so half of its accesses are free hits and no measure of adjacency can see it.

So the two columns are measuring spatial and temporal locality, and the sequential fraction sees only the first. An algorithm can have perfect adjacency and no reuse, which is bubble sort; or no adjacency and heavy reuse of one hot line, which is selection sort. The miss count is the product of both effects and the adjacency figure is one factor of it, which is why the essay’s own caution about selection sort — that the sequentiality measure understates it — generalises: the measure is not a weaker version of the miss count, it is a different quantity that happens to correlate on most of the table.

The practical form is a warning about the diagnostic rather than about either sort. A profile reporting “this loop is 75% sequential” is reporting that the loop will not pay per element, and is silent about whether it will pay per pass — and on data that does not fit, paying per pass is where the entire cost is. That is the cliff seen through an instrument that cannot detect it, which is a worse position than having no instrument, and it is the reason where an algorithm looks draws the whole trace rather than summarising it into an adjacency statistic.

What the model cannot establish #

Four things, and they are worth being explicit about because a plausible number invites over-reading.

It is not a time. Multiplying misses by a memory latency and adding comparisons times a comparison cost would produce a number. That number would be wrong, because it ignores instruction-level parallelism, out-of-order execution, and the fact that several misses can be in flight at once. Real processors overlap memory stalls with useful work to an extent this model has no way to represent — which is one more reason nothing here is called a time.

It has no prefetcher. This is the largest single omission and it biases against sequential algorithms. A real machine walking straight through an array pays almost nothing, because the hardware fetched the lines before they were needed. The model charges a full miss per line. So insertion sort’s 103,343 misses at n = 2,048 look much worse than they would be — 67% of its accesses are sequential and a real prefetcher would absorb most of that.

It has one level. Real hierarchies have three or four, and an access that misses L1 but hits L2 costs a tenth of one that reaches memory. The model’s binary hit-or-miss flattens a distinction that matters.

Associativity conflicts are absent. A real set-associative cache can evict a line while capacity remains, because too many hot addresses map to the same set. This produces the notorious pathologies where an array stride that happens to be a power of two is catastrophically slower than one that is not. The model, being fully associative, never sees them.

Every one of these makes the model optimistic or pessimistic in a known direction, which is the useful property: the numbers are comparable to each other even where they are not comparable to reality.

The parameters are a choice, and they are printed #

A miss count without a line size and a capacity is not a measurement of anything, so every figure on this site that reports one prints both.

The defaults are 64 lines of 8 elements — 512 elements of cache — and they were chosen to put the interesting transitions inside the range of sizes the site can afford to measure. A real last-level cache holds millions of elements, and using a realistic capacity would mean every figure showing a flat line until $n$ passed a million, which is beyond what the build can compute for a quadratic algorithm.

So the model is scaled down, deliberately, and the scaling is stated. What that preserves is the shape of every effect — the cliff, the difference between sequential and strided, the ranking of algorithms by locality — because all of those depend on the ratio between the data size and the capacity rather than on either absolutely.

What it does not preserve is any number that could be compared against a real machine. This is the same trade as choosing a cost model for comparisons: the model is a lens, it is stated, and the results are interpretable through it and not otherwise.

Two counts, and the resource neither of them is about #

Both quantities in this essay are proxies for duration. The comparison count is what the algorithm does; the modelled miss count is what the memory system does about it; and the case for carrying both is that the second explains variation the first cannot. They disagree, they are independent, and they are both answers to how long.

There is a third resource that neither of them touches, and it is not a refinement of either. How much memory the algorithm needs while it runs is a separate axis, it is measurable by the same discipline, and it is the one that decides whether a program runs at all rather than how quickly.

The distinction matters because the two axes trade against each other in both directions. Merge sort’s buffer is the reason its access pattern is so clean — a sequential write into scratch space rather than an in-place shuffle — so the memory it takes is buying the miss count that makes it look good in this essay. Heapsort takes none and pays for it in exactly the locality this essay measures. Neither fact is visible in a comparison count, and only half of it is visible in a miss count.

So the pair of numbers this field carries is not a complete cost model; it is two of three. Auxiliary space is the third, it is instrumented the same way — counted at the point of allocation rather than asserted from the code — and it turns “sorts in place” from a description into a claim that can fail.

The disagreement, four ways #

One scatter is one setting of four parameters. The claim is that the two counts disagree, so the useful question is whether they disagree everywhere or only here.

The input is the second parameter, and it is the only one of the four that moves the horizontal axis as well as the vertical one.

And the fourth is the line length, which reaches the same capacity by the other factor and is the one a programmer has no control over at all.

Why not just measure the time #

The honest answer is that measuring time properly is a different project.

Doing it well means a quiet machine, many trials, reported distributions, control over frequency scaling and address-space layout randomisation, and a clear statement of which machine. Doing it badly means publishing a number that describes a container that ran for eight seconds in 2026 and inviting readers to compare it against numbers from other pages that describe other containers.

The middle path this site takes is to model the specific mechanism that explains most of the variation, state the model’s parameters everywhere, and never call the output a time. That gives a second exact number that is genuinely independent of the first, which is enough to make the point that one number was never sufficient — and stops short of claims the method cannot support.

Where a time would settle a question, the essays say that a time would settle it and that this site does not have one. The crossover essay is the clearest case: it establishes that the familiar insertion-sort fallback is not about comparisons, and it stops there rather than claiming to know the exact threshold on any particular processor.