How Many Benchmark Runs Are Enough

Investigation · Part 12 of 20 · When the benchmark lies

How many runs do I need before I can trust a median? The usual answer is a number: 5, 10, 30. I wanted to see what these numbers mean on my laptop, so I made a benchmark that runs one sort of a million numbers in a fresh process and prints the time, and I ran it 300 times, in three sets of 100 runs, 20 seconds apart.

Here is the short version of the result, one line per set, each with the median and its 95 percent bootstrap interval:

  set 1: 100 runs  median 13.897  interval 13.595 to 14.313  mean 14.162  standard deviation 0.785
  set 2: 100 runs  median 14.393  interval 13.805 to 14.918  mean 14.590  standard deviation 1.439
  set 3: 100 runs  median 12.668  interval 12.567 to 12.822  mean 12.703  standard deviation 0.707

Each set says something like "the median is known within a few percent". And the third set is outside the intervals of the first two. So at least one of these intervals does not mean what it seems to mean. This part is about why.

One set of 100 runs

The program creates the same pseudo-random million u32 values in every process, sorts them with sort_unstable, and prints the time of the sort in milliseconds, and the frequency of its CPU right after it. The processes run one after the other, pinned to CPU 2. This is set 1:

100 runs, one sort of 1,000,000 u32 values each, in ms
  min 13.097  median 13.897  mean 14.162  max 15.477  standard deviation 0.785
histogram, bins of 0.5 ms:
    13.00 -   13.50   31  ###############################
    13.50 -   14.00   23  #######################
    14.00 -   14.50    8  ########
    14.50 -   15.00   14  ##############
    15.00 -   15.50   24  ########################

It does not look like the bell curve of a statistics book. It has two groups, one around 13.5 ms and one around 15 ms, with fewer runs between them. The mean, 14.16 ms, is in the gap. The standard deviation, 0.785 ms, describes the distance between the two groups more than any spread around one value. This is the first problem with "mean plus or minus standard deviation": it assumes a shape that the data does not have.

The order of the runs explains the two groups:

the runs in order, median of each group of 10:
  14.90 15.24 14.62 15.31 14.19 13.58 13.55 13.39 13.29 13.43

The first half of the set was slower than the second half. The raw file has the frequency after each run, and the clock moved: during the first 50 runs it was about 3.6 GHz on average, during the last 50 about 4.0 GHz. The times changed by the same ratio as the clock, 10 percent. Nothing in the program changed. This is the clock problem of part 6, now at the level of whole processes.

The bootstrap

To put an interval around a median, I used the bootstrap, which needs nothing but the data and some computation. Take the sample of k runs, draw k values from it at random, with replacement, and compute the median of this new sample. Do it 10,000 times. The middle 95 percent of these 10,000 medians is the interval. In Python, with only the standard library:

def bootstrap_median(sample, resamples=10_000, seed=1):
    rng = random.Random(seed)
    medians = sorted(statistics.median(rng.choices(sample, k=len(sample))) for _ in range(resamples))
    return medians[int(0.025 * resamples)], medians[int(0.975 * resamples) - 1]

The idea is that the sample is our best picture of the distribution, so resampling from it shows how much the median could move with another sample of the same size. Here is the interval when I use only the first k runs of set 1:

95% bootstrap interval of the median (10,000 resamples), using the first k runs:
  k=  5  median 14.809  interval 14.356 to 14.861  width 0.505 ms (3.4%)
  k= 10  median 14.899  interval 14.809 to 15.208  width 0.399 ms (2.7%)
  k= 30  median 15.038  interval 14.823 to 15.207  width 0.385 ms (2.6%)
  k=100  median 13.897  interval 13.595 to 14.313  width 0.718 ms (5.2%)

With 10 or 30 runs, the interval is between 14.8 and 15.2 ms, and it is narrow, less than 3 percent. And the median of all 100 runs, 13.897 ms, is not inside it. With 30 runs, I would have reported the median with an interval that is confident and wrong. I did not like that. The interval of 100 runs is wider than the interval of 30, which is the opposite of the textbook, because now the sample includes both halves of the set.

The same happens with runs from two moments of the same set:

  runs  34- 38  median 15.368  interval 15.296 to 15.477
  runs  67- 71  median 13.493  interval 13.381 to 13.596

Five runs here, five runs less than a second later, and two intervals that do not touch.

The runs were not independent

The bootstrap, like most of the statistics we use for benchmarks, assumes that every run is an independent sample from the same distribution. On this laptop that is false. A run is not only my program, it is my program plus the state of the machine at that moment: the clock, the other programs, the temperature. And this state changes more slowly than one run. So consecutive runs are similar to each other, and different from the runs of a few seconds later.

The cycles show it best. The summary multiplies each time by the frequency after the run:

the clock after each run, and millions of cycles per sort (ms times MHz, divided by 1000):
  set 1: median 3896 MHz  cycles: p10 53.3  median 53.9  p90 54.4  max 55.7 million
  set 2: median 3800 MHz  cycles: p10 53.3  median 53.9  p90 54.7  max 82.4 million
  set 3: median 4285 MHz  cycles: p10 52.2  median 54.4  p90 56.6  max 74.4 million

In cycles, the sort costs about 54 million in all three sets. I liked that. The work is the same; the clock is different, and set 3 ran at a higher clock than the two others. One frequency reading per run is approximate, but it is enough to see that the three medians differ because of the machine. (A few runs needed more cycles, up to 82 million. Those are slowed by something else, and I do not know what.)

So "how many runs" is the wrong question when the runs are not independent. Kalibera and Jones, in "Rigorous Benchmarking in Reasonable Time", make this point in a general way: "repetition is most needed where most uncertainty arises", for example between builds, between executions or between iterations. Here the biggest uncertainty was between moments. 100 runs in about two seconds repeated the wrong level: they gave a very precise picture of those two seconds.

When I ran this part a second time, on a quieter laptop, I got another picture of the same problem. The three sets agreed, with medians of 11.84 to 11.94 ms. But each set started with three to five runs that were two to four times slower, right after a pause (one second before set 1, 20 seconds before the other two), and with only its first 5 or 10 runs, the interval of set 1 was 59 and 135 percent wide. The runs were not independent there either; only the pattern was different (p12-how-many-runs.txt).

So how many?

For a single number about a program on this laptop, I now do this:

• Enough runs to see the shape of the distribution, and runs from more than one moment. 5 runs can not show two groups; 30 can, but only if both groups are inside them, and here the first 30 runs were all in the slow half.
• Several sets, at different moments, and the spread between their medians. If the sets disagree, the honest uncertainty is the disagreement, not the interval of one set.
• The median and the histogram, not the mean and the standard deviation, because the data is skewed or has groups. This is also why every line of this series reports a median since the first part.
• The clock or the cycles next to the time, so that I can see if the machine changed.

And when I compare two versions, I do not run all the runs of A and then all the runs of B. The second version would get a different minute. The next part measures what this does to a comparison.

Georges, Buytaert and Eeckhout reached a similar conclusion for Java in "Statistically Rigorous Java Performance Evaluation": they showed that common ways to report benchmark results "can be misleading, and can even lead to incorrect conclusions", because the data analysis is not statistically rigorous. The same problem appears with evaluation scores of AI systems, where a single score from a small eval set has a wide interval, and a paired comparison works much better than two separate scores.

The programs, the three sets of raw times and the analysis are in the fixture, in p12-how-many-runs.txt.

References

• Tomas Kalibera, Richard Jones: Rigorous Benchmarking in Reasonable Time, ISMM 2013 (author version)
• Andy Georges, Dries Buytaert, Lieven Eeckhout: Statistically Rigorous Java Performance Evaluation, OOPSLA 2007 (author version)
• Python documentation: random.choices