Determining the "variability" of a benchmark

Question

I have a software benchmark which is quite noisy. I am trying to for the bugs which are causing the noise, and I need to be able to measure it somehow.

The benchmark is comprised of a number of subbenchmarks, for example:

"3d-cube": 31.56884765625,
"3d-morph": 21.89599609375,
"3d-raytrace": 51.802978515625,
"access-binary-trees": 15.09521484375,
"access-fannkuch": 45.578857421875,
"access-nbody": 8.651123046875,

The times are in milliseconds. The times typically vary between runs. For example, on my machine, the "3d-cube" benchmark tends to take around 35ms, but I've seen it go as high as 44ms, and 31ms (above) is uncharacteristically low.

My aim is to change the benchmark so that minor improvements to the run-time can be visible in a benchmark result. What I need is a number that tells me whether I have reduced the "variability" of the benchmark.

My own solution

I run it the benchmark 1000 times, the took the sum of the differences between each subbenchmark's mean and its actual run-times. In pseudo-code:

v = 0
for s in subbenchmarks:
  x = mean of all iterations of s
  for i in iteration
    v += absolute_value(results[s][i] - x)

I'm sure this isn't statistically valid (having asked someone), but what is a "correct" way of measuring this "variability" so that I can reduce it.

Answer 1

As gd047 mentioned, the standard way of measuring variability is to use the variance. So your pseudo-code will be:

vnew = vector of length subbenchmarks
for s in subbenchmarks:
  vnew[i] = variance(s)

Now the problem is, even if you don't change your code, vnew will be different for each run - there is noise. To determine if a change is significant, we need to perform a hypothesis test, i.e. can the change be explained as random variation or is likely that something has changed. A quick and dirty rule would be:

\begin{equation} Y_i = \sqrt{n/2} \left(\frac{vnew_i}{vold_i} -1\right) \sim N(0,1) \end{equation}

This means any values of $Y_i < -1.96$ (at a 5% significance level) can be considered significant, i.e. an improvement. However, I would probably increase this to -3 or -4. This would test for improvement in individual benchmarks.

If you want to combine all your benchmarks into a single test, then let

\begin{equation} \bar Y = \frac{1}{n} \sum Y_i \end{equation}

So

\begin{equation} \sqrt{n} \bar Y \sim N(0, 1) \end{equation}

Hence, an appropriate test would be to consider values of $\bar Y < 1.96$ to indicate an improvement.

---

Edit

If the benchmarks aren't Normal, then I would try working with log(benchmarks). It also depends on what you want to do. I read your question as "You would like a good rule of thumb". In this case, taking logs is probably OK.

---

1. Further details of the mathematical reasoning are found at Section 3.2 of this document.
2. I've made a approximation by assuming that v_old represents the true underlying variance.

Answer 2

I guess that your method is the one described here, and it's apparently valid. You could also have used the standard deviation as a measure of variability (which according to the article, it's not as robust as your absolute deviation)

Check out this, for other measures of statistical dispersion.