subms_stats/
histogram.rs

1//! Log2-spaced CDF buckets. Behind the `histogram` Cargo feature
2//! (on by default).
3//!
4//! Use to export a full empirical distribution alongside the headline
5//! p50/p99 percentiles - downstream tooling can reconstruct any
6//! quantile from the bucket cumulative sums without needing the raw
7//! sample stream.
8
9/// Log2-spaced histogram of latencies. 64 buckets covering
10/// `[2^i, 2^(i+1))` nanoseconds for `i in 0..64`. A full empirical
11/// CDF can be reconstructed from the cumulative sum of this array.
12/// Empty input -> all-zero buckets.
13///
14/// Bucket bounds:
15///
16/// | Bucket | Range | Range (human) |
17/// |---|---|---|
18/// | 0 | [0, 2) ns | sub-ns |
19/// | 6 | [64, 128) ns | tens of ns |
20/// | 10 | [1024, 2048) ns | ~1 us |
21/// | 20 | [1048576, 2097152) ns | ~1 ms |
22/// | 30 | [~1.07e9, ~2.15e9) ns | ~1 s |
23/// | 63 | [2^63, 2^64) ns | ~292 years |
24pub fn cdf_buckets(samples: &[u64]) -> Vec<u64> {
25    let mut buckets = vec![0u64; 64];
26    for &v in samples {
27        let idx = if v == 0 {
28            0
29        } else {
30            // Highest set bit of v: log2 floor.
31            (63 - v.leading_zeros()) as usize
32        };
33        let idx = idx.min(63);
34        buckets[idx] = buckets[idx].saturating_add(1);
35    }
36    buckets
37}
38
39#[cfg(test)]
40mod tests {
41    use super::*;
42
43    #[test]
44    fn log2_placement() {
45        let buckets = cdf_buckets(&[1, 2, 3, 4, 8, 100, 1_000_000]);
46        assert_eq!(buckets[0], 1);
47        assert_eq!(buckets[1], 2);
48        assert_eq!(buckets[2], 1);
49        assert_eq!(buckets[3], 1);
50        assert_eq!(buckets[6], 1);
51        assert_eq!(buckets[19], 1);
52    }
53
54    #[test]
55    fn empty_input_all_zero() {
56        let buckets = cdf_buckets(&[]);
57        assert_eq!(buckets.len(), 64);
58        assert!(buckets.iter().all(|&c| c == 0));
59    }
60
61    #[test]
62    fn cdf_buckets_count_matches_total() {
63        let raw: Vec<u64> = (1..=1000).collect();
64        let buckets = cdf_buckets(&raw);
65        let total: u64 = buckets.iter().sum();
66        assert_eq!(total as usize, raw.len());
67    }
68
69    #[test]
70    fn zero_value_lands_in_bucket_zero() {
71        let buckets = cdf_buckets(&[0, 0, 0]);
72        assert_eq!(buckets[0], 3);
73    }
74}
subms_stats/histogram.rs

subms_stats/
histogram.rs
