• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 use crate::loom::sync::atomic::{AtomicU64, Ordering::Relaxed};
2 
3 use std::cmp;
4 use std::ops::Range;
5 
6 #[derive(Debug)]
7 pub(crate) struct Histogram {
8     /// The histogram buckets
9     buckets: Box<[AtomicU64]>,
10 
11     /// Bucket scale, linear or log
12     scale: HistogramScale,
13 
14     /// Minimum resolution
15     resolution: u64,
16 }
17 
18 #[derive(Debug, Clone)]
19 pub(crate) struct HistogramBuilder {
20     /// Histogram scale
21     pub(crate) scale: HistogramScale,
22 
23     /// Must be a power of 2
24     pub(crate) resolution: u64,
25 
26     /// Number of buckets
27     pub(crate) num_buckets: usize,
28 }
29 
30 #[derive(Debug)]
31 pub(crate) struct HistogramBatch {
32     buckets: Box<[u64]>,
33     scale: HistogramScale,
34     resolution: u64,
35 }
36 
37 cfg_unstable! {
38     /// Whether the histogram used to aggregate a metric uses a linear or
39     /// logarithmic scale.
40     #[derive(Debug, Copy, Clone, Eq, PartialEq)]
41     #[non_exhaustive]
42     pub enum HistogramScale {
43         /// Linear bucket scale
44         Linear,
45 
46         /// Logarithmic bucket scale
47         Log,
48     }
49 }
50 
51 impl Histogram {
num_buckets(&self) -> usize52     pub(crate) fn num_buckets(&self) -> usize {
53         self.buckets.len()
54     }
55 
get(&self, bucket: usize) -> u6456     pub(crate) fn get(&self, bucket: usize) -> u64 {
57         self.buckets[bucket].load(Relaxed)
58     }
59 
bucket_range(&self, bucket: usize) -> Range<u64>60     pub(crate) fn bucket_range(&self, bucket: usize) -> Range<u64> {
61         match self.scale {
62             HistogramScale::Log => Range {
63                 start: if bucket == 0 {
64                     0
65                 } else {
66                     self.resolution << (bucket - 1)
67                 },
68                 end: if bucket == self.buckets.len() - 1 {
69                     u64::MAX
70                 } else {
71                     self.resolution << bucket
72                 },
73             },
74             HistogramScale::Linear => Range {
75                 start: self.resolution * bucket as u64,
76                 end: if bucket == self.buckets.len() - 1 {
77                     u64::MAX
78                 } else {
79                     self.resolution * (bucket as u64 + 1)
80                 },
81             },
82         }
83     }
84 }
85 
86 impl HistogramBatch {
from_histogram(histogram: &Histogram) -> HistogramBatch87     pub(crate) fn from_histogram(histogram: &Histogram) -> HistogramBatch {
88         let buckets = vec![0; histogram.buckets.len()].into_boxed_slice();
89 
90         HistogramBatch {
91             buckets,
92             scale: histogram.scale,
93             resolution: histogram.resolution,
94         }
95     }
96 
measure(&mut self, value: u64, count: u64)97     pub(crate) fn measure(&mut self, value: u64, count: u64) {
98         self.buckets[self.value_to_bucket(value)] += count;
99     }
100 
submit(&self, histogram: &Histogram)101     pub(crate) fn submit(&self, histogram: &Histogram) {
102         debug_assert_eq!(self.scale, histogram.scale);
103         debug_assert_eq!(self.resolution, histogram.resolution);
104         debug_assert_eq!(self.buckets.len(), histogram.buckets.len());
105 
106         for i in 0..self.buckets.len() {
107             histogram.buckets[i].store(self.buckets[i], Relaxed);
108         }
109     }
110 
value_to_bucket(&self, value: u64) -> usize111     fn value_to_bucket(&self, value: u64) -> usize {
112         match self.scale {
113             HistogramScale::Linear => {
114                 let max = self.buckets.len() - 1;
115                 cmp::min(value / self.resolution, max as u64) as usize
116             }
117             HistogramScale::Log => {
118                 let max = self.buckets.len() - 1;
119 
120                 if value < self.resolution {
121                     0
122                 } else {
123                     let significant_digits = 64 - value.leading_zeros();
124                     let bucket_digits = 64 - (self.resolution - 1).leading_zeros();
125                     cmp::min(significant_digits as usize - bucket_digits as usize, max)
126                 }
127             }
128         }
129     }
130 }
131 
132 impl HistogramBuilder {
new() -> HistogramBuilder133     pub(crate) fn new() -> HistogramBuilder {
134         HistogramBuilder {
135             scale: HistogramScale::Linear,
136             // Resolution is in nanoseconds.
137             resolution: 100_000,
138             num_buckets: 10,
139         }
140     }
141 
build(&self) -> Histogram142     pub(crate) fn build(&self) -> Histogram {
143         let mut resolution = self.resolution;
144 
145         assert!(resolution > 0);
146 
147         if matches!(self.scale, HistogramScale::Log) {
148             resolution = resolution.next_power_of_two();
149         }
150 
151         Histogram {
152             buckets: (0..self.num_buckets)
153                 .map(|_| AtomicU64::new(0))
154                 .collect::<Vec<_>>()
155                 .into_boxed_slice(),
156             resolution,
157             scale: self.scale,
158         }
159     }
160 }
161 
162 impl Default for HistogramBuilder {
default() -> HistogramBuilder163     fn default() -> HistogramBuilder {
164         HistogramBuilder::new()
165     }
166 }
167 
168 #[cfg(test)]
169 mod test {
170     use super::*;
171 
172     macro_rules! assert_bucket_eq {
173         ($h:expr, $bucket:expr, $val:expr) => {{
174             assert_eq!($h.buckets[$bucket], $val);
175         }};
176     }
177 
178     #[test]
log_scale_resolution_1()179     fn log_scale_resolution_1() {
180         let h = HistogramBuilder {
181             scale: HistogramScale::Log,
182             resolution: 1,
183             num_buckets: 10,
184         }
185         .build();
186 
187         assert_eq!(h.bucket_range(0), 0..1);
188         assert_eq!(h.bucket_range(1), 1..2);
189         assert_eq!(h.bucket_range(2), 2..4);
190         assert_eq!(h.bucket_range(3), 4..8);
191         assert_eq!(h.bucket_range(9), 256..u64::MAX);
192 
193         let mut b = HistogramBatch::from_histogram(&h);
194 
195         b.measure(0, 1);
196         assert_bucket_eq!(b, 0, 1);
197         assert_bucket_eq!(b, 1, 0);
198 
199         b.measure(1, 1);
200         assert_bucket_eq!(b, 0, 1);
201         assert_bucket_eq!(b, 1, 1);
202         assert_bucket_eq!(b, 2, 0);
203 
204         b.measure(2, 1);
205         assert_bucket_eq!(b, 0, 1);
206         assert_bucket_eq!(b, 1, 1);
207         assert_bucket_eq!(b, 2, 1);
208 
209         b.measure(3, 1);
210         assert_bucket_eq!(b, 0, 1);
211         assert_bucket_eq!(b, 1, 1);
212         assert_bucket_eq!(b, 2, 2);
213 
214         b.measure(4, 1);
215         assert_bucket_eq!(b, 0, 1);
216         assert_bucket_eq!(b, 1, 1);
217         assert_bucket_eq!(b, 2, 2);
218         assert_bucket_eq!(b, 3, 1);
219 
220         b.measure(100, 1);
221         assert_bucket_eq!(b, 7, 1);
222 
223         b.measure(128, 1);
224         assert_bucket_eq!(b, 8, 1);
225 
226         b.measure(4096, 1);
227         assert_bucket_eq!(b, 9, 1);
228     }
229 
230     #[test]
log_scale_resolution_2()231     fn log_scale_resolution_2() {
232         let h = HistogramBuilder {
233             scale: HistogramScale::Log,
234             resolution: 2,
235             num_buckets: 10,
236         }
237         .build();
238 
239         assert_eq!(h.bucket_range(0), 0..2);
240         assert_eq!(h.bucket_range(1), 2..4);
241         assert_eq!(h.bucket_range(2), 4..8);
242         assert_eq!(h.bucket_range(3), 8..16);
243         assert_eq!(h.bucket_range(9), 512..u64::MAX);
244 
245         let mut b = HistogramBatch::from_histogram(&h);
246 
247         b.measure(0, 1);
248         assert_bucket_eq!(b, 0, 1);
249         assert_bucket_eq!(b, 1, 0);
250 
251         b.measure(1, 1);
252         assert_bucket_eq!(b, 0, 2);
253         assert_bucket_eq!(b, 1, 0);
254 
255         b.measure(2, 1);
256         assert_bucket_eq!(b, 0, 2);
257         assert_bucket_eq!(b, 1, 1);
258         assert_bucket_eq!(b, 2, 0);
259 
260         b.measure(3, 1);
261         assert_bucket_eq!(b, 0, 2);
262         assert_bucket_eq!(b, 1, 2);
263         assert_bucket_eq!(b, 2, 0);
264 
265         b.measure(4, 1);
266         assert_bucket_eq!(b, 0, 2);
267         assert_bucket_eq!(b, 1, 2);
268         assert_bucket_eq!(b, 2, 1);
269 
270         b.measure(5, 1);
271         assert_bucket_eq!(b, 0, 2);
272         assert_bucket_eq!(b, 1, 2);
273         assert_bucket_eq!(b, 2, 2);
274 
275         b.measure(6, 1);
276         assert_bucket_eq!(b, 0, 2);
277         assert_bucket_eq!(b, 1, 2);
278         assert_bucket_eq!(b, 2, 3);
279 
280         b.measure(7, 1);
281         assert_bucket_eq!(b, 0, 2);
282         assert_bucket_eq!(b, 1, 2);
283         assert_bucket_eq!(b, 2, 4);
284 
285         b.measure(8, 1);
286         assert_bucket_eq!(b, 0, 2);
287         assert_bucket_eq!(b, 1, 2);
288         assert_bucket_eq!(b, 2, 4);
289         assert_bucket_eq!(b, 3, 1);
290 
291         b.measure(100, 1);
292         assert_bucket_eq!(b, 6, 1);
293 
294         b.measure(128, 1);
295         assert_bucket_eq!(b, 7, 1);
296 
297         b.measure(4096, 1);
298         assert_bucket_eq!(b, 9, 1);
299 
300         for bucket in h.buckets.iter() {
301             assert_eq!(bucket.load(Relaxed), 0);
302         }
303 
304         b.submit(&h);
305 
306         for i in 0..h.buckets.len() {
307             assert_eq!(h.buckets[i].load(Relaxed), b.buckets[i]);
308         }
309 
310         b.submit(&h);
311 
312         for i in 0..h.buckets.len() {
313             assert_eq!(h.buckets[i].load(Relaxed), b.buckets[i]);
314         }
315     }
316 
317     #[test]
linear_scale_resolution_1()318     fn linear_scale_resolution_1() {
319         let h = HistogramBuilder {
320             scale: HistogramScale::Linear,
321             resolution: 1,
322             num_buckets: 10,
323         }
324         .build();
325 
326         assert_eq!(h.bucket_range(0), 0..1);
327         assert_eq!(h.bucket_range(1), 1..2);
328         assert_eq!(h.bucket_range(2), 2..3);
329         assert_eq!(h.bucket_range(3), 3..4);
330         assert_eq!(h.bucket_range(9), 9..u64::MAX);
331 
332         let mut b = HistogramBatch::from_histogram(&h);
333 
334         b.measure(0, 1);
335         assert_bucket_eq!(b, 0, 1);
336         assert_bucket_eq!(b, 1, 0);
337 
338         b.measure(1, 1);
339         assert_bucket_eq!(b, 0, 1);
340         assert_bucket_eq!(b, 1, 1);
341         assert_bucket_eq!(b, 2, 0);
342 
343         b.measure(2, 1);
344         assert_bucket_eq!(b, 0, 1);
345         assert_bucket_eq!(b, 1, 1);
346         assert_bucket_eq!(b, 2, 1);
347         assert_bucket_eq!(b, 3, 0);
348 
349         b.measure(3, 1);
350         assert_bucket_eq!(b, 0, 1);
351         assert_bucket_eq!(b, 1, 1);
352         assert_bucket_eq!(b, 2, 1);
353         assert_bucket_eq!(b, 3, 1);
354 
355         b.measure(5, 1);
356         assert_bucket_eq!(b, 5, 1);
357 
358         b.measure(4096, 1);
359         assert_bucket_eq!(b, 9, 1);
360 
361         for bucket in h.buckets.iter() {
362             assert_eq!(bucket.load(Relaxed), 0);
363         }
364 
365         b.submit(&h);
366 
367         for i in 0..h.buckets.len() {
368             assert_eq!(h.buckets[i].load(Relaxed), b.buckets[i]);
369         }
370 
371         b.submit(&h);
372 
373         for i in 0..h.buckets.len() {
374             assert_eq!(h.buckets[i].load(Relaxed), b.buckets[i]);
375         }
376     }
377 
378     #[test]
linear_scale_resolution_100()379     fn linear_scale_resolution_100() {
380         let h = HistogramBuilder {
381             scale: HistogramScale::Linear,
382             resolution: 100,
383             num_buckets: 10,
384         }
385         .build();
386 
387         assert_eq!(h.bucket_range(0), 0..100);
388         assert_eq!(h.bucket_range(1), 100..200);
389         assert_eq!(h.bucket_range(2), 200..300);
390         assert_eq!(h.bucket_range(3), 300..400);
391         assert_eq!(h.bucket_range(9), 900..u64::MAX);
392 
393         let mut b = HistogramBatch::from_histogram(&h);
394 
395         b.measure(0, 1);
396         assert_bucket_eq!(b, 0, 1);
397         assert_bucket_eq!(b, 1, 0);
398 
399         b.measure(50, 1);
400         assert_bucket_eq!(b, 0, 2);
401         assert_bucket_eq!(b, 1, 0);
402 
403         b.measure(100, 1);
404         assert_bucket_eq!(b, 0, 2);
405         assert_bucket_eq!(b, 1, 1);
406         assert_bucket_eq!(b, 2, 0);
407 
408         b.measure(101, 1);
409         assert_bucket_eq!(b, 0, 2);
410         assert_bucket_eq!(b, 1, 2);
411         assert_bucket_eq!(b, 2, 0);
412 
413         b.measure(200, 1);
414         assert_bucket_eq!(b, 0, 2);
415         assert_bucket_eq!(b, 1, 2);
416         assert_bucket_eq!(b, 2, 1);
417 
418         b.measure(299, 1);
419         assert_bucket_eq!(b, 0, 2);
420         assert_bucket_eq!(b, 1, 2);
421         assert_bucket_eq!(b, 2, 2);
422 
423         b.measure(222, 1);
424         assert_bucket_eq!(b, 0, 2);
425         assert_bucket_eq!(b, 1, 2);
426         assert_bucket_eq!(b, 2, 3);
427 
428         b.measure(300, 1);
429         assert_bucket_eq!(b, 0, 2);
430         assert_bucket_eq!(b, 1, 2);
431         assert_bucket_eq!(b, 2, 3);
432         assert_bucket_eq!(b, 3, 1);
433 
434         b.measure(888, 1);
435         assert_bucket_eq!(b, 8, 1);
436 
437         b.measure(4096, 1);
438         assert_bucket_eq!(b, 9, 1);
439 
440         for bucket in h.buckets.iter() {
441             assert_eq!(bucket.load(Relaxed), 0);
442         }
443 
444         b.submit(&h);
445 
446         for i in 0..h.buckets.len() {
447             assert_eq!(h.buckets[i].load(Relaxed), b.buckets[i]);
448         }
449 
450         b.submit(&h);
451 
452         for i in 0..h.buckets.len() {
453             assert_eq!(h.buckets[i].load(Relaxed), b.buckets[i]);
454         }
455     }
456 
457     #[test]
inc_by_more_than_one()458     fn inc_by_more_than_one() {
459         let h = HistogramBuilder {
460             scale: HistogramScale::Linear,
461             resolution: 100,
462             num_buckets: 10,
463         }
464         .build();
465 
466         let mut b = HistogramBatch::from_histogram(&h);
467 
468         b.measure(0, 3);
469         assert_bucket_eq!(b, 0, 3);
470         assert_bucket_eq!(b, 1, 0);
471 
472         b.measure(50, 5);
473         assert_bucket_eq!(b, 0, 8);
474         assert_bucket_eq!(b, 1, 0);
475 
476         b.measure(100, 2);
477         assert_bucket_eq!(b, 0, 8);
478         assert_bucket_eq!(b, 1, 2);
479         assert_bucket_eq!(b, 2, 0);
480 
481         b.measure(101, 19);
482         assert_bucket_eq!(b, 0, 8);
483         assert_bucket_eq!(b, 1, 21);
484         assert_bucket_eq!(b, 2, 0);
485 
486         for bucket in h.buckets.iter() {
487             assert_eq!(bucket.load(Relaxed), 0);
488         }
489 
490         b.submit(&h);
491 
492         for i in 0..h.buckets.len() {
493             assert_eq!(h.buckets[i].load(Relaxed), b.buckets[i]);
494         }
495 
496         b.submit(&h);
497 
498         for i in 0..h.buckets.len() {
499             assert_eq!(h.buckets[i].load(Relaxed), b.buckets[i]);
500         }
501     }
502 }
503