subms_stats/
bootstrap.rs

1//! Bootstrap confidence intervals. Behind the `bootstrap` Cargo
2//! feature (on by default).
3//!
4//! Use this when reporting a percentile to know how WIDE the
5//! confidence interval is - "p99 = 230us +- 50us" is meaningful;
6//! "p99 = 230us" alone is missing the noise floor.
7
8use crate::percentiles::percentile;
9
10/// Bootstrap a percentile estimate with `iters` resamples, returning
11/// the lower + upper bounds of the `confidence`-level interval.
12/// `confidence` in `[0.0, 1.0]`; typical value `0.95`. Uses a
13/// deterministic LCG (`SubMsLcg`-compatible constants) so results
14/// are reproducible across runs given the same `seed`.
15///
16/// Cost is `O(iters * n)`; defaults that work well in practice:
17/// `iters = 200..1000`, `confidence = 0.95`.
18pub fn bootstrap_percentile_ci(
19    samples: &[u64],
20    q: f64,
21    iters: usize,
22    confidence: f64,
23    seed: u64,
24) -> (u64, u64) {
25    if samples.is_empty() || iters == 0 {
26        return (0, 0);
27    }
28    let mut state = seed | 1;
29    let mut estimates = Vec::with_capacity(iters);
30    for _ in 0..iters {
31        let mut resample = Vec::with_capacity(samples.len());
32        for _ in 0..samples.len() {
33            state = state
34                .wrapping_mul(6364136223846793005)
35                .wrapping_add(1442695040888963407);
36            let idx = (state as usize) % samples.len();
37            resample.push(samples[idx]);
38        }
39        resample.sort_unstable();
40        estimates.push(percentile(&resample, q));
41    }
42    estimates.sort_unstable();
43    let lo_q = (1.0 - confidence) / 2.0;
44    let hi_q = 1.0 - lo_q;
45    (percentile(&estimates, lo_q), percentile(&estimates, hi_q))
46}
47
48#[cfg(test)]
49mod tests {
50    use super::*;
51
52    #[test]
53    fn p99_ci_brackets_point_estimate() {
54        let v: Vec<u64> = (0..1000).collect();
55        let (lo, hi) = bootstrap_percentile_ci(&v, 0.99, 200, 0.95, 42);
56        let point = {
57            let mut s = v.clone();
58            s.sort_unstable();
59            percentile(&s, 0.99)
60        };
61        assert!(lo <= point && point <= hi);
62    }
63
64    #[test]
65    fn empty_returns_zero_pair() {
66        assert_eq!(bootstrap_percentile_ci(&[], 0.99, 100, 0.95, 0), (0, 0));
67    }
68
69    #[test]
70    fn deterministic_under_same_seed() {
71        let v: Vec<u64> = (0..200).collect();
72        let a = bootstrap_percentile_ci(&v, 0.99, 100, 0.95, 7);
73        let b = bootstrap_percentile_ci(&v, 0.99, 100, 0.95, 7);
74        assert_eq!(a, b);
75    }
76
77    #[test]
78    fn zero_iters_returns_zero_pair() {
79        let v: Vec<u64> = (0..100).collect();
80        assert_eq!(bootstrap_percentile_ci(&v, 0.99, 0, 0.95, 0), (0, 0));
81    }
82}
subms_stats/bootstrap.rs

subms_stats/
bootstrap.rs
