Struct RollingMax

Source

pub struct RollingMax<T, const WINDOW: usize> { /* private fields */ }

Expand description

§Rolling Max

Tracks the largest value in a fixed-size window.

§Design

The algorithm for this is well-known but not formalized anywhere I found easily accessible. The constraint of accumulating values internally is also a slight divergence from how this problem is typically presented.

Implementations§

Source §

impl<T, const W: usize> RollingMax<T, W>
where T: PartialOrd,

Source

pub const fn new() -> Self

Constructs a new empty RollingMax.

This type is stored entirely on the stack, so be aware of window size. Boxing might be a good idea. Doing so yourself enables cache-friendlier patterns than if each RollingMax were unconditionally allocated on the heap.

use core::cmp::Reverse;
use high_roller::rolling_max::RollingMax;

const WINDOW: usize = 6000;

#[derive(Default)]
struct MyTelemetry {
    max_latency: RollingMax<u32, WINDOW>,
    min_latency: RollingMax<Reverse<u32>, WINDOW>,
    largest_batch: RollingMax<usize, WINDOW>
}

// `MyTelemetry` is too big to live comfortably on the stack.
// But keeping everything in one allocation may yield friendlier
// cache access patterns.
const _: () = assert!(core::mem::size_of::<MyTelemetry>() == 240120);
let _telemetry = Box::new(MyTelemetry::default());

Source

pub fn push(&mut self, entry: T)

Adds an entry to the rolling window. If the window is full, the oldest member is evicted.

use high_roller::rolling_max::RollingMax;

let mut window: RollingMax<usize, 3> = RollingMax::new();

window.push(usize::MAX);
window.push(1);
window.push(2);

assert_eq!(window.max().copied(), Some(usize::MAX));

// Evicts the first entry, which was previously the max.
window.push(0);
assert_eq!(window.max().copied(), Some(2));

Source

pub fn max(&self) -> Option<&T>

Returns the maximum entry in the window or None if the window is empty.

use high_roller::rolling_max::RollingMax;

let mut window: RollingMax<usize, 3> = RollingMax::new();
assert_eq!(window.max(), None);

window.push(5);
// Once any entry has been pushed, max will never again
// return None.
assert_eq!(window.max().copied(), Some(5));