cranpose_render_common/
bounded_lru_cache.rs

1use std::{hash::Hash, num::NonZeroUsize};
2
3use cranpose_core::collections::map::HashMap;
4
5struct CacheSlot<K, V> {
6    key: K,
7    value: V,
8    newer: Option<usize>,
9    older: Option<usize>,
10}
11
12/// Small bounded LRU cache used by renderer hot-path caches.
13///
14/// Hits update recency in place, so the common path is a single hash lookup.
15/// Eviction unlinks the oldest entry, which costs the same whether the cache
16/// holds ten entries or ten thousand.
17///
18/// The recency order is a linked list rather than a timestamp per entry
19/// because a timestamp makes eviction a scan for the minimum. These caches are
20/// large -- thousands of glyph masks -- and the workloads that need them most
21/// are the ones that miss steadily: text whose size animates re-rasterises
22/// every glyph of every frame, and every one of those inserts was walking the
23/// whole table to decide what to drop.
24///
25/// A key is held twice, once in the index and once in its slot, so an eviction
26/// can find the index entry to remove without searching for it. The keys these
27/// caches use are small `Copy` structs, and the duplicate is what keeps the
28/// links free of raw pointers.
29pub struct BoundedLruCache<K, V> {
30    index: HashMap<K, usize>,
31    slots: Vec<Option<CacheSlot<K, V>>>,
32    free: Vec<usize>,
33    newest: Option<usize>,
34    oldest: Option<usize>,
35    cap: NonZeroUsize,
36}
37
38impl<K, V> BoundedLruCache<K, V>
39where
40    K: Clone + Eq + Hash,
41{
42    pub fn new(cap: NonZeroUsize) -> Self {
43        Self {
44            index: HashMap::with_capacity(cap.get()),
45            slots: Vec::with_capacity(cap.get()),
46            free: Vec::new(),
47            newest: None,
48            oldest: None,
49            cap,
50        }
51    }
52
53    pub fn with_capacity_at_least_one(cap: usize) -> Self {
54        let cap = NonZeroUsize::new(cap).unwrap_or(NonZeroUsize::MIN);
55        Self::new(cap)
56    }
57
58    pub fn len(&self) -> usize {
59        self.index.len()
60    }
61
62    pub fn is_empty(&self) -> bool {
63        self.index.is_empty()
64    }
65
66    pub fn cap(&self) -> NonZeroUsize {
67        self.cap
68    }
69
70    pub fn contains(&self, key: &K) -> bool {
71        self.index.contains_key(key)
72    }
73
74    pub fn get(&mut self, key: &K) -> Option<&V> {
75        let slot = *self.index.get(key)?;
76        self.promote(slot);
77        Some(&self.slot(slot).value)
78    }
79
80    pub fn peek(&self, key: &K) -> Option<&V> {
81        let slot = *self.index.get(key)?;
82        Some(&self.slot(slot).value)
83    }
84
85    pub fn get_mut(&mut self, key: &K) -> Option<&mut V> {
86        let slot = *self.index.get(key)?;
87        self.promote(slot);
88        Some(&mut self.slot_mut(slot).value)
89    }
90
91    pub fn push(&mut self, key: K, value: V) -> Option<(K, V)> {
92        if let Some(&slot) = self.index.get(&key) {
93            self.promote(slot);
94            let old_value = std::mem::replace(&mut self.slot_mut(slot).value, value);
95            return Some((key, old_value));
96        }
97
98        let evicted = if self.index.len() == self.cap.get() {
99            self.pop_lru()
100        } else {
101            None
102        };
103
104        let slot = self.claim_slot(key.clone(), value);
105        self.index.insert(key, slot);
106        self.link_newest(slot);
107        evicted
108    }
109
110    pub fn put(&mut self, key: K, value: V) -> Option<V> {
111        self.push(key, value).map(|(_, value)| value)
112    }
113
114    pub fn pop_lru(&mut self) -> Option<(K, V)> {
115        let slot = self.oldest?;
116        self.unlink(slot);
117        let entry = self.release_slot(slot);
118        self.index.remove(&entry.key);
119        Some((entry.key, entry.value))
120    }
121
122    pub fn pop(&mut self, key: &K) -> Option<V> {
123        let slot = self.index.remove(key)?;
124        self.unlink(slot);
125        Some(self.release_slot(slot).value)
126    }
127
128    /// Entries most recently used first.
129    pub fn iter(&self) -> impl Iterator<Item = (&K, &V)> {
130        let mut next = self.newest;
131        std::iter::from_fn(move || {
132            let entry = self.slot(next?);
133            next = entry.older;
134            Some((&entry.key, &entry.value))
135        })
136    }
137
138    fn slot(&self, slot: usize) -> &CacheSlot<K, V> {
139        self.slots[slot]
140            .as_ref()
141            .expect("a linked cache slot is always occupied")
142    }
143
144    fn slot_mut(&mut self, slot: usize) -> &mut CacheSlot<K, V> {
145        self.slots[slot]
146            .as_mut()
147            .expect("a linked cache slot is always occupied")
148    }
149
150    fn promote(&mut self, slot: usize) {
151        if self.newest == Some(slot) {
152            return;
153        }
154        self.unlink(slot);
155        self.link_newest(slot);
156    }
157
158    fn link_newest(&mut self, slot: usize) {
159        let previous_newest = self.newest;
160        {
161            let entry = self.slot_mut(slot);
162            entry.newer = None;
163            entry.older = previous_newest;
164        }
165        if let Some(previous) = previous_newest {
166            self.slot_mut(previous).newer = Some(slot);
167        }
168        self.newest = Some(slot);
169        if self.oldest.is_none() {
170            self.oldest = Some(slot);
171        }
172    }
173
174    fn unlink(&mut self, slot: usize) {
175        let (newer, older) = {
176            let entry = self.slot_mut(slot);
177            (entry.newer.take(), entry.older.take())
178        };
179        match newer {
180            Some(newer) => self.slot_mut(newer).older = older,
181            None => self.newest = older,
182        }
183        match older {
184            Some(older) => self.slot_mut(older).newer = newer,
185            None => self.oldest = newer,
186        }
187    }
188
189    fn claim_slot(&mut self, key: K, value: V) -> usize {
190        let entry = CacheSlot {
191            key,
192            value,
193            newer: None,
194            older: None,
195        };
196        match self.free.pop() {
197            Some(slot) => {
198                self.slots[slot] = Some(entry);
199                slot
200            }
201            None => {
202                self.slots.push(Some(entry));
203                self.slots.len() - 1
204            }
205        }
206    }
207
208    fn release_slot(&mut self, slot: usize) -> CacheSlot<K, V> {
209        let entry = self.slots[slot]
210            .take()
211            .expect("a slot being released is always occupied");
212        self.free.push(slot);
213        entry
214    }
215}
216
217#[cfg(test)]
218mod tests {
219    use super::BoundedLruCache;
220
221    fn cache<K, V>(cap: usize) -> BoundedLruCache<K, V>
222    where
223        K: Clone + Eq + std::hash::Hash,
224    {
225        BoundedLruCache::with_capacity_at_least_one(cap)
226    }
227
228    #[test]
229    fn clamped_constructor_uses_minimum_nonzero_capacity() {
230        let mut cache = BoundedLruCache::with_capacity_at_least_one(0);
231        assert_eq!(cache.cap().get(), 1);
232        assert_eq!(cache.push("a", 1), None);
233        assert_eq!(cache.push("b", 2), Some(("a", 1)));
234        assert_eq!(cache.get(&"b"), Some(&2));
235    }
236
237    #[test]
238    fn get_promotes_entry_and_push_evicts_lru() {
239        let mut cache = cache(2);
240        assert_eq!(cache.push("a", 1), None);
241        assert_eq!(cache.push("b", 2), None);
242
243        assert_eq!(cache.get(&"a"), Some(&1));
244        assert_eq!(cache.push("c", 3), Some(("b", 2)));
245
246        assert!(cache.contains(&"a"));
247        assert!(cache.contains(&"c"));
248        assert!(!cache.contains(&"b"));
249    }
250
251    #[test]
252    fn push_existing_replaces_value_and_keeps_capacity() {
253        let mut cache = cache(2);
254        cache.push("a", 1);
255        cache.push("b", 2);
256
257        assert_eq!(cache.push("a", 3), Some(("a", 1)));
258        assert_eq!(cache.len(), 2);
259        assert_eq!(cache.get(&"a"), Some(&3));
260    }
261
262    #[test]
263    fn pop_removes_requested_entry_and_preserves_lru_order() {
264        let mut cache = cache(3);
265        cache.push("a", 1);
266        cache.push("b", 2);
267        cache.push("c", 3);
268
269        assert_eq!(cache.pop(&"b"), Some(2));
270        assert_eq!(cache.get(&"a"), Some(&1));
271        assert_eq!(cache.pop_lru(), Some(("c", 3)));
272        assert_eq!(cache.len(), 1);
273    }
274
275    #[test]
276    fn a_full_cache_that_only_misses_keeps_evicting_in_order() {
277        let mut cache = cache(4);
278        for step in 0..4 {
279            assert_eq!(cache.push(step, step * 10), None);
280        }
281
282        for step in 4..64 {
283            let evicted = cache.push(step, step * 10);
284            assert_eq!(
285                evicted,
286                Some((step - 4, (step - 4) * 10)),
287                "insert {step} must evict the oldest entry"
288            );
289            assert_eq!(cache.len(), 4);
290        }
291
292        let live: Vec<_> = cache.iter().map(|(key, value)| (*key, *value)).collect();
293        assert_eq!(live, vec![(63, 630), (62, 620), (61, 610), (60, 600)]);
294    }
295
296    #[test]
297    fn reused_slots_do_not_resurrect_the_entries_that_vacated_them() {
298        let mut cache = cache(3);
299        cache.push("a", 1);
300        cache.push("b", 2);
301        cache.push("c", 3);
302
303        assert_eq!(cache.pop(&"b"), Some(2));
304        assert_eq!(cache.push("d", 4), None);
305
306        assert!(!cache.contains(&"b"));
307        assert_eq!(cache.peek(&"d"), Some(&4));
308        assert_eq!(cache.len(), 3);
309        assert_eq!(cache.pop_lru(), Some(("a", 1)));
310        assert_eq!(cache.pop_lru(), Some(("c", 3)));
311        assert_eq!(cache.pop_lru(), Some(("d", 4)));
312        assert_eq!(cache.pop_lru(), None);
313        assert!(cache.is_empty());
314    }
315
316    #[test]
317    fn a_promoted_entry_survives_the_next_eviction() {
318        let mut cache = cache(3);
319        cache.push("a", 1);
320        cache.push("b", 2);
321        cache.push("c", 3);
322
323        assert_eq!(cache.get(&"a"), Some(&1));
324        assert_eq!(cache.get_mut(&"b").map(|value| *value), Some(2));
325
326        assert_eq!(cache.push("d", 4), Some(("c", 3)));
327        assert!(cache.contains(&"a"));
328        assert!(cache.contains(&"b"));
329    }
330
331    #[test]
332    fn peek_reads_without_promoting_entry() {
333        let mut cache = cache(2);
334        cache.push("a", 1);
335        cache.push("b", 2);
336
337        assert_eq!(cache.peek(&"a"), Some(&1));
338        assert_eq!(cache.push("c", 3), Some(("a", 1)));
339    }
340
341    #[test]
342    fn iter_reports_mru_to_lru_entries() {
343        let mut cache = cache(3);
344        cache.push("a", 1);
345        cache.push("b", 2);
346        cache.get(&"a");
347
348        let entries: Vec<_> = cache.iter().map(|(key, value)| (*key, *value)).collect();
349        assert_eq!(entries, vec![("a", 1), ("b", 2)]);
350    }
351}
cranpose_render_common/bounded_lru_cache.rs

cranpose_render_common/
bounded_lru_cache.rs
