Render: evict the least recently used animation instead of clearing the GIF cache

crates/render/src/images.rs

@@ -37,7 +37,8 @@ struct Cache {
     bad_order: VecDeque<usize>,
     bad_bytes: usize,
     /// GIFs by bytes address and adjustments (`None`: not animated); the bytes stay alive with them.
-    anims: HashMap<(usize, u64), (Arc<Vec<u8>>, Option<Arc<Anim>>)>,
+    /// Decoded animations by (bytes, adjustments), each with the clock of its last use.
+    anims: HashMap<(usize, u64), (Arc<Vec<u8>>, Option<Arc<Anim>>, u64)>,
 }
 
 /// Longest side, total decoded size and frame count kept for one animated GIF; the largest canvas
@@ -432,16 +433,33 @@ fn anim(bytes: &Arc<Vec<u8>>, adj: &PictureAdjust) -> Option<Arc<Anim>> {
         return None;
     }
     let key = (Arc::as_ptr(bytes) as usize, adjust_key(adj));
-    if let Some(a) = with(|c| c.anims.get(&key).map(|e| e.1.clone())) {
+    let hit = with(|c| {
+        c.clock += 1;
+        let clock = c.clock;
+        c.anims.get_mut(&key).map(|e| {
+            e.2 = clock;
+            e.1.clone()
+        })
+    });
+    if let Some(a) = hit {
         return a;
     }
     let a = decode_anim(bytes, adj).map(Arc::new);
     with(|c| {
-        let held: usize = c.anims.values().filter_map(|e| e.1.as_ref()).map(|a| a.bytes()).sum();
-        if held + a.as_ref().map_or(0, |a| a.bytes()) > GIF_CACHE_BUDGET || c.anims.len() >= 64 {
-            c.anims.clear();
+        // Make room by dropping the least recently used animations, not every one of them, so a
+        // slide whose animations overflow the cache does not decode all of them again each frame.
+        let new = a.as_ref().map_or(0, |a| a.bytes());
+        loop {
+            let held: usize = c.anims.values().filter_map(|e| e.1.as_ref()).map(|a| a.bytes()).sum();
+            if held + new <= GIF_CACHE_BUDGET && c.anims.len() < 64 {
+                break;
+            }
+            let Some(oldest) = c.anims.iter().min_by_key(|(_, e)| e.2).map(|(k, _)| *k) else { break };
+            c.anims.remove(&oldest);
         }
-        c.anims.insert(key, (bytes.clone(), a.clone()));
+        c.clock += 1;
+        let clock = c.clock;
+        c.anims.insert(key, (bytes.clone(), a.clone(), clock));
     });
     a
 }
@@ -535,6 +553,26 @@ mod tests {
         out.into_inner()
     }
 
+    /// A two-frame GIF whose first pixel is `n`, so each one has its own bytes.
+    fn gif(n: u8) -> Arc<Vec<u8>> {
+        use image::codecs::gif::GifEncoder;
+        let frame = |c: u8| image::Frame::new(image::RgbaImage::from_pixel(2, 2, image::Rgba([n, c, 0, 255])));
+        let mut out = Vec::new();
+        GifEncoder::new(&mut out).encode_frames([frame(0), frame(255)]).expect("encode");
+        Arc::new(out)
+    }
+
+    #[test]
+    fn a_full_animation_cache_drops_the_oldest_entry_not_all_of_them() {
+        let adj = PictureAdjust::default();
+        let gifs: Vec<_> = (0..70).map(gif).collect();
+        for g in &gifs {
+            assert!(anim(g, &adj).is_some());
+        }
+        let (len, newest) = with(|c| (c.anims.len(), c.anims.contains_key(&(Arc::as_ptr(&gifs[69]) as usize, adjust_key(&adj)))));
+        assert!(newest && len >= 32, "{len} cached");
+    }
+
     #[test]
     fn rgba_conversion_is_refused_past_the_cap() {
         let png = grey_png(100, 50);