perpcity-sdk 0.2.1

//! Rolling-window latency tracker with percentile statistics.
//!
//! Records latency samples in a fixed-size circular buffer (1024 entries)
//! for O(1) recording and O(n log n) percentile computation.
//!
//! # Example
//!
//! ```
//! use perpcity_sdk::hft::latency::LatencyTracker;
//!
//! let mut tracker = LatencyTracker::new();
//! for ns in [100_000, 200_000, 150_000, 300_000, 250_000] {
//!     tracker.record(ns);
//! }
//! let stats = tracker.stats().unwrap();
//! assert_eq!(stats.count, 5);
//! assert_eq!(stats.min_ns, 100_000);
//! assert_eq!(stats.max_ns, 300_000);
//! assert!(stats.p50_ns > 0);
//! ```

use serde::{Deserialize, Serialize};

/// Maximum number of samples retained in the rolling window.
///
/// Must be a power of 2 for the bitmask in [`LatencyTracker::record`].
const MAX_SAMPLES: usize = 1024;

// Compile-time assertion: record() uses `& (MAX_SAMPLES - 1)` as a
// bounds-check-free index, which requires a power-of-2 buffer size.
const _: () = assert!(
    MAX_SAMPLES.is_power_of_two(),
    "MAX_SAMPLES must be a power of 2 for bitmask indexing"
);

/// Computed latency statistics.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
pub struct LatencyStats {
    /// Total number of samples recorded (may exceed `MAX_SAMPLES`).
    pub count: u64,
    /// Minimum latency observed (nanoseconds).
    pub min_ns: u64,
    /// Maximum latency observed (nanoseconds).
    pub max_ns: u64,
    /// Average latency (nanoseconds). Computed over the rolling window.
    pub avg_ns: u64,
    /// 50th percentile (median) latency.
    pub p50_ns: u64,
    /// 95th percentile latency.
    pub p95_ns: u64,
    /// 99th percentile latency.
    pub p99_ns: u64,
}

/// Rolling-window latency tracker.
///
/// Uses a fixed 1024-sample circular buffer for O(1) recording.
/// Statistics are computed on-demand with an O(n log n) sort.
///
/// Running min/max are tracked globally (never reset unless explicit).
#[derive(Debug)]
pub struct LatencyTracker {
    samples: [u64; MAX_SAMPLES],
    /// How many samples are currently in the buffer (capped at MAX_SAMPLES).
    sample_count: usize,
    /// Next write index (wraps around).
    write_index: usize,

    // Running stats (over entire lifetime, not just the window)
    total_count: u64,
    min_ns: u64,
    max_ns: u64,
}

impl LatencyTracker {
    /// Create a new tracker with an empty window.
    pub fn new() -> Self {
        Self {
            samples: [0; MAX_SAMPLES],
            sample_count: 0,
            write_index: 0,
            total_count: 0,
            min_ns: u64::MAX,
            max_ns: 0,
        }
    }

    /// Record a latency sample in nanoseconds. **O(1).**
    ///
    /// Uses a power-of-2 bitmask for the circular buffer index, which the
    /// compiler optimizes to a single AND instruction with no bounds check.
    #[inline]
    pub fn record(&mut self, latency_ns: u64) {
        // SAFETY: write_index is always masked to [0, MAX_SAMPLES), and
        // MAX_SAMPLES is a power of 2 (1024), so the AND guarantees
        // the index is in bounds. This eliminates the bounds-check branch
        // that the compiler can't prove away with safe indexing.
        // Measured: 2.1ns → 0.6ns (3.5× speedup)
        let idx = self.write_index & (MAX_SAMPLES - 1);
        unsafe { *self.samples.get_unchecked_mut(idx) = latency_ns };
        self.write_index = idx + 1; // no need to mask here; masked on next read
        if self.sample_count < MAX_SAMPLES {
            self.sample_count += 1;
        }

        self.total_count += 1;
        self.min_ns = self.min_ns.min(latency_ns);
        self.max_ns = self.max_ns.max(latency_ns);
    }

    /// Record elapsed time between two timestamps and return the elapsed ns.
    ///
    /// Useful with `std::time::Instant::elapsed().as_nanos()`.
    /// Returns 0 if `end_ns <= start_ns`.
    pub fn record_elapsed(&mut self, start_ns: u64, end_ns: u64) -> u64 {
        let elapsed = end_ns.saturating_sub(start_ns);
        self.record(elapsed);
        elapsed
    }

    /// Compute percentile statistics over the rolling window. **O(n log n).**
    ///
    /// Returns `None` if no samples have been recorded.
    pub fn stats(&self) -> Option<LatencyStats> {
        if self.sample_count == 0 {
            return None;
        }

        let n = self.sample_count;
        let mut sorted = Vec::with_capacity(n);
        sorted.extend_from_slice(&self.samples[..n]);
        sorted.sort_unstable();

        let window_sum: u128 = sorted.iter().map(|&x| x as u128).sum();
        let avg = (window_sum / n as u128) as u64;

        Some(LatencyStats {
            count: self.total_count,
            min_ns: self.min_ns,
            max_ns: self.max_ns,
            avg_ns: avg,
            p50_ns: percentile(&sorted, 50),
            p95_ns: percentile(&sorted, 95),
            p99_ns: percentile(&sorted, 99),
        })
    }

    /// Reset all state: window, running stats, everything.
    pub fn reset(&mut self) {
        *self = Self::new();
    }
}

impl Default for LatencyTracker {
    fn default() -> Self {
        Self::new()
    }
}

/// Compute the p-th percentile from a sorted slice.
/// Uses nearest-rank method: `sorted[ceil(n * p / 100) - 1]`.
fn percentile(sorted: &[u64], p: u32) -> u64 {
    debug_assert!(!sorted.is_empty());
    debug_assert!(p <= 100);

    let n = sorted.len();
    // Nearest-rank: index = ceil(n * p / 100) - 1, clamped to [0, n-1]
    let rank = (n as u64 * p as u64).div_ceil(100) as usize;
    let idx = rank.saturating_sub(1).min(n - 1);
    sorted[idx]
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn empty_tracker_returns_none() {
        let t = LatencyTracker::new();
        assert!(t.stats().is_none());
    }

    #[test]
    fn single_sample() {
        let mut t = LatencyTracker::new();
        t.record(42_000);
        let s = t.stats().unwrap();
        assert_eq!(s.count, 1);
        assert_eq!(s.min_ns, 42_000);
        assert_eq!(s.max_ns, 42_000);
        assert_eq!(s.avg_ns, 42_000);
        assert_eq!(s.p50_ns, 42_000);
        assert_eq!(s.p95_ns, 42_000);
        assert_eq!(s.p99_ns, 42_000);
    }

    #[test]
    fn known_percentiles() {
        let mut t = LatencyTracker::new();
        // Insert 100 samples: 1, 2, 3, ..., 100 (in ns)
        for i in 1..=100 {
            t.record(i);
        }
        let s = t.stats().unwrap();
        assert_eq!(s.count, 100);
        assert_eq!(s.min_ns, 1);
        assert_eq!(s.max_ns, 100);
        assert_eq!(s.p50_ns, 50);
        assert_eq!(s.p95_ns, 95);
        assert_eq!(s.p99_ns, 99);
    }

    #[test]
    fn circular_buffer_wraps() {
        let mut t = LatencyTracker::new();
        // Write 2048 samples (wraps the 1024-sample buffer twice)
        for i in 0..2048u64 {
            t.record(i);
        }
        let s = t.stats().unwrap();
        assert_eq!(s.count, 2048); // total count
        // The window should contain samples 1024..2047
        assert_eq!(s.min_ns, 0); // running min from first pass
        assert_eq!(s.max_ns, 2047);
        // p50 of [1024..2047] should be around 1535
        assert!(s.p50_ns >= 1530 && s.p50_ns <= 1540);
    }

    #[test]
    fn avg_is_window_average() {
        let mut t = LatencyTracker::new();
        t.record(100);
        t.record(200);
        t.record(300);
        let s = t.stats().unwrap();
        assert_eq!(s.avg_ns, 200); // (100+200+300)/3
    }

    #[test]
    fn record_elapsed() {
        let mut t = LatencyTracker::new();
        let elapsed = t.record_elapsed(1_000_000, 2_500_000);
        assert_eq!(elapsed, 1_500_000);
        let s = t.stats().unwrap();
        assert_eq!(s.count, 1);
        assert_eq!(s.p50_ns, 1_500_000);
    }

    #[test]
    fn record_elapsed_handles_backwards_time() {
        let mut t = LatencyTracker::new();
        let elapsed = t.record_elapsed(5_000_000, 1_000_000);
        assert_eq!(elapsed, 0);
    }

    #[test]
    fn reset_clears_everything() {
        let mut t = LatencyTracker::new();
        for i in 0..100 {
            t.record(i * 1000);
        }
        assert!(t.stats().is_some());

        t.reset();
        assert!(t.stats().is_none());
    }

    #[test]
    fn percentile_function_edge_cases() {
        // Single element
        assert_eq!(percentile(&[42], 0), 42);
        assert_eq!(percentile(&[42], 50), 42);
        assert_eq!(percentile(&[42], 100), 42);

        // Two elements
        assert_eq!(percentile(&[10, 20], 0), 10);
        assert_eq!(percentile(&[10, 20], 50), 10);
        assert_eq!(percentile(&[10, 20], 51), 20);
        assert_eq!(percentile(&[10, 20], 100), 20);
    }

    #[test]
    fn running_min_max_persist_across_window() {
        let mut t = LatencyTracker::new();
        t.record(1); // min
        // Fill buffer to push out the min
        for _ in 0..(MAX_SAMPLES + 10) {
            t.record(1000);
        }
        let s = t.stats().unwrap();
        // Running min should still be 1 even though it's out of the window
        assert_eq!(s.min_ns, 1);
    }

    #[test]
    fn struct_sizes_and_alignment() {
        // LatencyStats fits in a single cache line (64 bytes)
        assert_eq!(std::mem::size_of::<LatencyStats>(), 56);
        assert_eq!(std::mem::align_of::<LatencyStats>(), 8);

        // LatencyTracker: 8KB buffer + 5 fields × 8 bytes
        assert_eq!(std::mem::size_of::<LatencyTracker>(), 8232);
    }
}