3
$\begingroup$

Most of the time, when I see someone reporting the average timing of a certain algorithm on a computer in a computational mathematics paper, they do something like this:

  1. Run the operation $n$ times (e.g., $n=100$ times);
  2. Discard the lowest and highest $m$ times (e.g., $m=10$ outliers);
  3. Compute the average of the remaining $n-2m$ times.

I can understand why dropping the highest results make sense: these are likely cases in which the computer switched threads into doing something else. I cannot understand why dropping the lowest results makes sense.

Why should I guard against an outlier being faster than the rest of the iterations? If anything, intuitively I would say that it is the minimum of the $n$ results that tells me how much time my computer really needs to run that algorithm. All other instances are cases when the computer switched into something else, or pipelines and multithreading were not used optimally.

The only case in which I can imagine this making sense is when the results reported are very close to the precision of the clock, but in this case I would say that the correct approach is repeatedly measuring the time for a sequence $k$ of runs at the same time (e.g., $k=100$) and then discarding outliers on those numbers. But in a case where outliers due to multitasking are the main concern, I do not see the advantages of this procedure.

$\endgroup$
  • $\begingroup$ If you look at really good benchmarking suites, such as criterion.rs, they don't do this: bheisler.github.io/criterion.rs/book/getting_started.html $\endgroup$ – user14717 Oct 12 at 12:35
  • $\begingroup$ I personally have never seen what you're describing . . . $\endgroup$ – user14717 Oct 12 at 12:37
  • $\begingroup$ @user14717 So what does that benchmarking suite do, exactly? $\endgroup$ – Federico Poloni Oct 12 at 12:43
  • $\begingroup$ Statistical analysis of performance data. $\endgroup$ – user14717 Oct 12 at 12:56
4
$\begingroup$

I don't know why Chris Rackaukas hid his answer because it's actually quite good. In the following, I'm going to assume that the program being tested is executing the same instructions every single time.

I believe that those who use averages or omit outliers in both directions have not fully understood what kind of statistics they would expect from run times. Their assumption seems to be that statistical noise for runtimes can be both positive and negative, but of course that is not actually true: The noise is always positive. As a consequence, computing the mean, or omitting outliers in both directions makes no sense. The only reasonable statistical estimator for the run time is to take the minimal run time.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ If your library would be used as part of a longer running calculation, the fastest times may represent an unusually light thermal load and therefore faster clock times, but that kind of qualification seems so unusual as to place an author trying to make it at a disadvantage. $\endgroup$ – Richard Oct 12 at 23:59
  • 1
    $\begingroup$ @Richard Yes, in times of processors that throttle their own speeds in response to thermal loads, this is a valid observation. But I still think that taking the minimum runtime is the only statistically useful metric. $\endgroup$ – Wolfgang Bangerth Oct 13 at 13:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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