zombie_rs/
meter.rs

1//! Time and space measurement for zombie eviction.
2//!
3//! This module provides:
4//! - [`ZombieOps`] trait for computing memory size
5//! - [`Time`] and [`Space`] quantized measurement types
6//! - [`ZombieMeter`] for timing operations
7//!
8//! # ZombieOps Trait
9//!
10//! The [`ZombieOps`] trait has two methods:
11//! - [`ZombieOps::stack_size()`] - Compile-time constant stack size
12//! - [`ZombieOps::heap_size()`] - Runtime O(1) heap size estimation
13//!
14//! The total size is `stack_size() + heap_size()`.
15//!
16//! ## Derive Macro
17//!
18//! For custom types, use `#[derive(ZombieOps)]`:
19//!
20//! ```rust,ignore
21//! use zombie_rs::meter::ZombieOps;
22//!
23//! #[derive(Clone, ZombieOps)]
24//! struct MyData {
25//!     buffer: Vec<u8>,
26//!     count: usize,
27//! }
28//! ```
29//!
30//! ## Orphan Rule Workaround
31//!
32//! Due to Rust's orphan rule, you cannot implement `ZombieOps` for types from
33//! external crates. Use a newtype wrapper:
34//!
35//! ```rust,ignore
36//! use zombie_rs::meter::ZombieOps;
37//! use external_crate::ExternalType;
38//!
39//! #[derive(Clone)]
40//! struct MyWrapper(ExternalType);
41//!
42//! impl ZombieOps for MyWrapper {
43//!     fn heap_size(&self) -> usize {
44//!         // Estimate heap size if ExternalType has heap allocations
45//!         0
46//!     }
47//! }
48//! ```
49
50use std::time::{Duration, Instant};
51
52// ============================================================================
53// Constants
54// ============================================================================
55
56/// Minimum time unit (1024 nanoseconds ≈ 1 microsecond).
57pub const PLANK_TIME_NS: u64 = 1024;
58
59/// Minimum space unit (16 bytes).
60pub const PLANK_SPACE_BYTES: usize = 16;
61
62// ============================================================================
63// ZombieOps Trait
64// ============================================================================
65
66/// Trait for computing memory size of zombie values.
67///
68/// This trait provides O(1) size calculation with zero heap iteration.
69/// The total memory footprint is `stack_size() + heap_size()`.
70///
71/// # Design Rationale
72///
73/// We split size into two parts:
74/// - `stack_size()`: Known at compile time, inlined to constant
75/// - `heap_size()`: O(1) estimation based on capacity, not content
76///
77/// This avoids the need for recursive traversal (which would be O(n))
78/// and provides predictable, fast size calculation.
79///
80/// # Implementation Guidelines
81///
82/// - `stack_size()` should return `std::mem::size_of::<Self>()`
83/// - `heap_size()` should return capacity-based estimation, NOT content iteration
84/// - For nested types, recursively call `heap_size()` on fields with heap allocations
85pub trait ZombieOps {
86    /// Stack size of this type (compile-time constant).
87    ///
88    /// Default: `std::mem::size_of::<Self>()`
89    #[inline]
90    fn stack_size() -> usize
91    where
92        Self: Sized,
93    {
94        std::mem::size_of::<Self>()
95    }
96
97    /// Heap size estimation (O(1), no iteration).
98    ///
99    /// Default: 0 (no heap allocation).
100    ///
101    /// Override for types with heap allocations (Vec, String, Box, etc.).
102    #[inline]
103    fn heap_size(&self) -> usize {
104        0
105    }
106
107    /// Total memory size = stack + heap.
108    ///
109    /// This is the primary method used by the eviction algorithm.
110    #[inline]
111    fn get_size(&self) -> usize
112    where
113        Self: Sized,
114    {
115        Self::stack_size() + self.heap_size()
116    }
117}
118
119// Re-export derive macro when feature is enabled
120#[cfg(feature = "derive")]
121pub use zombie_derive::ZombieOps;
122
123// ============================================================================
124// Primitive Implementations (heap_size = 0, use default)
125// ============================================================================
126
127macro_rules! impl_zombie_ops_primitive {
128    ($($t:ty),*) => {
129        $(
130            impl ZombieOps for $t {}
131        )*
132    };
133}
134
135impl_zombie_ops_primitive!(
136    u8, u16, u32, u64, u128, usize,
137    i8, i16, i32, i64, i128, isize,
138    f32, f64, bool, char, ()
139);
140
141// References: just pointer size, no heap
142impl<T: ?Sized> ZombieOps for &T {}
143
144// ============================================================================
145// Standard Library Types
146// ============================================================================
147
148// Vec<T>: capacity-based heap size (O(1))
149impl<T> ZombieOps for Vec<T> {
150    #[inline]
151    fn heap_size(&self) -> usize {
152        self.capacity() * std::mem::size_of::<T>()
153    }
154}
155
156// String: capacity-based heap size (O(1))
157impl ZombieOps for String {
158    #[inline]
159    fn heap_size(&self) -> usize {
160        self.capacity()
161    }
162}
163
164// Box<T>: heap contains the value itself plus its heap allocations
165impl<T: ZombieOps> ZombieOps for Box<T> {
166    #[inline]
167    fn heap_size(&self) -> usize {
168        T::stack_size() + self.as_ref().heap_size()
169    }
170}
171
172// Rc<T>: only pointer size, don't double-count shared data
173impl<T: ?Sized> ZombieOps for std::rc::Rc<T> {}
174
175// Arc<T>: only pointer size, don't double-count shared data
176impl<T: ?Sized> ZombieOps for std::sync::Arc<T> {}
177
178// Option<T>: propagate heap_size to inner value
179impl<T: ZombieOps> ZombieOps for Option<T> {
180    #[inline]
181    fn heap_size(&self) -> usize {
182        match self {
183            Some(v) => v.heap_size(),
184            None => 0,
185        }
186    }
187}
188
189// Result<T, E>: propagate heap_size to inner value
190impl<T: ZombieOps, E: ZombieOps> ZombieOps for Result<T, E> {
191    #[inline]
192    fn heap_size(&self) -> usize {
193        match self {
194            Ok(v) => v.heap_size(),
195            Err(e) => e.heap_size(),
196        }
197    }
198}
199
200// ============================================================================
201// Tuple Implementations
202// ============================================================================
203
204impl<A: ZombieOps, B: ZombieOps> ZombieOps for (A, B) {
205    #[inline]
206    fn heap_size(&self) -> usize {
207        self.0.heap_size() + self.1.heap_size()
208    }
209}
210
211impl<A: ZombieOps, B: ZombieOps, C: ZombieOps> ZombieOps for (A, B, C) {
212    #[inline]
213    fn heap_size(&self) -> usize {
214        self.0.heap_size() + self.1.heap_size() + self.2.heap_size()
215    }
216}
217
218impl<A: ZombieOps, B: ZombieOps, C: ZombieOps, D: ZombieOps> ZombieOps for (A, B, C, D) {
219    #[inline]
220    fn heap_size(&self) -> usize {
221        self.0.heap_size() + self.1.heap_size() + self.2.heap_size() + self.3.heap_size()
222    }
223}
224
225// ============================================================================
226// Array Implementation
227// ============================================================================
228
229impl<T: ZombieOps, const N: usize> ZombieOps for [T; N] {
230    #[inline]
231    fn heap_size(&self) -> usize {
232        // For primitives (heap_size = 0), this compiles to 0
233        self.iter().map(|e| e.heap_size()).sum()
234    }
235}
236
237// Note: &[T] is covered by `impl<T: ?Sized> ZombieOps for &T {}`
238// The slice itself doesn't own heap memory, only points to it.
239
240// ============================================================================
241// Time and Space Types
242// ============================================================================
243
244/// Quantized time measurement (stored as nanoseconds).
245///
246/// Uses u64 for compact 8-byte representation (vs Duration's 16 bytes).
247#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, PartialOrd, Ord)]
248pub struct Time(u64);
249
250impl Time {
251    pub const ZERO: Self = Time(0);
252
253    #[inline]
254    pub fn from_duration(d: Duration) -> Self {
255        Time(d.as_nanos() as u64)
256    }
257
258    #[inline]
259    pub const fn from_nanos(nanos: u64) -> Self {
260        Time(nanos)
261    }
262
263    /// Time in plank units (minimum 1 for non-zero).
264    #[inline]
265    pub fn plank(&self) -> u64 {
266        if self.0 == 0 {
267            0
268        } else {
269            (self.0 / PLANK_TIME_NS).max(1)
270        }
271    }
272
273    #[inline]
274    pub fn as_duration(&self) -> Duration {
275        Duration::from_nanos(self.0)
276    }
277
278    #[inline]
279    pub const fn as_nanos(&self) -> u64 {
280        self.0
281    }
282}
283
284impl std::ops::Add for Time {
285    type Output = Self;
286    #[inline]
287    fn add(self, rhs: Self) -> Self {
288        Time(self.0.saturating_add(rhs.0))
289    }
290}
291
292impl std::ops::Sub for Time {
293    type Output = Self;
294    #[inline]
295    fn sub(self, rhs: Self) -> Self {
296        Time(self.0.saturating_sub(rhs.0))
297    }
298}
299
300/// Quantized space measurement (stored as bytes).
301#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, PartialOrd, Ord)]
302pub struct Space(usize);
303
304impl Space {
305    pub const ZERO: Self = Space(0);
306
307    #[inline]
308    pub const fn from_bytes(bytes: usize) -> Self {
309        Space(bytes)
310    }
311
312    /// Space in plank units (minimum 1).
313    #[inline]
314    pub fn plank(&self) -> u64 {
315        ((self.0 / PLANK_SPACE_BYTES).max(1)) as u64
316    }
317
318    #[inline]
319    pub const fn as_bytes(&self) -> usize {
320        self.0
321    }
322}
323
324impl std::ops::Add for Space {
325    type Output = Self;
326    #[inline]
327    fn add(self, rhs: Self) -> Self {
328        Space(self.0 + rhs.0)
329    }
330}
331
332impl std::ops::AddAssign for Space {
333    #[inline]
334    fn add_assign(&mut self, rhs: Self) {
335        self.0 += rhs.0;
336    }
337}
338
339impl std::ops::Sub for Space {
340    type Output = Self;
341    #[inline]
342    fn sub(self, rhs: Self) -> Self {
343        Space(self.0.saturating_sub(rhs.0))
344    }
345}
346
347impl std::ops::SubAssign for Space {
348    #[inline]
349    fn sub_assign(&mut self, rhs: Self) {
350        self.0 = self.0.saturating_sub(rhs.0);
351    }
352}
353
354// ============================================================================
355// ZombieMeter
356// ============================================================================
357
358/// Clock for zombie operations with skip tracking.
359///
360/// Excludes time spent in nested recomputations to provide
361/// accurate measurement of actual computation time.
362pub struct ZombieMeter {
363    start: Instant,
364    skipped: Duration,
365    skip_stack: Vec<Duration>,
366}
367
368impl ZombieMeter {
369    pub fn new() -> Self {
370        Self {
371            start: Instant::now(),
372            skipped: Duration::ZERO,
373            skip_stack: Vec::new(),
374        }
375    }
376
377    /// Raw elapsed time since creation.
378    #[inline]
379    pub fn raw_time(&self) -> Duration {
380        self.start.elapsed()
381    }
382
383    /// Effective time excluding skipped periods.
384    #[inline]
385    pub fn time(&self) -> Time {
386        Time::from_duration(self.raw_time().saturating_sub(self.skipped))
387    }
388
389    /// Enter a block whose time should be excluded.
390    #[inline]
391    pub fn enter_skip_block(&mut self) {
392        self.skip_stack.push(self.raw_time());
393    }
394
395    /// Exit a skip block, adding elapsed time to skipped.
396    #[inline]
397    pub fn exit_skip_block(&mut self) {
398        if let Some(start) = self.skip_stack.pop() {
399            let elapsed = self.raw_time().saturating_sub(start);
400            self.skipped += elapsed;
401        }
402    }
403
404    /// Execute a function in a skip block.
405    #[inline]
406    pub fn in_skip_block<T, F: FnOnce() -> T>(&mut self, f: F) -> T {
407        self.enter_skip_block();
408        let result = f();
409        self.exit_skip_block();
410        result
411    }
412}
413
414impl Default for ZombieMeter {
415    fn default() -> Self {
416        Self::new()
417    }
418}
419
420// ============================================================================
421// Tests
422// ============================================================================
423
424#[cfg(test)]
425mod tests {
426    use super::*;
427
428    #[test]
429    fn test_time_plank() {
430        assert_eq!(Time::ZERO.plank(), 0);
431        assert_eq!(Time::from_nanos(1).plank(), 1);
432        assert_eq!(Time::from_nanos(1024).plank(), 1);
433        assert_eq!(Time::from_nanos(2048).plank(), 2);
434    }
435
436    #[test]
437    fn test_space_plank() {
438        assert_eq!(Space::from_bytes(0).plank(), 1);
439        assert_eq!(Space::from_bytes(1).plank(), 1);
440        assert_eq!(Space::from_bytes(16).plank(), 1);
441        assert_eq!(Space::from_bytes(32).plank(), 2);
442    }
443
444    #[test]
445    fn test_zombie_ops_primitives() {
446        assert_eq!(42i32.get_size(), 4);
447        assert_eq!(1.5f64.get_size(), 8);
448        assert_eq!(true.get_size(), 1);
449        // heap_size is 0 for primitives
450        assert_eq!(42i32.heap_size(), 0);
451    }
452
453    #[test]
454    fn test_zombie_ops_vec() {
455        let v: Vec<u8> = vec![1, 2, 3];
456        // stack: 24 bytes, heap: capacity * 1
457        assert_eq!(v.get_size(), Vec::<u8>::stack_size() + v.capacity());
458        assert_eq!(v.heap_size(), v.capacity());
459    }
460
461    #[test]
462    fn test_zombie_ops_string() {
463        let s = String::from("hello");
464        assert!(s.get_size() >= String::stack_size() + 5);
465        assert_eq!(s.heap_size(), s.capacity());
466    }
467
468    #[test]
469    fn test_zombie_ops_option() {
470        let none: Option<Vec<u8>> = None;
471        let some: Option<Vec<u8>> = Some(vec![1, 2, 3]);
472
473        // None: only stack size
474        assert_eq!(none.heap_size(), 0);
475
476        // Some: includes inner heap size
477        assert_eq!(some.heap_size(), some.as_ref().unwrap().capacity());
478    }
479
480    #[test]
481    fn test_zombie_ops_result() {
482        let ok: Result<Vec<u8>, String> = Ok(vec![1, 2, 3]);
483        let err: Result<Vec<u8>, String> = Err(String::from("error"));
484
485        // Ok: heap from inner Vec
486        assert_eq!(ok.heap_size(), ok.as_ref().unwrap().capacity());
487
488        // Err: heap from inner String
489        assert_eq!(err.heap_size(), err.as_ref().unwrap_err().capacity());
490    }
491
492    #[test]
493    fn test_zombie_ops_tuple() {
494        let t = (vec![1u8, 2, 3], String::from("test"));
495        let expected_heap = t.0.capacity() + t.1.capacity();
496        assert_eq!(t.heap_size(), expected_heap);
497    }
498
499    #[test]
500    fn test_zombie_ops_box() {
501        let b: Box<Vec<u8>> = Box::new(vec![1, 2, 3]);
502        // Box heap = Vec stack size + Vec heap size
503        let expected = Vec::<u8>::stack_size() + b.capacity();
504        assert_eq!(b.heap_size(), expected);
505    }
506
507    #[test]
508    fn test_zombie_ops_array() {
509        // Array of primitives: heap_size = 0
510        let arr: [i32; 4] = [1, 2, 3, 4];
511        assert_eq!(arr.heap_size(), 0);
512        assert_eq!(arr.get_size(), std::mem::size_of::<[i32; 4]>());
513    }
514
515    // Manual implementation test
516    #[derive(Clone)]
517    struct TestStruct {
518        data: Vec<u8>,
519        name: String,
520    }
521
522    impl ZombieOps for TestStruct {
523        fn heap_size(&self) -> usize {
524            self.data.heap_size() + self.name.heap_size()
525        }
526    }
527
528    #[test]
529    fn test_zombie_ops_manual_impl() {
530        let s = TestStruct {
531            data: vec![0; 10],
532            name: String::from("test"),
533        };
534        let expected_heap = s.data.capacity() + s.name.capacity();
535        assert_eq!(s.heap_size(), expected_heap);
536        assert_eq!(
537            s.get_size(),
538            TestStruct::stack_size() + expected_heap
539        );
540    }
541
542    #[test]
543    fn test_zombie_ops_simple_struct() {
544        #[derive(Clone)]
545        struct SimpleStruct {
546            _x: usize,
547        }
548
549        impl ZombieOps for SimpleStruct {}
550
551        let s = SimpleStruct { _x: 100 };
552        assert_eq!(s.heap_size(), 0);
553        assert_eq!(s.get_size(), SimpleStruct::stack_size());
554    }
555}
zombie_rs/meter.rs

zombie_rs/
meter.rs
