oximedia_graph/
node_cache.rs

1#![allow(dead_code)]
2//! Caching system for graph node outputs.
3//!
4//! This module provides a caching layer for intermediate results produced
5//! by graph nodes. This avoids redundant computation when multiple
6//! downstream nodes consume the same data or when re-evaluating a graph
7//! with unchanged inputs.
8
9use std::collections::HashMap;
10
11/// Unique key for a cached result.
12#[derive(Debug, Clone, PartialEq, Eq, Hash)]
13pub struct CacheKey {
14    /// Node identifier.
15    pub node_id: u64,
16    /// Output port index.
17    pub port: u32,
18    /// Generation/version counter for invalidation.
19    pub generation: u64,
20}
21
22impl CacheKey {
23    /// Create a new cache key.
24    pub fn new(node_id: u64, port: u32, generation: u64) -> Self {
25        Self {
26            node_id,
27            port,
28            generation,
29        }
30    }
31}
32
33impl std::fmt::Display for CacheKey {
34    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
35        write!(f, "{}:{}@{}", self.node_id, self.port, self.generation)
36    }
37}
38
39/// A cached data entry.
40#[derive(Debug, Clone)]
41pub struct CacheEntry {
42    /// The cached data as raw bytes.
43    pub data: Vec<u8>,
44    /// Size in bytes.
45    pub size: usize,
46    /// Number of times this entry has been accessed.
47    pub access_count: u64,
48    /// Creation timestamp (monotonic counter).
49    pub created_at: u64,
50    /// Last access timestamp (monotonic counter).
51    pub last_accessed: u64,
52}
53
54impl CacheEntry {
55    /// Create a new cache entry.
56    pub fn new(data: Vec<u8>, timestamp: u64) -> Self {
57        let size = data.len();
58        Self {
59            data,
60            size,
61            access_count: 0,
62            created_at: timestamp,
63            last_accessed: timestamp,
64        }
65    }
66
67    /// Record an access to this entry.
68    pub fn touch(&mut self, timestamp: u64) {
69        self.access_count += 1;
70        self.last_accessed = timestamp;
71    }
72}
73
74/// Eviction policy for the cache.
75#[derive(Debug, Clone, Copy, PartialEq, Eq)]
76pub enum EvictionPolicy {
77    /// Least Recently Used.
78    Lru,
79    /// Least Frequently Used.
80    Lfu,
81    /// First In, First Out.
82    Fifo,
83}
84
85/// Cache statistics.
86#[derive(Debug, Clone, Default, PartialEq)]
87pub struct CacheStatistics {
88    /// Number of cache hits.
89    pub hits: u64,
90    /// Number of cache misses.
91    pub misses: u64,
92    /// Number of evictions.
93    pub evictions: u64,
94    /// Number of explicit invalidations.
95    pub invalidations: u64,
96    /// Current number of entries.
97    pub entry_count: usize,
98    /// Current total memory usage in bytes.
99    pub memory_bytes: usize,
100}
101
102impl CacheStatistics {
103    /// Compute hit rate as a ratio (0.0 to 1.0).
104    #[allow(clippy::cast_precision_loss)]
105    pub fn hit_rate(&self) -> f64 {
106        let total = self.hits + self.misses;
107        if total == 0 {
108            return 0.0;
109        }
110        self.hits as f64 / total as f64
111    }
112}
113
114/// A cache for graph node outputs.
115pub struct NodeCache {
116    /// Stored entries.
117    entries: HashMap<CacheKey, CacheEntry>,
118    /// Maximum memory budget in bytes.
119    max_memory: usize,
120    /// Current memory usage.
121    current_memory: usize,
122    /// Eviction policy.
123    policy: EvictionPolicy,
124    /// Monotonic clock for timestamps.
125    clock: u64,
126    /// Statistics.
127    stats: CacheStatistics,
128}
129
130impl NodeCache {
131    /// Create a new node cache with a given memory budget and eviction policy.
132    pub fn new(max_memory: usize, policy: EvictionPolicy) -> Self {
133        Self {
134            entries: HashMap::new(),
135            max_memory,
136            current_memory: 0,
137            policy,
138            clock: 0,
139            stats: CacheStatistics::default(),
140        }
141    }
142
143    /// Create a cache with LRU policy.
144    pub fn lru(max_memory: usize) -> Self {
145        Self::new(max_memory, EvictionPolicy::Lru)
146    }
147
148    /// Insert data into the cache.
149    ///
150    /// May evict existing entries if the memory budget is exceeded.
151    pub fn insert(&mut self, key: CacheKey, data: Vec<u8>) {
152        let entry_size = data.len();
153        // Evict if necessary
154        while self.current_memory + entry_size > self.max_memory && !self.entries.is_empty() {
155            self.evict_one();
156        }
157        // If single entry exceeds budget, do not insert
158        if entry_size > self.max_memory {
159            return;
160        }
161        self.clock += 1;
162        let entry = CacheEntry::new(data, self.clock);
163        self.current_memory += entry_size;
164        // If replacing existing entry, subtract old size
165        if let Some(old) = self.entries.insert(key, entry) {
166            self.current_memory -= old.size;
167        }
168        self.stats.entry_count = self.entries.len();
169        self.stats.memory_bytes = self.current_memory;
170    }
171
172    /// Get a reference to cached data.
173    pub fn get(&mut self, key: &CacheKey) -> Option<&[u8]> {
174        self.clock += 1;
175        let ts = self.clock;
176        if let Some(entry) = self.entries.get_mut(key) {
177            entry.touch(ts);
178            self.stats.hits += 1;
179            Some(&entry.data)
180        } else {
181            self.stats.misses += 1;
182            None
183        }
184    }
185
186    /// Check if a key is present without updating access stats.
187    pub fn contains(&self, key: &CacheKey) -> bool {
188        self.entries.contains_key(key)
189    }
190
191    /// Remove a specific key from the cache.
192    pub fn invalidate(&mut self, key: &CacheKey) -> bool {
193        if let Some(entry) = self.entries.remove(key) {
194            self.current_memory -= entry.size;
195            self.stats.invalidations += 1;
196            self.stats.entry_count = self.entries.len();
197            self.stats.memory_bytes = self.current_memory;
198            true
199        } else {
200            false
201        }
202    }
203
204    /// Invalidate all entries for a given node.
205    pub fn invalidate_node(&mut self, node_id: u64) {
206        let keys_to_remove: Vec<CacheKey> = self
207            .entries
208            .keys()
209            .filter(|k| k.node_id == node_id)
210            .cloned()
211            .collect();
212        for key in keys_to_remove {
213            self.invalidate(&key);
214        }
215    }
216
217    /// Clear all entries.
218    pub fn clear(&mut self) {
219        self.entries.clear();
220        self.current_memory = 0;
221        self.stats.entry_count = 0;
222        self.stats.memory_bytes = 0;
223    }
224
225    /// Current number of entries.
226    pub fn len(&self) -> usize {
227        self.entries.len()
228    }
229
230    /// Whether the cache is empty.
231    pub fn is_empty(&self) -> bool {
232        self.entries.is_empty()
233    }
234
235    /// Current memory usage.
236    pub fn memory_usage(&self) -> usize {
237        self.current_memory
238    }
239
240    /// Get cache statistics.
241    pub fn statistics(&self) -> &CacheStatistics {
242        &self.stats
243    }
244
245    /// Evict a single entry according to the eviction policy.
246    fn evict_one(&mut self) {
247        let victim = match self.policy {
248            EvictionPolicy::Lru => self.find_lru(),
249            EvictionPolicy::Lfu => self.find_lfu(),
250            EvictionPolicy::Fifo => self.find_fifo(),
251        };
252        if let Some(key) = victim {
253            if let Some(entry) = self.entries.remove(&key) {
254                self.current_memory -= entry.size;
255                self.stats.evictions += 1;
256                self.stats.entry_count = self.entries.len();
257                self.stats.memory_bytes = self.current_memory;
258            }
259        }
260    }
261
262    /// Find the least recently used entry.
263    fn find_lru(&self) -> Option<CacheKey> {
264        self.entries
265            .iter()
266            .min_by_key(|(_, e)| e.last_accessed)
267            .map(|(k, _)| k.clone())
268    }
269
270    /// Find the least frequently used entry.
271    fn find_lfu(&self) -> Option<CacheKey> {
272        self.entries
273            .iter()
274            .min_by_key(|(_, e)| e.access_count)
275            .map(|(k, _)| k.clone())
276    }
277
278    /// Find the oldest entry (FIFO).
279    fn find_fifo(&self) -> Option<CacheKey> {
280        self.entries
281            .iter()
282            .min_by_key(|(_, e)| e.created_at)
283            .map(|(k, _)| k.clone())
284    }
285}
286
287#[cfg(test)]
288mod tests {
289    use super::*;
290
291    #[test]
292    fn test_cache_key_display() {
293        let key = CacheKey::new(42, 0, 7);
294        assert_eq!(format!("{key}"), "42:0@7");
295    }
296
297    #[test]
298    fn test_cache_insert_and_get() {
299        let mut cache = NodeCache::lru(1024);
300        let key = CacheKey::new(1, 0, 1);
301        cache.insert(key.clone(), vec![1, 2, 3, 4]);
302        let data = cache.get(&key).expect("get should succeed");
303        assert_eq!(data, &[1, 2, 3, 4]);
304    }
305
306    #[test]
307    fn test_cache_miss() {
308        let mut cache = NodeCache::lru(1024);
309        let key = CacheKey::new(1, 0, 1);
310        assert!(cache.get(&key).is_none());
311        assert_eq!(cache.statistics().misses, 1);
312    }
313
314    #[test]
315    fn test_cache_hit_rate() {
316        let mut cache = NodeCache::lru(1024);
317        let key = CacheKey::new(1, 0, 1);
318        cache.insert(key.clone(), vec![1, 2, 3]);
319        cache.get(&key); // hit
320        cache.get(&CacheKey::new(2, 0, 1)); // miss
321        let rate = cache.statistics().hit_rate();
322        assert!((rate - 0.5).abs() < f64::EPSILON);
323    }
324
325    #[test]
326    fn test_cache_eviction_lru() {
327        let mut cache = NodeCache::lru(10); // 10 bytes max
328        cache.insert(CacheKey::new(1, 0, 1), vec![0; 5]);
329        cache.insert(CacheKey::new(2, 0, 1), vec![0; 5]);
330        // Cache is full (10 bytes)
331        assert_eq!(cache.len(), 2);
332        // Insert another, should evict LRU (key 1)
333        cache.insert(CacheKey::new(3, 0, 1), vec![0; 5]);
334        assert_eq!(cache.len(), 2);
335        assert!(!cache.contains(&CacheKey::new(1, 0, 1)));
336        assert!(cache.contains(&CacheKey::new(3, 0, 1)));
337    }
338
339    #[test]
340    fn test_cache_eviction_fifo() {
341        let mut cache = NodeCache::new(10, EvictionPolicy::Fifo);
342        cache.insert(CacheKey::new(1, 0, 1), vec![0; 5]);
343        cache.insert(CacheKey::new(2, 0, 1), vec![0; 5]);
344        cache.insert(CacheKey::new(3, 0, 1), vec![0; 5]);
345        // Should have evicted the first inserted
346        assert!(!cache.contains(&CacheKey::new(1, 0, 1)));
347    }
348
349    #[test]
350    fn test_cache_eviction_lfu() {
351        let mut cache = NodeCache::new(15, EvictionPolicy::Lfu);
352        cache.insert(CacheKey::new(1, 0, 1), vec![0; 5]);
353        cache.insert(CacheKey::new(2, 0, 1), vec![0; 5]);
354        cache.insert(CacheKey::new(3, 0, 1), vec![0; 5]);
355        // Access key 1 and 3 multiple times
356        cache.get(&CacheKey::new(1, 0, 1));
357        cache.get(&CacheKey::new(1, 0, 1));
358        cache.get(&CacheKey::new(3, 0, 1));
359        // Now insert something that forces eviction of LFU (key 2)
360        cache.insert(CacheKey::new(4, 0, 1), vec![0; 5]);
361        assert!(!cache.contains(&CacheKey::new(2, 0, 1)));
362    }
363
364    #[test]
365    fn test_cache_invalidate() {
366        let mut cache = NodeCache::lru(1024);
367        let key = CacheKey::new(1, 0, 1);
368        cache.insert(key.clone(), vec![1, 2, 3]);
369        assert!(cache.invalidate(&key));
370        assert!(!cache.contains(&key));
371        assert_eq!(cache.statistics().invalidations, 1);
372    }
373
374    #[test]
375    fn test_cache_invalidate_node() {
376        let mut cache = NodeCache::lru(1024);
377        cache.insert(CacheKey::new(1, 0, 1), vec![1]);
378        cache.insert(CacheKey::new(1, 1, 1), vec![2]);
379        cache.insert(CacheKey::new(2, 0, 1), vec![3]);
380        cache.invalidate_node(1);
381        assert_eq!(cache.len(), 1);
382        assert!(cache.contains(&CacheKey::new(2, 0, 1)));
383    }
384
385    #[test]
386    fn test_cache_clear() {
387        let mut cache = NodeCache::lru(1024);
388        cache.insert(CacheKey::new(1, 0, 1), vec![1, 2]);
389        cache.insert(CacheKey::new(2, 0, 1), vec![3, 4]);
390        cache.clear();
391        assert!(cache.is_empty());
392        assert_eq!(cache.memory_usage(), 0);
393    }
394
395    #[test]
396    fn test_cache_memory_tracking() {
397        let mut cache = NodeCache::lru(1024);
398        cache.insert(CacheKey::new(1, 0, 1), vec![0; 100]);
399        assert_eq!(cache.memory_usage(), 100);
400        cache.insert(CacheKey::new(2, 0, 1), vec![0; 200]);
401        assert_eq!(cache.memory_usage(), 300);
402        cache.invalidate(&CacheKey::new(1, 0, 1));
403        assert_eq!(cache.memory_usage(), 200);
404    }
405
406    #[test]
407    fn test_cache_oversize_entry_not_inserted() {
408        let mut cache = NodeCache::lru(10);
409        cache.insert(CacheKey::new(1, 0, 1), vec![0; 20]);
410        assert!(cache.is_empty());
411    }
412
413    #[test]
414    fn test_cache_statistics_default() {
415        let stats = CacheStatistics::default();
416        assert_eq!(stats.hits, 0);
417        assert_eq!(stats.misses, 0);
418        assert!((stats.hit_rate() - 0.0).abs() < f64::EPSILON);
419    }
420
421    #[test]
422    fn test_cache_entry_touch() {
423        let mut entry = CacheEntry::new(vec![1, 2, 3], 10);
424        assert_eq!(entry.access_count, 0);
425        entry.touch(20);
426        assert_eq!(entry.access_count, 1);
427        assert_eq!(entry.last_accessed, 20);
428    }
429}
oximedia_graph/node_cache.rs

oximedia_graph/
node_cache.rs
