hashiverse_lib/tools/
decaying_counter.rs

1//! # Exponentially-decaying event counter
2//!
3//! A tiny book-keeping helper for "how busy has this been *lately*" metrics. Each
4//! [`DecayingCounter`] holds a single `f64` accumulator that decays continuously
5//! toward zero with a configurable time constant `τ`. Recording an event adds to
6//! the accumulator; reading it decays the stored value forward to the current
7//! instant first.
8//!
9//! For a steady arrival rate `r` (events per millisecond) the accumulator settles
10//! at `r · τ`. So a counter with `τ = 1 hour` reads directly as "estimated events
11//! in the last hour", `τ = 1 day` as "events in the last day", and so on — the
12//! same exponentially-weighted idea behind Unix's `load_1m/5m/15m`.
13//!
14//! Like [`crate::tools::pow_required_estimator`] this takes [`TimeMillis`] as a
15//! plain parameter rather than depending on a `TimeProvider`, which keeps it
16//! trivially testable with explicit timestamps.
17
18use crate::tools::time::{DurationMillis, TimeMillis};
19
20/// A single exponentially-weighted decaying accumulator. See the module docs for
21/// the `r · τ` steady-state interpretation.
22#[derive(Debug, Clone)]
23pub struct DecayingCounter {
24    value: f64,
25    last_update_millis: TimeMillis,
26    time_constant_millis: f64,
27}
28
29impl DecayingCounter {
30    /// Create an empty counter with the given decay time constant `τ`.
31    pub fn new(time_constant: DurationMillis) -> Self {
32        Self {
33            value: 0.0,
34            // TimeMillis(0) is safe as a baseline: a zero accumulator decays to
35            // zero from any starting point, so the first `record` just anchors the
36            // clock without spuriously decaying a real value.
37            last_update_millis: TimeMillis::zero(),
38            time_constant_millis: time_constant.0 as f64,
39        }
40    }
41
42    /// Decay the stored value forward to `now`, then add `count` events.
43    pub fn record(&mut self, now: TimeMillis, count: u64) {
44        self.value = self.estimate(now) + count as f64;
45        self.last_update_millis = now;
46    }
47
48    /// The decayed accumulator at `now` — an estimate of the number of events in
49    /// roughly the last `τ`. Does not mutate, so repeated calls at the same `now`
50    /// are stable.
51    pub fn estimate(&self, now: TimeMillis) -> f64 {
52        // Clamp to >= 0: a `now` earlier than the last update (clock skew, or a
53        // scaled test clock stepping backwards) must not inflate the value.
54        let elapsed_millis = (now.0 - self.last_update_millis.0).max(0) as f64;
55        self.value * (-elapsed_millis / self.time_constant_millis).exp()
56    }
57}
58
59#[cfg(test)]
60mod tests {
61    use super::*;
62    use crate::tools::time::{MILLIS_IN_HOUR, MILLIS_IN_MINUTE};
63
64    #[test]
65    fn zero_before_any_record() {
66        let counter = DecayingCounter::new(MILLIS_IN_HOUR);
67        assert_eq!(counter.estimate(TimeMillis::zero()), 0.0);
68        assert_eq!(counter.estimate(TimeMillis(MILLIS_IN_HOUR.0)), 0.0);
69    }
70
71    #[test]
72    fn single_record_reads_count_immediately_then_decays() {
73        let mut counter = DecayingCounter::new(MILLIS_IN_HOUR);
74        let t0 = TimeMillis(MILLIS_IN_HOUR.0); // non-zero so we exercise real decay maths
75        counter.record(t0, 100);
76
77        // Immediately, the estimate is the recorded count.
78        assert!((counter.estimate(t0) - 100.0).abs() < 1e-9, "got {}", counter.estimate(t0));
79
80        // After one time constant it has decayed by a factor of e.
81        let after_one_tau = TimeMillis(t0.0 + MILLIS_IN_HOUR.0);
82        let expected = 100.0 / std::f64::consts::E;
83        assert!((counter.estimate(after_one_tau) - expected).abs() < 1e-6, "got {}", counter.estimate(after_one_tau));
84
85        // Far in the future it approaches zero.
86        let much_later = TimeMillis(t0.0 + MILLIS_IN_HOUR.0 * 100);
87        assert!(counter.estimate(much_later) < 1e-6, "got {}", counter.estimate(much_later));
88    }
89
90    #[test]
91    fn steady_cadence_converges_near_rate_times_tau() {
92        // One event per minute into a 1-hour counter should settle near 60.
93        let mut counter = DecayingCounter::new(MILLIS_IN_HOUR);
94        let mut now = TimeMillis::zero();
95        for _ in 0..10_000 {
96            now = TimeMillis(now.0 + MILLIS_IN_MINUTE.0);
97            counter.record(now, 1);
98        }
99        let estimate = counter.estimate(now);
100        assert!((estimate - 60.0).abs() < 1.0, "expected ~60, got {}", estimate);
101    }
102
103    #[test]
104    fn estimate_is_non_mutating() {
105        let mut counter = DecayingCounter::new(MILLIS_IN_HOUR);
106        counter.record(TimeMillis(MILLIS_IN_HOUR.0), 50);
107        let later = TimeMillis(MILLIS_IN_HOUR.0 * 3);
108        let first = counter.estimate(later);
109        let second = counter.estimate(later);
110        assert_eq!(first, second);
111    }
112
113    #[test]
114    fn backwards_now_does_not_inflate() {
115        let mut counter = DecayingCounter::new(MILLIS_IN_HOUR);
116        let t0 = TimeMillis(MILLIS_IN_HOUR.0 * 5);
117        counter.record(t0, 100);
118        // A timestamp before the last update is clamped — never larger than the value at t0.
119        let earlier = TimeMillis(t0.0 - MILLIS_IN_HOUR.0);
120        assert!(counter.estimate(earlier) <= 100.0 + 1e-9, "got {}", counter.estimate(earlier));
121        assert!((counter.estimate(earlier) - 100.0).abs() < 1e-9, "got {}", counter.estimate(earlier));
122    }
123}
hashiverse_lib/tools/decaying_counter.rs

hashiverse_lib/tools/
decaying_counter.rs
