Confidence Intervals for the Difference Between Two Benchmark Runtimes

Comparing two versions of a program is the central act of performance work, and it is a two-sample problem with a small sample size, a skewed distribution, and a strong dependence on the machine state. The usual output, a pair of means and a percentage, discards the information needed to know whether the difference is real. An interval on the difference carries that information, and its width is determined by the design of the experiment rather than by the analysis.

The interval on each side is the wrong object

Two runs produce two intervals, and the question is whether the difference between them is distinguishable from zero. The reflex of checking whether the intervals overlap is not a valid test, because each interval is computed at a coverage level chosen for its own mean, and the coverage of the combined statement is not the product of the two.

The concrete failure direction is one-sided: non-overlapping intervals do imply a difference at the stated level, but overlapping intervals do not imply the absence of one. Two 95 percent intervals can overlap by a meaningful amount while the 95 percent interval on their difference excludes zero, because the standard error of the difference of two independent means is $\sqrt{s_1^2/n_1 + s_2^2/n_2}$, which grows as the variances add rather than as the standard errors add.

The correct procedure computes the difference and its standard error directly, then forms the interval on that. For independent samples with means $\bar{x}_1, \bar{x}_2$ and sample variances $s_1^2, s_2^2$ over $n_1, n_2$ observations, the interval is

$$\bar{x}_1 - \bar{x}2 \pm t{1-\alpha/2,,\nu} \sqrt{\frac{s_1^2}{n_1} + \frac{s_2^2}{n_2}}$$

with the degrees of freedom $\nu$ given by the Welch–Satterthwaite approximation when the variances are unequal. The approximation matters in benchmarking because the two versions commonly have different variance: a change that trades a consistent cost for an occasional slow path can leave the mean similar and the variance much larger.

from math import sqrt
from statistics import NormalDist, fmean, stdev

def diff_interval(a, b, level=0.95):
    """Normal-approximation interval for mean(b) - mean(a).

    Exact coverage for small samples needs the Student t quantile with
    Welch-Satterthwaite degrees of freedom; the normal quantile is the
    large-sample limit of that.
    """
    se = sqrt(stdev(a) ** 2 / len(a) + stdev(b) ** 2 / len(b))
    z = NormalDist().inv_cdf(0.5 + level / 2)
    diff = fmean(b) - fmean(a)
    return diff - z * se, diff + z * se

Paired designs collapse the machine’s contribution

The dominant source of variance between two runs is usually not the code. It is the machine: frequency state, cache and memory placement, other processes, thermal conditions, and for virtualised hosts the neighbour’s load. All of that is common to both versions when they are measured in the same session, and it is independent noise when they are measured in separate sessions.

A paired design measures the difference within a block and removes the block effect. Running version A and version B alternately, each $k$ times, and computing the difference within each pair, gives a series of differences whose variance excludes everything that changed slowly relative to the alternation period. The interval is then formed on the mean of the paired differences with standard error $s_d/\sqrt{m}$ over $m$ pairs.

The gain can be large. If the block-to-block variance is $\sigma_b^2$ and the within-block variance is $\sigma_w^2$, the variance of an unpaired difference of means is $2(\sigma_b^2 + \sigma_w^2)/n$, while the paired version is $2\sigma_w^2/m$. When the machine drifts by more than the effect under test, which is common, the paired design is the difference between detecting the change and not.

The cost is a constraint on ordering. Alternation must not line up with a periodic cycle in the machine, such as a frequency governor’s own period or a background job’s schedule. A randomised order within blocks, or a longer alternation period than any suspected cycle, protects against this. Variance Reduction by Pairing, Interleaving, and Blocking develops the design side of this in more detail.

Where the normal approximation stops working

The $t$ interval assumes the sample mean is approximately normal. With independent samples of a skewed quantity, the central limit theorem makes the mean approximately normal at a rate that depends on the skew. Latency data is extremely skewed, and a sample of a few dozen observations from a distribution with a heavy right tail can produce an interval that excludes the true mean far more often than the nominal rate.

There are three honest responses. Increase the sample size until the approximation holds, and check the skew to know how large that must be. Transform the data, with the logarithm the usual choice for latency, forming the interval on log values and exponentiating the endpoints; this makes the interval multiplicative and changes the estimand to the ratio of geometric means. Or use a method that does not rely on normality, which Distribution-Free Comparison When the Data Is Not Normal covers.

The choice changes the claim. An interval on the difference of means answers “how much total time does this change add per operation”. An interval on the ratio of geometric means answers “by what factor does this change multiply the typical cost”. These are different questions and can give different signs of conclusion for a distribution with a small typical value and a heavy tail.

The ratio, and why it is the reported number

Benchmarks are usually reported as a ratio or a percentage because absolute times are not comparable across machines. The ratio of two means is not the interval of the numerator divided by the interval of the denominator; its standard error needs the delta method or a paired construction, and the resulting interval is asymmetric around the point estimate when the relative error is not small.

For paired data the ratio of means can be formed from the per-pair ratios when the denominator is bounded away from zero, and the interval computed on those. The caveat is that a ratio of means is not the mean of ratios, and the two differ by an amount that depends on the correlation between numerator and denominator. A version that is faster on average may be slower in every individual pair if it is faster only where the machine is fast, which is a real possibility when the two versions respond differently to frequency or cache state.

The practical rule is to report the estimand explicitly. A statement of the form “version B is 3 percent faster” is ambiguous until it says whether it means the totals, the typical operation, or the median. Each has a separate interval and a separate design requirement.

Effects smaller than the harness can detect

An interval that includes zero is not evidence that the two versions are identical. It is evidence that the experiment could not distinguish them at the chosen level, and the width of the interval quantifies how large an effect could have been present and missed. Reporting only the p-value discards this, and reporting only the point estimate hides it.

The number that captures it is the minimum detectable effect, which for a two-sided test at level $\alpha$ and power $1-\beta$ is approximately $(z_{1-\alpha/2} + z_{1-\beta})$ times the standard error of the difference. At the conventional five percent level and eighty percent power that factor is about $2.8$ standard errors, while the 95 percent interval’s half-width is about $1.96$ standard errors. The detectable effect is therefore roughly one and a half times the half-width of the interval the experiment reports.

The consequence for regression detection is direct. A harness with a standard error of 2 percent on the difference can detect a 6 percent change reliably and cannot detect a 1 percent change at all, no matter how many times the mean is computed from the same numbers. Closing that gap requires reducing the standard error, which means a better design rather than a more elaborate analysis: more independent trials, paired blocks, and control over the machine’s state.

A second consequence is that a null result must be reported with its width. A change that shows a difference of $0.4$ percent with a half-width of $3$ percent has not been shown to be neutral; it has been shown to be somewhere within $\pm 3$ percent, which for a hot path may be an unacceptable uncertainty.