Skip to content

Memoization

Caching tool — instantiates Demand-Triggered Deferred Evaluation

Stores the result of a computation keyed by its inputs, so a repeat call with the same inputs returns the saved value instead of recomputing it.

Memoization is the store-and-reuse end of demand-triggered evaluation. The first time a value is demanded it is computed normally; the result is then filed under a key derived from the inputs, and every later demand for the same inputs is answered from that store rather than run again. Its defining move is deduplication across time: it collapses repeated identical work into one computation plus cheap lookups. That is a different job from suspending the first computation until it is needed (a thunk) and from collapsing concurrent duplicate demands into one in-flight run (single-flight) — memoization assumes the work will run at least once and concerns itself only with never running it twice for the same inputs. Everything that makes it tricky lives in three questions: what the key is, where the store lives, and when a stored answer has gone stale.

Example

A logistics planner calls road_distance(origin, destination), which runs an expensive shortest-path search over a national road graph. The same warehouse-to-store pairs are queried thousands of times a day. Wrapping the function in memoization files each computed distance under its (origin, destination) key; the first query for a pair pays the full search, and the millionth is a dictionary hit in microseconds.

The subtlety shows up when a bridge closes. The road graph now has a version — call it generation 47 — and any distance computed against generation 46 is silently wrong. So the memo store keys on (origin, destination, graph_version): the closure bumps the version token, the stale entries simply stop matching, and new demands recompute against the new graph while everything untouched keeps serving from cache. The output is the same numbers the bare function would return, minus almost all of the recomputation — and without the classic hazard of a cache still answering from a map of a road that no longer exists.

How it works

  • Key derivation. Reduce the inputs to a canonical key. The key must be total over everything that affects the result — miss a hidden input (a locale, a global flag, the graph version) and the cache will confidently return wrong answers.
  • The store. A keyed map with a size bound and an eviction policy (LRU is the default); it may be per-process, shared across a fleet, or persisted to disk.
  • Invalidation. Decide when an entry stops being valid: a time-to-live, an explicit event, or a version token that changes when the underlying world does.
  • Purity assumption. Memoization is correct only when the function is a pure function of its key; the whole mechanism rests on that.

Tuning parameters

  • Key granularity — how finely inputs map to keys. Coarser keys raise the hit rate but risk merging inputs that should differ; finer keys are safer but colder.
  • Store size and eviction — the memory budget and which entries to drop first. A bigger store lifts hit rate until memory pressure or staleness dominates.
  • Invalidation strategy — TTL vs. version token vs. explicit event. TTL is simplest; a version token is exact but needs a real version to track; events are precise but easy to forget to fire.
  • Scope — per-call, per-process, or shared across nodes. Wider scope multiplies reuse but adds coherence and invalidation cost.

When it helps, and when it misleads

Memoization pays off exactly when a pure, expensive function is called repeatedly with a repeating set of inputs — high hit rate, stable answers. It turns quadratic recomputation into near-constant lookup, and it is the store that a single-flight fill or a lazy evaluator ultimately populates.

It misleads in three familiar ways. Memoizing an impure function — one whose result depends on inputs not in the key (the clock, a mutable global, the road graph you forgot to version) — caches a lie and serves it forever; this is the practical face of the maxim that cache invalidation is one of the genuinely hard problems. An unbounded store is a memory leak wearing a performance costume. And a low hit rate buys nothing but the cache's own overhead. The classic misuse is caching a value whose key does not actually capture all of its inputs, so correctness quietly degrades while the dashboards stay green. The discipline: memoize only referentially-transparent functions,[1] make the key total over every input, and pair every store with an explicit size bound and invalidation rule rather than treating "cache it" as free.

How it implements the components

  • memoized_result_store — the keyed store of realized results is the mechanism: computed once, read many.
  • invalidation_rule — the TTL / event / version logic that decides when a stored answer may no longer be served.
  • version_token — the generation stamp folded into the key, so a change in the underlying world retires stale entries without a manual purge.

It does NOT coordinate concurrent first-fills — that duplicate-suppression across simultaneous callers is single_flight_and_duplicate_suppression_rule / result_sharing_policy, owned by Single-Flight Request Coalescing — and it does NOT model the suspended first computation as a reusable unit (deferred_work_unit, suspended_evaluation_state), which is the Thunk or Lazy Promise.

Notes

Memoization and Single-Flight Request Coalescing are often conflated because both "avoid recomputation," but they deduplicate on different axes — memoization across time (a later caller reuses a stored result), single-flight across concurrency (simultaneous callers share one in-flight run). They compose cleanly: single-flight fills the memo store exactly once even under a stampede, and memoization serves it thereafter.

References

[1] A function is referentially transparent if it can be replaced by its result without changing program behaviour — it depends only on its inputs and has no observable side effects. Memoization is sound precisely for such functions; applying it to an impure one is the root of most memoization bugs. ↩