Learn JS Series (#29) - Memoization: Trading Memory for Speed with Closures

scipio(71)

Published in

StemSocial

Words

2950

Reading

14 min

Listen

Play

17h

Learn JS Series (#29) - Memoization: Trading Memory for Speed with Closures

What will I learn

You will learn what memoization is: caching a function's results so repeat calls are instant;
why it only works safely for pure functions, and how that connects directly to last episode;
how to write a memoized function by hand with a closure and a private cache;
how to build a generic memoize higher-order function that wraps any pure function;
how cache keys actually work, and the traps that come with JSON.stringify and object arguments;
the trade-offs: memory versus speed, bounded caches, and where memoization helps and where it hurts.

Requirements

A working modern computer running macOS, Windows or Ubuntu;
An installed Node.js (20+) distribution, or just a modern browser console;
Episodes 1-28 read, especially closures, higher-order functions, and pure functions.

Difficulty

Intermediate

Curriculum (of the `Learn JS Series`):

Learn JS Series (#29) - Memoization: Trading Memory for Speed with Closures

Solutions to Episode 28 Exercises

Exercise 1 - pure or impure:

const a = (n) => n * 2;              // PURE: same input, same output, no effects
const b = (arr) => arr.sort();      // IMPURE: sort mutates the input array
const c = () => new Date().getHours(); // IMPURE: depends on the clock (external, changing)

The insight: sort mutates its argument, and reading the current time depends on external state, so only the first is pure.

Exercise 2 - a pure discount:

function discount(cart) {
  return { ...cart, total: cart.total * 0.9 }; // new object, original untouched
}
const cart = { total: 100 };
console.log(discount(cart)); // { total: 90 }
console.log(cart);           // { total: 100 } - unchanged

The insight: spreading into a new object and overriding total avoids mutating the caller's cart.

Exercise 3 - pure core, impure shell:

const bigDoubled = (prices) => prices.filter((p) => p > 50).map((p) => p * 2); // pure
function report(prices) {
  console.log(bigDoubled(prices)); // the only side effect, at the edge
}
report([30, 60, 90]); // [120, 180]

The insight: the pure core is testable by comparing input to output with no setup, while the shell isolates the single logging effect.

Last episode I closed with a promise I made a point of not cashing yet. I said a pure function is cacheable -- because it always returns the same output for the same input, you can remember what it returned last time and skip the work entirely on a repeat call. That is memoization, and today we collect on that promise properly. It is one of my favourite topics in the whole phase, because it is not some abstract functional-programming curiosity: it is a concrete, measurable performance technique that falls out almost for free once you have closures (episode 17), higher-order functions (episode 18), and purity (episode 28) in your toolbox. Everything Phase 2 taught, converging on one genuinely useful pattern. Let's build it up carefully.

What memoization actually is

Memoization is an optimization technique: you cache (remember) the result of a function call, so that if the function is ever called again with the same arguments, you return the stored result instantly in stead of recomputing it. The word comes from "memo" -- the function keeps a little memo of what it has already worked out, and consults that memo before doing any real work.

The core idea is embarrassingly simple, and that simplicity is exactly why it is worth mastering. You keep a cache (usually a Map, sometimes a plain object) keyed by the arguments. On each call you check the cache first: if the answer is already there, hand it straight back; if it is not, compute it the slow way, store it in the cache, and then return it. The second time round, the slow path never runs. Here is a memoized square-root by hand, using a closure to hold the private cache so nothing on the outside can tamper with it:

function makeMemoizedSqrt() {
  const cache = new Map(); // private cache, lives in the closure
  return function (n) {
    if (cache.has(n)) {
      console.log(`cache hit for ${n}`);
      return cache.get(n);
    }
    console.log(`computing for ${n}`);
    const result = Math.sqrt(n);
    cache.set(n, result);
    return result;
  };
}

const sqrt = makeMemoizedSqrt();
console.log(sqrt(16)); // "computing for 16", then 4
console.log(sqrt(16)); // "cache hit for 16", then 4 - no recompute
console.log(sqrt(25)); // "computing for 25", then 5

Read the log output and the whole mechanism is right there. The first sqrt(16) prints "computing for 16" and does the real work. The second sqrt(16) prints "cache hit for 16" and returns the stored 4 without ever calling Math.sqrt again. The cache survives between calls precisely because it lives in the closure -- this is the exact "private state that persists" pattern we met back in episode 17, put to real work. That, in its purest form, is memoization: a function with a memory.

Notice Math.sqrt is a poor real-world target (it is already lightning fast), so here the logging is the point, not the speed win. In real code you memoize things that are actually expensive. But the shape of the code never changes: check the cache, compute on a miss, store, return.

Why it only works for pure functions

This is the crucial connection to last episode, and now you can see exactly why purity was not just some tidy-minded discipline. Memoization is only safe for pure functions, full stop. A pure function returns the same output for the same input, always -- today, tomorrow, on your machine, on mine. That guarantee is precisely what makes caching correct: if f(16) gave 4 a moment ago, it will still give 4 now, so returning the cached value is provably identical to recomputing it. The cache can never lie, because the function itself never changes its mind.

For an impure function this whole edifice collapses. If a function leans on external state (the clock, a global, a database, a random number), the same input can produce different outputs over time, and a cached result becomes a stale, silent bug:

// DO NOT memoize this: same input, DIFFERENT output over time
let discountRate = 0.1;
function priceWithDiscount(price) {
  return price * (1 - discountRate); // depends on the external 'discountRate'
}
// Suppose you cache priceWithDiscount(100) = 90.
// Later, discountRate changes to 0.2 somewhere else in the app.
// A memoized version would keep returning the stale 90 forever. Wrong!

So the rule is firm, and it is worth burning into your memory: memoize pure functions freely; never memoize a function whose output can change for the same input. Purity here is not a nice-to-have -- it is the precondition that makes the optimization valid at all. This is why I made such a fuss last episode about spotting impurity at a glance. That skill is not academic; it is exactly the check you run in your head before you dare wrap a function in a cache. Reach for memoization on an impure function and you have not sped your program up, you have introduced a bug that only shows up after state changes -- the nastiest kind to track down.

A generic memoize helper

Writing a bespoke cache for every single function, as we did for sqrt, gets tedious fast, and repetition is a smell. Since memoization is fundamentally a wrapper around a function -- take a function, return an enhanced version of it -- it is a textbook job for a higher-order function (episode 18). Let's build one generic memoize that turns any pure function into a cached version, once, and reuse it everywhere:

function memoize(fn) {
  const cache = new Map();
  return function (...args) {
    const key = JSON.stringify(args); // turn the arguments into a cache key
    if (cache.has(key)) return cache.get(key);
    const result = fn(...args);
    cache.set(key, result);
    return result;
  };
}

const slowAdd = (a, b) => {
  for (let i = 0; i < 1e7; i++) {} // pretend this is genuinely expensive work
  return a + b;
};
const fastAdd = memoize(slowAdd);
console.log(fastAdd(2, 3)); // slow the first time - does the loop
console.log(fastAdd(2, 3)); // instant the second time - straight from cache

The heart of this is the rest parameter ...args (episode 20) collecting every argument into an array, plus the trick of turning that array into a single cache key. Because a Map keyed on the raw array would never hit (two different arrays are never === equal, even with identical contents -- remember reference semantics from episode 12), we serialize the arguments into a string with JSON.stringify(args). Now [2, 3] becomes the string "[2,3]", and that compares reliably. One memoize now wraps any pure function you like and makes every repeat call effectively free. That is the higher-order-function payoff in a nutshell: write the caching logic once, apply it to a hundred functions.

The cache key is where the bodies are buried

That JSON.stringify(args) line looks innocent, but it is doing quite some heavy lifting, and it has sharp edges you need to know about before you trust it in production. The key must be a value that (a) is the same string for arguments you consider "the same", and (b) is a different string for arguments you consider "different". JSON.stringify gets that right for numbers, strings, booleans, and plain arrays and objects with a stable key order. It gets it wrong, or refuses entirely, in a few cases worth seeing:

// 1) Object key ORDER changes the string, so these two "equal" calls miss each other:
JSON.stringify({ a: 1, b: 2 }); // '{"a":1,"b":2}'
JSON.stringify({ b: 2, a: 1 }); // '{"b":2,"a":1}'  -> different key, no cache hit

// 2) Functions and undefined silently vanish or break the key:
JSON.stringify([function () {}]); // '[null]'  -> two different fns collide!

// 3) It cannot serialize a BigInt or a circular structure at all (throws)

None of this means JSON.stringify is bad -- for the overwhelmingly common case of numeric and string arguments it is perfectly serviceable, and I reach for it constantly. But you should know its limits so you are not baffled when a cache mysteriously never hits (probably object key order) or two distinct calls collide (probably a function argument). For single-primitive-argument functions there is an even simpler and faster option: skip the stringify and key the Map directly on the argument itself, exactly as we did in makeMemoizedSqrt. The right key strategy depends on the shape of your arguments, and choosing it well is most of the craft of writing a good memoize.

The classic win: expensive recursion

Memoization's most famous demonstration -- the one in every textbook, and for good reason -- is the naive recursive Fibonacci. Written the obvious way, it recomputes the same sub-results an astronomical number of times, because each call branches into two more, which each branch into two more, and so on. fibSlow(40) triggers well over a billion calls, and every one of them re-derives values it has already computed a thousand times over. Memoized, the same fib(40) makes about forty real computations. Watch:

// naive: catastrophically re-computes the same values, exponential time
function fibSlow(n) {
  if (n < 2) return n;
  return fibSlow(n - 1) + fibSlow(n - 2);
}

// memoized: each fib(k) is computed exactly once, then served from cache
function makeFib() {
  const cache = new Map();
  return function fib(n) {
    if (n < 2) return n;
    if (cache.has(n)) return cache.get(n);
    const result = fib(n - 1) + fib(n - 2);
    cache.set(n, result);
    return result;
  };
}
const fib = makeFib();
console.log(fib(40)); // 102334155 - near-instant, ~40 real computations

The magic is subtle and beautiful: the recursive fib calls itself through the cache, so the moment fib(38) has been computed once, every later call that needs it is a free lookup. That single change turns an exponential-time disaster into a linear-time function, without touching the algorithm's logic at all -- purely by remembering. This is the poster child for memoization: a pure function with heavily overlapping repeated sub-work. When your expensive function keeps being asked the same sub-questions, caching the answers is transformative. When it never repeats itself, as we will see, caching buys you nothing.

How other languages handle this

Since quite some of you came in from the Learn Python Series (with a handful of Rust readers along for the ride), a look sideways nails the idea down -- memoization is a universal concept, not a JavaScript trick.

Python does not even make you write the wrapper. The standard library ships functools.lru_cache (and the simpler functools.cache), a decorator that memoizes any function for you, with a bounded size built in. What we just hand-rolled, Python gives you as a one-liner:

from functools import lru_cache

@lru_cache(maxsize=None)   # None = unbounded, like our plain Map
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(40))   # 102334155, near-instant - the decorator caches every call

Same idea, same purity requirement (the Python docs spell out that the function should be pure), just handed to you pre-built. The lru_cache name is a hint at something we are about to discuss: the "LRU" means least-recently-used eviction, a strategy for keeping the cache from growing without bound.

Rust takes the ideas we care about (predictability, controlling shared mutable state) and bakes them into the compiler, but memoization itself is still just a cache you write, typically with a HashMap:

use std::collections::HashMap;

fn fib(n: u64, cache: &mut HashMap<u64, u64>) -> u64 {
    if n < 2 {
        return n;
    }
    if let Some(&cached) = cache.get(&n) {
        return cached;
    }
    let result = fib(n - 1, cache) + fib(n - 2, cache);
    cache.insert(n, result);
    result
}

fn main() {
    let mut cache = HashMap::new();
    println!("{}", fib(40, &mut cache)); // 102334155
}

Notice Rust forces you to pass the cache explicitly as &mut -- the language makes the mutable state visible and controlled rather than tucking it away in a closure. That is the same private-cache idea we used, just with Rust's insistence that mutation be spelled out loud. The portable lesson across all three languages: cache the results of pure, repeat-heavy work, and mind how big that cache is allowed to grow. Which brings us neatly to the catch.

The trade-offs (memoization is not free)

Here is the honest part, because I would be selling you a half-truth if I made memoization sound like pure upside. It trades memory for speed. Every result you cache stays in memory for as long as the cache is alive. A function memoized with our plain unbounded Map and then called with thousands upon thousands of distinct inputs will happily hold onto every single one of them -- a slow, invisible memory leak dressed up as an optimization. That is a real problem we will revisit properly when we get to memory and the engine internals in Phase 7.

The professional fix is a bounded cache: cap how many entries you keep, and evict the oldest (or least-recently-used) when you hit the ceiling. A tiny sketch of the idea, exploiting the fact that a JS Map remembers insertion order:

function memoizeBounded(fn, maxSize = 100) {
  const cache = new Map();
  return function (...args) {
    const key = JSON.stringify(args);
    if (cache.has(key)) return cache.get(key);
    const result = fn(...args);
    cache.set(key, result);
    if (cache.size > maxSize) {
      const oldest = cache.keys().next().value; // first inserted key
      cache.delete(oldest);                      // evict it to cap memory
    }
    return result;
  };
}

This is a crude version of what Python's lru_cache(maxsize=...) does for you. It stops the cache from growing forever, at the cost of occasionally re-computing something that got evicted. That is the whole game: you are constantly trading memory against speed, and a bounded cache lets you pick where on that line you want to sit.

So weigh it honestly, every time:

Memoize when the function is pure, expensive to compute, and called repeatedly with the same inputs. Then the memory cost buys you a large, real speed win. Fibonacci, expensive parsing, costly derived data from the same records -- perfect candidates.
Do NOT memoize when the function is cheap (the cache lookup and key-building can cost more than just recomputing -- memoizing (x) => x + 1 is pure theatre), when inputs are almost always unique (the cache never hits, so you pay memory for nothing and never collect a win), or when the function is impure (the cache would be silently wrong).

// GOOD candidate: pure, expensive, and hammered with repeat inputs
// e.g. an expensive pure parse of the same handful of config strings

// BAD candidate: trivial and/or always-fresh inputs
const addOne = (x) => x + 1;        // too cheap to bother caching
const idOf = (user) => user.id + Date.now(); // impure AND ever-unique - never do this

Having said that, the meta-rule is the same one that governs every optimization in this series, and it is the one I will keep hammering: measure first. Memoization applied where a profiler shows a genuine hot spot with repeated inputs is a beautiful, cheap win. Memoization sprinkled everywhere "just in case" is wasted memory and added complexity that makes your code slower and harder to read. Reach for it deliberately, not reflexively. Used with judgment, it is a lovely little demonstration of closures, higher-order functions, and purity all clicking together into one practical tool -- the forementioned convergence of everything Phase 2 has been building toward. ;-)

Try it yourself

Three exercises, increasing in difficulty. Try to reason each one through before you run it -- full solutions open the next episode.

Write a memoized factorial using a closure and a Map cache. Call it with 5, then 6, and add logging so you can see that computing 6 reuses the cached 5! in stead of recomputing the whole product from scratch (structure the recursion so factorial(6) calls factorial(5) through the cache).
Implement the generic memoize(fn) helper and wrap a function slowSquare(n) that loops a lot before returning n * n. Log a timestamp before and after each call and show that the first call with a given argument is slow while the second call with the same argument is effectively instant.
Explain, with a concrete example, why memoizing a function that returns Math.random() or reads the current time would be a bug. Then give one example of a function that is a perfect memoization candidate and say, in one sentence, exactly why it qualifies (pure? expensive? repeated inputs?).

So what did we actually cover?

Memoization caches a function's results keyed by its arguments, returning the stored result instantly on repeat calls -- a function with a memory.
It only works safely for pure functions, because only they guarantee the same output for the same input, which is exactly what makes a cached value correct rather than stale.
You build it by hand with a closure holding a private cache (a Map), checking the cache before doing any real work.
A generic memoize(fn) higher-order function wraps any pure function, commonly keying the cache with JSON.stringify(args) -- which is fine for primitives but has real traps around object key order, functions, and BigInt.
The classic win is expensive, overlapping recursion like Fibonacci, where remembering sub-results turns exponential work into linear.
Other languages agree: Python hands you functools.lru_cache, Rust uses an explicit HashMap; the concept is universal.
It trades memory for speed. Bound the cache (LRU-style eviction) for unbounded input spaces, and only memoize pure, expensive, repeat-called functions -- never cheap ones, unique-input ones, or impure ones. Measure first.

Next episode we close Phase 2 with a mini-project: we roll everything from this whole phase -- first-class functions, closures, higher-order functions, currying, composition, purity, and memoization -- into one small, reusable functional toolkit of our own. No new theory, just the satisfying part where the pieces snap together into something you would genuinely reach for.