use std::collections::BTreeMap;
#[derive(Clone, Copy, Debug)]
struct Layout {
half_magnitude: u32,
highest: u64,
}
#[derive(Debug)]
pub(crate) struct Histogram {
layout: Layout,
counts: BTreeMap<u64, u64>,
total: u64,
}
#[derive(Debug, PartialEq)]
pub(crate) struct Row {
pub(crate) value: u64,
pub(crate) cumulative: u64,
}
impl Histogram {
pub(crate) fn sizes() -> Histogram {
Histogram::new(4, 1 << 40)
}
pub(crate) fn recalls() -> Histogram {
Histogram::new(2, 1_000_000)
}
pub(crate) fn latencies() -> Histogram {
Histogram::new(3, 60_000_000)
}
fn new(figures: u32, highest: u64) -> Histogram {
let single = 2 * 10u64.pow(figures);
let magnitude = 64 - (single - 1).leading_zeros();
Histogram {
layout: Layout { half_magnitude: magnitude - 1, highest },
counts: BTreeMap::new(),
total: 0,
}
}
pub(crate) fn record(&mut self, value: u64) {
if value > self.layout.highest {
return;
}
*self.counts.entry(self.layout.index_of(value)).or_default() += 1;
self.total += 1;
}
pub(crate) fn total(&self) -> u64 {
self.total
}
pub(crate) fn percentile_rows(&self) -> Vec<Row> {
let mut rows: Vec<Row> = Vec::new();
let mut target = 0.0f64;
let mut cumulative = 0u64;
for (&index, &count) in &self.counts {
cumulative += count;
let reached = 100.0 * cumulative as f64 / self.total as f64;
if target > reached {
continue;
}
let value = self.layout.highest_equivalent(self.layout.value_at(index));
if rows.last().is_none_or(|r| r.value != value) {
rows.push(Row { value, cumulative });
}
while cumulative < self.total && target <= reached {
target = next_target(target);
}
}
rows
}
pub(crate) fn value_at_percentile(&self, percentile: f64) -> u64 {
if percentile <= 0.0 {
return self.counts.keys().next().map_or(0, |&i| self.layout.value_at(i));
}
let wanted = ((percentile.min(100.0) / 100.0 * self.total as f64 + 0.5) as u64).max(1);
let mut cumulative = 0;
for (&index, &count) in &self.counts {
cumulative += count;
if cumulative >= wanted {
return self.layout.highest_equivalent(self.layout.value_at(index));
}
}
0
}
pub(crate) fn bounds(&self) -> (u64, u64) {
let low = self.counts.keys().next().map_or(0, |&i| self.layout.value_at(i));
let high = self
.counts
.keys()
.next_back()
.map_or(0, |&i| self.layout.highest_equivalent(self.layout.value_at(i)));
(low, high)
}
pub(crate) fn mean_and_deviation(&self) -> (f64, f64) {
if self.total == 0 {
return (0.0, 0.0);
}
let middle = |index: u64| self.layout.median_equivalent(self.layout.value_at(index)) as f64;
let sum: f64 = self.counts.iter().map(|(&i, &c)| c as f64 * middle(i)).sum();
let mean = sum / self.total as f64;
let spread: f64 =
self.counts.iter().map(|(&i, &c)| c as f64 * (middle(i) - mean).powi(2)).sum();
(mean, (spread / self.total as f64).sqrt())
}
}
fn next_target(p: f64) -> f64 {
let halvings = (100.0 / (100.0 - p)).log2() as i64 + 1;
let ticks = 2f64.powi(halvings as i32);
p + 100.0 / ticks
}
impl Layout {
fn half(self) -> u64 {
1 << self.half_magnitude
}
fn bucket_of(self, value: u64) -> (u32, u64) {
let mask = (1u64 << (self.half_magnitude + 1)) - 1;
let pow2ceiling = 64 - (value | mask).leading_zeros();
let bucket = pow2ceiling - (self.half_magnitude + 1);
(bucket, value >> bucket)
}
fn index_of(self, value: u64) -> u64 {
let (bucket, sub) = self.bucket_of(value);
(u64::from(bucket) << self.half_magnitude) + sub
}
fn value_at(self, index: u64) -> u64 {
let bucket = (index >> self.half_magnitude) as i64 - 1;
let sub = (index & (self.half() - 1)) + self.half();
if bucket < 0 { sub - self.half() } else { sub << bucket }
}
fn range_size(self, value: u64) -> u64 {
let (bucket, sub) = self.bucket_of(value);
let adjusted = if sub >= 2 * self.half() { bucket + 1 } else { bucket };
1 << adjusted
}
fn lowest_equivalent(self, value: u64) -> u64 {
let (bucket, sub) = self.bucket_of(value);
sub << bucket
}
fn highest_equivalent(self, value: u64) -> u64 {
self.lowest_equivalent(value) + self.range_size(value) - 1
}
fn median_equivalent(self, value: u64) -> u64 {
self.lowest_equivalent(value) + (self.range_size(value) >> 1)
}
}
#[cfg(test)]
mod tests {
use super::{Histogram, Row};
fn of(make: fn() -> Histogram, values: &[u64]) -> Histogram {
let mut h = make();
values.iter().for_each(|&v| h.record(v));
h
}
#[test]
fn small_values_are_exact_and_rows_follow_halving_percentiles() {
let rows = of(Histogram::sizes, &[32, 37, 37, 39, 56]).percentile_rows();
let expect = [(32, 1), (37, 3), (39, 4), (56, 5)]
.map(|(value, cumulative)| Row { value, cumulative });
assert_eq!(rows, expect);
let rows =
of(Histogram::sizes, &[30, 40, 80, 281, 334, 81944, 81944, 81944]).percentile_rows();
assert_eq!(rows.iter().map(|r| r.cumulative).collect::<Vec<_>>(), [1, 4, 8]);
assert_eq!((rows[0].value, rows[1].value), (30, 281));
}
#[test]
fn large_values_share_buckets() {
let sizes = Histogram::sizes().layout;
assert_eq!(sizes.highest_equivalent(1000), 1000);
assert_eq!(sizes.highest_equivalent(80020), 80023);
assert_eq!(sizes.median_equivalent(80020), 80022);
let latencies = Histogram::latencies().layout;
assert_eq!(latencies.highest_equivalent(2047), 2047, "three figures: exact below 2048");
assert_eq!(latencies.highest_equivalent(5000), 5003);
let (mean, dev) = of(Histogram::sizes, &[10, 20]).mean_and_deviation();
assert_eq!((mean, dev), (15.0, 5.0));
assert_eq!(Histogram::sizes().mean_and_deviation(), (0.0, 0.0));
let mut h = Histogram::latencies();
h.record(60_000_001);
assert_eq!(h.total(), 0, "past the highest trackable value");
}
#[test]
fn value_at_percentile_is_the_bucket_holding_that_rank() {
let h = of(Histogram::latencies, &[100, 200, 300, 400]);
assert_eq!(h.value_at_percentile(50.0), 200);
assert_eq!(h.value_at_percentile(99.0), 400);
assert_eq!(h.value_at_percentile(0.0), 100, "the lowest of the first bucket");
let r = of(Histogram::recalls, &[8001, 10001, 10001]);
assert_eq!(r.value_at_percentile(0.0), 8000);
assert_eq!(r.value_at_percentile(0.1), 8031);
assert_eq!(r.value_at_percentile(50.0), 10047);
assert_eq!(r.bounds(), (8000, 10047));
assert_eq!(Histogram::recalls().bounds(), (0, 0));
assert_eq!(h.value_at_percentile(150.0), 400);
assert_eq!(Histogram::latencies().value_at_percentile(50.0), 0);
}
}