12
$\begingroup$

Say I have slow and fast versions of some code, and want to report a speedup number comparing the two. I run the slow version $n$ times and the fast version $m$ times, producing times $(s_1, \ldots, s_n)$ and $(f_1, \ldots, f_m)$. The simplest way to produce a speedup is to average the means: $$\frac{\bar{s}}{\bar{f}} = \frac{m \sum_{i<n} s_i}{n \sum_{j<m} f_j}$$ However, this does not take outliers into account.

Question: What is the best statistic to use when reporting speedup numbers?

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ How big is the standard deviation in comparison to the mean? Whatever you do, you should report what you did and probably put error bars if they are large. If they are really large, you should investigate the source. Most computer code should run pretty deterministically in time unless there's a random component to the program itself or you are sharing computer resources with others (this could be networking or disk, not just cluster nodes). If competition for disk resources is the problem, you might consider reporting performance with I/O disabled (quite common)--just be sure to note it. $\endgroup$
    – Bill Barth
    Feb 23, 2014 at 21:36
  • $\begingroup$ On Edison (a Cray supercomputer), I have a 2% difference between two samples. On my laptop I see a 6-8% standard deviation measured over 10 samples. Both are for compute kernel only, no I/O. $\endgroup$
    – Geoffrey Irving
    Feb 23, 2014 at 21:50
  • $\begingroup$ To clarify why I am mentioning outliers if the variances are already reasonably low: this is a sufficiently fundamental statistical quantity that I would like to know the ideal way to report it, even I nonideal ways are fine in this particular case. $\endgroup$
    – Geoffrey Irving
    Feb 23, 2014 at 21:52
  • 2
    $\begingroup$ The question is what are you trying to communicate, and formula would communicate that best? I don't think I've ever seen a paper that reports the run-to-run variability in speedup unless the cause was central to the paper. Given that we posit a linear relationship between run time and processor/task/thread count, you're probably fine to use the ratio of means, but then error bar that with the ratio of max-to-min and min-to-max if you think showing the range is important. Also, you should probably look at your frequency scaling and task pinning options to cut down on your variability. :) $\endgroup$
    – Bill Barth
    Feb 23, 2014 at 23:06
  • $\begingroup$ There can be a lot of trickery in eliminating IO. Between compiler optimizations to "Copy On Write" tricks there can be really non-obvious ties downward. I usually follow the prototype of d1 = loadData(); d2 = copy(d1); r1=algo(d2); r2=algo(d1), and only consider the time of the second run. $\endgroup$
    – meawoppl
    Feb 26, 2014 at 1:29

3 Answers 3

Reset to default
9
$\begingroup$

In addition to all that Bill Barth has already said above, let me mention that people often report the fastest of several runs. The rationale is that the actual run time is the ideal run time plus any number of slow downs resulting from other processes running, OS delays, network delays, etc. Since these are all noise we are not interested in, using the fastest run time comes closest to the one we really want to know.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Unfortunately, this principle doesn't help when reporting a speedup between two algorithms. $\endgroup$
    – Geoffrey Irving
    Feb 24, 2014 at 6:02
  • 3
    $\begingroup$ @GeoffreyIrving, why not? Both algorithms have a theoretical performance expectation vs. problem size (or processor count or other non-statistical parameter) with low-order and parameter-independent terms ignored. Using the fastest time (and noting this fact) is simply helping you to ignore these additional terms. Which seems like a fine strategy. Unless you tell us differently, it seems like you're trying to figure out how to communicate the difference between to algorithms most effectively, and Wolfgang's suggestion is conventional and expected so it might convey that information best. $\endgroup$
    – Bill Barth
    Feb 24, 2014 at 13:34
  • 1
    $\begingroup$ Oops, yep, you're right. I happily withdraw my statement. $\endgroup$
    – Geoffrey Irving
    Feb 24, 2014 at 17:45
  • $\begingroup$ (+1) A side-question: I complete see your point about non-symmetric noise distribution, etc. Let's say though that I make an implementation A, and an implementation B and I benchmark them and after a reasonable amount of runs, the 25-th quantile and the median and mean are ~4.5x faster in A than B while the 0% quantile is ~3x. When comparing implementation A to B, despite the fact that: yes A is theoretically only ~3x faster, isn't a ~3x speed-up unrepresentative of the speed-up on might expect when using implementation A instead of B? (This is a real-life example by the way) $\endgroup$
    – usεr11852
    Apr 19, 2015 at 7:59
  • 1
    $\begingroup$ @usεr11852: It all depends on the system you're on. If your median or 25th quantile are so far apart as to distort the statistics in the way you hypothesize here, then you're likely on a system that has a lot of noise. For example, it may be used by others at the same time, etc. That may not be representative of the systems others have for their repeat experiments, and it would sound to me like you're overselling your results in that case. So, I still suggest to report the best runs. Whatever you do, you should report in the paper what statistics you use. $\endgroup$
    – Wolfgang Bangerth
    Apr 19, 2015 at 18:41
1
$\begingroup$

I suggest you use the median to give a statistical estimate. Unlike the mean, the median is not corrupted by outliers.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ For data where all noise is positive (i.e., with a non-symmetric noise distribution), the median is as bad as any other statistic. For run-times, this is indeed the case, see my answer above. $\endgroup$
    – Wolfgang Bangerth
    Feb 27, 2014 at 13:23
0
$\begingroup$

If the standard deviation is not negligible, you could use two box plots side-by-side, constructed each with the timing of one of the algorithms. They are by all means not standard in numerical analysis, but they do a great job in displaying this kind of information.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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