Memoization & laziness

Save work, delay work

Some work is slow, like a long calculation or a request to a server. This lesson shows two ways to do less of it:

• Save the answer. If you already worked something out, keep the answer and use it again.
• Wait until it is needed. Don't work something out until your code asks for it.

This lesson uses ideas from earlier lessons: pure functions, closures, Map & Set, WeakMap & WeakSet, generators, and iterator helpers. Each one is explained again when it shows up.

Let's build a helper called memoize. You give it a function. It gives back a new function, called a wrapper. The wrapper does the same job, but it saves its answers.

The wrapper keeps its answers in a Map. A Map stores pairs: a key and a value. Here the key is the argument, and the value is the answer for that argument.

Each time you call the wrapper, one of two things happens:

• A cache hit: the key is already in the Map. The wrapper returns the saved answer. The original function does not run.
• A cache miss: the key is not there yet. The wrapper calls the original function, saves the answer under the key, and returns it.

The Map is made once, inside memoize. The wrapper is a closure: a function that still remembers the variables around it. So the same Map stays alive from one call to the next.

The example uses Fibonacci numbers. Each one is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8. So fib(6) is 8. A plain recursive fib works out the same smaller numbers again and again.

To show the saving, the code counts how often the real function body runs, in a variable called calls. A count is the same on every computer, so it is better proof than a stopwatch.

• Plain recursion: fib(6) runs the body 25 times.
• Memoized: fib(6) runs the body 7 times, once for each key from 0 to 6.
• A second memoized fib(6) runs the body 0 more times, because it is a cache hit.

1function memoize(fn) {Run2  const cache = new Map();3  return function memoized(arg) {4    if (cache.has(arg)) return cache.get(arg);5    const result = fn(arg);6    cache.set(arg, result);7    return result;8  };9}10 11let calls = 0;12let fib;13fib = memoize((n) => {14  calls++;15  return n < 2 ? n : fib(n - 1) + fib(n - 2);16});17 18console.log(fib(4));19console.log(calls);20console.log(fib(4));21console.log(calls);

function memoize(fn) {
  const cache = new Map();
  const memoized = (key) => {
    if (cache.has(key)) return cache.get(key);
    const result = fn(key);
    cache.set(key, result);
    return result;
  };
  memoized.clear = () => cache.clear();
  return memoized;
}

let taxRate = 0.1;
const total = memoize((price) => Math.round(price * (1 + taxRate)));
console.log(total(100));
taxRate = 0.2;
console.log(total(100));
total.clear();
console.log(total(100));

The total function reads taxRate, but taxRate is not one of its arguments. That makes it a hidden input.

1. Line 15 prints 110: 100 plus 10% tax.
2. Line 16 changes the tax to 20%.
3. Line 17 still prints 110. The key is still 100, so it is a cache hit, and the old answer comes back.
4. Line 18 empties the cache with the clear method that line 9 added.
5. Line 19 is now a miss. It works out the total again and prints 120.

In a real app, clear the cache whenever the data behind it changes.

function memoize(fn) {
  const cache = new Map();
  return (key) => {
    if (cache.has(key)) return cache.get(key);
    const result = fn(key);
    cache.set(key, result);
    return result;
  };
}

let visits = 0;
const labelVisit = memoize((name) => {
  visits++;
  return name + ":" + visits;
});

console.log(labelVisit("Asha"));
console.log(labelVisit("Asha"));
console.log(visits);

This function adds 1 to visits each time it runs. That is a side effect. Line 17 runs it and prints Asha:1. Line 18 is a cache hit, so the function does not run. It prints Asha:1 again, and visits stays at 1. The second visit was never counted, so don't memoize a function like this.

The key decides when two calls count as "the same input". So pick it on purpose:

• One simple argument, such as a string or a number: use the argument itself as the key.
• Several arguments: joining them into one string can mix them up. Put one Map inside another instead. These are called nested maps.
• An object argument: decide if you mean "this exact object" or "any object with the same fields".

Each row of this table is one kind of input. Read across to see which key to use and what to watch out for.

const cache = new Map();
const firstUser = { id: 1 };
const secondUser = { id: 1 };
cache.set(firstUser, "saved");

console.log(cache.get(firstUser));
console.log(cache.get(secondUser) ?? "miss");

1. Line 4 saves the value "saved" under the object firstUser.
2. Line 6 looks up that same object, so it prints saved.
3. Line 7 looks up secondUser. It has the same field, but it is a different object. So the lookup gives undefined.
4. The ?? operator gives its right side when its left side is null or undefined. So line 7 prints miss.

A Map matches object keys by which object they are, not by what is inside them. Only build a key from the fields when your app really treats objects with the same fields as the same thing.

1function memoize(fn) {2  const cache = new Map();3  return (key) => {4    if (cache.has(key)) return cache.get(key);5    const result = fn(key);6    cache.set(key, result);7    return result;8  };9}10 11let calls = 0;12const shout = memoize((name) => {13  calls++;14  return name.toUpperCase();15});16 17console.log(shout("ada"));18console.log(shout("ada"));19console.log(calls);

const cache = new Map();
const key = (first, second) => first + second;

cache.set(key("1", "23"), "first pair");
console.log(cache.get(key("12", "3")));

Line 2 makes a key by joining two strings. On line 4, "1" and "23" become "123". On line 5, "12" and "3" also become "123". So the lookup finds the wrong entry and prints first pair. Nested maps keep the two arguments apart, so this mix-up can't happen.

JSON.stringify turns an object into a string, so you can use that string as a key. It works only for small, plain objects whose fields are always added in the same order. It has three problems:

• It leaves out some values, such as functions and undefined.
• It throws an error if an object points back to itself.
• It keeps the order the fields were added in. Two objects with the same fields in a different order give different strings.

Nested Maps avoid these problems when "the same object" is what you mean.

A Map keeps every key and value for as long as the Map exists. Say a page stays open for hours and keeps adding keys. Then the cache keeps growing. Memory that fills up and is never freed is called a memory leak.

A WeakMap helps when the keys are objects. When nothing else in your program uses a key object any more, JavaScript may throw away that object and its cached value. Freeing unused memory like this is called garbage collection.

Each row of this table is one place to keep cached answers. Read across to see how it behaves and when to use it.

When the keys are not objects, set a size limit instead. The panel below keeps at most two answers. It follows a "least recently used" rule:

• A hit moves its key to the newest spot.
• When a third key is added, the oldest key is deleted.

A Map remembers the order its keys were added in. So cache.keys().next().value on line 13 gives the first key, which is the oldest one.

1function memoizeWithLimit(fn, limit = 2) {2  const cache = new Map();3  return (arg) => {4    if (cache.has(arg)) {5      const value = cache.get(arg);6      cache.delete(arg);7      cache.set(arg, value);8      return value;9    }10    const value = fn(arg);11    cache.set(arg, value);12    if (cache.size > limit) {13      const oldest = cache.keys().next().value;14      cache.delete(oldest);15    }16    return value;17  };18}19 20let calls = 0;21const square = memoizeWithLimit((n) => {22  calls++;23  return n * n;24});25 26console.log(square(2));27console.log(square(3));28console.log(square(2));29console.log(square(4));30console.log(square(3));31console.log(calls);

function memoize(fn) {
  let saved;
  return () => saved ??= fn();
}

const getTags = memoize(() => ["tea"]);
const tags = getTags();
tags.push("sugar");
console.log(getTags().join("+"));

This memoize saves just one answer. Line 3 uses ??=, which you'll meet again below: it runs fn() only if saved is still empty.

1. Line 7 gets the saved array.
2. Line 8 adds "sugar" to it.
3. tags and the cache hold the same array, not two copies. So line 9 prints tea+sugar.

If callers must not change cached data, return a copy. Or lock the value with Object.freeze, which stops anyone from changing it.

An async function returns a promise: an object that stands for a result that will arrive later. Say two parts of a page ask for the same user at the same time. If you save only the finished result, you save it too late. The second request has already started before the first one ends.

So save the promise itself, right away. Then:

• The second caller gets the same promise, and both wait for the same request.
• If the promise fails (we say it is rejected), delete its key. Then a retry makes a new request instead of getting the same failed promise back.

1function memoizeAsync(fn) {2  const cache = new Map();3  return (key) => {4    if (cache.has(key)) return cache.get(key);5    const promise = fn(key).catch((error) => {6      cache.delete(key);7      throw error;8    });9    cache.set(key, promise);10    return promise;11  };12}13 14let calls = 0;15const loadUser = memoizeAsync(async (id) => {16  calls++;17  if (id === "bad") throw new Error("not found");18  return { id, name: "Ada" };19});20 21(async () => {22  const [first, second] = await Promise.all([loadUser("42"), loadUser("42")]);23  console.log(first === second);24  console.log(calls);25  try { await loadUser("bad"); } catch {}26  try { await loadUser("bad"); } catch {}27  console.log(calls);28})();

1. Line 4 returns the saved promise on a hit.
2. Lines 5 to 8 add a .catch handler. If the promise is rejected, it deletes the key, then throws the error again so the caller still sees it.
3. Line 9 saves the promise before it finishes.
4. The output is true (both callers got the same user object), then 1 (the loader ran once), then 3 (each failed retry ran the loader again).

Here are three ways to wait until a value is needed:

• A thunk is a function you call later to get a value, like () => expensiveValue(). Nothing is worked out until you call it.
• A getter is a function that runs when you read a property. You write it as get name() { … } inside an object. A lazy getter works out the value on the first read. Then it replaces itself with a normal property that holds the value, so later reads skip the work.
• ??= is the nullish assignment operator. a ??= b sets a to b only if a is null or undefined. It means "fill this in only if it is empty".

1const profile = {Run2  get permissions() {3    console.log("compute permissions");4    const value = ["read", "write"];5    Object.defineProperty(this, "permissions", {6      value,7      enumerable: true,8      configurable: true,9    });10    return value;11  },12};13 14console.log("before");15console.log(profile.permissions.join("+"));16console.log(profile.permissions.join("+"));17 18const state = {};19state.config ??= (() => {20  console.log("init config");21  return { theme: "dark" };22})();23state.config ??= { theme: "light" };24console.log(state.config.theme);

Line 5 uses Object.defineProperty, which adds or replaces a property on an object. Here it swaps the getter for a normal property that holds the array. That is why compute permissions prints only once. On line 23, state.config already holds an object, so the second ??= does nothing and the theme stays dark.

Array methods are eager: each one does its whole job right away. map visits every item. Then filter visits every item. Only then does slice keep the first few.

A generator is a function written with function*. It gives out values one at a time with yield. After each one, it pauses until someone asks for the next value.

Iterator helpers are methods such as map, filter, and take that work on a one-at-a-time source like a generator. Node 22 and current Chrome have them.

• Iterator.from(source) wraps the source so you can use these methods.
• take(3) stops after 3 values.
• toArray() collects the values into an array.

The chain reads like array code. But each number goes through the whole chain before the next number is made.

1function* naturals() {2  let n = 1;3  while (true) {4    produced++;5    yield n++;6  }7}8 9let produced = 0;10let mapped = 0;11let tested = 0;12 13const firstEvenSquares = Iterator.from(naturals())14  .map((n) => {15    mapped++;16    return n * n;17  })18  .filter((square) => {19    tested++;20    return square % 2 === 0;21  })22  .take(3)23  .toArray();24 25console.log(firstEvenSquares.join(","));26console.log(produced + "/" + mapped + "/" + tested);

1let produced = 0;2let mapped = 0;3let tested = 0;4 5const firstEvenSquares = Array.from({ length: 1000 }, (_, index) => {6  produced++;7  return index + 1;8})9  .map((n) => {10    mapped++;11    return n * n;12  })13  .filter((square) => {14    tested++;15    return square % 2 === 0;16  })17  .slice(0, 3);18 19console.log(firstEvenSquares.join(","));20console.log(produced + "/" + mapped + "/" + tested);

Look at the counter lines. The squares of 1 to 6 are 1, 4, 9, 16, 25, and 36. Three of them are even: 4, 16, and 36. So the lazy chain only has to make the numbers 1 to 6. The eager array makes, squares, and tests all 1000 numbers before it keeps the same three.

Use memoization for slow work whose answer depends only on its inputs, such as:

• building a search index from a list of products,
• reading a page address and working out which page to show,
• formatting labels and prices,
• building a regular expression (a text pattern) once and reusing it,
• working out what a user is allowed to do,
• loading a resource that gives the same result every time.

Use laziness for:

• panels that most people never open,
• settings that are rarely read,
• very long or endless lists,
• data you handle one piece at a time.

A cache holds part of your app's data. Give it a clear name, keep it small, and delete entries as soon as their data is out of date.

Common misconceptions

• "Memoization only makes code faster." It also changes when, and how often, the function runs. If the function is not pure, that changes what your program does.
• "The cache key is a small detail." The key decides what counts as "the same input".
• "A WeakMap is a smaller Map." It is a different tool, about how long entries live. It takes only object keys, you can't loop over it, and it has no size.
• "Lazy code is always faster." It is faster only when the work it skips is bigger than the extra code it adds.
• "Generators are arrays written another way." A generator pauses and goes on. It does not hold all its future values.

Each row of this table is a common wrong idea. Read across for the better rule and the reason.

Key takeaways

• Memoize a function only if the same inputs always give the same answer. Pick a key that says what "the same inputs" means.
• Show what happens with call counters and printed output, not with timings.
• A Map, nested Maps, a WeakMap, and a Map with a size limit each keep answers for a different length of time. Pick the one that fits.
• For async work, save the promise right away, and delete it if it is rejected.
• Lazy values and lazy lists do work only when asked, so they can skip most of the work.

Next comes advanced recursion. The same habits help there: count which calls really run, and keep saved data where you can see it.