27

I've quite frequently seen benchmarks where the tester discarded the highest and the lowest time out of N runs.

Discarding the highest time I understand; it's probably high because of some other processes running suddenly demanding more CPU.

But doesn't the lowest time indicate the best possible performance when the benchmark was running full tilt without interruptions?

6
  • 1
    do you have an example? – Ewan Dec 31 '20 at 10:35
  • 21
    If you were travelling to work via a commute that takes an average of 1 hour each way during typical rush hour traffic, would you care that it'd also be possible to do that exact same journey in 15 minutes at 4am on a Sunday morning when the roads are empty? – Ben Cottrell Dec 31 '20 at 11:01
  • I prefer to simply discard the highest and the lowest, then take the mean of the remainder. Discarding only the lowest seems unjustifiable to me. Although usually the slowest time is obtained on the first run; subsequent runs already have the code loaded into the cache, where it can execute more quickly. How you analyze the data depends on what you're actually trying to measure. Answering the question comprehensively really requires more details. – Cody Gray Jan 1 at 7:08
  • @CodyGray I've edited my question to better reflect what I was trying to find clarification to. – pepoluan Jan 1 at 7:31
  • 1
    @BenCottrell, that's ok with something so random as traffic. But a computer won't be randomly much faster in a run. If you get a quite better mark just once, it probably means there's something usually affecting your performance. – Andrew Jan 29 at 3:37
30

The lowest timing might indeed represent the "true" timing without outside interference, or it might be a measurement error. E.g. the boosting behaviour of a CPU might speed up the first run in a larger benchmarking suite, or a less congested network might speed up a net-dependent benchmark during certain times of day. Similarly, the highest timing might represent the true worst case, or non-representative interference. E.g. a background service might have started during the benchmark, or a SMR hard drive cache is being flushed during an IO-based benchmark.

Such interference indicates a flawed experimental design that fails to control for these influences, but it's not always possible or economical to design the perfect experiment. So we have to deal with the messy real-world data that we have.

Statistics like the mean (average) of some values is very sensitive to outliers. It is thus common to use a trimmed mean where we remove outliers, in the hopes of getting closer to the "true" mean. Various methods for determining outliers exist, with the simplest approach being to remove the top/bottom p%, for some value p. Another option is to use techniques like bootstrapping that let us estimate how reliable the estimate is: instead of removing top/bottom observations, we remove random observations and repeat the calculations multiple times.

However, it is not generally necessary to calculate the mean run time when doing benchmarking. For comparing the typical behaviour, we can use measures like the median or other quantiles. Especially when measuring latencies, quantiles like the 95%-percentile are often used (meaning: 95% of measurements were this fast or faster).

It is also unnecessary to calculate the mean when trying to determine whether one program is significantly faster than another. Instead of parametric statistical tests that require such parameters to be estimated from the sample, it is possible to use non-parametric tests. E.g. the Mann–Whitney Rank Sum Test only considers the order of values from two samples, not their actual values. While this is more flexible and more rigorous, this does lose some statistical power (you might not be able to detect a significant difference even if it exists).

4
  • 7
    My experience has generally been the exact opposite - the first run of a given test always seems to take considerably longer, due presumably to overhead of loading the program into memory and freeing up whatever resources it needs, so I'll usually throw out the first result because it's slower than the rest, rather than faster. – Darrel Hoffman Dec 31 '20 at 19:19
  • 1
    Depending upon how benchmarks are performed, there may be some factors that might arbitrarily affect one run, but would be unlikely to affect more than one. Discarding only the minimum seems odd, but discarding both the maximum and minimum would guard against situations where e.g. a computer clock which was a second ahead of or behind a that of a time server gets resynchronized during a test. Using a guaranteed-monotonic time source might be better, but such things may not always be readily available. – supercat Dec 31 '20 at 21:21
  • @DarrelHoffman Yes, that's my experience as well – modern computing involves so many caches that running a program twice in a row is usually faster. There are two experimental design approaches to address this: either perform warmup before performing benchmarking runs, or perform all experiments in a random order. But I've also had computational experiments where CPU boosting messed up comparability. E.g. colleague and I have identical hardware, but my Linux kernel had a different power management profile that prevented boosting in some experiments. – amon Jan 1 at 13:14
  • @amon Awesome answer, thanks! Especially the tip on 95% percentile. – pepoluan Jan 2 at 6:07
27

Outliers indicate unusual situations. Outliers are interesting in science, because they give you something to investigate, but they are useless in benchmarks.

If you have 10000 benchmark runs, and 9999 of them took one hour, but 1 of them took 1 second, then it is useless for your customers to tell them it will take 1 second, if there is a 99.99% chance that it will take one hour.

The problem is unexplained outliers, and it is usually simpler to discard the outliers than to investigate and find an explanation. Especially since oftentimes the explanation will be some freak occurrence that does not apply to real-world usage of the program, and thus makes it unlikely that your users will ever experience that performance.

1
7

I'd add the thought that before doing anything else I would eyeball the data, that is plot the distribution data. I'd do that with most datasets, for that matter. My experience as a retired statto is that missing this step and going for some mechanistic strategy can lead to missing the obvious.

There might be two peaks, with a whole clutch of unusually slow running times. If that is the case, I would then think it important to understand the cause, because the code might end up being used in an environment where that cause is the norm.

2
  • Yes, first comprehend the data set, certainly before changing it, by inspection of both the distribution and probability plots. The common practice is not right (in the sense of being correct) for every case. (Motto: The statto hats know all that.) – u2n Jan 28 at 13:37
  • Interesting thought... is there an automated/formulaic/programmatic way to, say, "alert" of "unusual" / "highly suspect" distribution? – pepoluan Jan 28 at 15:56
1

Another point: benchmarks are generally "averaged" using the geometric mean. The geometric mean intrinsically upweights the lowest value in the list, when compared to the algebraic mean.

On top of the domain-specific reasons for distrusting the lowest value, the use of the geometric mean intrinsically gives it extra weight.

0

Good benchmark design depends on what one is measuring, and who is doing the measuring. Throwing out low numbers is most likely to remove cases which benefit disproportionately from caching.

Not the answer you're looking for? Browse other questions tagged or ask your own question.