# How do I measure a speedup?

I have two versions of the same program. I apply a number of performance tests to both and measure their response time, for instance https://gist.github.com/valtih1978/d2cc2fe96fbbe1987ada

//  random(10000) //> compressed 10000-char msg into 66271 bits
//| in 59 (tree) vs 20 (table) msec
//| in 68 (tree) vs 17 (table) msec
//| in 45 (tree) vs 23 (table) msec
//| in 44 (tree) vs 19 (table) msec
//| in 42 (tree) vs 16 (table) msec
//| compressed 10000-char msg into 66319 bits
//| in 44 (tree) vs 15 (table) msec
//| in 77 (tree) vs 15 (table) msec
//| in 40 (tree) vs 95 (table) msec
//| in 47 (tree) vs 17 (table) msec
//| in 42 (tree) vs 15 (table) msec
//| compressed 10000-char msg into 66264 bits
//| in 45 (tree) vs 15 (table) msec
//| in 86 (tree) vs 15 (table) msec
//| in 39 (tree) vs 20 (table) msec
//| in 43 (tree) vs 14 (table) msec
//| in 41 (tree) vs 14 (table) msec
//| compressed 10000-char msg into 66315 bits
//| in 109 (tree) vs 17 (table) msec
//| in 85 (tree) vs 15 (table) msec
//| in 41 (tree) vs 21 (table) msec
//| in 94 (tree) vs 29 (table) msec
//| in 45 (tree) vs 30 (table) msec
//| compressed 10000-char
//| Output exceeds cutoff limit.


I want to figure out if one is faster and how much. This means that I have two samples, each has some variation. Now, how do I ensure that one is n times faster than another? Should I build some confidence distribution which will tell me that this it is k times faster with that probability? What can variance of rations can give me? Should I use resampling?

I cannot even figure out how to compute average speedup. Should I take average of corresponding speedups, $speedup_{avg} = (b_1/a_1 + b_2/a_2 + \ldots)/n$ or somehow compute $b_1$ vs. all $a_n$s and then aggregate them? If I was interested in aboslute differences, I would take $speedup_{avg} = (b_1 - a_1 + b_2 - a_2 + \ldots)/n$ because it is equal to running all $a$ tests, then all $b$ tests and taking the avarage difference $speedup_{avg} = ((b_1 + b_2 + \ldots) - (a_1 + a_2 + \ldots))/n$ or average of resampling all $b_i$ against all $a_j$, $$speedup_{avg} = {1/n\ (b_1 - a_1 + b_1 - a_2 + \ldots) + (b_2 - a_1 + b_2 - a_2 + \ldots)/n + \sum_{i=3}^n{\sum{(b_i - a_j)}/n} \over n}.$$ The fact that averages of agerages converge seems not the case for the ratios, howver. For instance,

$$avg_1 = {(b_1 + b_2)/(a_1 + a_2) \over 2}$$ $$avg_2 = {b_1/a_1 + b_2/a_2 \over 2} = {(b_1 + b_2 + b_2 a_1/a_2 + b_1 a_2/a_1) \over 2 (a_1+a_2)} = avg_1 + {b_2 {a_1 \over a_2} + b_1 {a_2 \over a_1} \over 2 (a_1+a_2)}$$

I am lost. Does it mean that any ratio-based statistic is not ergodic? I mean, can I just add up execution time of the first sample and divide by total executoin time of second to get the avarage ratio, can I just make one long run of the first program and long run of the second program instead of breaking them into pieces or I need that for the variance?

Should I use harmonic measure (workloads are the same for all the tests)? Or should I use square root for averaging? How do I decide?

Some people say that Fieller's Theorem must be used but I do not understand what should be proven here.

Is there a right measure for my purpose or there are many? Which is the simples and does the job?

• My suggestion: keep it low-level. Run both versions ~10000 times (should be no problem for runtimes in the order msec) and calculate the average time. Shorter average time -> faster program (at least on your machine and with your compiler ... another two reasons for not investing too much here). – davidhigh Jul 9 '14 at 9:52
• @davidhigh Might be my figures were too optimiztic. Here is more difficult to spot: one of the sequences must be 10% faster than the other given seq1(7,1,3,6,7,6,3,6,8,5,6,4,3,3,3,3,0,2,7,3,2,9,0,4,3,3,8,7,4,9,9,3,4) and seq2(5,5,0,9,5,7,3,7,10,1,3,9,0,2,6,9,1,7,8,5,7,3,1,8,10,9,4,3,5,9,8,7,5). Can you demonstrate that that? – Val Jul 9 '14 at 10:04
• That seems to me like a related but more theoretical problem (and, admittedly, I have not fully understood how to read your measurement results). My suggestion was completely pragmatic: if your program runs for milliseconds, let it run many times and compare the averages. This is what all the fancy statistical tests would do if they could ... (but if you are interested in these tests, maybe you should edit your question and pose the problem in your comment) – davidhigh Jul 9 '14 at 10:11
• @davidhigh You read it simply: one column contains execution time of the first program, another - of the second. For every execution of first program, I executed second. I do want a simple and practical method. Executing tests however takes time (hundreds of secons actually if not days, do not be confused by sample figures) and I have to have a statistical criteria for "statistically significant". This is what your method of longer runs lacks. I need to know when to stop. Do you mean that we sample one program until average has very low variance and then just take ratio of averages? – Val Jul 9 '14 at 14:41

You probably solved or worked around your questions long ago, but for the benefit of people finding this via search - as I did:

I cannot answer all questions, but especially this one:

Should I take average of corresponding speedups

No, you should never take the average of normalized values, it is meaningless. For an explanation, see the following paper from 1986: How not to lie with statistics: the correct way to summarize benchmark results by Fleming and Wallace.

As a simple example from the paper, consider that you have speed measurements of 20 (benchmark/sample 1) and 40 (benchmark 2) for X and 10 and 80 for Y. You compute the speedup of Y over X for each: 0.5 and 2.0 and their arithmetic mean is thus 1.25, so you would consider Y to be 25% slower than X. However, if you normalize to Y and get the speedups of X, you again get 2.0 and 0.5 resulting in an average of 1.25 - but for X this time, which is now 25% slower than Y!

There are more examples of that kind in the paper and even a proof of why the geometric mean is the only useful mean of normalized values.

A simple and useful thing one can do, is to compute the speedup of the average time: $(a_1 + a_2 + \ldots)/n \over (b_1 + b_2 + \ldots)/m$ or medians: $median(a_1, a_2, \ldots) \over median(b_1, b_2, \ldots)$.

For a more elaborate approach to speed-up evaluation see the article The Speedup-Test: A Statistical Methodology for Program Speedup Analysis and Computation by Touati et al.

They detail how to use statistical tests and confidence intervals with average and median speed-up measurements and provide flow charts to adhere to when declaring statistical significance and confidence levels.

• Thanks! I'm not a statistics expert, but was searching for the above papers again to refresh my memory and came across this question. – Klaas Sep 28 '15 at 14:03