All topics
89 / 100
Performanceintermediate

Memoization and Caching Strategies

Storing the results of expensive function calls keyed by their arguments, so repeated calls with the same input can return a cached result instantly.

Memoisation caches a function's result by its arguments.

Memoization is like a chef who, instead of re-cooking an entire dish from scratch every single time a specific order comes in, keeps a small stash of a few recently prepared dishes on standby — if the exact same order comes in again while that stash entry is still fresh, it goes straight out from the stash instead of back through the whole cooking process again.

Key Concepts

1
    function memoize(fn) {
      const cache = new Map();
      return (...args) => {
        const key = JSON.stringify(args);
        if (cache.has(key)) return cache.get(key);
        const result = fn(...args);
        cache.set(key, result);
        return result;
      };
    }
2
It is only correct on a pure function. Same input, same output, no side effects. Memoising something that reads changing state returns a stale answer forever.
3
The effect can be dramatic.
    const fib = memoize(n => n <= 1 ? n : fib(n - 1) + fib(n - 2));
4
    fib(40) unmemoised   ~1.6 billion calls
    fib(40) memoised     40 calls
5
Not because recursion was slow — because the same subproblems were recomputed.
6
The key function is where implementations differ.
    JSON.stringify(args)     simple; slow for large arguments,
                             and wrong for objects with different
                             key order
    args[0]                  fine when there is one primitive argument
    a WeakMap                keyed by object identity
7
{a:1,b:2} and {b:2,a:1} stringify differently and are the same input, which is the flaw in the general approach.
{a:1,b:2}{b:2,a:1}
8
Unbounded caches leak. A Map that only grows will eventually be the largest thing in the process.
Map
9
    an LRU with a size limit
    a TTL, so entries expire
    a WeakMap, so entries vanish with their key
10
Where you already use it.
    React.memo            skip a re-render when props are unchanged
    useMemo               recompute only when dependencies change
    reselect              memoised selectors over Redux state
11
When it is not worth it. A cheap function — the lookup and the key construction can cost more than recomputing. Arguments that are almost always different, so the hit rate is near zero. And anything whose result can go stale.
12
The measurement to take first. Memoisation trades memory for time. Both are measurable, and adding it without measuring the hit rate is how a cache ends up costing more than it saves.
13
What the interviewer is probing.1. "What makes a function safe to memoise?" Probing: the precondition. Stalls: "Any function." Moves up: purity — same input, same output, no side effects; otherwise the cache returns a stale or wrong result.
14
2. "What is the risk of an unbounded cache?" Probing: the leak. Stalls: "None." Moves up: it grows forever, which is a memory leak; bound it with an LRU or a WeakMap keyed by object.
15
3. "How do you key a cache on object arguments?" Probing: the problem. Stalls: "JSON.stringify." Moves up: a WeakMap keyed by identity, since stringify is slow, order-dependent and breaks on cycles.
16
4. "When does memoisation not pay?" Probing: judgement. Stalls: "It always pays." *Moves up:* when the computation is cheaper than the lookup and hashing, or when inputs rarely repeat.
Use cases:performanceoptimizationfunctions