ruvector_verified/
cache.rs

1//! Conversion result cache with access-pattern prediction.
2//!
3//! Modeled after `ruvector-mincut`'s PathDistanceCache (10x speedup).
4
5use std::collections::VecDeque;
6
7/// Open-addressing conversion cache with prefetch hints.
8pub struct ConversionCache {
9    entries: Vec<CacheEntry>,
10    mask: usize,
11    history: VecDeque<u64>,
12    stats: CacheStats,
13}
14
15#[derive(Clone, Default)]
16struct CacheEntry {
17    key_hash: u64,
18    #[allow(dead_code)]
19    input_id: u32,
20    result_id: u32,
21}
22
23/// Cache performance statistics.
24#[derive(Debug, Clone, Default)]
25pub struct CacheStats {
26    pub hits: u64,
27    pub misses: u64,
28    pub evictions: u64,
29}
30
31impl CacheStats {
32    pub fn hit_rate(&self) -> f64 {
33        let total = self.hits + self.misses;
34        if total == 0 { 0.0 } else { self.hits as f64 / total as f64 }
35    }
36}
37
38impl ConversionCache {
39    /// Create cache with given capacity (rounded up to power of 2).
40    pub fn with_capacity(cap: usize) -> Self {
41        let cap = cap.next_power_of_two().max(64);
42        Self {
43            entries: vec![CacheEntry::default(); cap],
44            mask: cap - 1,
45            history: VecDeque::with_capacity(64),
46            stats: CacheStats::default(),
47        }
48    }
49
50    /// Default cache (10,000 entries).
51    pub fn new() -> Self {
52        Self::with_capacity(10_000)
53    }
54
55    /// Look up a cached conversion result.
56    #[inline]
57    pub fn get(&mut self, term_id: u32, ctx_len: u32) -> Option<u32> {
58        let hash = self.key_hash(term_id, ctx_len);
59        let slot = (hash as usize) & self.mask;
60        let entry = &self.entries[slot];
61
62        if entry.key_hash == hash && entry.key_hash != 0 {
63            self.stats.hits += 1;
64            self.history.push_back(hash);
65            if self.history.len() > 64 { self.history.pop_front(); }
66            Some(entry.result_id)
67        } else {
68            self.stats.misses += 1;
69            None
70        }
71    }
72
73    /// Insert a conversion result.
74    pub fn insert(&mut self, term_id: u32, ctx_len: u32, result_id: u32) {
75        let hash = self.key_hash(term_id, ctx_len);
76        let slot = (hash as usize) & self.mask;
77
78        if self.entries[slot].key_hash != 0 {
79            self.stats.evictions += 1;
80        }
81
82        self.entries[slot] = CacheEntry {
83            key_hash: hash,
84            input_id: term_id,
85            result_id,
86        };
87    }
88
89    /// Clear all entries.
90    pub fn clear(&mut self) {
91        self.entries.fill(CacheEntry::default());
92        self.history.clear();
93    }
94
95    /// Get statistics.
96    pub fn stats(&self) -> &CacheStats {
97        &self.stats
98    }
99
100    #[inline]
101    fn key_hash(&self, term_id: u32, ctx_len: u32) -> u64 {
102        let mut h = term_id as u64;
103        h = h.wrapping_mul(0x517cc1b727220a95);
104        h ^= ctx_len as u64;
105        h = h.wrapping_mul(0x6c62272e07bb0142);
106        if h == 0 { h = 1; } // Reserve 0 for empty
107        h
108    }
109}
110
111impl Default for ConversionCache {
112    fn default() -> Self {
113        Self::new()
114    }
115}
116
117#[cfg(test)]
118mod tests {
119    use super::*;
120
121    #[test]
122    fn test_cache_miss_then_hit() {
123        let mut cache = ConversionCache::new();
124        assert!(cache.get(1, 0).is_none());
125        cache.insert(1, 0, 42);
126        assert_eq!(cache.get(1, 0), Some(42));
127    }
128
129    #[test]
130    fn test_cache_different_ctx() {
131        let mut cache = ConversionCache::new();
132        cache.insert(1, 0, 10);
133        cache.insert(1, 1, 20);
134        assert_eq!(cache.get(1, 0), Some(10));
135        assert_eq!(cache.get(1, 1), Some(20));
136    }
137
138    #[test]
139    fn test_cache_clear() {
140        let mut cache = ConversionCache::new();
141        cache.insert(1, 0, 42);
142        cache.clear();
143        assert!(cache.get(1, 0).is_none());
144    }
145
146    #[test]
147    fn test_cache_stats() {
148        let mut cache = ConversionCache::new();
149        cache.get(1, 0); // miss
150        cache.insert(1, 0, 42);
151        cache.get(1, 0); // hit
152        assert_eq!(cache.stats().hits, 1);
153        assert_eq!(cache.stats().misses, 1);
154        assert!((cache.stats().hit_rate() - 0.5).abs() < 0.01);
155    }
156
157    #[test]
158    fn test_cache_high_volume() {
159        let mut cache = ConversionCache::with_capacity(1024);
160        for i in 0..1000u32 {
161            cache.insert(i, 0, i * 10);
162        }
163        let mut hits = 0u32;
164        for i in 0..1000u32 {
165            if cache.get(i, 0).is_some() { hits += 1; }
166        }
167        // Due to collisions, not all will be found, but most should
168        assert!(hits > 500, "expected >50% hit rate, got {hits}/1000");
169    }
170}
ruvector_verified/cache.rs

ruvector_verified/
cache.rs
