research30 min studyLesson 985 in Engineering

Repeated runs and variance decomposition

Allocate repetition to independent experimental levels instead of treating every nested timing as a new system execution.

On this page

What you’ll understand

  • Identify the independent units behind nested benchmark observations.
  • Decompose a simple run-level and iteration-level variance model.
  • Choose repetition based on uncertainty sources and experimental cost.

A thousand timings collected inside one process do not provide the same evidence as a thousand independently started processes. They share address layout, compilation decisions, machine state, and sometimes a slowly changing background load. Repetition matters at the level where uncertainty arises. A defensible experiment keeps those levels visible and spends its budget on independent units that can change the conclusion, rather than merely producing a large count of correlated measurements.

Write down the nesting before calculating an error bar

Builds can contain executions, and executions can contain timed iterations. Data-center studies may add machines, allocation windows, or clusters above those levels. Record identifiers for each observation’s parents. When a treatment is assigned to an entire process, iterations within that process are not independent treatment assignments. Warmup and steady-state behavior also require a declared policy: discarding initial iterations after inspecting each run’s favorable region can select the answer. Retain the original observations and document any justified stabilization rule.

A simple balanced random-effects model represents one run-specific offset plus independent within-run noise. The run offsets are independent across runs, the residuals are independent across iterations and runs, and the two families are independent. These assumptions are illustrative, not automatic properties of benchmark data. Autocorrelation, machine drift, unequal variances, and heavy tails may require richer models or different estimators. A variance component associated with builds or hosts must be modeled at that level rather than folded into a fictitious independent iteration count.

Yij=μ+bi+εij,Var⁡(bi)=σb2,Var⁡(εij)=σe2Y_{ij}=\mu+b_i+\varepsilon_{ij},\qquad \operatorname{Var}(b_i)=\sigma_b^2,\quad \operatorname{Var}(\varepsilon_{ij})=\sigma_e^2
Y_ij is a timing in milliseconds for iteration j of run i. The zero-mean random offsets and residuals satisfy the stated mutual independence assumptions. Variances therefore have units ms²; this two-level model is not a universal benchmark distribution.↔ Scroll wide equations horizontally.

Reduce the component that dominates uncertainty

Under this balanced model, averaging k iterations reduces within-run noise, but it does not average away the offset shared by all iterations of one run. Independent runs reduce both components in the overall mean. This explains why collecting more iterations in a single process can reach diminishing returns. Pilot measurements can estimate where uncertainty is concentrated, subject to their own sampling error. Use that evidence with startup, rebuild, or allocation costs to plan repetition rather than applying a fixed count to every benchmark.

Allocate independent units to both comparison arms and preserve meaningful pairing when they share inputs or machine-time blocks. Analyze paired differences at the level where pairing actually occurs. For a bootstrap, resample the appropriate independent clusters or use a hierarchy-aware method; resampling individual requests ignores a common run effect. Confidence intervals for a mean do not describe the full latency distribution or the uncertainty of a high percentile. Report the estimand, variance model, unit counts, and method together.

Var⁡(Yˉ)=σb2m+σe2mk\operatorname{Var}(\bar Y)=\frac{\sigma_b^2}{m}+\frac{\sigma_e^2}{mk}
There are m independent runs and k iterations per run in a balanced design, under the preceding model. The grand mean has units ms and its variance ms². This formula assumes the components are known for the calculation; real estimates and intervals add estimation uncertainty.↔ Scroll wide equations horizontally.

Preserve variation instead of hiding it in a summary

Publish run-level summaries and enough raw data to inspect drift, multimodality, and failures. A minimum execution time may answer a best-case question but cannot silently stand in for a representative mean. Report any exclusions, machine replacements, or unsuccessful starts. If a large allocation permits only a few independent runs, state the resulting limitation rather than multiplying its internal samples into false certainty. Repetition improves precision under an appropriate sampling model; it cannot remove systematic bias shared by every run.

The sampling instrument isolates only independent Bernoulli averaging. Reset, set both p=0.5 and n=25, predict mean 0.5 and standard deviation 0.1 for K/n, then Play or Step. Separately Reset, set both p=0.5 and n=100, predict mean 0.5 and standard deviation 0.05, then Play or Step. The bars are exact probabilities and playback highlights outcomes rather than generating samples. This model has no process offsets, build variability, warmup, or correlated request timings, so its narrowing must not be used as a hierarchical benchmark uncertainty estimate.

More runs can beat more iterations

Assume known variance components σ_b²=9 ms² and σ_e²=16 ms². Compare four independent runs with 25 iterations each against ten independent runs with ten iterations each; both collect 100 timings and ignore startup costs for this exercise.

  1. For m=4 and k=25, the grand-mean variance is 9/4+16/100=2.25+0.16=2.41 ms². Its standard deviation is √2.41≈1.5524 ms.

  2. For m=10 and k=10, the variance is 9/10+16/100=0.9+0.16=1.06 ms². Its standard deviation is approximately 1.0296 ms with the same total number of timings.

  3. Keeping only four runs but increasing to 100 iterations each gives 9/4+16/400=2.29 ms². Four times as many timings barely change the dominant run component; an actual budget decision must also include independent-run startup costs.

The result

The number and cost of independent units matter more than a raw observation count when shared run effects dominate.

Explore the model

Interactive lab

Interactive lab · sampling

Observe independent averaging without inventing run independence

Reset, set both p=0.5 and n=25, predict mean 0.5 and standard deviation 0.1, then Play or Step. Separately Reset, set both p=0.5 and n=100, predict mean 0.5 and standard deviation 0.05, then Play or Step. Exact iid Bernoulli mean masses do not model nested benchmark variability.

Observe independent averaging without inventing run independenceExact binomial masses for the mean of n independent Bernoulli trials, compared with normal mass between adjacent half-count boundaries; normal tails outside the finite support remain outside the bars. Playback highlights outcomes, not random samples. The Berry–Esseen bound applies to standardized CDFs, not individual bars or continuity-corrected errors. At p = 0 or 1, normal comparison and that bound are disabled. Normal-CDF evaluation uses a numerical approximation with absolute error below 7.5×10⁻⁸ (at most 1.5×10⁻⁷ per interval, before rounding). Current readings: Mean sample proportion: 0.5; Sample-mean variance: 0.0125; Uniform CDF error bound: ≤ 0.1062. All parameters are adjustable with the labeled controls below.Exact distribution of the mean of 20 independent Bernoulli variables with success probability 0.5; playback highlights outcome 0.00.250.50.75100.0580.1150.1730.23Sample mean · k / nProbability massNormal bin masses are an approximationk = 0 · exact probability = 9.54e-7
Exact binomial massNormal interval massHighlighted outcome / mean
Mean sample proportion
0.5
Sample-mean variance
0.0125
Uniform CDF error bound
≤ 0.1062
t = 0 s

Exact binomial masses for the mean of n independent Bernoulli trials, compared with normal mass between adjacent half-count boundaries; normal tails outside the finite support remain outside the bars. Playback highlights outcomes, not random samples. The Berry–Esseen bound applies to standardized CDFs, not individual bars or continuity-corrected errors. At p = 0 or 1, normal comparison and that bound are disabled. Normal-CDF evaluation uses a numerical approximation with absolute error below 7.5×10⁻⁸ (at most 1.5×10⁻⁷ per interval, before rounding). Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.

Look forIncreasing n narrows this independent model; real experiments must justify what counts as n.

Check your understanding

Which change most directly averages away a process-specific offset shared by all its timed iterations?

Try it yourself

Under the same known components, calculate the grand-mean variance and standard deviation for nine independent runs with sixteen iterations per run.

Take a moment to make a prediction or work it out on paper. Open a hint when you need one.

Give me a hint

Use m=9 and mk=144; keep variance in squared milliseconds until the final square root.

Compare with the solution

The variance is 9/9+16/144=1+1/9=10/9 ms². The standard deviation is √(10/9)≈1.0541 ms. This is the model’s sampling standard deviation with known components, not a complete confidence interval fitted from nine observed runs.

Take it with you

  • Keep build, run, machine, and iteration levels visible in the data.
  • Allocate repetition where independent variation dominates, including its startup cost.
  • A large nested sample count does not establish a large number of independent units.

Read further

Original sources and deeper explanations to follow at your own pace.

Optional progress, saved in this browser when available. Revisit any lesson at any time.

Lesson not marked complete.