keyhog_core/
timing.rs

1//! Shared statistical evidence for paired performance comparisons.
2
3use std::time::Duration;
4
5/// A two-sided 95% confidence interval for a paired candidate/reference ratio.
6#[derive(Clone, Copy, Debug, PartialEq)]
7pub struct PairedRatioConfidence {
8    /// Number of paired observations.
9    pub sample_count: usize,
10    /// Geometric mean of the paired candidate/reference ratios.
11    pub geometric_mean_ratio: f64,
12    /// Lower bound of the two-sided 95% interval.
13    pub low_ratio: f64,
14    /// Upper bound of the two-sided 95% interval.
15    pub high_ratio: f64,
16}
17
18/// Overflow-safe midpoint for two ordered unsigned observations.
19pub fn midpoint_u128(lower: u128, upper: u128) -> u128 {
20    lower + (upper - lower) / 2
21}
22
23/// Compute a paired 95% confidence interval in log-ratio space.
24///
25/// Pairing removes shared trial-to-trial host noise. Every duration must be
26/// positive, the slices must have equal length, and at least two pairs are
27/// required so the interval has measured variance.
28pub fn paired_ratio_confidence_95(
29    reference: &[Duration],
30    candidate: &[Duration],
31) -> Option<PairedRatioConfidence> {
32    if reference.len() != candidate.len() || reference.len() < 2 {
33        return None;
34    }
35    let mut log_ratios = Vec::with_capacity(reference.len());
36    for (&reference_duration, &candidate_duration) in reference.iter().zip(candidate) {
37        let reference_secs = reference_duration.as_secs_f64();
38        let candidate_secs = candidate_duration.as_secs_f64();
39        if reference_secs <= 0.0 || candidate_secs <= 0.0 {
40            return None;
41        }
42        log_ratios.push((candidate_secs / reference_secs).ln());
43    }
44    let count = log_ratios.len() as f64;
45    let mean = log_ratios.iter().sum::<f64>() / count;
46    let variance = log_ratios
47        .iter()
48        .map(|ratio| {
49            let delta = ratio - mean;
50            delta * delta
51        })
52        .sum::<f64>()
53        / (count - 1.0);
54    let half_width = two_sided_95_student_t_critical(log_ratios.len()) * (variance / count).sqrt();
55    Some(PairedRatioConfidence {
56        sample_count: log_ratios.len(),
57        geometric_mean_ratio: mean.exp(),
58        low_ratio: (mean - half_width).exp(),
59        high_ratio: (mean + half_width).exp(),
60    })
61}
62/// Select the earliest candidate unless paired 95% evidence proves a later
63/// candidate faster.
64///
65/// Every candidate must provide the same number of positive observations, with
66/// at least two observations per candidate. Returning the earliest candidate
67/// when intervals overlap gives callers a deterministic tie-break without
68/// converting measurement noise into a route change.
69pub fn select_confidently_fastest_index<'a>(
70    sample_sets: impl IntoIterator<Item = &'a [Duration]>,
71) -> Option<usize> {
72    let mut candidates = sample_sets.into_iter().enumerate();
73    let (_, mut selected_samples) = candidates.next()?;
74    if selected_samples.len() < 2 || selected_samples.iter().any(|sample| sample.is_zero()) {
75        return None;
76    }
77
78    let mut selected_index = 0;
79    for (index, candidate_samples) in candidates {
80        let comparison = paired_ratio_confidence_95(selected_samples, candidate_samples)?;
81        if comparison.high_ratio < 1.0 {
82            selected_index = index;
83            selected_samples = candidate_samples;
84        }
85    }
86    Some(selected_index)
87}
88
89/// Median duration using the midpoint of the two central observations for an
90/// even-length sample.
91pub fn median_duration(samples: &[Duration]) -> Option<Duration> {
92    if samples.is_empty() {
93        return None;
94    }
95    let mut sorted = samples.to_vec();
96    sorted.sort_unstable();
97    let middle = sorted.len() / 2;
98    if sorted.len() % 2 == 1 {
99        Some(sorted[middle])
100    } else {
101        let lower = sorted[middle - 1];
102        let upper = sorted[middle];
103        let midpoint_nanos = midpoint_u128(lower.as_nanos(), upper.as_nanos());
104        let seconds = midpoint_nanos / 1_000_000_000;
105        let nanos = (midpoint_nanos % 1_000_000_000) as u32;
106        Some(Duration::new(seconds as u64, nanos))
107    }
108}
109
110/// Conservative two-sided 95% Student-t critical value for a sample count.
111pub fn two_sided_95_student_t_critical(sample_count: usize) -> f64 {
112    match sample_count {
113        0 | 1 => 0.0,
114        2 => 12.706_204_736,
115        3 => 4.302_652_73,
116        4 => 3.182_446_305,
117        5 => 2.776_445_105,
118        6 => 2.570_581_836,
119        7 => 2.446_911_851,
120        8 => 2.364_624_252,
121        9 => 2.306_004_135,
122        10 => 2.262_157_163,
123        11 => 2.228_138_852,
124        12 => 2.200_985_16,
125        13 => 2.178_812_83,
126        14 => 2.160_368_656,
127        15 => 2.144_786_688,
128        16 => 2.131_449_546,
129        17 => 2.119_905_299,
130        18 => 2.109_815_578,
131        19 => 2.100_922_04,
132        20 => 2.093_024_054,
133        21 => 2.085_963_447,
134        22 => 2.079_613_845,
135        23 => 2.073_873_068,
136        24 => 2.068_657_61,
137        25 => 2.063_898_562,
138        26 => 2.059_538_553,
139        27 => 2.055_529_439,
140        28 => 2.051_830_516,
141        29 => 2.048_407_142,
142        30 => 2.045_229_642,
143        31 => 2.042_272_456,
144        _ => 2.042_272_456,
145    }
146}
keyhog_core/timing.rs

keyhog_core/
timing.rs
