Statistics and design decisions

Everything below is implemented in src/benchdiff/stats.py (primitives), analysis.py (putting them together), engine.py (measurement) and history.py (change points).

1. Measurement design

Interleaving (ABBA blocks)

Machines drift: thermal state, other processes, frequency governors. If you benchmark ref A for a minute and then ref B for a minute, any drift shows up as a "difference". benchdiff therefore never runs one ref's samples back to back.

One round is a random permutation of the refs followed by its reverse:

refs = [A, B]   ->  A B B A   or   B A A B
refs = [A, B, C] -> B C A A C B

Every ref runs twice per round and the schedule is a palindrome, so linear drift contributes equally to every ref's mean position. Randomizing which order is used removes any systematic "A always goes first" effect (cache state left by the previous run, for example). engine.abba_schedule is the whole implementation.

Warmup and adaptive run count

Shell benchmarks: warmup discarded runs per ref (interleaved) before sampling starts.
Python benchmarks: each subprocess runs warmup untimed calls first, then repeat timed calls. The process is fresh each time, so hash seeds, memory layout and caches are re-sampled instead of being frozen in one process.
Sampling continues round by round until all of these hold: min_runs samples per ref, min_time seconds, and the relative half-width of every ref's bootstrap CI of the median is at most target_ci (default 1%). It stops early at max_runs, or at max_time (never before 5 samples). The reason (target, max_runs, max_time) is stored and reported, so a noisy benchmark that gave up is visible rather than silently imprecise.

What is recorded

Wall time (perf_counter_ns), CPU time (user+system, from the kernel's wait4 rusage for shell commands and process_time_ns for Python benchmarks) and peak RSS (ru_maxrss). Statistics run on wall time by default (--metric cpu switches). The environment (CPU model, governor, load average, Python version) is stored with every run, and noisy conditions (load per CPU above 0.5, a non-performance governor) produce warnings.

2. Outliers: Tukey fences

With Q1, Q3 and IQR = Q3 - Q1, a point is a mild outlier outside [Q1 - 1.5 IQR, Q3 + 1.5 IQR] and severe outside the 3 IQR fences. Timing data is right-skewed and contaminated by scheduler hiccups, so this is useful information, but removing points changes the question being asked and hides how noisy the run was. benchdiff therefore flags and reports outliers but keeps them; the robust statistics below (medians, rank tests) are what protect the verdict. The box plots draw the whiskers over the non-outliers and the outliers as dots.

3. Ratio of medians with a bootstrap CI

The headline number is median(new) / median(base). The median is robust to the long right tail; the ratio is what "30% slower" means and is scale free across benchmarks.

There is no closed form CI for a ratio of medians, so both samples are resampled independently (2000 resamples by default) and the ratio recomputed. Two interval types are available (method=):

percentile: the 2.5th and 97.5th percentiles of the bootstrap ratios.
bca (default): bias-corrected and accelerated. Percentile intervals are biased when the bootstrap distribution is skewed, which is exactly the case for ratios and for small samples. BCa shifts the quantile levels by z0 (bias: how far the bootstrap median is from the estimate, z0 = Phi^-1(P[boot < theta_hat])) and a (acceleration, from a jackknife over both samples: leave out each observation in turn and compute the ratio). Adjusted level: Phi(z0 + (z0 + z_alpha) / (1 - a (z0 + z_alpha))).

Worked example: base median 1.16 ms, head median 1.54 ms gives a ratio 1.33; a typical interval is [1.30, 1.36], reported as [+30.2%, +35.6%]. tests/test_stats.py runs a coverage simulation (150 simulated experiments with a known true ratio of 1.2): both methods land inside 88-99.5% for a nominal 95%.

The same machinery, applied to one sample, gives the stopping criterion: the relative half-width of the percentile bootstrap CI of the median, (hi - lo) / 2 / median.

4. Mann-Whitney U test

A two-sided Mann-Whitney U test (scipy.stats.mannwhitneyu) asks whether values from one ref tend to be larger than the other's. It uses ranks only, so it needs no normality assumption and is insensitive to the outliers kept in the data. If every value in both samples is identical the p-value is defined as 1.

5. Cliff's delta

delta = P(new > base) - P(new < base), in [-1, 1], computed over all pairs. It is an effect size that does not depend on the unit or the spread: +1 means every new sample was slower than every base sample. Reported magnitudes follow Romano et al.: |d| < 0.147 negligible, < 0.33 small, < 0.474 medium, otherwise large. It matters because with enough samples, a 0.3% difference can be "significant"; the verdict also needs a practically relevant change (below).

6. Holm-Bonferroni correction

A run compares many (benchmark, ref) pairs, so some will look significant by chance. Holm's step-down procedure controls the family-wise error rate and is uniformly more powerful than plain Bonferroni:

sort p ascending; adjusted_(i) = max over j<=i of (m - j + 1) * p_(j)   (capped at 1)

Example: p = [0.01, 0.04, 0.03, 0.005] -> sorted 0.005, 0.01, 0.03, 0.04 -> 0.02, 0.03, 0.06, 0.06 (the last is raised to keep the sequence monotone) -> adjusted [0.03, 0.06, 0.06, 0.02] in input order. The correction spans all comparisons of a run (and across all refs when more than two are given).

7. The verdict

A comparison is slower (or faster) only if all three hold:

Holm-adjusted p < 0.05,
the 95% CI of the ratio excludes 1.0,
the change is at least --threshold (default 2%, in the direction of the effect).

Otherwise it is no change. Significance alone is not enough (a tiny stable shift is not interesting) and a big change inside a wide CI is not enough (it could be noise).

--fail-on-regression X% exits with status 1 if any comparison has p_adj < 0.05, a CI lower bound above 1.0 and a change of at least X%. It is independent of --threshold, so a report can show 2% changes while CI only fails the build at 5%.

8. History and change points

benchdiff history BENCH takes the newest stored measurement per commit and orders commits by committer date. For each commit it shows the median and the change versus the previous commit, and runs binary segmentation on the log-medians:

For a segment, find the split point that most reduces the sum of squared errors around segment means (a mean-shift cost; on logs a level shift is a ratio).
Accept the split if the reduction exceeds 2 sigma^2 ln(n) (a BIC-style penalty) and the segments' geometric means differ by at least --min-change (default 5%).
sigma is a robust noise estimate: 1.4826 * MAD of the successive differences / sqrt(2), floored at 0.5%.
Recurse into both halves.

Example (word_freq, 6 commits): medians 1.16, 1.16, 1.15, 1.62, 1.60, 1.55 ms. The best split is before the fourth point (segment means 1.16 vs 1.59, +37%), which clears the penalty and the 5% minimum, so commit 4 is flagged. Splitting the right half again would only separate 1.62 from 1.55 (-3%), below --min-change. Medians from different runs are compared, so history is a screening tool: use run (interleaved) or bisect to confirm.

9. Bisect

benchdiff bisect BENCH GOOD BAD --threshold 5% does not touch your checkout or git bisect state. It lists the commits GOOD..BAD (git rev-list --ancestry-path, oldest first) and binary searches them:

Measure GOOD against BAD (interleaved). If the verdict is not slower at the threshold, stop: there is nothing to find.
For a midpoint commit, measure it interleaved with GOOD (a fresh paired comparison, immune to the machine having changed since the previous probe). slower means the regression is at or before the midpoint.
Repeat until the bad/good boundary is one commit wide.

This needs about log2(n) + 1 probes. It assumes a regression that persists once introduced; a regression that is later fixed and reintroduced can mislead any bisect, including git bisect.