External Validity and the Limits of What a Benchmark Shows

A benchmark is an experiment, and the result of an experiment is a statement about the conditions in which it was run. Internal validity asks whether the comparison inside the experiment was sound: whether the two versions differed only in the change under test, whether the noise was estimated rather than assumed, whether the design removed the drift. External validity asks a different question: whether the conditions of the experiment resemble the conditions under which the change will actually be judged. A result can be internally impeccable and still not transfer, and the failure is usually not statistical.

The result holds for the configuration, not for the program

An internally valid result is a claim of the form “under this input, this concurrency level, this data size, this machine, and this harness, version B cost less than version A by an interval of this width”. Every clause is a condition, and dropping one of them silently widens the claim.

The clauses fail independently. A change that reduces instruction count on one input path may increase it on another, and if the benchmark’s input distribution is narrow the second path is never exercised. A change that reduces the number of memory accesses may nonetheless cost more at saturation, when the reduction comes from batching that increases queueing. A change that helps on a machine with a large last-level cache may hurt when the working set no longer fits. None of these are measurement errors; they are conditions under which the measured result does not hold.

The useful form of a report therefore includes the conditions rather than only the estimate. Workload parameters, data scale, concurrency, machine description, and the harness’s warmup policy all belong next to the number, because they are part of the claim.

Data scale selects the regime

Performance as a function of input size is not one function with a constant factor attached. Cache-bound and memory-bound regimes differ by an order of magnitude in per-element cost, and the transition depends on the working set crossing a cache capacity. A benchmark run at a size that fits comfortably in cache measures a different machine than the same code at a size that does not.

This produces a specific pathology in comparing two implementations. If version A has a lower constant factor and version B has a better asymptotic behaviour, a benchmark at a small size will favour A and a benchmark at a large size will favour B, and neither result is wrong. Reporting one point on the curve answers a question about that point. Reporting the curve, or at least three sizes with a factor of ten between adjacent ones, distinguishes a constant-factor improvement from a change in slope, which is the difference between an optimisation and a different algorithm.

Extrapolating from one point to a regime is where benchmarks mislead most often. Complexity analysis gives the shape for the asymptotic region, but the constants that dominate in the transition region are exactly what the small-size measurement captures and exactly what is not preserved at scale: allocator behaviour, hash collisions, page sharing, and cache residency all change as data grows. A measurement at one size supports a claim at that size and at sizes where the regime is demonstrably the same. Establishing that requires measuring more than one.

import math

def loglog_slope(sizes, per_element):
    """Least-squares slope of log(time per element) against log(size)."""
    xs = [math.log(n) for n in sizes]
    ys = [math.log(t) for t in per_element]
    mx = sum(xs) / len(xs)
    my = sum(ys) / len(ys)
    num = sum((x - mx) * (y - my) for x, y in zip(xs, ys))
    den = sum((x - mx) ** 2 for x in xs)
    return num / den

A constant-factor improvement leaves the slope unchanged and moves the intercept; a change in asymptotic behaviour changes the slope. The intercept difference is the factor, and the slope difference is the algorithm.

Load level is a design variable, not a setting

A throughput measurement at low load and a latency measurement at high load describe different systems. At low load there is no queueing and the service time is the whole story; near saturation the queue is the dominant term and a small change in service time moves the tail latency substantially. A change that reduces service time by a few percent at low load can show a much larger effect near saturation, and a change that reduces service time by adding a shared resource can show the opposite, because contention grows faster than the service saving.

The consequence is that a single number, throughput at some fixed concurrency, answers neither question. The standard presentational form is a set of points along the load axis, with both throughput and latency reported at each, which shows the saturation point and the shape of the curve on either side. Two changes are comparable only at the same point on that axis, and often the interesting comparison is of the whole curve: a change that raises peak throughput but degrades latency at moderate load has made a trade whose acceptability depends on the workload’s position.

The related modelling constraint is Amdahl’s argument applied to a profile. Improving a component that occupies a fraction $f$ of the end-to-end time bounds the possible end-to-end gain at $1/(1-f)$ however much the component improves. A microbenchmark showing a large improvement in a component does not produce a proportional end-to-end improvement, and the arithmetic is elementary: a component that is 5 percent of the total can at best yield a little under 5.3 percent.

Where the workload comes from determines what it can represent

Synthetic workloads generate inputs from a distribution chosen by the experimenter, which makes them controllable and reproducible and makes them a hypothesis about the real input distribution. Traces record inputs that actually occurred, which makes them representative of the period they were captured in and makes them a sample of size one from a distribution that drifts.

Both choices have failure modes that are the mirror of each other. A synthetic distribution that omits a heavy tail of key sizes will produce a smooth result that no real deployment sees. A trace replayed against a system that would have changed the response to it produces results that are internally consistent and externally stale, since the recorded input is a response to a system that no longer exists. The standard mitigation for the second is to capture the request stream rather than the derived state, so the replay poses the same questions to a different implementation, which is what benchmark harnesses for storage and key-value systems do.

The choice of operation mix is a third degree of freedom. A distribution over operations determines which code paths receive weight, and the weights are the least transferable part of a workload description because they vary with clients, with time, and with the system’s own behaviour. Reporting the mix with the result at least makes the weight explicit.

Containers and virtualisation change the machine

A measurement taken inside a container is a measurement of a machine the container’s configuration defines. CPU quota is the clearest case: a control group limited by a bandwidth quota is allowed its budget within a fixed period, defaulting to a hundred milliseconds in the kernel’s CPU controller, and a workload that exhausts the budget before the period ends is throttled until the next period. A benchmark whose bursts fit inside the budget sees full speed; one whose bursts do not sees a stall whose length depends on where in the period the burst began.

That makes throttle-induced latency partly a function of phase, so the variation between runs includes the alignment of the workload with the quota period. Repeatable measurement requires either staying well inside the budget or knowing the period and measuring enough periods. Memory limits behave similarly: a limit below the working set turns the measurement into a measurement of reclaim, prefetch policy, and in the worst case early out-of-memory killing rather than of the code.

Virtualisation adds a floor under every measurement. Privileged operations that trap to the hypervisor cost microseconds rather than nanoseconds, clock reads may be trapped, and steal time appears as elapsed time during which the guest had no CPU. A comparison of two implementations inside a virtual machine is still internally valid, since both see the same conditions, but the size of the measured effect is compressed toward zero by the fixed overhead, which is the reason a null result from a virtualised environment says little about the same change on bare metal.

Goodhart’s problem with a fixed benchmark

Unlike the statistical defects, this one does not shrink with more runs. A benchmark that is used as a target becomes a thing to be optimised, and the optimisations that move the number are not necessarily the ones that improve the system. A workload with a fixed input file permits special-casing that file; a workload with a known access pattern permits prefetching that pattern; a compiler tuned by measuring against a suite can become good at that suite’s idioms in ways that generalise unevenly.

The statistical analogue is that repeated comparison against the same sample selects for effects that are specific to that sample, which is the multiple-comparisons problem applied to workload selection rather than to testing. It is addressed the same way, by holding out data: keeping a workload or a data set that is not used during optimisation and measuring against it at the end. The held-out result is a less biased estimate of the effect, though it is a single draw with its own interval.

The alternative is to accept the benchmark as a proxy and say so, which is a weaker claim than it appears. A proxy that has been optimised against for long enough stops tracking the quantity it was chosen to proxy, and the fix is to change the workload rather than to refine the measurement. Deciding when a benchmark has stopped being informative is a judgement about the workload, not about the statistics.

The checks that survive a change of environment

Three checks are inexpensive and catch most of the failures described here. Measure at more than one data size, so a slope change is distinguishable from a constant-factor change. Measure at more than one load level, so the throughput-latency trade is visible. Hold out at least one workload, so the result is not purely a property of the workloads used during development.

Where the measured object is a comparison rather than an absolute number, the estimators in Confidence Intervals for the Difference Between Two Benchmark Runtimes and the aggregation rules in Averaging Ratios and the Geometric Mean in Composite Scores apply within each configuration. External validity is a question about which configurations were sampled, and the sampling error across configurations is usually larger than the sampling error within one.