shape_vm/
megamorphic_cache.rs

1//! Direct-mapped lossy cache for megamorphic property lookups.
2//!
3//! When a property access site has seen too many different schemas
4//! (Megamorphic state), we use this global cache as a last-resort
5//! optimization before falling back to name-based lookup.
6
7const CACHE_SIZE: usize = 1024;
8
9#[derive(Debug, Clone, Copy)]
10pub struct MegamorphicEntry {
11    pub key: u64,
12    pub field_idx: u16,
13    pub field_type_tag: u16,
14    pub valid: bool,
15}
16
17impl Default for MegamorphicEntry {
18    fn default() -> Self {
19        Self {
20            key: 0,
21            field_idx: 0,
22            field_type_tag: 0,
23            valid: false,
24        }
25    }
26}
27
28pub struct MegamorphicCache {
29    entries: Box<[MegamorphicEntry; CACHE_SIZE]>,
30}
31
32impl MegamorphicCache {
33    /// Creates a new cache with all entries invalid.
34    pub fn new() -> Self {
35        Self {
36            entries: Box::new([MegamorphicEntry::default(); CACHE_SIZE]),
37        }
38    }
39
40    /// Combines a schema_id and field name into a hash key.
41    ///
42    /// Uses FNV-1a-inspired mixing: fold the field name bytes into the
43    /// schema_id with multiply-xor rounds.
44    pub fn hash_key(schema_id: u64, field_name: &str) -> u64 {
45        // FNV-1a offset basis mixed with schema_id
46        let mut hash: u64 = 0xcbf29ce484222325 ^ schema_id;
47        for byte in field_name.bytes() {
48            hash ^= byte as u64;
49            hash = hash.wrapping_mul(0x100000001b3);
50        }
51        hash
52    }
53
54    /// Probes the cache for a matching entry.
55    /// Returns `Some((field_idx, field_type_tag))` on hit, `None` on miss.
56    pub fn probe(&self, key: u64) -> Option<(u16, u16)> {
57        let idx = (key as usize) % CACHE_SIZE;
58        let entry = &self.entries[idx];
59        if entry.valid && entry.key == key {
60            Some((entry.field_idx, entry.field_type_tag))
61        } else {
62            None
63        }
64    }
65
66    /// Inserts an entry at the direct-mapped position (key % CACHE_SIZE).
67    /// Overwrites any existing entry at that index.
68    pub fn insert(&mut self, key: u64, field_idx: u16, field_type_tag: u16) {
69        let idx = (key as usize) % CACHE_SIZE;
70        self.entries[idx] = MegamorphicEntry {
71            key,
72            field_idx,
73            field_type_tag,
74            valid: true,
75        };
76    }
77
78    /// Marks all entries as invalid.
79    pub fn invalidate_all(&mut self) {
80        for entry in self.entries.iter_mut() {
81            entry.valid = false;
82        }
83    }
84
85    /// Returns the ratio of valid entries (diagnostic).
86    pub fn hit_rate(&self) -> f64 {
87        let valid_count = self.entries.iter().filter(|e| e.valid).count();
88        valid_count as f64 / CACHE_SIZE as f64
89    }
90}
91
92impl Default for MegamorphicCache {
93    fn default() -> Self {
94        Self::new()
95    }
96}
97
98#[cfg(test)]
99mod tests {
100    use super::*;
101
102    #[test]
103    fn test_new_cache_empty() {
104        let cache = MegamorphicCache::new();
105        assert_eq!(cache.hit_rate(), 0.0);
106        // Probe any key should miss
107        assert_eq!(cache.probe(12345), None);
108    }
109
110    #[test]
111    fn test_insert_and_probe_hit() {
112        let mut cache = MegamorphicCache::new();
113        let key = MegamorphicCache::hash_key(42, "name");
114        cache.insert(key, 3, 7);
115
116        let result = cache.probe(key);
117        assert_eq!(result, Some((3, 7)));
118    }
119
120    #[test]
121    fn test_probe_miss() {
122        let mut cache = MegamorphicCache::new();
123        let key1 = MegamorphicCache::hash_key(42, "name");
124        let key2 = MegamorphicCache::hash_key(42, "age");
125        cache.insert(key1, 3, 7);
126
127        // Different key at potentially different index
128        // Even if same index, key won't match
129        assert_eq!(cache.probe(key2), None);
130    }
131
132    #[test]
133    fn test_hash_key_consistency() {
134        let k1 = MegamorphicCache::hash_key(100, "field_a");
135        let k2 = MegamorphicCache::hash_key(100, "field_a");
136        assert_eq!(k1, k2);
137
138        // Different field name -> different key
139        let k3 = MegamorphicCache::hash_key(100, "field_b");
140        assert_ne!(k1, k3);
141
142        // Different schema -> different key
143        let k4 = MegamorphicCache::hash_key(200, "field_a");
144        assert_ne!(k1, k4);
145    }
146
147    #[test]
148    fn test_invalidate_all() {
149        let mut cache = MegamorphicCache::new();
150        for i in 0..10u64 {
151            let key = MegamorphicCache::hash_key(i, "x");
152            cache.insert(key, i as u16, 0);
153        }
154        assert!(cache.hit_rate() > 0.0);
155
156        cache.invalidate_all();
157        assert_eq!(cache.hit_rate(), 0.0);
158
159        // Previously inserted keys should miss
160        let key = MegamorphicCache::hash_key(0, "x");
161        assert_eq!(cache.probe(key), None);
162    }
163
164    #[test]
165    fn test_collision_overwrites() {
166        let mut cache = MegamorphicCache::new();
167
168        // Two keys that map to the same index
169        let key1 = 100u64;
170        let key2 = key1 + CACHE_SIZE as u64; // same index: both % 1024 == 100
171
172        cache.insert(key1, 1, 10);
173        assert_eq!(cache.probe(key1), Some((1, 10)));
174
175        // Overwrite with key2 at same index
176        cache.insert(key2, 2, 20);
177        assert_eq!(cache.probe(key2), Some((2, 20)));
178
179        // key1 is now evicted (same slot, different key)
180        assert_eq!(cache.probe(key1), None);
181    }
182}
shape_vm/megamorphic_cache.rs

shape_vm/
megamorphic_cache.rs
