Caching Computed Values in Rust With Memoization Explained

Computing the same expensive thing twice is the easiest performance bug to fix, and the easiest to fix wrongly. Memoization stores the result keyed by the input. It works for pure functions, which is the condition people forget. This post shows the plain HashMap version, the recursive one, and the limits. For caches that outlive one computation, see in-process caches. Both belong to the performance cluster started in profiling Rust programs.

Rust 1.90, edition 2024.

A cache in front of a function

use std::collections::HashMap;

fn slow_square(n: u64) -> u64 {
    // pretend this is expensive
    n * n
}

struct Memo {
    cache: HashMap<u64, u64>,
}

impl Memo {
    fn new() -> Self { Memo { cache: HashMap::new() } }

    fn square(&mut self, n: u64) -> u64 {
        if let Some(&v) = self.cache.get(&n) {
            return v;
        }
        let v = slow_square(n);
        self.cache.insert(n, v);
        v
    }
}

A second call with the same n returns from the map. With the entry API the two lookups collapse into one: *self.cache.entry(n).or_insert_with(|| slow_square(n)), covered in the HashMap entry API.

Recursion

The classic case is Fibonacci, where the naive recursion repeats work exponentially.

use std::collections::HashMap;

fn fib(n: u64, memo: &mut HashMap<u64, u64>) -> u64 {
    if n < 2 {
        return n;
    }
    if let Some(&v) = memo.get(&n) {
        return v;
    }
    let v = fib(n - 1, memo) + fib(n - 2, memo);
    memo.insert(n, v);
    v
}

fn main() {
    let mut memo = HashMap::new();
    println!("{}", fib(50, &mut memo));
}

It prints 12586269025. The naive version makes roughly forty billion calls for fib(50); the memoized one makes about a hundred. For this particular function a loop with two variables needs no map at all, so memoization is a tool for functions where the repeated subproblems are not so tidy.

Key design

The key must include everything the result depends on. A function price(product, currency) cached by product alone returns euros to a dollar customer. Reading an environment variable or the clock inside a "memoized" function makes it impure and the cache wrong. Floating-point keys are awkward, because f64 is not Hash; use the bit pattern (to_bits) or round to an integer.

Bound it

Each distinct input adds an entry. If inputs are user supplied, the cache grows without limit and an attacker can fill your memory. Use a maximum entry count with eviction (LRU), or a time to live. The moka crate provides both with thread-safe access, and cached offers an attribute macro (#[cached]) that memoizes a function in one line.

Threads

A Mutex<HashMap> held while computing serializes every caller. Lock, check, unlock, compute, lock, insert; accept that two threads may compute the same value at once, or use moka's get_with, which makes concurrent callers for one key wait for a single computation.

When not to memoize

Cheap functions, inputs that never repeat, and results that depend on mutable state. Check the hit rate: count hits and misses, and remove the cache if misses dominate. Cache invalidation, always the hard part, is discussed in the performance posts around in-process caches. The standard library's HashMap entry API is the building block.