How do I measure a speedup?

Question

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?

Answer 1

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.