How to benchmark honestly

Before comparing algorithms, you need to learn to measure. It looks simple: note the time before, note it after, subtract. Below is a sort of twenty thousand numbers repeated a hundred and fifty times in a row on the server that runs this catalogue's code. The code and the data do not change, but the time does. The second histogram is the same measurement with one inconspicuous mistake: it shows a speed-up of tens of times that does not exist.

Look at the fair histogram: most measurements lie close together, but there is a tail to the right—single runs one and a half, two, even seven times slower. Nobody slowed them down on purpose: at that moment the processor was distracted by other processes, the OS kernel was switching tasks, the garbage collector was tidying up. Press “Measure again”—you will get a similar picture, but not the same one.

What a measurement really measures

A program's running time is a random variable. One measurement is one value of it, and nothing can be said from it: maybe you were lucky, maybe not. You need many repetitions and a look at the distribution—at least at the minimum and the median.

Where the noise comes from:

• Neighbours. Other processes run on the machine, and the OS scheduler shares the processor among them. Our server is shared by all readers, and your measurement may coincide with someone else's.
• Processor frequency. Modern processors change frequency with load and temperature, sometimes within fractions of a second.
• Caches. The first pass reads the data from memory, the following ones from the processor's cache. The first measurements are often slower than the rest: that is the warm-up.
• Garbage collection. Python and Go free memory from time to time, and that lands in somebody's measurement.
• Clock resolution. A clock ticks in finite steps. An operation of a few nanoseconds cannot be timed once—it has to be repeated a million times and divided.

Minimum, median and mean

Noise almost always adds time and almost never takes it away. So the distribution of measurements is lopsided: a sharp edge on the left—the machine cannot go faster—and a tail stretching right. Hence the different meanings of different numbers:

The documentation of the timeit module plainly advises looking at the minimum: higher values are usually caused not by Python getting slower but by other processes interfering with the timing. The mean and the standard deviation say little here—the tail drags them to the right. But if you are measuring not an algorithm but a service, where real people live through the tail, it is the other way round: you look at percentiles.

The mistake that speeds things up forty times

Go back to the second histogram. The code is almost the same: an in-place sort, xs.sort(). Only it sorts the same list every time, and from the second repetition on the list is already sorted. Python sorts with Timsort and Go with pdqsort, and both notice already ordered stretches and pass them in linear time. So the “sorting benchmark” actually measures a check that everything is already in place.

This is a particular case of a general trouble: a measurement must run on the same data as the real program. Sorted instead of random, small instead of large, cached instead of cold—and the numbers will be beautiful and useless. A good habit is to check the result inside the measurement: if the sort rearranged nothing, something is wrong.

Code

For short measurements Python has the timeit module. Its repeat function runs several series, each with a given number of runs, and returns the time of each series. Take the best series and divide by the number of runs. The setup code runs outside the measurement.

In Go the standard way is the benchmarks of the testing package. They are usually run with go test -bench, but testing.Benchmark can be called from an ordinary program too. It picks the number of repetitions b.N itself so that the measurement lasts about a second, and returns the mean time per operation. The for b.Loop() loop (Go 1.24 and later) also guarantees that the compiler does not throw the loop body away even if nobody uses its result.

Note the second line of the output: copying the data is work too, and if the copy got inside the measurement, you need to know its cost. Here it is tens of times smaller than the sort and can be ignored. Sometimes it is the other way round.

And this is the program that built the histograms above: it prints a line of JSON for each repetition, and the page draws them on the chart.

The rules of a fair measurement

1. Repeat. One measurement means nothing. Run series and look at the distribution.
2. Measure long enough. If an operation takes less than a microsecond, repeat it in a loop until a series takes at least a tenth of a second, and divide.
3. Warm up. Throw the first runs away, or at least look at them separately.
4. The same data as in real life. Size, order, distribution of values.
5. Nothing extra inside. Printing, reading a file, generating data—outside the measurement, unless that is what you measure.
6. Compare on one machine, interleaved. Measure two versions of code in turn several times, not one in the morning and the other in the evening.
7. Say where you measured. A number without the machine, the language and the data size means nothing. Every measurement in this catalogue is labelled.

What it costs

A fair measurement is expensive: hundreds of repetitions instead of one. But usually that is seconds, while the price of a mistake is a week of optimisation that in fact sped nothing up. If a measurement is hard to repeat, that is a reason to simplify it, not a reason to trust a single number. How to tell from measurements at several sizes how the time grows is the subject of empirical complexity; where exactly a program spends its time, of profilers.

Problems

From a series of measurements, compute everything discussed here: the minimum, the median, the mean and the mean without outliers.