1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

// Copyright 2022 Twitter, Inc.
// Licensed under the Apache License, Version 2.0
// http://www.apache.org/licenses/LICENSE-2.0

mod bucket;
mod error;
mod histogram;
mod percentile;

pub use self::histogram::{Builder, Histogram};
pub use bucket::Bucket;
pub use error::Error;
pub use percentile::Percentile;

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    // run some test cases for various histogram sizes
    fn num_buckets() {
        let histogram = Histogram::new(0, 2, 10).unwrap();
        assert_eq!(histogram.buckets(), 20);

        let histogram = Histogram::new(0, 10, 20).unwrap();
        assert_eq!(histogram.buckets(), 6144);

        let histogram = Histogram::new(0, 10, 30).unwrap();
        assert_eq!(histogram.buckets(), 11264);

        let histogram = Histogram::new(1, 10, 20).unwrap();
        assert_eq!(histogram.buckets(), 3072);

        let histogram = Histogram::new(0, 9, 20).unwrap();
        assert_eq!(histogram.buckets(), 3328);
    }

    #[test]
    fn percentiles_1() {
        let histogram = Histogram::new(0, 2, 10).unwrap();

        for v in 1..1024 {
            assert!(histogram.increment(v, 1).is_ok());
            assert_eq!(histogram.percentile(0.0).map(|b| b.high()), Ok(1));

            assert!(histogram.percentile(100.0).map(|b| b.high()).unwrap_or(0) >= v);
            assert!(histogram.percentile(100.0).map(|b| b.low()).unwrap_or(0) <= v);
        }

        let percentiles: Vec<(u64, u64)> = histogram
            .percentiles(&[1.0, 10.0, 25.0, 50.0, 75.0, 90.0, 99.0])
            .unwrap()
            .iter()
            .map(|p| (p.bucket().low(), p.bucket().high()))
            .collect();

        // this histogram config doesn't have much resolution, which results in
        // the upper percentiles falling into buckets that are rather wide
        assert_eq!(
            &percentiles,
            &[
                (8, 11),
                (96, 127),
                (256, 383),
                (512, 767),
                (768, 1023),
                (768, 1023),
                (768, 1023)
            ]
        );
    }

    #[test]
    fn percentiles_2() {
        let histogram = Histogram::new(0, 5, 10).unwrap();

        for v in 1..1024 {
            assert!(histogram.increment(v, 1).is_ok());
            assert_eq!(histogram.percentile(0.0).map(|b| b.high()), Ok(1));

            assert!(histogram.percentile(100.0).map(|b| b.high()).unwrap_or(0) >= v);
            assert!(histogram.percentile(100.0).map(|b| b.low()).unwrap_or(0) <= v);
        }

        let percentiles: Vec<(u64, u64)> = histogram
            .percentiles(&[1.0, 10.0, 25.0, 50.0, 75.0, 90.0, 99.0])
            .unwrap()
            .iter()
            .map(|p| (p.bucket().low(), p.bucket().high()))
            .collect();

        // this histogram config has enough resolution to keep the error lower
        assert_eq!(
            &percentiles,
            &[
                (11, 11),
                (100, 103),
                (256, 271),
                (512, 543),
                (768, 799),
                (896, 927),
                (992, 1023)
            ]
        );
    }

    #[test]
    fn percentiles_3() {
        let histogram = Histogram::builder().build().unwrap();
        histogram.increment(1, 1).unwrap();
        histogram.increment(10000000, 1).unwrap();

        let percentiles = histogram.percentiles(&[25.0, 75.0]).unwrap();

        assert_eq!(histogram.percentile(25.0).map(|b| b.high()), Ok(1));
        assert_eq!(histogram.percentile(75.0).map(|b| b.high()), Ok(10010623));

        assert_eq!(percentiles.get(0).map(|b| b.bucket().high()), Some(1));
        assert_eq!(
            percentiles.get(1).map(|b| b.bucket().high()),
            Some(10010623)
        );
    }
}