Counting instead of timing

There are two ways to find out what an algorithm costs: run it and look at a clock, or run it and count.

The first is what almost everybody does, and it produces a number that describes the machine it ran on. Change the machine and the number changes. Change the compiler, the memory pressure, whether a background process woke up during the third trial, whether the CPU decided to boost its clock — the number changes. Run the identical benchmark twice on the identical machine and the number changes, which is why anyone doing this carefully reports a median of many trials and a confidence interval, and why the results are hard to compare against anybody else’s.

The second produces a number that describes the algorithm. Selection sort performs exactly 130,816 comparisons on 512 elements. Not approximately, not on average, not on this machine: exactly, always, on every input of that size, forever. That number is $\frac{n(n-1)}{2}$ with $n = 512$, and it will be the same number today and when the hardware this page was built on is landfill.

Every measurement on this site is of the second kind.

What a stopwatch is measuring #

It is worth being concrete about what goes wrong with timing, because “benchmarks are noisy” undersells it.

Suppose two sorting algorithms are timed on a million elements and one comes out 8% faster. What has been learned? Possibly that it does less work. Possibly that it happens to fit in this processor’s L2 cache and the other one does not, which will reverse on a machine with a different cache. Possibly that the compiler unrolled one inner loop and not the other. Possibly that the faster one allocated no scratch memory and so avoided a page fault that the slower one paid once. Possibly that the operating system scheduled a timer interrupt during the wrong trial.

Every one of those is a real effect and only the first is a property of the algorithm. Disentangling them is a serious undertaking — and it is a different undertaking from the one most people think they are doing when they write a benchmark loop.

A count has none of these problems, at the price of not being a time. That is a trade this site makes deliberately and re-examines whenever it matters, which is most of the machine field.

The instrumented array #

Every algorithm on this site is written against a small object rather than against a plain array. It has four primitives that touch data:

• get(i) — read the element at index i
• set(i, v) — write v at index i
• cmp(i, j) — compare the elements at i and j
• swap(i, j) — exchange them

Each one increments a counter before doing its job. Running an algorithm therefore leaves behind a tally: comparisons, swaps, reads, writes, and the complete sequence of indices touched in the order they were touched.

That last item matters more than it looks and gets an essay of its own. The other four are what the textbooks count.

There is no way to stop an implementation reaching past the primitives and touching the underlying array directly. Nothing in the language prevents it, and an implementation that did would sort perfectly and be counted wrongly — a sabotage that survives every other check on this site. The gate breaks exactly that way on purpose and requires the discrepancy to be caught by a count known independently.

What counts as one comparison #

cmp(i, j) is recorded as one comparison and two reads. That is the convention every textbook analysis uses and it is worth saying out loud that it is a convention rather than a fact.

An implementation that kept one operand in a register across an inner loop — which insertion sort’s inner loop does naturally, and which the version here reflects with a separate cmpValue primitive counted as one comparison and one read — performs the same number of comparisons and strictly fewer reads. Neither count is more correct. They answer different questions, and the answer to “how many operations” begins with naming the operation.

The convention also flattens something real. Comparing two machine integers and comparing two long strings that share a prefix cost wildly different amounts, and this site’s count does not distinguish them. Where that difference is the point, the essay says so; where it is not, the flattening is the same one every complexity analysis makes, and it is what makes the numbers portable.

Determinism, or the figures would lie #

An algorithm’s cost depends on its input. Measuring the average case means averaging over random inputs, and the obvious way to generate those is a random number generator.

Math.random() is unusable here, and the reason is specific rather than fastidious. Figures on this site are generated at build time and their captions quote the numbers in them. A figure built on an unseeded generator produces different numbers on every build, so a caption saying 2,086 comparisons would be quoting a number that the picture beside it does not contain — the picture on the reader’s screen came from a different build. The caption and the figure would drift apart silently and permanently.

So every random input here comes from a stated seed through a small deterministic generator, and the seeds are in the source. The consequence is that every number in every caption is the number in the figure beside it, and rebuilding the site produces byte-identical output. The distributions are averages over hundreds of inputs, and those hundreds are the same hundreds every time.

There is a real cost to this. Determinism means these are not independent samples in the statistical sense — they are one fixed sample, drawn once. A figure claiming a 95% confidence interval would be claiming more than the method supports. The figures do not; they show the whole distribution and let the spread speak.

The sample size is then a question that can be answered by measurement rather than by rule of thumb.

One number needs the input named #

The other thing a single count hides is that most algorithms do not have one cost. They have a cost per kind of input, and for the adaptive ones the spread is enormous.

At n = 512, insertion sort performs 511 comparisons on an already sorted array and 130,816 on a reversed one — a factor of 256, and the gap widens with n. Selection sort performs 130,816 on both, and on every other input of that size, because its two loops run to completion regardless of what they encounter. That difference between the two algorithms is not visible in their shared classification as quadratic, and it is the difference that decides which one is worth having when the data is nearly in order.

Every measurement on this site therefore carries its input kind, and the five kinds are fixed and stated: uniformly random, already sorted, reversed, nearly sorted, and few distinct values. The last two exist because they are where the interesting failures live — nearly sorted is where adaptivity is supposed to pay off, and few distinct values is where several perfectly respectable quicksort variants fall apart.

The check that catches everything #

The single most valuable line in the measurement machinery is this one: after a sorting algorithm runs, the array is checked to be sorted, and if it is not, the run is an error rather than a measurement.

This has caught more mistakes during construction than every other check combined, and the reason is worth dwelling on. A broken sorting algorithm produces a perfectly convincing growth curve. If the inner loop stops one element early, the array comes out almost sorted, the comparison count is very slightly lower than it should be, the curve on logarithmic axes is a straight line with the same slope, and the fitted exponent is 2.00 to three digits. Every check on this site except one would pass. The figure would be beautiful and wrong.

Counting the counter #

There is a subtler failure available. Suppose a primitive forgot to increment — cmp counted comparisons but cmpValue did not, say.

Every count on the site would fall. Every curve would still be a curve. Every fitted exponent would still be right, because a constant factor does not change a slope on logarithmic axes, and the fitted constant would be wrong by exactly the factor that got dropped. Nothing would look broken.

The only defence against a systematically wrong instrument is a case whose answer is known by an independent route. Selection sort is that case. Its comparison count is $\frac{n(n-1)}{2}$ for every input of size n, derivable in one line from its two nested loops, and the counters are checked against that closed form on every build. At n = 512 the machinery must report 130,816 and nothing else.

The check is unglamorous and it is the reason to trust any other number here.

Four counts, and they disagree #

Once the counting is in place, the first thing it shows is that “number of operations” is not one number.

At n = 512 on random input:

Selection sort makes 2.1 times as many comparisons as insertion sort and 1/124th as many writes. Bubble sort makes about the same number of comparisons as selection sort and 62 times as many swaps. If the elements being sorted are machine integers, selection sort’s write economy is worth very little. If they are large records that must be physically moved, it is worth a great deal, and the ranking by comparisons is the wrong ranking entirely.

Insertion sort records zero swaps, which is not a claim that it does not move anything — it moves a great deal, but it does so by shifting with get and set rather than by exchanging, so the movement appears in the read and write columns instead. That is an artefact of how the algorithm is written, and it is visible only because four counts are kept instead of one.

This is the first appearance of a pattern that runs through the whole site: the ranking depends on the quantity, and the quantity has to be named. It appears again, much more sharply, when the second and genuinely independent count is introduced.

What a count is not #

An operation count is exact, machine-independent, and not a running time.

The gap between the two is mostly memory. A comparison whose operands are already in the processor’s cache costs a fraction of a nanosecond; one that has to reach main memory costs a hundred times more. An algorithm performing half as many comparisons in a worse order is routinely slower on real hardware, and no amount of counting comparisons will reveal that.

This is not a small caveat to be mentioned once. It is why the site carries a second count alongside the first, why the insertion-sort fallback that every standard library implements turns out not to be about comparisons at all, and why an essay here will say fewer comparisons rather than faster unless it has measured something that entitles it to the stronger word.

There is a second thing a count is not, and it is more fundamental. A finite set of measurements cannot establish an asymptotic claim. Measuring an algorithm at every size up to a million establishes nothing certain about a billion, because infinitely many functions agree with any finite sample and diverge beyond it. That limit is real, it applies to everything on this site, and it is taken seriously enough to have its own essay — including a case where the fitted class genuinely changes when the range is extended.

What counting can do is refute a claim, and measure the constant. Both are worth having.

Why not both? #

The obvious objection to all of this is that timings are what people actually care about, so why not measure them too?

Because a timing on the machine that built this page is a fact about that machine, and publishing it would invite exactly the inference it cannot support. Readers would compare the numbers across essays, and the comparison would be dominated by which build ran on which container with what else running. The honest options are to measure timings properly — many trials, a quiet machine, reported distributions, all of it stated — or not to publish them at all.

This site does not publish them. What it does instead is model the part of the machine that explains most of the difference, which is memory, and state the model’s parameters wherever a number from it appears. That model does not produce a time and no essay treats its output as one. It produces a second count, and the interesting thing about a second count is that it can disagree with the first.

The whole method, in order #

1. Write the algorithm against instrumented primitives and nothing else.
2. Run it on inputs generated from stated seeds.
3. Check the output. A sort that did not sort is an error, not a data point.
4. Record comparisons, swaps, reads, writes, and the access trace.
5. Repeat across sizes spanning three orders of magnitude.
6. Fit the measured counts against the candidate complexity classes, and grant a class only if the fit holds.
7. Replay the access trace through a stated cache model to get the second count.
8. Print the model’s parameters on any figure that reports a number from it.

Six of those eight steps are about not fooling yourself. That ratio is about right.

The pay-off is that every claim on this site is checkable by running the code, and every number in every caption came from the run that drew the figure.

It also has a consequence that was not planned. Two of the ten sorting algorithms here originally declared a complexity class that the fit refused to grant, and the refusals were not mistakes in the machinery. Bubble sort’s advertised behaviour on nearly sorted input fits neither of the classes it is usually assigned. The hybrid merge sort’s behaviour on reversed input fits one class up to n = 4,096 and a different one out to n = 65,536, with nothing changing but the range.

Both claims were withdrawn. Both became essays, because a measurement that disagrees with the expected answer is the only kind worth taking.