Benchfmt.rs: Bringing Go's benchmarking and benchstat workflow to Rust

Typically, the reason we're running benchmarks is to detect changes of at least some minimum difference -- a minimum detectable effect size. Assuming such a difference exists, we'd typically want to detect it with a high enough probability (i.e., statistical power, which is 1 minus the probability of a false negative), or else we're wasting time and money on a flaky result. Given a target false positive rate, power, a minimum effect size, and a few other assumptions, we can estimate how big of a sample size we would need to drive down our false negative rate enough to make the benchmark a reliable detector of performance changes, and thus the resources we'd need to spend on running the benchmark for it to be useful.

These other assumptions typically rely on statements about what the statistical test is trying to detect. Phrased in the context of benchstat, a Mann-Whitney U test is testing whether the probability of a sample of A being less than or equal to a sample of B is (without loss of generality) more than 1/2. The benchstat docs state "The p-value measures how likely it is that any differences were due to random chance (i.e., noise). In this case, it's extremely unlikely the difference between the medians was due to chance." If we make an additional assumption that the distribution of B has the same shape as the distribution of A, except that we've shifted its location -- a location-shift alternate hypothesis -- then the Mann-Whitney U test is testing a difference in medians (sort of; I'm omitting details for brevity).

benchstat's confidence intervals on medians are unrelated to the U test, so we can't use them to estimate the probability of a false negative under assumptions -- assumptions that benchstat isn't entirely explicit about -- and it's difficult to provide a user with some feedback suggesting they may want to run more (or fewer!) samples. There's no reason to believe that a location-shift hypothesis for benchmarking is sensible, if that is indeed an assumption the package's authors make deliberately, and it's not entirely clear to me that the assumption is deliberate, either. A location-shift assumption could be reasonable in some contexts, but we don't know, and benchstat doesn't provide any diagnostics to tell us one way or the other. benchstat also doesn't really clarify why (or when!) n = 10 or n = 20 is a good idea. Unless the minimum detectable effect size we're looking for is large, I'd expect benchstat's approach to be underpowered, so it might fail to detect smaller performance differences. And if n = 10 or n = 20 is really a hard limit or an overriding user preference, there are methods that trade simplicity for a modest amount of compute, like permutation tests, that are simpler to explain and easier to use for simulations to determine statistical power without making parametric assumptions; these approaches would generalize to bootstrap or Monte Carlo methods at larger sample sizes, and permutation tests tend to have higher power than Mann-Whitney unless populations are skewed.

Medians are asymptotically normally distributed, so it's possible to use t-tests or bootstrap methods. There are caveats to such approaches, of course, but it's easier to do power calculations in that context to estimate prospective sample size, even if only to do back-of-the-envelope estimates.

The nonparametric approach benchstat uses to compute confidence intervals on medians is coherent, but at such sample sizes, it also tends to be coarse. If we're really concerned about the difference in medians as an engineering figure of merit, it would probably be a good idea to compute a confidence interval about that difference, too, but benchstat doesn't do that either, and if it's making a big deal about medians, I would argue it probably should. If relative difference in medians is the preferred figure of merit, a delta method correction for a confidence interval would be a good idea for that quantity.