Memoization: a cache with Map

Memoization keeps the result of a function under the arguments that produced it, so the next call with the same arguments returns the stored value instead of doing the work again. It is a cache with a very small key space, and it costs memory for the speed it buys. The idea only works for a pure function: if the same arguments can give different answers, the first answer is the only one that will ever be seen again.

This lesson writes the cache twice, once by hand for one function and once as a wrapper for any function, counts the calls so that the saving is visible, and then goes through the cases where memoization is a bug: a counter, a function that writes something, and a value that changes under the cache. Map is used throughout because it keeps keys of any type apart, which a plain object does not.

A cache with Map

The cache below is a Map from the argument to the result, and the memoized function asks it first. A counter inside the real function reports how many times the calculation ran, which is the number memoization is supposed to reduce.

let calls = 0; function square(n) { calls += 1; return n * n; } const cache = new Map(); function memoSquare(n) { if (cache.has(n)) { return cache.get(n); } const value = square(n); cache.set(n, value); return value; } console.log(memoSquare(4)); console.log(memoSquare(4)); console.log(memoSquare(5)); console.log(memoSquare(4)); console.log('square calls:', calls); console.log('keys in the cache:', cache.size); console.log('a hit returns the same value:', memoSquare(5) === 25);

node cache.js

16
16
25
16
square calls: 2
keys in the cache: 2
a hit returns the same value: true

Four calls, two calculations, two keys. The third call of memoSquare(4) was a hit and never reached square, which is why the counter says two instead of four. The check uses has before get rather than testing the result for undefined, because a function may legitimately return undefined and the cache would then recalculate every time.

A memoize for any function

The wrapper below takes a function and returns a new one with a cache of its own. The key is the argument list serialised with JSON.stringify, so a call of two arguments and the same two arguments swapped are two different keys. The original function is closed over and never touched.

function memoize(fn) { const cache = new Map(); return function memoized(...args) { const key = JSON.stringify(args); if (cache.has(key)) { return cache.get(key); } const value = fn(...args); cache.set(key, value); return value; }; } let calls = 0; function slowSum(a, b) { calls += 1; return a + b; } const memoSum = memoize(slowSum); console.log(memoSum(1, 2)); console.log(memoSum(1, 2)); console.log('calls:', calls); console.log(memoSum(2, 1)); console.log('calls after the swapped arguments:', calls); console.log('the key is the whole argument list:', JSON.stringify([1, 2]) !== JSON.stringify([2, 1]));

node generic.js

3
3
calls: 1
3
calls after the swapped arguments: 2
the key is the whole argument list: true

The second call was a hit and the counter stayed at one. The fourth call returned the same value from a different calculation, because [1, 2] and [2, 1] serialise to different text. A wrapper like this belongs next to the function it wraps and nowhere near a call site, since two wrappers over the same function do not share a cache and neither one knows what the other has stored.

What must not be cached

A memoized function runs once per key, so everything the first call did happens once. That is the saving for arithmetic and the bug for anything else. The program below memoizes a counter and gets the same number three times, then memoizes a login that writes to a counter outside itself and finds that the second call never ran.

function memoize(fn) { const cache = new Map(); return function memoized(...args) { const key = JSON.stringify(args); if (cache.has(key)) { return cache.get(key); } const value = fn(...args); cache.set(key, value); return value; }; } let counter = 0; function next() { counter += 1; return counter; } const memoNext = memoize(next); console.log(memoNext()); console.log(memoNext()); console.log(memoNext()); console.log('the counter really moved:', counter); let logins = 0; function login(name) { logins += 1; return `session-${name}`; } const memoLogin = memoize(login); console.log(memoLogin('ada')); console.log(memoLogin('ada')); console.log('logins:', logins);

node not.js

1
1
1
the counter really moved: 1
session-ada
session-ada
logins: 1

Three calls of next produced one increment, because the other two were hits: the function is impure and the cache froze its first answer. The login is the subtler case, since the answer looks stable and the side effect behind it is the point: a session that is created once and returned three times is not three logins. The rule is short: memoize a function only when the answer depends on the arguments alone, and count the calls of a suspected function before and after the wrapper.

The key is the whole argument list

A cache keyed on an object has two problems. The object is a key by identity, so a second object with the same content is a miss, and a read through the cache keeps the object alive. The Map below uses the object itself, and the first call keeps the result for ever while the object changes.

const user = { name: 'ada' }; const byObject = new Map(); function greet(person) { if (byObject.has(person)) { return byObject.get(person); } const text = `Hello, ${person.name}`; byObject.set(person, text); return text; } console.log(greet(user)); user.name = 'grace'; console.log(greet(user)); console.log('still the old text:', greet(user) === 'Hello, ada'); const byName = new Map(); function greetByName(name) { if (byName.has(name)) { return byName.get(name); } const text = `Hello, ${name}`; byName.set(name, text); return text; } console.log(greetByName(user.name)); user.name = 'alan'; console.log(greetByName(user.name)); console.log('the name is the key:', byName.size);

node keys.js

Hello, ada
Hello, ada
still the old text: true
Hello, grace
Hello, alan
the name is the key: 2

The second call returned the old sentence from the cache, and no amount of changing the object will move it. The second cache keys on the string, which is a value rather than a reference, so a changed name is a new key and gets its own answer. The same distinction is why the lesson on copying separates primitives from objects: a primitive key is compared by value, and an object key by identity.

Exercises

  1. Remove the has check from memoSquare in cache.js and test the stored value with cache.get(n) !== undefined. Which case is then computed twice?
  2. Call memoSum in generic.js with a string and a number. What is the key, and what does the cache store?
  3. Memoize greet from keys.js with the wrapper of generic.js and change the name between two calls. Which line of the output would the wrapper print?
  4. Add memoNext() a fourth time in not.js and print the counter again. What do the two numbers say about the cache?
  5. Give memoize a second parameter that limits the cache size to two entries. Which function of the Map removes the oldest key, and what happens to the third distinct call?

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What does memoization store?

    Answer

    The result of a call under the arguments that produced it

    A cache maps the argument list to the result, so a repeated call can skip the work.

  2. Which function must not be memoized?

    Answer

    One whose result changes or whose side effect is the point

    A second call with the same arguments would return the first answer and skip the effect entirely.

  3. What does this program print? const cache = new Map(); let calls = 0; function f(n) { if (cache.has(n)) return cache.get(n); calls += 1; cache.set(n, n * 2); return n * 2; } console.log(f(2), f(2), calls);

    Answer

    4 4 1

    The second call is a hit, so the counter stays at one while both calls return the same four.

  4. Why is a Map preferred to a plain object for a cache keyed on numbers and strings?

    Answer

    It keeps the types of its keys apart and has no inherited keys

    An object turns every key into a string and brings its prototype with it, while a Map keeps 1 and "1" as two keys.

  5. What does this program print? let n = 0; function next() { n += 1; return n; } const cache = new Map(); function memo() { if (!cache.has("x")) cache.set("x", next()); return cache.get("x"); } console.log(memo(), memo(), n);

    Answer

    1 1 1

    The second call is a hit and the counter behind the function moved only once.

  6. What does this program print? const cache = new Map(); function f(a, b) { const k = JSON.stringify([a, b]); if (!cache.has(k)) cache.set(k, a + b); return cache.get(k); } console.log(f(1, 2), f(1, 2), cache.size);

    Answer

    3 3 1

    Both calls serialise to the same key, so the second is a hit and the cache holds one entry.

  7. What does this program print? const cache = new Map(); cache.set(1, "number"); cache.set("1", "string"); console.log(cache.size);

    Answer

    2

    A Map compares keys with the SameValueZero rule, so the number and the text are two different keys.

  8. Why does a cached function that writes a log line stop writing it?

    Answer

    The stored result is returned before the body runs again

    A hit returns the stored value, so everything in the body, including the side effect, is skipped.

  9. Why can a cache keyed on an object return a stale answer?

    Answer

    The key is the identity of the object, and its fields may change while the entry stays

    The same object keeps its entry, so a change inside it is invisible to a cache that only compares the reference.

  10. When is memoization worth its memory?

    Answer

    When a pure function is called repeatedly with the same arguments

    The saving comes from a repeated call with the same key, and a pure function makes the stored answer safe to reuse.

The code on this page was run with Node.js 24.22.1 and linted with ESLint 10.14.0 on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev

Banner image