Rust memoization: cache keys, limits and failure handling

A saved answer is only useful for the same question

Memoization stores a function's answer so a repeated request can reuse it. The attractive part is avoiding repeated work; the difficult part is deciding whether two requests actually ask the same question. A lookup keyed only by a filename is wrong if the file's contents can change. A lookup keyed only by a query is wrong if the calculation also depends on the dataset, permissions, rounding policy, or configuration revision.

Start by writing the function as though no cache existed. Identify its inputs, result, errors, and resource limits. Then define the circumstances under which an earlier result remains valid. This guide develops two small standard-library examples: a bounded-domain recursive calculation and a cache with explicit revision keys and capacity behavior. Both are ordinary Rust programs rather than a promise that one map can solve every storage or concurrency problem.

First ask whether there is repeated work to remove

A cache adds hashing, comparisons, storage, and maintenance. For a cheap calculation used once per key, those costs can exceed the computation it replaces. Before adding one, describe the expected workload: how often requests repeat, how expensive a miss is, how large a value becomes, and how long the answers stay useful. An optimization that helps a tiny demonstration may retain unnecessary memory in a long-running application.

The recursive Fibonacci sequence is useful here because repeated subproblems are easy to see. It is a teaching example, not a recommendation to implement a production Fibonacci service with a map. A simple iterative calculation can solve this particular problem with less storage. We use recursion to make the memoization boundary observable, then transfer the reasoning to calculations whose overlapping subproblems are less obvious.

Give the recursive example a finite numeric contract

Our function accepts indices through 94 and returns an optional u64. Index 93 fits, while index 94 overflows the result type. Larger indices are rejected before recursion, so a huge request cannot produce a huge recursive call chain or fill the map with millions of entries. The limit belongs to this function's documented domain; it is not a general property of memoization.

The cache stores Option<u64> values. A stored None means the calculation was performed for a supported index and found that its result does not fit. An absent key means no result has been stored. Those are separate states. Looking up a nested option and accidentally flattening the distinction can cause deterministic failures to be recomputed forever or make a missing answer look like a known overflow.

A complete memoized function with checked arithmetic

The program checks the map before descending, copies the small optional value out of the borrowed entry, computes on a miss, and stores the outcome. The immutable lookup borrow ends before the recursive calls need mutable access to the same map. This order avoids holding an entry borrow across recursion, a tempting arrangement that makes the ownership relationship much harder to express correctly.

The assertions check a familiar small value, the largest representable result in the supported sequence, the overflow case, and rejection beyond the domain. A repeated successful request must leave the number of entries unchanged. These checks establish correctness and basic reuse; they do not establish a speedup. Performance claims require a representative workload and measurements that distinguish initial misses from later hits.

use std::collections::HashMap;

fn fib(n: u32, cache: &mut HashMap<u32, Option<u64>>) -> Option<u64> {
    if n > 94 { return None; }
    if let Some(answer) = cache.get(&n) { return *answer; }
    let answer = match n {
        0 => Some(0),
        1 => Some(1),
        _ => fib(n - 1, cache)
            .zip(fib(n - 2, cache))
            .and_then(|(a, b)| a.checked_add(b)),
    };
    cache.insert(n, answer);
    answer
}

fn main() {
    let mut cache = HashMap::new();
    assert_eq!(fib(10, &mut cache), Some(55));
    assert_eq!(fib(93, &mut cache), Some(12_200_160_415_121_876_738));
    assert_eq!(fib(94, &mut cache), None);
    let entries = cache.len();
    assert_eq!(fib(10, &mut cache), Some(55));
    assert_eq!(cache.len(), entries);
    assert_eq!(fib(u32::MAX, &mut cache), None);
    assert_eq!(cache.len(), entries);
    println!("{entries} cached inputs; repeated requests reuse answers");
}

Sources: Standard library: HashMap · Standard library: u64 checked_add

Read the cache diagram as a state table

For a fresh request for fib(5), the completed map contains the distinct inputs zero through five with values zero, one, one, two, three, and five. A second request for five can return the stored five. The diagram counts distinct cached inputs, not total function invocations: recursive calls and cache checks still occur while the first result is assembled.

That distinction prevents a misleading comparison. Memoization removes repeated computation after a result is known, but it does not erase the work needed to discover keys, look them up, or return values. When explaining an optimization, label exactly what a number counts. A diagram showing six stored inputs should not be presented as evidence of six total calls, constant memory, or a particular performance multiplier.

Make hidden context visible in the key

Suppose an application calculates a score for a query against a dataset. The query alone is insufficient: the same query can produce a different score after the dataset changes. Our second example uses a key containing both the query text and an application-managed revision number. A revision must identify an immutable interpretation of the data; reusing a revision after modifying the data breaks the contract.

There are other valid designs. You can keep a cache inside an immutable dataset object, replace the whole cache when that object changes, or include a content digest in the key. Choose the smallest design that reliably distinguishes answer-changing context. Do not add a field merely because it is available, and do not omit one merely because the first demonstration happened to keep it constant.

Choose an eviction rule you can explain accurately

This cache has a maximum entry count. When a successful miss arrives at capacity, it clears all existing entries and inserts the new answer. That is a simple bounded policy, not least-recently-used eviction. It may cause bursts of recomputation, but its behavior is short enough to review and test. A production workload with frequent churn may justify a more sophisticated policy after measurement.

Capacity zero means bypassing storage while still computing the answer. Errors are returned without insertion, and a failed calculation does not evict successful older answers. The example stores small copied integers; entry count is therefore an understandable first limit. For large strings or trees, a count limit alone is insufficient because one entry may consume most of the process's memory. Define a byte or domain-size budget when values vary substantially.

A revision-aware cache without cached transient errors

Here is the complete second program. The caller provides the actual calculation as a closure, allowing the tests to count work without a network, database, or clock. The cache owns its key and copies its small result on a hit. The implementation computes successfully before clearing a full map, so a failed attempt preserves previously useful entries.

Notice that this interface cannot verify the caller's revision discipline. That invariant belongs to the application model and must be enforced where data changes. A type can help organize a contract without magically proving facts about external state. The examples deliberately make this responsibility visible instead of hiding it behind a generic function named cached whose actual validity rules are undocumented.

use std::collections::HashMap;

#[derive(Clone, Debug, PartialEq, Eq, Hash)]
struct Key { revision: u64, query: String }

struct Scores { capacity: usize, values: HashMap<Key, u64> }

impl Scores {
    fn new(capacity: usize) -> Self {
        Self { capacity, values: HashMap::new() }
    }

    fn get_or_compute<E>(
        &mut self, key: Key, compute: impl FnOnce() -> Result<u64, E>,
    ) -> Result<u64, E> {
        if let Some(value) = self.values.get(&key) { return Ok(*value); }
        let value = compute()?;
        if self.capacity != 0 {
            if self.values.len() >= self.capacity { self.values.clear(); }
            self.values.insert(key, value);
        }
        Ok(value)
    }
}

fn main() {
    let mut cache = Scores::new(2);
    let first = Key { revision: 1, query: "rust".into() };
    let second = Key { revision: 2, query: "rust".into() };
    let mut calls = 0;
    for key in [first.clone(), first, second.clone()] {
        let value = cache.get_or_compute(key.clone(), || {
            calls += 1;
            Ok::<u64, &str>(key.revision * 10)
        }).unwrap();
        assert_eq!(value, key.revision * 10);
    }
    assert_eq!(calls, 2);
    for _ in 0..2 {
        let failed = Key { revision: 3, query: "offline".into() };
        assert_eq!(cache.get_or_compute(failed, || Err("offline")), Err("offline"));
    }
    assert_eq!(cache.values.len(), 2);
    assert_eq!(cache.get_or_compute(second, || Err("must be a hit")), Ok(20));
    let third = Key { revision: 3, query: "new".into() };
    assert_eq!(cache.get_or_compute(third, || Ok::<_, &str>(30)), Ok(30));
    assert_eq!(cache.values.len(), 1);
    let mut disabled = Scores::new(0);
    let key = Key { revision: 1, query: "fresh".into() };
    assert_eq!(disabled.get_or_compute(key, || Ok::<_, &str>(7)), Ok(7));
    assert!(disabled.values.is_empty());
    println!("Revision, retry and capacity contracts passed");
}

Decide which failures are stable enough to remember

The Fibonacci cache remembers overflow because it is a deterministic answer for that input and numeric type. The score cache does not remember errors because its caller may fail for a temporary reason. These choices differ intentionally. A missing object in an immutable snapshot may be a stable negative answer, while a temporary service outage is usually not evidence that the requested object does not exist.

If you cache negative answers, specify their validity rules as carefully as successful answers. Include the relevant revision, expiration rule, or invalidation event. Also preserve the distinction between a calculation that returned no value and a calculation that could not be completed. Collapsing those states into one cached sentinel makes retries, diagnostics, and user messages misleading even if the happy path appears faster.

Ownership determines the cost of returning a hit

Returning a copied integer is inexpensive and keeps the examples focused. A real cache may hold a large document. Returning an owned clone duplicates that document, returning a reference ties the caller to the cache's borrow, and returning a shared ownership handle introduces another lifetime and allocation policy. None of those choices is automatically best; the right interface follows how callers use the result.

Avoid solving borrow-checker pressure by cloning every object without considering the data size. Sometimes a short inner scope or computing before insertion is enough. Sometimes a cache should own immutable shared values so callers can retain them while later requests mutate the map. Write down whether a returned answer may outlive its cache entry before selecting the return type. That decision affects eviction semantics as well as convenience.

Invalidation should follow the data model

A revision key prevents new requests from confusing different snapshots, but it does not remove old entries. The capacity policy still needs to reclaim them. If only the current dataset is useful, replacing the whole cache on revision change may be simpler than storing many generations. If users compare snapshots, keeping multiple revisions may be intentional. The application should make that choice rather than accidentally retaining every version forever.

For mutable external data without revisions, time-based expiration is only an approximation of freshness. It says how old an answer may become under a chosen policy; it does not prove that the source remained unchanged during that interval. State that limitation honestly in the product. A cache used for an informational preview can tolerate different freshness rules from one deciding access rights or financial balances.

Parallel requests add a separate coordination problem

A mutex around a map protects access to the map, but deciding where computation happens remains important. Holding a global lock during an expensive calculation can serialize unrelated keys. Releasing it before calculation allows concurrent misses to compute the same answer more than once. Both designs can be correct, but their resource behavior differs, and neither is a complete policy for a busy service.

Per-key coordination can avoid duplicate work, but then cancellation, failed computations, waiting callers, and removal of in-progress entries need explicit behavior. Do not casually extend the single-threaded examples into a global concurrent cache by adding one wrapper type and assuming the reasoning is finished. Begin with a scoped cache when possible, and introduce shared coordination only when the application actually needs cross-request reuse.

Measure hits, misses and retained size separately

A useful measurement includes the uncached baseline, an empty-cache run, a representative mixed workload, and repeated hits. Report the distribution of keys and the amount of retained data alongside elapsed time. A test that repeatedly requests one already-cached value measures a narrow path; it does not predict startup cost or a workload where every request is new.

Instrumentation should not expose sensitive query contents merely to count hits. Aggregate counters, bounded diagnostics, and anonymized workload shapes can often answer the engineering question. Watch whether the miss rate rises after a capacity reset or revision change. Those transitions explain real latency spikes that disappear in an average assembled from a long stretch of easy repeated hits.

Normalization belongs to the question being cached

Two strings that look similar are not necessarily equivalent queries. Lowercasing, trimming spaces, removing punctuation, or applying Unicode normalization changes the question unless the domain explicitly defines those transformations. If the uncached function treats two inputs differently, a cache must not merge them merely to improve its hit rate. Start with exact keys and introduce normalization only alongside a tested semantic rule.

When normalization is intentional, apply it consistently before both lookup and computation, or include the relevant policy revision in the key. Otherwise a cache can store an answer computed for one representation under a key describing another. Keep fixtures for inputs that should remain distinct as well as inputs that should collapse together. Those pairs are often more revealing than a long list of ordinary repeated requests.

A cache lifetime can be simpler than an eviction algorithm

Sometimes the cleanest limit is scope. A cache owned by one document import can disappear when the import finishes; a cache owned by one immutable analysis session can disappear when the session closes. That design avoids cross-session invalidation and makes retained memory follow an operation the application already understands. It can also make tests more independent because one test's entries never leak into another.

Compare that option with a process-wide cache before adding global state. Global reuse may be valuable, but it introduces questions about user separation, configuration changes, memory pressure, and shutdown behavior. A scoped map can deliver the useful repeated-work savings without requiring answers to all of those questions at once. The correct lifetime is an application design choice, not a property automatically supplied by HashMap.

Cached answers must not cross authorization boundaries accidentally

If an answer depends on who may see the underlying data, that context belongs in the validity design. Sharing a cache entry between users can expose information or return an answer computed under permissions the current caller does not have. Sometimes the correct design is separate caches per authorized dataset rather than adding a user identifier to an otherwise global key.

Check authorization before serving a cached result according to the product's rules, and ensure permission changes invalidate or isolate answers that are no longer appropriate. Do not assume expiration alone provides immediate revocation. The small numeric examples have no accounts or sensitive data, but a real application must revisit that assumption when the same memoization pattern moves from a local calculation into a shared service.

Test equality semantics as carefully as the calculation

Our derived key equality compares both revision and query text. A custom key implementation must preserve a consistent relationship between equality and hashing. Do not compare only a display label while hashing hidden context, and do not mutate answer-changing key data behind a shared reference after insertion. Such designs make lookup behavior difficult to reason about even before cache invalidation enters the picture.

Keep the key small and immutable enough to inspect in a focused test. Construct pairs that should compare equal and pairs that differ in exactly one meaningful field. Then exercise the public cache operation with those pairs rather than relying only on low-level hash output. The promise is semantic reuse for equivalent questions, not a particular hash value that can change across implementations or process runs.

Turn validity rules into small executable checks

Keep tests for repeated identical requests, answer-changing context, errors, disabled storage, and capacity transitions. Add a test proving that two different query strings cannot accidentally share an answer merely because their revisions match. For a cache that stores large values, test the actual resource policy rather than just the number of map entries. These cases express the cache's contract more directly than testing every private helper in isolation.

Memoization succeeds when it preserves the uncached function's meaning while avoiding work under a clearly defined workload. Start with a correct function, a complete key, and a bounded lifetime. Then measure whether reuse pays for the added machinery. The map is the easy part; the useful engineering is knowing exactly when a saved answer is still an answer to the question being asked.