Frontend Beauty
ESC

Type to search the knowledge base.

Memoize Function

Cache a function by arguments. Map keys vs JSON.stringify collisions, resolver functions, cache clear, and why this-bound methods need care.

intermediate5 min read
  • javascript
  • memoize
  • performance
  • interview

A memoize function that keys the cache with JSON.stringify(args) looks fine on (2, 3) and then lies. { a: 1, b: 2 } and { b: 2, a: 1 } miss each other. [undefined] and [null] share a slot because stringify writes null in arrays. A new object with the same fields hits a previous call even though the caller passed a different reference. Then someone wraps Math.random or a fetch and the cache serves a stale side effect forever.

Memoization is “same inputs, same output, skip the work.” That sentence is only true for a pure function. The interview is the cache key, this, and clear. Once is a different tool: one call, arguments ignored after that. React useMemo is a different tool: a render-time recompute gate, not a map from arguments to results.

Key takeaways

  • A single-argument Map is honest: object keys are identity. Two { x: 1 } literals miss.
  • JSON.stringify multi-arg keys collide on key order, on undefined vs null, and they drop functions.
  • Pass a resolver so the caller chooses the key. Expose cache.clear.
  • Do not memoize impure functions: clocks, random, I/O, in-place mutation.
  • The wrapper is a function, not an arrow, and it calls fn.apply(this, args).

Cache by arguments, and the Map vs JSON.stringify key trap

Map compares keys with SameValueZero. That is perfect when the memoized function takes one value and you want identity: the same object in, the cached result out. A different object with the same shape is a miss. That is usually what you want for DOM nodes, request controllers, and records you already interned.

function memoize(fn, resolver) {
  const cache = new Map();

  function memoized(...args) {
    const key = resolver
      ? resolver.apply(this, args)
      : args.length === 1
        ? args[0]
        : defaultKey(args);

    if (cache.has(key)) {
      return cache.get(key);
    }

    const result = fn.apply(this, args);
    cache.set(key, result);
    return result;
  }

  memoized.cache = cache;
  memoized.clear = () => cache.clear();
  return memoized;
}

function defaultKey(args) {
  throw new TypeError(
    'memoize: pass a resolver for 0 or 2+ arguments; Map identity only works for one'
  );
}

That default is strict on purpose. Silently JSON.stringifying a rest parameter is how the collisions below ship.

Why JSON.stringify is a bad default key

Inputs JSON.stringify(args) What you wanted
{ a: 1, b: 2 } vs { b: 2, a: 1 } different strings, cache miss same fields, maybe a hit if the fn is structural
[undefined] vs [null] '[null]' for both, cache hit different values
[1, undefined] vs [1, null] same different
object with a method method omitted either a miss or a throw, not silent drop
n = 0 vs empty args, if you stringify poorly easy to collide with '[]' / other sentinels distinct 
JSON.stringify([undefined]); // '[null]'
JSON.stringify([null]); // '[null]'
JSON.stringify({ a: 1, b: 2 }) === JSON.stringify({ b: 2, a: 1 }); // false

If the interviewer wants a structural key, provide a resolver they can see:

const keyOfUser = (user) => user.id;

const loadUser = memoize(async function loadUser(user) {
  return db.find(user.id);
}, keyOfUser);

user.id as a primitive Map key is stable across object identity. Two { id: 7 } records now share work. That is the point of a resolver: you name the equality you mean.

A resolver that returns JSON.stringify(args) is allowed if you say the collisions out loud and the arguments are primitives in a fixed order.

this, methods, and arrows

const counter = {
  n: 0,
  inc(k) {
    this.n += k;
    return this.n;
  },
};

counter.inc = memoize(counter.inc);
counter.inc(1); // this is counter, because the wrapper is a method call

The wrapper must be a function so this comes from the call site (this binding, apply). An arrow wrapper would lock this to the module. fn.apply(this, args) is the whole trick. Memoizing an already-bound function is fine: bound this wins inside fn.

Do not memoize inc anyway. It mutates. The cache would freeze n at the first return.

Impure functions and promises

Memoize is a correctness footgun before it is a performance win.

  1. Date.now, Math.random, performance.now: the first call’s value sticks.
  2. Functions that write to a store or to the DOM: skipped calls skip the write.
  3. fetch / any I/O: you may want in-flight dedupe, which is memoizing the promise. A rejection stays in the cache unless you delete on catch. Say the policy: cache fulfillments only, or cache the promise including reject, or cache with a TTL.
  4. Recursion (fib(n) = fib(n-1) + fib(n-2)): memoize is the usual demo. Still pure.
function memoizePromise(fn, resolver) {
  const memoized = memoize(function (...args) {
    return Promise.resolve(fn.apply(this, args)).catch((err) => {
      memoized.cache.delete(resolver ? resolver.apply(this, args) : args[0]);
      throw err;
    });
  }, resolver);
  return memoized;
}

Unbounded cache is a leak. clear is the minimum API. An LRU (maxSize, delete the oldest Map key) is extra credit; Map iterates in insertion order, so cache.keys().next().value is the oldest if you set only on miss (re-set on hit if you want true LRU).

The conceptual page is memoization. This page is the interview contract: identity vs stringify, resolver, this, purity.

Procedure

  1. Ask whether arguments are compared by identity or by structure.
  2. One object/primitive: Map, key is args[0].
  3. Several arguments or a record: caller-supplied resolver.
  4. Wrapper: function, apply, cache.has / set.
  5. Expose clear. Refuse to memoize an impure fn unless they explicitly want dedupe.

Interview answer (out loud)

For one argument I use a Map so objects compare by identity. JSON.stringify as a multi-arg key collides: object key order misses, undefined in an array becomes null, functions disappear. I take a resolver and I expose cache.clear. The wrapper is a plain function that applys the original this. I will not memoize an impure function. If they want fetch dedupe I cache the promise and I say whether a rejection stays.

Further reading

Related guides