How to measure which program is faster than another in a statistically meaningful way?

I am trying to compare 2 computer programs, X and Y, for speed. I want to determine which one is faster. I could, for example, chronometer those programs 20 times, take the average and state that the program with the lowest average is the fastest one.

I don't know much about statistics, though - is that what I'm doing actually correct? What would be a more meaningful way to test them?

• You may be interested in criterion, a Haskell library that benchmarks programs statistically. Here is some example output that came from this Stack Overflow answer. – jtobin Sep 9 '13 at 21:37
• My suggestion would be to construct a confidence interval for either the difference in time, or the difference in log-time or the difference in speed (1/time), whichever is the most relevant for you. If the difference you use has a CI that includes zero, you can't distinguish the time-difference from just random noise and should probably avoid calling one of the programs faster. Such a CI could be constructed via a bootstrap if the sample size isn't too small, or via permutation/rank based methods, or via parametric methods (e.g. from a GLM type model) – Glen_b Sep 9 '13 at 23:57

There are (at least) two aspects to your question:

1) What do you mean by "faster"? 2) Once you've established that, how do you test it?

The first is one that you will have to answer: What is a "faster" program depends on what the nature of the program is. If it's a sort, for example, how many items? How sorted before? How linked to other things? etc. For more complex programs, more things can vary. E.g. a program to do regression would vary on a dozen parameters or so. So, you'd have to figure that out. Then you'd have to test the two programs for a variety of conditions. You might have to test more than once for each condition, if there is much variation over time (I don't know if there is).

For 2) it might be possible to do something as simple as a t-test, but probably you will be interested in how the relative speed varies as a function of the parameters. (e.g. program A is faster when there are 10,000,000 items to sort, but B is faster when there are 1,000,000,000 items or something like that). That might call for some sort of regression model

Speed ~ program + parameter1 + parameter2 .....

IMO, averaging 20 runs and then comparing the averages of each program is a fine start. You might also want to record some measure of dispersion for each set of runs; a range, standard deviation, etc.

What's important is to ensure that you're dealing with a clean benchmarking environment. I.e., that each run of the program is performed over as similar a background state as possible. This is a trickier issue, and is difficult to achieve perfectly on most computers.

This blog post explaining the criterion library might be a worthwhile read.