Skip to main content

zero_client/
tdigest.rs

1//! A t-digest, for the inspector's percentiles (`TDigest` in
2//! `packages/shared/src/tdigest.ts`, itself a port of
3//! <https://github.com/influxdata/tdigest>, Apache License 2.0).
4//!
5//! The port does the same arithmetic in the same order as JS, so a digest
6//! fed the same values gives JS's quantiles exactly, and reads and writes
7//! the same JSON: `[compression, mean, weight, mean, weight, ...]`, which is
8//! how zero-cache sends its metrics.
9
10use crate::json::Value;
11use std::cell::RefCell;
12
13/// Initial capacity of the buffer of unprocessed values.
14const INITIAL_CAPACITY: usize = 16;
15
16/// A digest of a distribution of numbers, for its quantiles: it keeps
17/// roughly `compression` centroids, and buffers up to eight times as many
18/// values between merges.
19///
20/// Reading it (`quantile`, `count`, `to_json`, ...) merges the buffered
21/// values first, as in JS, so those take `&self`.
22#[derive(Clone, Debug)]
23pub struct TDigest {
24    compression: f64,
25    max_unprocessed: f64,
26    state: RefCell<State>,
27}
28
29#[derive(Clone, Debug)]
30struct State {
31    /// Means of the processed centroids, ascending.
32    means: Vec<f64>,
33    /// Weights of the processed centroids, parallel to `means`.
34    weights: Vec<f64>,
35    /// The values added since the last `process`, in order.
36    unprocessed_means: Vec<f64>,
37    unprocessed_weights: Vec<f64>,
38    cumulative: Vec<f64>,
39    processed_weight: f64,
40    unprocessed_weight: f64,
41    min: f64,
42    max: f64,
43}
44
45impl Default for TDigest {
46    /// A digest of compression 100, JS's default.
47    fn default() -> Self {
48        TDigest::new(100.0)
49    }
50}
51
52impl PartialEq for TDigest {
53    /// Digests are equal when their JSON forms are.
54    fn eq(&self, other: &Self) -> bool {
55        self.to_vec() == other.to_vec()
56    }
57}
58
59/// `Math.max`: NaN if either is, and +0 over -0.
60fn js_max(a: f64, b: f64) -> f64 {
61    if a.is_nan() || b.is_nan() {
62        return f64::NAN;
63    }
64    if a == b {
65        return if a.is_sign_negative() { b } else { a };
66    }
67    if a > b { a } else { b }
68}
69
70/// `Math.min`: NaN if either is, and -0 over +0.
71fn js_min(a: f64, b: f64) -> f64 {
72    if a.is_nan() || b.is_nan() {
73        return f64::NAN;
74    }
75    if a == b {
76        return if a.is_sign_negative() { a } else { b };
77    }
78    if a < b { a } else { b }
79}
80
81/// `binarySearch` in `packages/shared/src/binary-search.ts`.
82fn binary_search(mut high: usize, compare: impl Fn(usize) -> f64) -> usize {
83    let mut low = 0;
84    while low < high {
85        let mid = low + ((high - low) >> 1);
86        let i = compare(mid);
87        if i == 0.0 {
88            return mid;
89        }
90        if i > 0.0 {
91            low = mid + 1;
92        } else {
93            high = mid;
94        }
95    }
96    low
97}
98
99fn weighted_average(x1: f64, w1: f64, x2: f64, w2: f64) -> f64 {
100    if x1 <= x2 {
101        weighted_average_sorted(x1, w1, x2, w2)
102    } else {
103        weighted_average_sorted(x2, w2, x1, w1)
104    }
105}
106
107fn weighted_average_sorted(x1: f64, w1: f64, x2: f64, w2: f64) -> f64 {
108    let x = (x1 * w1 + x2 * w2) / (w1 + w2);
109    js_max(x1, js_min(x, x2))
110}
111
112impl TDigest {
113    /// An empty digest. JS's default compression, 100, keeps p50, p95 and
114    /// p99 within about 0.5%.
115    pub fn new(compression: f64) -> Self {
116        let max_unprocessed = compression.ceil() * 8.0;
117        let capacity = if max_unprocessed + 1.0 < INITIAL_CAPACITY as f64 {
118            (max_unprocessed + 1.0).max(0.0) as usize
119        } else {
120            INITIAL_CAPACITY
121        };
122        TDigest {
123            compression,
124            max_unprocessed,
125            state: RefCell::new(State {
126                means: Vec::new(),
127                weights: Vec::new(),
128                unprocessed_means: Vec::with_capacity(capacity),
129                unprocessed_weights: Vec::with_capacity(capacity),
130                cumulative: Vec::new(),
131                processed_weight: 0.0,
132                unprocessed_weight: 0.0,
133                min: f64::MAX,
134                max: -f64::MAX,
135            }),
136        }
137    }
138
139    /// The digest of its JSON form, `[compression, mean, weight, ...]`
140    /// (`TDigest.fromJSON`).
141    pub fn from_json(data: &[f64]) -> Result<Self, String> {
142        let mut digest = TDigest::new(data.first().copied().unwrap_or(100.0));
143        if data.len() % 2 != 1 {
144            return Err("Invalid centroids array".into());
145        }
146        for pair in data[1..].chunks(2) {
147            digest.add(pair[0], pair[1]);
148        }
149        Ok(digest)
150    }
151
152    /// [`from_json`](Self::from_json) of a JSON value: an array of numbers.
153    pub fn from_json_value(v: &Value) -> Result<Self, String> {
154        let Some(a) = v.as_array() else {
155            return Err("Expected a TDigest array".into());
156        };
157        let numbers: Option<Vec<f64>> = a.iter().map(Value::as_f64).collect();
158        let numbers = numbers.ok_or("Expected a TDigest array of numbers")?;
159        TDigest::from_json(&numbers)
160    }
161
162    /// The compression the digest was made with.
163    pub fn compression(&self) -> f64 {
164        self.compression
165    }
166
167    /// Empties the digest.
168    pub fn reset(&mut self) {
169        let s = self.state.get_mut();
170        s.means.clear();
171        s.weights.clear();
172        s.unprocessed_means.clear();
173        s.unprocessed_weights.clear();
174        s.cumulative.clear();
175        s.processed_weight = 0.0;
176        s.unprocessed_weight = 0.0;
177        s.min = f64::MAX;
178        s.max = -f64::MAX;
179    }
180
181    /// Adds a value with a weight (1 in JS by default). A weight that isn't
182    /// positive and finite is ignored, as is a NaN mean.
183    pub fn add(&mut self, mean: f64, weight: f64) {
184        if mean.is_nan() || weight <= 0.0 || !weight.is_finite() {
185            return;
186        }
187        let process = {
188            let s = self.state.get_mut();
189            s.unprocessed_means.push(mean);
190            s.unprocessed_weights.push(weight);
191            s.unprocessed_weight += weight;
192            s.unprocessed_means.len() as f64 > self.max_unprocessed
193        };
194        if process {
195            Self::process(self.compression, self.state.get_mut());
196        }
197    }
198
199    /// Adds each of `other`'s centroids (`merge`).
200    pub fn merge(&mut self, other: &TDigest) {
201        let (means, weights) = {
202            let mut s = other.state.borrow_mut();
203            Self::process(other.compression, &mut s);
204            (s.means.clone(), s.weights.clone())
205        };
206        for (m, w) in means.into_iter().zip(weights) {
207            self.add(m, w);
208        }
209    }
210
211    /// The processed centroids, as `(mean, weight)`, ascending.
212    pub fn centroids(&self) -> Vec<(f64, f64)> {
213        let s = self.processed();
214        s.means
215            .iter()
216            .copied()
217            .zip(s.weights.iter().copied())
218            .collect()
219    }
220
221    /// The total weight of the values added.
222    pub fn count(&self) -> f64 {
223        self.processed().processed_weight
224    }
225
226    /// The JSON form, `[compression, mean, weight, ...]` (`toJSON`).
227    pub fn to_vec(&self) -> Vec<f64> {
228        let s = self.processed();
229        let mut data = Vec::with_capacity(1 + 2 * s.means.len());
230        data.push(self.compression);
231        for (m, w) in s.means.iter().zip(&s.weights) {
232            data.push(*m);
233            data.push(*w);
234        }
235        data
236    }
237
238    /// [`to_vec`](Self::to_vec) as a JSON value.
239    pub fn to_json(&self) -> Value {
240        Value::Array(self.to_vec().into_iter().map(Value::Number).collect())
241    }
242
243    fn processed(&self) -> std::cell::RefMut<'_, State> {
244        let mut s = self.state.borrow_mut();
245        Self::process(self.compression, &mut s);
246        s
247    }
248
249    /// Merges the unprocessed values into the centroids: walks both in
250    /// order of mean, folding each into the last centroid while that stays
251    /// within its size limit, and starting a new centroid otherwise.
252    fn process(compression: f64, s: &mut State) {
253        if s.unprocessed_means.is_empty() {
254            return;
255        }
256        let (new_means, new_weights) = sorted_unprocessed(s);
257        s.unprocessed_means.clear();
258        s.unprocessed_weights.clear();
259        let n = new_means.len();
260        let p = s.means.len();
261        s.processed_weight += s.unprocessed_weight;
262        s.unprocessed_weight = 0.0;
263        let total = s.processed_weight;
264
265        let mut means = Vec::with_capacity(p + 1);
266        let mut weights = Vec::with_capacity(p + 1);
267        let mut mean = 0.0;
268        let mut weight = 0.0;
269        let mut so_far = 0.0;
270        let mut limit = 0.0;
271        let (mut i, mut j) = (0, 0);
272        while i < n || j < p {
273            // On a tie the new value goes first.
274            let (m, w);
275            if i < n && (j == p || new_means[i] <= s.means[j]) {
276                m = new_means[i];
277                w = new_weights[i];
278                i += 1;
279            } else {
280                m = s.means[j];
281                w = s.weights[j];
282                j += 1;
283            }
284            if so_far + w <= limit {
285                weight += w;
286                mean += (w * (m - mean)) / weight;
287            } else {
288                if weight > 0.0 {
289                    means.push(mean);
290                    weights.push(weight);
291                }
292                let k = integrated_location(compression, so_far / total);
293                limit = total * integrated_q(compression, k + 1.0);
294                mean = m;
295                weight = w;
296            }
297            so_far += w;
298        }
299        means.push(mean);
300        weights.push(weight);
301
302        s.min = js_min(s.min, means[0]);
303        s.max = js_max(s.max, *means.last().expect("a centroid"));
304        s.means = means;
305        s.weights = weights;
306    }
307
308    fn update_cumulative(s: &mut State) {
309        // Weight only increases, so an unchanged total means nothing
310        // changed since the last update.
311        if s.cumulative.last() == Some(&s.processed_weight) {
312            return;
313        }
314        s.cumulative.resize(s.means.len() + 1, 0.0);
315        let mut prev = 0.0;
316        for i in 0..s.means.len() {
317            let cur = s.weights[i];
318            s.cumulative[i] = prev + cur / 2.0;
319            prev += cur;
320        }
321        let n = s.means.len();
322        s.cumulative[n] = prev;
323    }
324
325    /// The (approximate) value at quantile `q`, between 0 and 1. NaN when
326    /// the digest is empty or `q` is out of range.
327    pub fn quantile(&self, q: f64) -> f64 {
328        let mut s = self.processed();
329        Self::update_cumulative(&mut s);
330        if q < 0.0 || q > 1.0 || s.means.is_empty() {
331            return f64::NAN;
332        }
333        if s.means.len() == 1 {
334            return s.means[0];
335        }
336        if q.is_nan() {
337            // JS reads past the arrays and gets NaN.
338            return f64::NAN;
339        }
340        let index = q * s.processed_weight;
341        if index <= s.weights[0] / 2.0 {
342            return s.min + ((2.0 * index) / s.weights[0]) * (s.means[0] - s.min);
343        }
344        let lower = binary_search(s.cumulative.len(), |i| -s.cumulative[i] + index);
345        if lower >= s.cumulative.len() {
346            // The sum of the weights rounded below `index`: JS reads past
347            // the arrays and gets NaN.
348            return f64::NAN;
349        }
350        if lower + 1 != s.cumulative.len() {
351            let z1 = index - s.cumulative[lower - 1];
352            let z2 = s.cumulative[lower] - index;
353            return weighted_average(s.means[lower - 1], z2, s.means[lower], z1);
354        }
355        let z1 = index - s.processed_weight - s.weights[lower - 1] / 2.0;
356        let z2 = s.weights[lower - 1] / 2.0 - z1;
357        weighted_average(*s.means.last().expect("a centroid"), z1, s.max, z2)
358    }
359
360    /// The (approximate) fraction of the values at or below `x`.
361    pub fn cdf(&self, x: f64) -> f64 {
362        let mut s = self.processed();
363        Self::update_cumulative(&mut s);
364        match s.means.len() {
365            0 => return 0.0,
366            1 => {
367                let width = s.max - s.min;
368                if x <= s.min {
369                    return 0.0;
370                }
371                if x >= s.max {
372                    return 1.0;
373                }
374                if x - s.min <= width {
375                    // Too close together to interpolate.
376                    return 0.5;
377                }
378                return (x - s.min) / width;
379            }
380            _ => {}
381        }
382        if x <= s.min {
383            return 0.0;
384        }
385        if x >= s.max {
386            return 1.0;
387        }
388        let m0 = s.means[0];
389        if x <= m0 {
390            if m0 - s.min > 0.0 {
391                return (((x - s.min) / (m0 - s.min)) * s.weights[0]) / s.processed_weight / 2.0;
392            }
393            return 0.0;
394        }
395        let mn = *s.means.last().expect("a centroid");
396        if x >= mn {
397            if s.max - mn > 0.0 {
398                return 1.0
399                    - (((s.max - x) / (s.max - mn)) * s.weights.last().expect("a centroid"))
400                        / s.processed_weight
401                        / 2.0;
402            }
403            return 1.0;
404        }
405        // Equal counts as greater, for the upper index.
406        let upper = binary_search(s.means.len(), |i| {
407            let d = x - s.means[i];
408            if d == 0.0 || d.is_nan() { 1.0 } else { d }
409        });
410        let z1 = x - s.means[upper - 1];
411        let z2 = s.means[upper] - x;
412        weighted_average(s.cumulative[upper - 1], z2, s.cumulative[upper], z1) / s.processed_weight
413    }
414}
415
416/// The unprocessed means and weights, sorted by mean, as JS sorts them.
417fn sorted_unprocessed(s: &State) -> (Vec<f64>, Vec<f64>) {
418    let means = &s.unprocessed_means;
419    let weights = &s.unprocessed_weights;
420    // `fromJSON` and `merge` add centroids in order of mean.
421    if means
422        .windows(2)
423        .all(|w| w[1].partial_cmp(&w[0]) != Some(std::cmp::Ordering::Less))
424    {
425        return (means.clone(), weights.clone());
426    }
427    // With one weight for every value, a numeric sort of the means alone
428    // (`Float64Array.prototype.sort`: -0 before +0).
429    if weights.iter().all(|w| *w == weights[0]) {
430        let mut sorted = means.clone();
431        sorted.sort_by(f64::total_cmp);
432        return (sorted, weights.clone());
433    }
434    // A stable sort by `means[a] - means[b]`.
435    let mut order: Vec<usize> = (0..means.len()).collect();
436    order.sort_by(|&a, &b| {
437        let d = means[a] - means[b];
438        if d < 0.0 {
439            std::cmp::Ordering::Less
440        } else if d > 0.0 {
441            std::cmp::Ordering::Greater
442        } else {
443            std::cmp::Ordering::Equal
444        }
445    });
446    (
447        order.iter().map(|&k| means[k]).collect(),
448        order.iter().map(|&k| weights[k]).collect(),
449    )
450}
451
452fn integrated_q(compression: f64, k: f64) -> f64 {
453    ((js_min(k, compression) * std::f64::consts::PI / compression - std::f64::consts::PI / 2.0)
454        .sin()
455        + 1.0)
456        / 2.0
457}
458
459fn integrated_location(compression: f64, q: f64) -> f64 {
460    (compression * ((2.0 * q - 1.0).asin() + std::f64::consts::PI / 2.0)) / std::f64::consts::PI
461}
462
463#[cfg(test)]
464mod tests {
465    use super::*;
466
467    #[test]
468    fn quantiles_of_a_few_values() {
469        let mut d = TDigest::default();
470        assert!(d.quantile(0.5).is_nan());
471        for v in [1.0, 2.0, 3.0, 4.0] {
472            d.add(v, 1.0);
473        }
474        assert_eq!(d.count(), 4.0);
475        assert_eq!(d.quantile(0.0), 1.0);
476        assert_eq!(d.quantile(1.0), 4.0);
477        assert_eq!(
478            d.to_vec(),
479            vec![100.0, 1.0, 1.0, 2.0, 1.0, 3.0, 1.0, 4.0, 1.0]
480        );
481        let back = TDigest::from_json(&d.to_vec()).unwrap();
482        assert_eq!(back, d);
483        assert!(TDigest::from_json(&[100.0, 1.0]).is_err());
484    }
485
486    #[test]
487    fn js_min_max() {
488        assert!(js_max(1.0, f64::NAN).is_nan());
489        assert!(js_max(-0.0, 0.0).is_sign_positive());
490        assert!(js_min(0.0, -0.0).is_sign_negative());
491    }
492}