An LRU cache

A cache keeps a limited number of recent results close at hand, so a program does not have to compute or fetch them again. A web browser caches images. A database caches disk pages in memory. A CPU caches memory in small, fast storage next to its cores, which chapter 15 looks at.

A cache has a fixed size. When it is full and a new entry arrives, it must remove, or evict, an old entry. The rule for choosing which entry to evict is the cache’s eviction policy.

This chapter builds a cache with the least recently used (LRU) policy: evict the entry that has gone longest without being used. The idea is that an entry used recently is likely to be used again soon.

You have already built both parts of an LRU cache. Chapter 3 covered HashMap, and chapters 8 and 9 covered linked lists and Rc. This chapter combines them, four ways, and then measures two of them.

13.1 What an LRU cache does

An LRU cache has two operations:

• get(key) returns the value for key, or nothing if the key is not cached. A successful get counts as a use, so the key becomes the most recently used.
• put(key, value) stores the value. The key becomes the most recently used. If the cache was full and the key is new, the least recently used entry is evicted.

Figure 13.1 follows five calls on a cache with room for two entries.

The third call changes the outcome. Without get(A), A would be the least recent entry, and put(C, 3) would evict A. Because get(A) counted as a use, B is evicted instead.

13.1.1 What a cache saves

A cache pays off when a hit is much cheaper than the work it replaces. Suppose a lookup in the cache takes 100 ns, and a miss means a database query that takes 1 ms, ten thousand times longer. The average cost of a request is then set almost entirely by the misses:

Going from 90% to 99% makes the average ten times smaller. The hit rate depends on what stays in the cache, and the eviction policy decides that.

Here is a longer trace. The cache holds three entries, and eight requests arrive: A, B, A, C, A, D, A, B. A request for a cached key is a hit; any other request is a miss, which fetches the value and stores it. The table follows the LRU rule, and a simpler rule for comparison. FIFO, first in, first out, evicts the entry that arrived earliest, and ignores use. The order is shown most recent first.

LRU scores 3 hits, and FIFO 2. A is used most, and LRU never evicts it: every use moves it back to the front. FIFO evicts A at the sixth request because A arrived first, and the very next request misses on A.

Animation 13.1 plays the same trace, with a robot for the cache and one for the slow store behind it.

LRU works when the recent past predicts the near future, which holds for most workloads. One pattern breaks it: a scan that reads many keys once each. Every key in the scan becomes the most recent, and the scan pushes out the entries that were in steady use. Databases defend against this with variants that admit a key fully only on its second use.

A cache needs to answer two questions fast:

1. Is this key cached, and what is its value? A HashMap answers that in O(1).
2. Which entry is the least recently used? This needs an order that changes on every call.

Keeping the order in a Vec would be slow. Moving an entry from the middle to the front shifts every element between, which is O(n). The four versions in this chapter keep the order in structures where each step is O(1).

13.2 Version 1: stamped events in a queue

The first version avoids a linked list entirely. Its idea is to record each use as an event, and to sort out which events still count only when something must be evicted.

The cache has a counter called generation that goes up by one on every call. Each call stamps the key with the current generation in two places (figure 13.2):

• The map stores each key’s value and its latest stamp: HashMap<K, (V, u64)>.
• A queue, recency, receives a (key, stamp) event at the back on every use.

The queue is in the order of use, oldest at the front. A key used several times has several events in it. Only the event whose stamp matches the map is current. The others are stale, the same idea as the stale heap entries of Dijkstra’s algorithm in section 12.9.

To evict, the cache pops events from the front. It skips stale events, and removes the key of the first current event. That key is the least recently used one.

Listing 13.1 The type (lines 10 to 24). src/problems/lru_cache.rs

use std::{
    collections::{HashMap, VecDeque},
    hash::Hash,
};

pub struct LruCache<K, V>
where
    K: Eq + Hash + Clone,
    V: Clone,
{
    capacity: usize,
    map: HashMap<K, (V, u64)>,
    recency: VecDeque<(K, u64)>,
    generation: u64,
}

The key must be Clone, because a copy of it goes into the queue with every event. The value must be Clone, because get returns a copy of it.

Listing 13.2 get and put (lines 49 to 71).

impl<K, V> LruCache<K, V>
where
    K: Eq + Hash + Clone,
    V: Clone,
{
    // ...
    pub fn get(&mut self, key: &K) -> Option<V> {
        let (value, _) = self.map.get(key)?.clone();
        self.generation += 1;
        self.recency
            .push_back((key.clone(), self.generation));
        self.map
            .insert(key.clone(), (value.clone(), self.generation));
        Some(value)
    }

    pub fn put(&mut self, key: K, value: V) {
        self.generation += 1;
        let is_new = self
            .map
            .insert(key.clone(), (value, self.generation))
            .is_none();
        self.recency
            .push_back((key, self.generation));

        if is_new {
            self.evict_if_needed();
        }
    }
    // ...
}

get looks up the key and returns early with None if it is missing: self.map.get(key)?. Then it advances the generation, records an event, and stores the value again with the new stamp.

put stores the value with a new stamp, and records an event. HashMap::insert returns the old value if the key was already present, or None if it was new. Only a new key can make the map too large, so only a new key triggers eviction.

Listing 13.3 Eviction (lines 73 to 87).

impl<K, V> LruCache<K, V>
where
    K: Eq + Hash + Clone,
    V: Clone,
{
    // ...
    fn evict_if_needed(&mut self) {
        while self.map.len() > self.capacity {
            let Some((key, generation)) = self.recency.pop_front() else {
                break;
            };

            match self.map.get(&key) {
                Some((_, current)) if *current == generation => {
                    self.map.remove(&key);
                    break;
                }
                _ => {}
            }
        }
    }
}

The loop runs while the map holds more keys than the capacity. Each pass pops the oldest event. The match guard Some((_, current)) if *current == generation accepts the event only if its stamp matches the key’s stamp in the map. A match removes the key and ends the loop. A stale event matches the _ arm and is dropped.

Each event is pushed once and popped at most once. So the total work over many calls is proportional to the number of calls, and each call costs O(1) on average. A cost measured this way, averaged over a sequence of calls, is called amortized.

Animation 13.2 runs the four calls of figure 13.2 with a capacity of 2, then a run of hits.

13.3 Version 2: a linked list inside a Vec

The classic LRU design keeps the entries in a doubly linked list, ordered from most to least recently used. A doubly linked list can move an entry to the front in O(1). Removing the last entry and adding one at the front are O(1) too. The map stores, for each key, where that key’s node is.

Chapter 9 showed that a doubly linked list of Rc<RefCell<_>> nodes is awkward in Rust. Each node is owned jointly, every change goes through runtime borrow checks, and the back links must be Weak to avoid leaks.

This version uses a different approach. All nodes live in one Vec, and a link is the index of another node in that Vec. A Vec used as a pool of nodes this way is called an arena. Figure 13.3 shows one.

An index is a plain usize. The borrow checker does not track it, so a node can be “pointed to” by several other nodes with no Rc and no RefCell. The cost is that the compiler cannot catch a wrong index. The code must keep the links correct by itself.

Listing 13.4 The node and the cache (lines 20 to 45). src/problems/lru_cache_easy.rs

use std::{collections::HashMap, hash::Hash};

/// A single cache entry, linked into the recency list by index.
struct Node<K, V> {
    /// Retained so we can delete the corresponding map entry when evicting.
    key: K,
    value: V,
    /// Neighbour closer to the MRU end (or `None` if this is `head`).
    prev: Option<usize>,
    /// Neighbour closer to the LRU end (or `None` if this is `tail`).
    next: Option<usize>,
}

/// Fixed-capacity LRU cache.
pub struct LruCache<K, V> {
    /// Maximum number of entries; `>= 1` (enforced by `new`).
    cap: usize,
    /// Key → arena index. The single source of truth for "is this key cached?".
    lookup_table: HashMap<K, usize>,
    /// Arena of nodes; indices are the "pointers" of the linked list.
    nodes: Vec<Node<K, V>>,
    /// Arena index of the most recently used entry.
    head: Option<usize>,
    /// Arena index of the least recently used entry (next to be evicted).
    tail: Option<usize>,
}

Each node stores its key as well as its value. When a node is evicted, the cache reads the key from the node to remove the key from lookup_table.

prev and next are Option<usize>, where None means “no neighbor on that side”. head is the index of the most recently used node, and tail is the index of the least recently used one.

13.3.1 Moving a node to the front

Every get and put ends by moving one node to the front of the list. The method touch does it in two steps (figure 13.4):

1. Detach the node: make its two neighbors point at each other, so the list skips it.
2. Push it to the front: make it point at the old head, and make it the new head.

Animation 13.3 runs touch on a list of four entries. The Vec sits underneath and never moves. Only the links above it change. Watch the arrows: when C is lifted out, A’s next swings over to D.

Listing 13.5 new and touch (lines 51 to 101).

impl<K, V> LruCache<K, V>
where
    K: Hash + Eq + Clone,
{
    /// Create a cache holding at most `cap` entries.
    ///
    /// # Panics
    /// Panics if `cap == 0`, since a zero-capacity cache cannot store anything.
    pub fn new(cap: usize) -> Self {
        assert!(cap > 0, "capacity must be > 0");
        Self {
            cap,
            lookup_table: HashMap::new(),
            nodes: Vec::new(),
            head: None,
            tail: None,
        }
    }

    /// Promote node `i` to `head` (MRU).
    ///
    /// Handles both cases in one pass:
    /// * **Already linked** — detach from its current neighbours first.
    /// * **Brand new** — the node has `prev = next = None` and is not yet
    ///   referenced by `head`/`tail`, so the detach step is skipped.
    fn touch(&mut self, i: usize) {
        let (prev, next) = (self.nodes[i].prev, self.nodes[i].next);

        // A node is "linked" if any of its four references exist.
        let linked =
            prev.is_some() || next.is_some() || self.head == Some(i) || self.tail == Some(i);

        if linked {
            // Splice `i` out of the list.
            match prev {
                Some(p) => self.nodes[p].next = next,
                None => self.head = next,
            }
            match next {
                Some(n) => self.nodes[n].prev = prev,
                None => self.tail = prev,
            }
        }

        // Splice `i` in at the front.
        self.nodes[i].prev = None;
        self.nodes[i].next = self.head;
        if let Some(h) = self.head {
            self.nodes[h].prev = Some(i);
        }
        self.head = Some(i);
        if self.tail.is_none() {
            self.tail = Some(i);
        }
    }
    // ...
}

touch first copies the node’s prev and next into local variables. Option<usize> is Copy, so this reads the values without keeping a borrow of self.nodes.

A brand-new node is not in the list yet, so there is nothing to detach. touch tells the two cases apart with linked. A node is in the list if it has a neighbor, or if it is the head or the tail. A list with one node has no neighbors, so the head and tail checks are needed for that case.

The detach step handles the ends of the list. If the node has no prev, it was the head, so the head moves to its next. If it has no next, it was the tail, so the tail moves to its prev.

The push step sets the node’s links, points the old head back at it, and makes it the head. If the list was empty, the node is also the tail.

13.3.2 get and put

Listing 13.6 get and put (lines 103 to 147).

impl<K, V> LruCache<K, V>
where
    K: Hash + Eq + Clone,
{
    // ...
    /// Look up `key`, promoting it to MRU on a hit.
    ///
    /// Returns `None` if the key is not cached.
    pub fn get(&mut self, key: &K) -> Option<&V> {
        let i = *self.lookup_table.get(key)?;
        self.touch(i);
        Some(&self.nodes[i].value)
    }

    /// Insert or update `key`. Promotes it to MRU. Evicts the LRU entry if
    /// the cache is full.
    pub fn put(&mut self, key: K, value: V) {
        // Case 1: key already present → update value, promote.
        if let Some(&i) = self.lookup_table.get(&key) {
            self.nodes[i].value = value;
            self.touch(i);
            return;
        }

        // Case 2: room to grow → append a fresh node.
        if self.nodes.len() < self.cap {
            let i = self.nodes.len();
            self.nodes.push(Node {
                key: key.clone(),
                value,
                prev: None,
                next: None,
            });
            self.lookup_table.insert(key, i);
            self.touch(i);
            return;
        }

        // Case 3: at capacity → reuse the LRU slot.
        // `tail` is guaranteed to be `Some` here because `cap >= 1` and the
        // arena is full, but we still handle `None` gracefully.
        if let Some(i) = self.tail {
            let old_key = std::mem::replace(&mut self.nodes[i].key, key);
            self.nodes[i].value = value;
            self.lookup_table.remove(&old_key);
            self.lookup_table
                .insert(self.nodes[i].key.clone(), i);
            self.touch(i);
        }
    }
}

get finds the index, touches the node, and returns a reference to the value. The return type Option<&V> borrows from the cache. Because get takes &mut self, the cache stays mutably borrowed while you hold that reference.

put has three cases:

1. The key is present. Replace the value and touch the node.
2. There is room. Push a new node onto the end of the Vec, record its index, and touch it.
3. The cache is full. Reuse the tail node’s slot for the new entry.

The third case is the arena’s advantage. Eviction does not free anything, and insertion does not allocate. The tail slot receives the new key and value, and touch moves it to the front.

std::mem::replace(&mut self.nodes[i].key, key) puts the new key into the node and returns the old key, in one step. The old key is then removed from lookup_table. The new key was moved into the node, so the map receives a clone of it.

Animation 13.4 plays the three cases in order. It fills the cache, updates an entry, and then evicts the tail by reusing its slot. The last run leaves out the remove of the old key.

The file src/bin/lru_cache_arena.rs has the same cache with a main function:

Listing 13.7 The main function (lines 150 to 165). src/bin/lru_cache_arena.rs

use std::{collections::HashMap, hash::Hash};

fn main() {
    let mut cache = LruCache::new(2);

    cache.put("A", 10);
    cache.put("B", 20);
    println!("get A = {:?}", cache.get(&"A")); // Some(10), A now MRU

    cache.put("C", 30); // evicts B (LRU)

    println!("get B = {:?}", cache.get(&"B")); // None
    println!("get A = {:?}", cache.get(&"A")); // Some(10)
    println!("get C = {:?}", cache.get(&"C")); // Some(30)

    cache.put("A", 99);
    println!("get A = {:?}", cache.get(&"A")); // Some(99)
}

$ cargo run --bin lru_cache_arena
get A = Some(10)
get B = None
get A = Some(10)
get C = Some(30)
get A = Some(99)

13.4 Version 3: one operation per method

touch in version 2 does two jobs, and must first work out which situation it is in. Version 3 splits it into three methods, each with a stated precondition. A precondition is something that must be true when a function is called. The compiler cannot check these preconditions, so the doc comments state them.

This version also fixes the key and value types to i32. i32 is Copy, so the code never clones a key.

Listing 13.8 The link operations (lines 63 to 94). src/bin/lru_cache_modular.rs

use std::collections::HashMap;

impl LruCache {
    // ...
    /// Unlink node `i` from the list. `i` must currently be linked.
    fn detach(&mut self, i: usize) {
        let (prev, next) = (self.nodes[i].prev, self.nodes[i].next);
        match prev {
            Some(p) => self.nodes[p].next = next,
            None => self.head = next,
        }
        match next {
            Some(n) => self.nodes[n].prev = prev,
            None => self.tail = prev,
        }
    }

    /// Link node `i` in at the MRU end. `i` must currently be unlinked.
    fn push_front(&mut self, i: usize) {
        self.nodes[i].prev = None;
        self.nodes[i].next = self.head;
        match self.head {
            Some(h) => self.nodes[h].prev = Some(i),
            None => self.tail = Some(i), // list was empty
        }
        self.head = Some(i);
    }

    /// Promote an already-linked node to MRU.
    fn promote_to_front(&mut self, i: usize) {
        if self.head == Some(i) {
            return; // already MRU
        }
        self.detach(i);
        self.push_front(i);
    }
    // ...
}

• detach unlinks a node. Its precondition is that the node is in the list.
• push_front links a node at the head. Its precondition is that the node is not in the list.
• promote_to_front combines them for a node that is in the list. If the node is already the head, it does nothing.

Each method now does one thing, with no linked check. put calls push_front for a new node and promote_to_front for an existing one, so each call satisfies its precondition.

$ cargo run --bin lru_cache_modular
get 1 = Some(10)
get 2 = None
get 1 = Some(10)
get 3 = Some(30)
get 1 = Some(99)

13.5 Version 4: measuring the arena against Rc<RefCell<_>>

Is the arena faster than a list of Rc<RefCell<_>> nodes, and by how much? The only reliable answer is to measure. This section builds both caches behind one trait, and runs the same requests through each.

13.5.1 One trait, two caches

Listing 13.9 The trait. benchmarking_examples/cache/mod.rs

//! Two LRU caches of the same design, stored differently, so one benchmark loop
//! can cover both.
//!
//! [`arena`] keeps nodes in a `Vec` and links them by `usize` index.
//! [`rc_list`] allocates an `Rc<RefCell<_>>` per node and links them by pointer.

pub mod arena;
pub mod rc_list;

use std::hash::Hash;

/// The operations every cache supports.
pub trait Cache<K, V>
where
    K: Hash + Eq + Clone,
    V: Copy,
{
    /// A cache that holds at most `capacity` entries.
    ///
    /// # Panics
    /// Panics if `capacity == 0`, since a zero-capacity cache cannot store
    /// anything.
    fn new(capacity: usize) -> Self;

    /// Looks up `key`, promoting it to most recently used on a hit.
    fn get(&mut self, key: &K) -> Option<V>;

    /// Inserts or updates `key`, evicting the least recently used entry when
    /// the cache is full.
    fn put(&mut self, key: K, value: V);

    /// How many entries are cached.
    fn len(&self) -> usize;

    /// Whether the cache holds no entries.
    fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// The variant's name, for benchmark output.
    fn variant() -> &'static str;
}

The trait Cache<K, V> lists what the benchmark needs. new is part of the trait, so generic code can create a cache with C::new(capacity) without knowing which type C is. variant has no self parameter. It is called on the type, and gives each cache a name for the output.

V: Copy lets get return the value itself, Option<V>, instead of a reference. The benchmark stores u64 values, which are Copy.

The arena cache is version 2, split into two impl blocks. touch stays in an ordinary impl, because it is not part of the trait. The trait methods go in impl<K, V> Cache<K, V> for LruCache<K, V>, and their bodies are the get and put of section 13.3.2:

Listing 13.10 The arena cache's trait methods (lines 91 to 154). benchmarking_examples/cache/arena.rs

impl<K, V> Cache<K, V> for LruCache<K, V>
where
    K: Hash + Eq + Clone,
    V: Copy,
{
    fn new(capacity: usize) -> Self {
        assert!(capacity > 0, "capacity must be > 0");
        Self {
            cap: capacity,
            lookup_table: HashMap::new(),
            nodes: Vec::new(),
            head: None,
            tail: None,
        }
    }

    fn get(&mut self, key: &K) -> Option<V> {
        let i = *self.lookup_table.get(key)?;
        self.touch(i);
        Some(self.nodes[i].value)
    }

    fn put(&mut self, key: K, value: V) {
        // Case 1: key already present, update the value and promote.
        if let Some(&i) = self.lookup_table.get(&key) {
            self.nodes[i].value = value;
            self.touch(i);
            return;
        }

        // Case 2: room to grow, append a fresh node.
        if self.nodes.len() < self.cap {
            let i = self.nodes.len();
            self.nodes.push(Node {
                key: key.clone(),
                value,
                prev: None,
                next: None,
            });
            self.lookup_table.insert(key, i);
            self.touch(i);
            return;
        }

        // Case 3: at capacity, reuse the LRU slot. `tail` is `Some` here because
        // `cap >= 1` and the arena is full, but handle `None` anyway.
        if let Some(i) = self.tail {
            let old_key = std::mem::replace(&mut self.nodes[i].key, key);
            self.nodes[i].value = value;
            self.lookup_table.remove(&old_key);
            self.lookup_table
                .insert(self.nodes[i].key.clone(), i);
            self.touch(i);
        }
    }

    fn len(&self) -> usize {
        self.lookup_table.len()
    }

    fn variant() -> &'static str {
        "arena (Vec + indices)"
    }
}

Listing 13.20, at the end of the chapter, has the whole file.

13.5.2 The Rc<RefCell<_>> list

Listing 13.11 The node and the cache (lines 10 to 33). benchmarking_examples/cache/rc_list.rs

use std::{
    cell::RefCell,
    collections::HashMap,
    hash::Hash,
    rc::{Rc, Weak},
};

use super::Cache;

type Link<K, V> = Option<Rc<RefCell<Node<K, V>>>>;

struct Node<K, V> {
    key: K,
    value: V,
    prev: Weak<RefCell<Node<K, V>>>,
    next: Link<K, V>,
}

pub struct LruCache<K, V> {
    cap: usize,
    map: HashMap<K, Rc<RefCell<Node<K, V>>>>,
    head: Link<K, V>,
    tail: Link<K, V>,
}

This is the doubly linked list of chapter 9. A node is Rc<RefCell<Node>>: Rc so several owners can hold it, and RefCell so it can be changed through those shared handles. next is a strong link, and prev is a Weak link, so two neighbors do not keep each other alive forever. The map holds one more Rc to every node.

Listing 13.12 detach and push_front (lines 35 to 69).

impl<K, V> LruCache<K, V>
where
    K: Hash + Eq + Clone,
    V: Copy,
{
    fn detach(&mut self, node: &Rc<RefCell<Node<K, V>>>) {
        let (prev, next) = {
            let entry = node.borrow();
            (entry.prev.clone(), entry.next.clone())
        };

        match prev.upgrade() {
            Some(previous) => previous.borrow_mut().next = next.clone(),
            None => self.head = next.clone(),
        }
        match &next {
            Some(following) => following.borrow_mut().prev = prev,
            None => self.tail = prev.upgrade(),
        }
    }

    fn push_front(&mut self, node: Rc<RefCell<Node<K, V>>>) {
        let head = self.head.clone();
        {
            let mut entry = node.borrow_mut();
            entry.prev = Weak::new();
            entry.next = head.clone();
        }
        match &head {
            Some(previous) => previous.borrow_mut().prev = Rc::downgrade(&node),
            None => self.tail = Some(node.clone()),
        }
        self.head = Some(node);
    }
}

The logic matches listing 13.8, with pointers instead of indices. The difference is in the ceremony around each step:

• detach reads the node’s links inside a small block. node.borrow() returns a guard that holds a shared borrow of the RefCell. The block ends before any neighbor is changed, so the guard is dropped early. A RefCell panics if a borrow_mut happens while another borrow of the same cell is alive.
• prev.upgrade() turns the Weak link into an Rc, if the node still exists.
• Each .clone() of an Rc or a Weak increases a reference count, and each drop decreases one.

Listing 13.13 The trait methods and Drop (lines 71 to 139).

impl<K, V> Cache<K, V> for LruCache<K, V>
where
    K: Hash + Eq + Clone,
    V: Copy,
{
    fn new(capacity: usize) -> Self {
        assert!(capacity > 0, "capacity must be > 0");
        Self {
            cap: capacity,
            map: HashMap::new(),
            head: None,
            tail: None,
        }
    }

    fn get(&mut self, key: &K) -> Option<V> {
        let node = self.map.get(key)?.clone();
        self.detach(&node);
        self.push_front(node.clone());
        Some(node.borrow().value)
    }

    fn put(&mut self, key: K, value: V) {
        if let Some(node) = self.map.get(&key).cloned() {
            node.borrow_mut().value = value;
            self.detach(&node);
            self.push_front(node);
            return;
        }

        if self.map.len() >= self.cap
            && let Some(victim) = self.tail.clone()
        {
            let old_key = victim.borrow().key.clone();
            self.map.remove(&old_key);
            self.detach(&victim);
        }

        let node = Rc::new(RefCell::new(Node {
            key: key.clone(),
            value,
            prev: Weak::new(),
            next: None,
        }));
        self.map.insert(key, node.clone());
        self.push_front(node);
    }

    fn len(&self) -> usize {
        self.map.len()
    }

    fn variant() -> &'static str {
        "Rc<RefCell> list"
    }
}

impl<K, V> Drop for LruCache<K, V> {
    fn drop(&mut self) {
        // Unlink iteratively: dropping a million-node chain recursively overflows
        // the stack.
        let mut current = self.head.take();
        while let Some(node) = current {
            let next = node.borrow_mut().next.take();
            node.borrow_mut().prev = Weak::new();
            current = next;
        }
    }
}

On a miss with a full cache, put removes the tail node from the map and detaches it. When victim goes out of scope, the last Rc to that node is dropped, and its memory is freed. Then Rc::new allocates a new node for the new key. So every eviction frees one heap block and allocates another.

The Drop implementation is the fix from chapter 9. Dropping a long chain of next links recursively uses one stack frame per node, and a large cache would overflow the stack. The loop breaks the links one node at a time. The map drops its Rc handles afterward, and each drop then frees a single node.

Figure 13.5 compares where the two caches keep their nodes.

The arena’s node is 48 bytes: the key and value take 8 bytes each, and each Option<usize> takes 16. The Rc node is 32 bytes. The heap block around it adds a strong count, a weak count, and the RefCell flag, for 56 bytes. The memory sizes are close. What differs is the number of allocations and where the nodes sit in memory.

13.5.3 The benchmark

Listing 13.14 The request stream and the timed loop (lines 52 to 106). benchmarking_examples/benchmark.rs

use std::{
    hint::black_box,
    time::{Duration, Instant},
};

use systems_lab::{
    cache::{Cache, arena::LruCache as ArenaCache, rc_list::LruCache as RcCache},
    lists::{SinglyList, boxed, boxed_drop, enum_drop, enum_node},
};

// ---------------------------------------------------------------------------
// Cache: arena vs Rc<RefCell> linked list
// ---------------------------------------------------------------------------

/// Request stream with realistic locality: four requests in five come from a hot
/// set of 1% of the keys, the rest from the whole space.
fn key_at(state: u64) -> u64 {
    let mixed = state >> 17;
    if (state >> 33) % 100 < 80 {
        mixed % (KEY_SPACE / 100)
    } else {
        mixed % KEY_SPACE
    }
}

/// The fastest of `CACHE_RUNS` timed passes, with the hit count and final size
/// from the last one. Each pass starts from an empty cache, so the stream is the
/// same every time.
fn best_cache_run<C: Cache<u64, u64>>() -> (Duration, u64, usize) {
    let mut best = Duration::MAX;
    let mut hits = 0;
    let mut len = 0;

    for _ in 0..CACHE_RUNS {
        let mut cache = C::new(CACHE_CAPACITY);
        let (elapsed, run_hits) = cache_workload(&mut cache);
        best = best.min(elapsed);
        hits = run_hits;
        len = cache.len();
    }
    (best, hits, len)
}

/// The same request stream against any cache.
fn cache_workload<C: Cache<u64, u64>>(cache: &mut C) -> (Duration, u64) {
    let mut state = 0x9e37_79b9_7f4a_7c15u64;
    let mut hits = 0u64;

    let start = Instant::now();
    for _ in 0..OPERATIONS {
        state = state
            .wrapping_mul(6_364_136_223_846_793_005)
            .wrapping_add(1_442_695_040_888_963_407);
        let key = key_at(state);

        match cache.get(&key) {
            Some(value) => {
                hits += 1;
                black_box(value);
            }
            None => cache.put(key, key.rotate_left(17)),
        }
    }
    (start.elapsed(), hits)
}

A fair comparison needs both caches to see exactly the same requests. The program makes its own request stream from a number called state. Each step multiplies and adds two fixed constants, so the same starting state always produces the same sequence. A generator of this kind is called a linear congruential generator.

key_at shapes the stream to look like real traffic. Real caches see some keys far more often than others. Here, 80% of requests pick from a hot set of 1% of the keys, and the rest pick from all 131,072 keys. The capacity, 65,536, is half the key space.

Each request calls get. On a miss, it calls put, the way a program fills a cache after it computes a missing value. black_box tells the compiler to treat the value as used, so the optimizer cannot remove the work.

Listing 13.15 Running and checking both caches (lines 108 to 158).

fn cache_benchmark() {
    println!(
        "LRU cache: {} entries, {} requests over {} keys",
        with_thousands(CACHE_CAPACITY as u64),
        with_thousands(OPERATIONS),
        with_thousands(KEY_SPACE)
    );
    println!("A miss inserts and evicts the least recently used entry.");
    println!("Best of {CACHE_RUNS} runs per cache.\n");

    let (arena_time, arena_hits, arena_len) = best_cache_run::<ArenaCache<u64, u64>>();
    let (list_time, list_hits, list_len) = best_cache_run::<RcCache<u64, u64>>();

    // Same population and same hit count, or this compares nothing.
    assert_eq!(arena_len, list_len);
    assert_eq!(
        arena_hits, list_hits,
        "the two runs saw different request streams"
    );

    println!(
        "  hit rate: {:.1}%  ({} hits, {} inserts)\n",
        arena_hits as f64 * 100.0 / OPERATIONS as f64,
        with_thousands(arena_hits),
        with_thousands(OPERATIONS - arena_hits)
    );

    let per_request = |elapsed: Duration| elapsed.as_nanos() as f64 / OPERATIONS as f64;

    // `{:.2?}` uses Duration's own Debug format, rounded to two decimals.
    println!("  {:<22} {:>12} {:>13}", "storage", "total", "per request");
    println!("  {}", "-".repeat(48));
    for (name, elapsed) in [
        (
            <ArenaCache<u64, u64> as Cache<u64, u64>>::variant(),
            arena_time,
        ),
        (<RcCache<u64, u64> as Cache<u64, u64>>::variant(), list_time),
    ] {
        println!(
            "  {name:<22} {elapsed:>12.2?} {:>8.0} ns",
            per_request(elapsed)
        );
    }

    let speedup = list_time.as_secs_f64() / arena_time.as_secs_f64();
    println!(
        "\n  the arena is {speedup:.2}x faster on the same requests: {arena_time:.2?} against {list_time:.2?}"
    );
    println!("  the arena reuses the evicted slot; the list frees a node and allocates another");
}

best_cache_run::<ArenaCache<u64, u64>>() runs the generic function with the arena cache, and the next line runs it with the Rc cache. The ::<...> syntax, called the turbofish, names the type parameter explicitly.

Before printing any times, the function checks that both caches finished with the same size and the same number of hits. Two correct LRU caches given the same requests make the same decisions. If the counts differed, one cache would have a bug, and its time would mean nothing.

<ArenaCache<u64, u64> as Cache<u64, u64>>::variant() is the fully qualified way to call a trait function that has no self. It names both the type and the trait.

Listing 13.16 The complete benchmark program. benchmarking_examples/benchmark.rs

//! One main for every benchmark in the lab.
//!
//! Usage:
//!   cargo run --release --bin benchmark                    # cache, then lists
//!   cargo run --release --bin benchmark cache              # cache only
//!   cargo run --release --bin benchmark list               # all four variants
//!   cargo run --release --bin benchmark list enum 500000   # one variant, one size
//!
//! The recursive list variants abort with a stack overflow past roughly 265,000
//! nodes, so run them below that size or on their own.

use std::{
    hint::black_box,
    time::{Duration, Instant},
};

use systems_lab::{
    cache::{Cache, arena::LruCache as ArenaCache, rc_list::LruCache as RcCache},
    lists::{SinglyList, boxed, boxed_drop, enum_drop, enum_node},
};

const CACHE_CAPACITY: usize = 65_536;
const KEY_SPACE: u64 = 131_072;
const OPERATIONS: u64 = 10_000_000;
const DEFAULT_LIST_ELEMENTS: usize = 200_000;
/// Timed passes per cache; the fastest is reported, since a slow pass is noise.
const CACHE_RUNS: usize = 3;
/// Timed passes per list variant.
const LIST_RUNS: usize = 3;

fn main() {
    let arguments: Vec<String> = std::env::args().skip(1).collect();

    match arguments.first().map(String::as_str) {
        Some("cache") => cache_benchmark(),
        Some("list") => {
            let variant = arguments.get(1).map(String::as_str);
            let elements = arguments
                .get(2)
                .and_then(|value| value.parse().ok())
                .unwrap_or(DEFAULT_LIST_ELEMENTS);
            list_benchmark(variant, elements);
        }
        _ => {
            cache_benchmark();
            println!();
            list_benchmark(None, DEFAULT_LIST_ELEMENTS);
        }
    }
}

// ---------------------------------------------------------------------------
// Cache: arena vs Rc<RefCell> linked list
// ---------------------------------------------------------------------------

/// Request stream with realistic locality: four requests in five come from a hot
/// set of 1% of the keys, the rest from the whole space.
fn key_at(state: u64) -> u64 {
    let mixed = state >> 17;
    if (state >> 33) % 100 < 80 {
        mixed % (KEY_SPACE / 100)
    } else {
        mixed % KEY_SPACE
    }
}

/// The fastest of `CACHE_RUNS` timed passes, with the hit count and final size
/// from the last one. Each pass starts from an empty cache, so the stream is the
/// same every time.
fn best_cache_run<C: Cache<u64, u64>>() -> (Duration, u64, usize) {
    let mut best = Duration::MAX;
    let mut hits = 0;
    let mut len = 0;

    for _ in 0..CACHE_RUNS {
        let mut cache = C::new(CACHE_CAPACITY);
        let (elapsed, run_hits) = cache_workload(&mut cache);
        best = best.min(elapsed);
        hits = run_hits;
        len = cache.len();
    }
    (best, hits, len)
}

/// The same request stream against any cache.
fn cache_workload<C: Cache<u64, u64>>(cache: &mut C) -> (Duration, u64) {
    let mut state = 0x9e37_79b9_7f4a_7c15u64;
    let mut hits = 0u64;

    let start = Instant::now();
    for _ in 0..OPERATIONS {
        state = state
            .wrapping_mul(6_364_136_223_846_793_005)
            .wrapping_add(1_442_695_040_888_963_407);
        let key = key_at(state);

        match cache.get(&key) {
            Some(value) => {
                hits += 1;
                black_box(value);
            }
            None => cache.put(key, key.rotate_left(17)),
        }
    }
    (start.elapsed(), hits)
}

fn cache_benchmark() {
    println!(
        "LRU cache: {} entries, {} requests over {} keys",
        with_thousands(CACHE_CAPACITY as u64),
        with_thousands(OPERATIONS),
        with_thousands(KEY_SPACE)
    );
    println!("A miss inserts and evicts the least recently used entry.");
    println!("Best of {CACHE_RUNS} runs per cache.\n");

    let (arena_time, arena_hits, arena_len) = best_cache_run::<ArenaCache<u64, u64>>();
    let (list_time, list_hits, list_len) = best_cache_run::<RcCache<u64, u64>>();

    // Same population and same hit count, or this compares nothing.
    assert_eq!(arena_len, list_len);
    assert_eq!(
        arena_hits, list_hits,
        "the two runs saw different request streams"
    );

    println!(
        "  hit rate: {:.1}%  ({} hits, {} inserts)\n",
        arena_hits as f64 * 100.0 / OPERATIONS as f64,
        with_thousands(arena_hits),
        with_thousands(OPERATIONS - arena_hits)
    );

    let per_request = |elapsed: Duration| elapsed.as_nanos() as f64 / OPERATIONS as f64;

    // `{:.2?}` uses Duration's own Debug format, rounded to two decimals.
    println!("  {:<22} {:>12} {:>13}", "storage", "total", "per request");
    println!("  {}", "-".repeat(48));
    for (name, elapsed) in [
        (
            <ArenaCache<u64, u64> as Cache<u64, u64>>::variant(),
            arena_time,
        ),
        (<RcCache<u64, u64> as Cache<u64, u64>>::variant(), list_time),
    ] {
        println!(
            "  {name:<22} {elapsed:>12.2?} {:>8.0} ns",
            per_request(elapsed)
        );
    }

    let speedup = list_time.as_secs_f64() / arena_time.as_secs_f64();
    println!(
        "\n  the arena is {speedup:.2}x faster on the same requests: {arena_time:.2?} against {list_time:.2?}"
    );
    println!("  the arena reuses the evicted slot; the list frees a node and allocates another");
}

// ---------------------------------------------------------------------------
// Lists: four variants, one loop
// ---------------------------------------------------------------------------

fn list_benchmark(variant: Option<&str>, elements: usize) {
    println!(
        "Singly linked list: push {} values, pop them back in order, then drop a full list",
        with_thousands(elements as u64)
    );
    println!("Best of {LIST_RUNS} runs per variant, allocator warmed up.\n");
    println!(
        "  {:<10} {:>12} {:>13} {:>13}",
        "variant", "elements", "push", "drop"
    );
    println!("  {}", "-".repeat(52));

    match variant {
        Some("box") => run_list::<boxed::LinkedList<u64>>(elements),
        Some("enum") => run_list::<enum_node::LinkedList<u64>>(elements),
        Some("box+drop") => run_list::<boxed_drop::LinkedList<u64>>(elements),
        Some("enum+drop") => run_list::<enum_drop::LinkedList<u64>>(elements),
        _ => {
            run_list::<boxed::LinkedList<u64>>(elements);
            run_list::<enum_node::LinkedList<u64>>(elements);
            run_list::<boxed_drop::LinkedList<u64>>(elements);
            run_list::<enum_drop::LinkedList<u64>>(elements);
        }
    }
}

fn run_list<L: SinglyList<u64>>(elements: usize) {
    // Warm the allocator first: without this the first variant in a process pays
    // for fresh heap pages and looks several times slower than an identical one.
    let mut warm_up = L::new();
    for value in 0..elements as u64 {
        warm_up.push_front(value);
    }
    drop(warm_up);

    let mut best_push = Duration::MAX;
    let mut best_drop = Duration::MAX;

    for _ in 0..LIST_RUNS {
        let mut list = L::new();

        let start = Instant::now();
        for value in 0..elements as u64 {
            list.push_front(value);
        }
        best_push = best_push.min(start.elapsed());

        // Pop every value back and check the order, so a broken list cannot post
        // a fast time.
        let mut expected = elements as u64;
        while let Some(value) = list.pop_front() {
            expected -= 1;
            assert_eq!(value, expected, "{} lost LIFO order", L::variant());
        }
        assert_eq!(expected, 0);
        black_box(expected);

        // Rebuild, then time the drop of a full list. This is where the
        // recursive variants overflow the stack.
        for value in 0..elements as u64 {
            list.push_front(value);
        }
        let start = Instant::now();
        drop(list);
        best_drop = best_drop.min(start.elapsed());
    }

    println!(
        "  {:<10} {:>12} {best_push:>13.2?} {best_drop:>13.2?}",
        L::variant(),
        with_thousands(elements as u64)
    );
}

fn with_thousands(value: u64) -> String {
    let digits = value.to_string();
    let mut out = String::with_capacity(digits.len() + digits.len() / 3);
    for (index, digit) in digits.chars().enumerate() {
        if index > 0 && (digits.len() - index).is_multiple_of(3) {
            out.push(',');
        }
        out.push(digit);
    }
    out
}

The list half of this file was explained in section 9.8. Run only the cache half with the cache argument, and always with --release. A debug build is not optimized, and its times do not show how the code performs.

$ cargo run --release --bin benchmark cache
LRU cache: 65,536 entries, 10,000,000 requests over 131,072 keys
A miss inserts and evicts the least recently used entry.
Best of 3 runs per cache.

  hit rate: 89.8%  (8,979,314 hits, 1,020,686 inserts)

  storage                       total   per request
  ------------------------------------------------
  arena (Vec + indices)      587.49ms       59 ns
  Rc<RefCell> list              1.86s      186 ns

  the arena is 3.16x faster on the same requests: 587.49ms against 1.86s
  the arena reuses the evicted slot; the list frees a node and allocates another

On this machine, the arena handled a request in 59 ns on average, and the Rc list took 186 ns. Your numbers will differ, but the ratio should be similar on most machines.

The two caches do the same O(1) work per request. Three differences in how they do it add up:

• Allocation. About one request in ten is a miss, and each miss in the Rc list frees a node and allocates another. The arena reuses the tail slot.
• Bookkeeping. The Rc list updates reference counts on every clone and drop, and checks the RefCell borrow flag on every access. The arena reads and writes plain integers.
• Location. The arena’s nodes sit side by side in one block. The Rc nodes sit wherever the allocator put them. Chapter 15 explains why nearby memory is faster to reach.

This benchmark measures the total, and does not separate the three costs. Exercise 4 suggests a way to separate them.

13.6 The complete files

The sections above showed these files in excerpts. Here each one is whole.

Listing 13.17 Version 1, stamped events, with tests. src/problems/lru_cache.rs

//! LRU cache without a linked list.
//!
//! Design: `HashMap<K, (V, generation)>` + `VecDeque<(K, generation)>`.
//!
//! Each access pushes a new `(key, generation)` event to the back. On eviction
//! we pop old events until we find the newest generation for a key, then remove
//! it. Stale events are skipped. This keeps amortized O(1) operations while
//! preserving true LRU semantics.

use std::{
    collections::{HashMap, VecDeque},
    hash::Hash,
};

pub struct LruCache<K, V>
where
    K: Eq + Hash + Clone,
    V: Clone,
{
    capacity: usize,
    map: HashMap<K, (V, u64)>,
    recency: VecDeque<(K, u64)>,
    generation: u64,
}

impl<K, V> LruCache<K, V>
where
    K: Eq + Hash + Clone,
    V: Clone,
{
    pub fn new(capacity: usize) -> Self {
        assert!(capacity > 0, "LRU cache capacity must be > 0");
        Self {
            capacity,
            map: HashMap::new(),
            recency: VecDeque::new(),
            generation: 0,
        }
    }

    pub fn len(&self) -> usize {
        self.map.len()
    }

    pub fn is_empty(&self) -> bool {
        self.map.is_empty()
    }

    pub fn get(&mut self, key: &K) -> Option<V> {
        let (value, _) = self.map.get(key)?.clone();
        self.generation += 1;
        self.recency
            .push_back((key.clone(), self.generation));
        self.map
            .insert(key.clone(), (value.clone(), self.generation));
        Some(value)
    }

    pub fn put(&mut self, key: K, value: V) {
        self.generation += 1;
        let is_new = self
            .map
            .insert(key.clone(), (value, self.generation))
            .is_none();
        self.recency
            .push_back((key, self.generation));

        if is_new {
            self.evict_if_needed();
        }
    }

    fn evict_if_needed(&mut self) {
        while self.map.len() > self.capacity {
            let Some((key, generation)) = self.recency.pop_front() else {
                break;
            };

            match self.map.get(&key) {
                Some((_, current)) if *current == generation => {
                    self.map.remove(&key);
                    break;
                }
                _ => {}
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn put_get_and_len() {
        let mut cache = LruCache::new(2);
        cache.put("a".to_string(), 1);
        cache.put("b".to_string(), 2);

        assert_eq!(cache.len(), 2);
        assert_eq!(cache.get(&"a".to_string()), Some(1));
        assert_eq!(cache.get(&"missing".to_string()), None);
    }

    #[test]
    fn evicts_least_recently_used() {
        let mut cache = LruCache::new(2);
        cache.put("a".to_string(), 1);
        cache.put("b".to_string(), 2);
        cache.put("c".to_string(), 3);

        assert_eq!(cache.get(&"a".to_string()), None);
        assert_eq!(cache.get(&"b".to_string()), Some(2));
        assert_eq!(cache.get(&"c".to_string()), Some(3));
    }

    #[test]
    fn get_updates_recency() {
        let mut cache = LruCache::new(2);
        cache.put("a".to_string(), 1);
        cache.put("b".to_string(), 2);

        // Access "a" so it becomes most recently used.
        assert_eq!(cache.get(&"a".to_string()), Some(1));

        cache.put("c".to_string(), 3); // evicts "b"
        assert_eq!(cache.get(&"b".to_string()), None);
        assert_eq!(cache.get(&"a".to_string()), Some(1));
        assert_eq!(cache.get(&"c".to_string()), Some(3));
    }

    #[test]
    fn updating_existing_key_moves_it_to_mru() {
        let mut cache = LruCache::new(2);
        cache.put("a".to_string(), 1);
        cache.put("b".to_string(), 2);

        // Update "a"; it becomes MRU, so "b" should be evicted next.
        cache.put("a".to_string(), 10);
        cache.put("c".to_string(), 3);

        assert_eq!(cache.get(&"a".to_string()), Some(10));
        assert_eq!(cache.get(&"b".to_string()), None);
        assert_eq!(cache.get(&"c".to_string()), Some(3));
    }
}

The tests cover the cases of figure 13.1. They check plain eviction, a get that saves an entry, and a put to an existing key, which also counts as a use.

Listing 13.18 Version 2, the arena, with tests. src/problems/lru_cache_easy.rs

//! A fixed-capacity LRU (Least Recently Used) cache.
//!
//! ## Design
//!
//! Two structures cooperate to give O(1) `get` and `put`:
//!
//! * `map: HashMap<K, usize>` — key → index into the arena.
//! * `nodes: Vec<Node<K, V>>` — an **arena** of nodes; indices play the role
//!   of pointers, sidestepping `Rc<RefCell<…>>` and its borrow-checker pain.
//!
//! The arena is stitched into a doubly linked list through `head`/`tail`:
//!
//! ```text
//!   MRU  →  head → … → tail  →  LRU
//! ```
//!
//! On eviction we **reuse the tail slot** instead of removing it, so no node
//! is ever deallocated mid-life. That keeps the arena dense and index-stable.

use std::{collections::HashMap, hash::Hash};

/// A single cache entry, linked into the recency list by index.
struct Node<K, V> {
    /// Retained so we can delete the corresponding map entry when evicting.
    key: K,
    value: V,
    /// Neighbour closer to the MRU end (or `None` if this is `head`).
    prev: Option<usize>,
    /// Neighbour closer to the LRU end (or `None` if this is `tail`).
    next: Option<usize>,
}

/// Fixed-capacity LRU cache.
pub struct LruCache<K, V> {
    /// Maximum number of entries; `>= 1` (enforced by `new`).
    cap: usize,
    /// Key → arena index. The single source of truth for "is this key cached?".
    lookup_table: HashMap<K, usize>,
    /// Arena of nodes; indices are the "pointers" of the linked list.
    nodes: Vec<Node<K, V>>,
    /// Arena index of the most recently used entry.
    head: Option<usize>,
    /// Arena index of the least recently used entry (next to be evicted).
    tail: Option<usize>,
}

impl<K, V> LruCache<K, V>
where
    K: Hash + Eq + Clone,
{
    /// Create a cache holding at most `cap` entries.
    ///
    /// # Panics
    /// Panics if `cap == 0`, since a zero-capacity cache cannot store anything.
    pub fn new(cap: usize) -> Self {
        assert!(cap > 0, "capacity must be > 0");
        Self {
            cap,
            lookup_table: HashMap::new(),
            nodes: Vec::new(),
            head: None,
            tail: None,
        }
    }

    /// Promote node `i` to `head` (MRU).
    ///
    /// Handles both cases in one pass:
    /// * **Already linked** — detach from its current neighbours first.
    /// * **Brand new** — the node has `prev = next = None` and is not yet
    ///   referenced by `head`/`tail`, so the detach step is skipped.
    fn touch(&mut self, i: usize) {
        let (prev, next) = (self.nodes[i].prev, self.nodes[i].next);

        // A node is "linked" if any of its four references exist.
        let linked =
            prev.is_some() || next.is_some() || self.head == Some(i) || self.tail == Some(i);

        if linked {
            // Splice `i` out of the list.
            match prev {
                Some(p) => self.nodes[p].next = next,
                None => self.head = next,
            }
            match next {
                Some(n) => self.nodes[n].prev = prev,
                None => self.tail = prev,
            }
        }

        // Splice `i` in at the front.
        self.nodes[i].prev = None;
        self.nodes[i].next = self.head;
        if let Some(h) = self.head {
            self.nodes[h].prev = Some(i);
        }
        self.head = Some(i);
        if self.tail.is_none() {
            self.tail = Some(i);
        }
    }

    /// Look up `key`, promoting it to MRU on a hit.
    ///
    /// Returns `None` if the key is not cached.
    pub fn get(&mut self, key: &K) -> Option<&V> {
        let i = *self.lookup_table.get(key)?;
        self.touch(i);
        Some(&self.nodes[i].value)
    }

    /// Insert or update `key`. Promotes it to MRU. Evicts the LRU entry if
    /// the cache is full.
    pub fn put(&mut self, key: K, value: V) {
        // Case 1: key already present → update value, promote.
        if let Some(&i) = self.lookup_table.get(&key) {
            self.nodes[i].value = value;
            self.touch(i);
            return;
        }

        // Case 2: room to grow → append a fresh node.
        if self.nodes.len() < self.cap {
            let i = self.nodes.len();
            self.nodes.push(Node {
                key: key.clone(),
                value,
                prev: None,
                next: None,
            });
            self.lookup_table.insert(key, i);
            self.touch(i);
            return;
        }

        // Case 3: at capacity → reuse the LRU slot.
        // `tail` is guaranteed to be `Some` here because `cap >= 1` and the
        // arena is full, but we still handle `None` gracefully.
        if let Some(i) = self.tail {
            let old_key = std::mem::replace(&mut self.nodes[i].key, key);
            self.nodes[i].value = value;
            self.lookup_table.remove(&old_key);
            self.lookup_table
                .insert(self.nodes[i].key.clone(), i);
            self.touch(i);
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn basic_eviction() {
        let mut c = LruCache::new(2);
        c.put("A", 1);
        c.put("B", 2);

        assert_eq!(c.get(&"A"), Some(&1)); // A is now MRU
        c.put("C", 3); // evicts B

        assert_eq!(c.get(&"B"), None);
        assert_eq!(c.get(&"A"), Some(&1));
        assert_eq!(c.get(&"C"), Some(&3));
    }

    #[test]
    fn updating_existing_key_keeps_it() {
        let mut c = LruCache::new(2);
        c.put("A", 1);
        c.put("B", 2);

        c.put("A", 100); // update A, A becomes MRU
        c.put("C", 3); // evicts B

        assert_eq!(c.get(&"A"), Some(&100));
        assert_eq!(c.get(&"B"), None);
        assert_eq!(c.get(&"C"), Some(&3));
    }

    #[test]
    fn get_refreshes_recency() {
        let mut c = LruCache::new(2);
        c.put("A", 1);
        c.put("B", 2);

        assert_eq!(c.get(&"A"), Some(&1)); // A refreshed
        c.put("C", 3); // evicts B

        assert_eq!(c.get(&"B"), None);
        assert_eq!(c.get(&"A"), Some(&1));
    }

    #[test]
    fn capacity_one() {
        let mut c = LruCache::new(1);
        c.put("A", 1);
        c.put("B", 2); // evicts A

        assert_eq!(c.get(&"A"), None);
        assert_eq!(c.get(&"B"), Some(&2));
    }

    #[test]
    fn missing_key_returns_none() {
        let mut c: LruCache<&str, i32> = LruCache::new(2);
        assert_eq!(c.get(&"nope"), None);
    }

    #[test]
    #[should_panic(expected = "capacity must be > 0")]
    fn zero_capacity_panics() {
        let _: LruCache<&str, i32> = LruCache::new(0);
    }
}

The tests include a capacity of 1, where the single node is the head and the tail at once. Another test checks that a capacity of 0 panics.

Listing 13.19 Version 3, one operation per method. src/bin/lru_cache_modular.rs

//! A fixed-capacity LRU (Least Recently Used) cache.
//!
//! ## Design
//!
//! Two structures cooperate to give O(1) `get` and `put`:
//!
//! * `lookup_table: HashMap<i32, usize>` — key → index into the arena.
//! * `nodes: Vec<Node>` — an **arena** of nodes; indices play the role
//!   of pointers, sidestepping `Rc<RefCell<…>>` and its borrow-checker pain.
//!
//! The arena is stitched into a doubly linked list through `head`/`tail`:
//!
//! ```text
//!   MRU  →  head → … → tail  →  LRU
//! ```
//!
//! On eviction we **reuse the tail slot** instead of removing it, so no node
//! is ever deallocated mid-life. That keeps the arena dense and index-stable.

use std::collections::HashMap;

/// A single cache entry, linked into the recency list by index.
struct Node {
    /// Retained so we can delete the corresponding map entry when evicting.
    key: i32,
    value: i32,
    /// Neighbour closer to the MRU end (or `None` if this is `head`).
    prev: Option<usize>,
    /// Neighbour closer to the LRU end (or `None` if this is `tail`).
    next: Option<usize>,
}

/// Fixed-capacity LRU cache.
pub struct LruCache {
    /// Maximum number of entries; `>= 1` (enforced by `new`).
    cap: usize,
    /// Key → arena index. The single source of truth for "is this key cached?".
    lookup_table: HashMap<i32, usize>,
    /// Arena of nodes; indices are the "pointers" of the linked list.
    nodes: Vec<Node>,
    /// Arena index of the most recently used entry.
    head: Option<usize>,
    /// Arena index of the least recently used entry (next to be evicted).
    tail: Option<usize>,
}

impl LruCache {
    /// Create a cache holding at most `cap` entries.
    ///
    /// # Panics
    /// Panics if `cap == 0`, since a zero-capacity cache cannot store anything.
    pub fn new(cap: usize) -> Self {
        assert!(cap > 0, "capacity must be > 0");
        Self {
            cap,
            lookup_table: HashMap::new(),
            nodes: Vec::new(),
            head: None,
            tail: None,
        }
    }

    /// Unlink node `i` from the list. `i` must currently be linked.
    fn detach(&mut self, i: usize) {
        let (prev, next) = (self.nodes[i].prev, self.nodes[i].next);
        match prev {
            Some(p) => self.nodes[p].next = next,
            None => self.head = next,
        }
        match next {
            Some(n) => self.nodes[n].prev = prev,
            None => self.tail = prev,
        }
    }

    /// Link node `i` in at the MRU end. `i` must currently be unlinked.
    fn push_front(&mut self, i: usize) {
        self.nodes[i].prev = None;
        self.nodes[i].next = self.head;
        match self.head {
            Some(h) => self.nodes[h].prev = Some(i),
            None => self.tail = Some(i), // list was empty
        }
        self.head = Some(i);
    }

    /// Promote an already-linked node to MRU.
    fn promote_to_front(&mut self, i: usize) {
        if self.head == Some(i) {
            return; // already MRU
        }
        self.detach(i);
        self.push_front(i);
    }

    /// Look up `key`, promoting it to MRU on a hit.
    ///
    /// Returns `None` if the key is not cached.
    pub fn get(&mut self, key: i32) -> Option<i32> {
        let i = *self.lookup_table.get(&key)?;
        self.promote_to_front(i);
        Some(self.nodes[i].value)
    }

    /// Insert or update `key`. Promotes it to MRU. Evicts the LRU entry if
    /// the cache is full.
    pub fn put(&mut self, key: i32, value: i32) {
        // Case 1: key already present → update value, promote.
        if let Some(&i) = self.lookup_table.get(&key) {
            self.nodes[i].value = value;
            self.promote_to_front(i);
            return;
        }

        // Case 2: room to grow → append a fresh (unlinked) node.
        if self.nodes.len() < self.cap {
            let i = self.nodes.len();
            self.nodes.push(Node {
                key,
                value,
                prev: None,
                next: None,
            });
            self.lookup_table.insert(key, i);
            self.push_front(i);
            return;
        }

        // Case 3: at capacity → reuse the LRU slot.
        // `tail` is guaranteed to be `Some` here because `cap >= 1` and the
        // arena is full, but we still handle `None` gracefully.
        if let Some(i) = self.tail {
            // Swap the new key into the node and hand back the old one it held.
            let old_key = std::mem::replace(&mut self.nodes[i].key, key);
            self.nodes[i].value = value;
            self.lookup_table.remove(&old_key);
            self.lookup_table.insert(key, i);
            self.promote_to_front(i);
        }
    }
}

fn main() {
    let mut cache = LruCache::new(2);

    cache.put(1, 10);
    cache.put(2, 20);
    println!("get 1 = {:?}", cache.get(1)); // Some(10), 1 now MRU

    cache.put(3, 30); // evicts 2 (LRU)

    println!("get 2 = {:?}", cache.get(2)); // None
    println!("get 1 = {:?}", cache.get(1)); // Some(10)
    println!("get 3 = {:?}", cache.get(3)); // Some(30)

    cache.put(1, 99);
    println!("get 1 = {:?}", cache.get(1)); // Some(99)
}

#[cfg(test)]
mod tests_for_lru {
    use super::*;

    #[test]
    fn basic_eviction() {
        let mut c = LruCache::new(2);
        c.put(1, 10);
        c.put(2, 20);

        assert_eq!(c.get(1), Some(10)); // 1 is now MRU
        c.put(3, 30); // evicts 2

        assert_eq!(c.get(2), None);
        assert_eq!(c.get(1), Some(10));
        assert_eq!(c.get(3), Some(30));
    }

    #[test]
    fn updating_existing_key_keeps_it() {
        let mut c = LruCache::new(2);
        c.put(1, 10);
        c.put(2, 20);

        c.put(1, 100); // update 1, 1 becomes MRU
        c.put(3, 30); // evicts 2

        assert_eq!(c.get(1), Some(100));
        assert_eq!(c.get(2), None);
        assert_eq!(c.get(3), Some(30));
    }

    #[test]
    fn get_refreshes_recency() {
        let mut c = LruCache::new(2);
        c.put(1, 10);
        c.put(2, 20);

        assert_eq!(c.get(1), Some(10)); // 1 refreshed
        c.put(3, 30); // evicts 2

        assert_eq!(c.get(2), None);
        assert_eq!(c.get(1), Some(10));
    }

    #[test]
    fn capacity_one() {
        let mut c = LruCache::new(1);
        c.put(1, 10);
        c.put(2, 20); // evicts 1

        assert_eq!(c.get(1), None);
        assert_eq!(c.get(2), Some(20));
    }

    #[test]
    fn missing_key_returns_none() {
        let mut c = LruCache::new(2);
        assert_eq!(c.get(42), None);
    }

    #[test]
    #[should_panic(expected = "capacity must be > 0")]
    fn zero_capacity_panics() {
        let _ = LruCache::new(0);
    }
}

Listing 13.20 The arena LRU cache. src/bin/lru_cache_arena.rs

//! A fixed-capacity LRU (Least Recently Used) cache.
//!
//! ## Design
//!
//! Two structures cooperate to give O(1) `get` and `put`:
//!
//! * `map: HashMap<K, usize>` — key → index into the arena.
//! * `nodes: Vec<Node<K, V>>` — an **arena** of nodes; indices play the role
//!   of pointers, sidestepping `Rc<RefCell<…>>` and its borrow-checker pain.
//!
//! The arena is stitched into a doubly linked list through `head`/`tail`:
//!
//! ```text
//!   MRU  →  head → … → tail  →  LRU
//! ```
//!
//! On eviction we **reuse the tail slot** instead of removing it, so no node
//! is ever deallocated mid-life. That keeps the arena dense and index-stable.

use std::{collections::HashMap, hash::Hash};

/// A single cache entry, linked into the recency list by index.
struct Node<K, V> {
    /// Retained so we can delete the corresponding map entry when evicting.
    key: K,
    value: V,
    /// Neighbour closer to the MRU end (or `None` if this is `head`).
    prev: Option<usize>,
    /// Neighbour closer to the LRU end (or `None` if this is `tail`).
    next: Option<usize>,
}

/// Fixed-capacity LRU cache.
pub struct LruCache<K, V> {
    /// Maximum number of entries; `>= 1` (enforced by `new`).
    cap: usize,
    /// Key → arena index. The single source of truth for "is this key cached?".
    lookup_table: HashMap<K, usize>,
    /// Arena of nodes; indices are the "pointers" of the linked list.
    nodes: Vec<Node<K, V>>,
    /// Arena index of the most recently used entry.
    head: Option<usize>,
    /// Arena index of the least recently used entry (next to be evicted).
    tail: Option<usize>,
}

impl<K, V> LruCache<K, V>
where
    K: Hash + Eq + Clone,
{
    /// Create a cache holding at most `cap` entries.
    ///
    /// # Panics
    /// Panics if `cap == 0`, since a zero-capacity cache cannot store anything.
    pub fn new(cap: usize) -> Self {
        assert!(cap > 0, "capacity must be > 0");
        Self {
            cap,
            lookup_table: HashMap::new(),
            nodes: Vec::new(),
            head: None,
            tail: None,
        }
    }

    /// Promote node `i` to `head` (MRU).
    ///
    /// Handles both cases in one pass:
    /// * **Already linked** — detach from its current neighbours first.
    /// * **Brand new** — the node has `prev = next = None` and is not yet
    ///   referenced by `head`/`tail`, so the detach step is skipped.
    fn touch(&mut self, i: usize) {
        let (prev, next) = (self.nodes[i].prev, self.nodes[i].next);

        // A node is "linked" if any of its four references exist.
        let linked =
            prev.is_some() || next.is_some() || self.head == Some(i) || self.tail == Some(i);

        if linked {
            // Splice `i` out of the list.
            match prev {
                Some(p) => self.nodes[p].next = next,
                None => self.head = next,
            }
            match next {
                Some(n) => self.nodes[n].prev = prev,
                None => self.tail = prev,
            }
        }

        // Splice `i` in at the front.
        self.nodes[i].prev = None;
        self.nodes[i].next = self.head;
        if let Some(h) = self.head {
            self.nodes[h].prev = Some(i);
        }
        self.head = Some(i);
        if self.tail.is_none() {
            self.tail = Some(i);
        }
    }

    /// Look up `key`, promoting it to MRU on a hit.
    ///
    /// Returns `None` if the key is not cached.
    pub fn get(&mut self, key: &K) -> Option<&V> {
        let i = *self.lookup_table.get(key)?;
        self.touch(i);
        Some(&self.nodes[i].value)
    }

    /// Insert or update `key`. Promotes it to MRU. Evicts the LRU entry if
    /// the cache is full.
    pub fn put(&mut self, key: K, value: V) {
        // Case 1: key already present → update value, promote.
        if let Some(&i) = self.lookup_table.get(&key) {
            self.nodes[i].value = value;
            self.touch(i);
            return;
        }

        // Case 2: room to grow → append a fresh node.
        if self.nodes.len() < self.cap {
            let i = self.nodes.len();
            self.nodes.push(Node {
                key: key.clone(),
                value,
                prev: None,
                next: None,
            });
            self.lookup_table.insert(key, i);
            self.touch(i);
            return;
        }

        // Case 3: at capacity → reuse the LRU slot.
        // `tail` is guaranteed to be `Some` here because `cap >= 1` and the
        // arena is full, but we still handle `None` gracefully.
        if let Some(i) = self.tail {
            let old_key = std::mem::replace(&mut self.nodes[i].key, key);
            self.nodes[i].value = value;
            self.lookup_table.remove(&old_key);
            self.lookup_table
                .insert(self.nodes[i].key.clone(), i);
            self.touch(i);
        }
    }
}

fn main() {
    let mut cache = LruCache::new(2);

    cache.put("A", 10);
    cache.put("B", 20);
    println!("get A = {:?}", cache.get(&"A")); // Some(10), A now MRU

    cache.put("C", 30); // evicts B (LRU)

    println!("get B = {:?}", cache.get(&"B")); // None
    println!("get A = {:?}", cache.get(&"A")); // Some(10)
    println!("get C = {:?}", cache.get(&"C")); // Some(30)

    cache.put("A", 99);
    println!("get A = {:?}", cache.get(&"A")); // Some(99)
}

#[cfg(test)]
mod tests_for_lru {
    use super::*;

    #[test]
    fn basic_eviction() {
        let mut c = LruCache::new(2);
        c.put("A", 1);
        c.put("B", 2);

        assert_eq!(c.get(&"A"), Some(&1)); // A is now MRU
        c.put("C", 3); // evicts B

        assert_eq!(c.get(&"B"), None);
        assert_eq!(c.get(&"A"), Some(&1));
        assert_eq!(c.get(&"C"), Some(&3));
    }

    #[test]
    fn updating_existing_key_keeps_it() {
        let mut c = LruCache::new(2);
        c.put("A", 1);
        c.put("B", 2);

        c.put("A", 100); // update A, A becomes MRU
        c.put("C", 3); // evicts B

        assert_eq!(c.get(&"A"), Some(&100));
        assert_eq!(c.get(&"B"), None);
        assert_eq!(c.get(&"C"), Some(&3));
    }

    #[test]
    fn get_refreshes_recency() {
        let mut c = LruCache::new(2);
        c.put("A", 1);
        c.put("B", 2);

        assert_eq!(c.get(&"A"), Some(&1)); // A refreshed
        c.put("C", 3); // evicts B

        assert_eq!(c.get(&"B"), None);
        assert_eq!(c.get(&"A"), Some(&1));
    }

    #[test]
    fn capacity_one() {
        let mut c = LruCache::new(1);
        c.put("A", 1);
        c.put("B", 2); // evicts A

        assert_eq!(c.get(&"A"), None);
        assert_eq!(c.get(&"B"), Some(&2));
    }

    #[test]
    fn missing_key_returns_none() {
        let mut c: LruCache<&str, i32> = LruCache::new(2);
        assert_eq!(c.get(&"nope"), None);
    }

    #[test]
    #[should_panic(expected = "capacity must be > 0")]
    fn zero_capacity_panics() {
        let _: LruCache<&str, i32> = LruCache::new(0);
    }
}

Listing 13.21 The Rc<RefCell<_>> LRU cache used by the benchmark. benchmarking_examples/cache/rc_list.rs

//! LRU cache built from an `Rc<RefCell<_>>` doubly linked list.
//!
//! The textbook version: `Rc` forward, `Weak` back, and a `HashMap` from key to
//! node. Every node is its own heap allocation, and every move to the front
//! clones an `Rc`, upgrades a `Weak`, and borrows the `RefCell`.
//!
//! The default drop would free a node, which frees its `next`, one stack frame
//! per element, so `Drop` is written to unlink iteratively.

use std::{
    cell::RefCell,
    collections::HashMap,
    hash::Hash,
    rc::{Rc, Weak},
};

use super::Cache;

type Link<K, V> = Option<Rc<RefCell<Node<K, V>>>>;

struct Node<K, V> {
    key: K,
    value: V,
    prev: Weak<RefCell<Node<K, V>>>,
    next: Link<K, V>,
}

pub struct LruCache<K, V> {
    cap: usize,
    map: HashMap<K, Rc<RefCell<Node<K, V>>>>,
    head: Link<K, V>,
    tail: Link<K, V>,
}

impl<K, V> LruCache<K, V>
where
    K: Hash + Eq + Clone,
    V: Copy,
{
    fn detach(&mut self, node: &Rc<RefCell<Node<K, V>>>) {
        let (prev, next) = {
            let entry = node.borrow();
            (entry.prev.clone(), entry.next.clone())
        };

        match prev.upgrade() {
            Some(previous) => previous.borrow_mut().next = next.clone(),
            None => self.head = next.clone(),
        }
        match &next {
            Some(following) => following.borrow_mut().prev = prev,
            None => self.tail = prev.upgrade(),
        }
    }

    fn push_front(&mut self, node: Rc<RefCell<Node<K, V>>>) {
        let head = self.head.clone();
        {
            let mut entry = node.borrow_mut();
            entry.prev = Weak::new();
            entry.next = head.clone();
        }
        match &head {
            Some(previous) => previous.borrow_mut().prev = Rc::downgrade(&node),
            None => self.tail = Some(node.clone()),
        }
        self.head = Some(node);
    }
}

impl<K, V> Cache<K, V> for LruCache<K, V>
where
    K: Hash + Eq + Clone,
    V: Copy,
{
    fn new(capacity: usize) -> Self {
        assert!(capacity > 0, "capacity must be > 0");
        Self {
            cap: capacity,
            map: HashMap::new(),
            head: None,
            tail: None,
        }
    }

    fn get(&mut self, key: &K) -> Option<V> {
        let node = self.map.get(key)?.clone();
        self.detach(&node);
        self.push_front(node.clone());
        Some(node.borrow().value)
    }

    fn put(&mut self, key: K, value: V) {
        if let Some(node) = self.map.get(&key).cloned() {
            node.borrow_mut().value = value;
            self.detach(&node);
            self.push_front(node);
            return;
        }

        if self.map.len() >= self.cap
            && let Some(victim) = self.tail.clone()
        {
            let old_key = victim.borrow().key.clone();
            self.map.remove(&old_key);
            self.detach(&victim);
        }

        let node = Rc::new(RefCell::new(Node {
            key: key.clone(),
            value,
            prev: Weak::new(),
            next: None,
        }));
        self.map.insert(key, node.clone());
        self.push_front(node);
    }

    fn len(&self) -> usize {
        self.map.len()
    }

    fn variant() -> &'static str {
        "Rc<RefCell> list"
    }
}

impl<K, V> Drop for LruCache<K, V> {
    fn drop(&mut self) {
        // Unlink iteratively: dropping a million-node chain recursively overflows
        // the stack.
        let mut current = self.head.take();
        while let Some(node) = current {
            let next = node.borrow_mut().next.take();
            node.borrow_mut().prev = Weak::new();
            current = next;
        }
    }
}

Chapter 14 spreads a cache across several machines, and asks how to decide which machine holds which key.

Exercises

1. Bound the queue in version 1. When recency grows longer than twice the capacity, rebuild it with only the current events. Check that the cost stays amortized O(1).
2. Add peek(&self, key: &K) -> Option<&V> to version 2, which returns a value without changing the order.
3. Add remove(&mut self, key: &K) -> Option<V> to version 3. The removed slot must be reused by a later put. Keep a list of free slots.
4. Change the benchmark’s CACHE_CAPACITY to the full key space, so no request evicts anything. Compare the ratio with the one above, and explain what the change tells you about the cost of allocation.