Memoization means saving a function's result for the arguments it was called with, so that calling it again with the same arguments returns the saved result instead of running the function again. The saved results are the function's cache. When a call finds its result there, that's a cache hit; when it doesn't, it's a miss, and the function runs and its result is saved. Memoizing trades memory for time, so it pays off for functions that are slow and get called with the same arguments again and again.
It's like writing the answer to a long sum in the margin, so the next time someone asks, you read it off instead of working it out. Take countPrimes(n), which counts the prime numbers below n and is slow when n is large. Here's what a memoized version does over four calls, next to a lighter variant that remembers only its most recent call:
| Call | Memoized: remembers every call | Remembers only the last call |
|---|---|---|
countPrimes(1000000) | Miss: runs, returns 78498, and saves it. | Miss: runs, returns 78498, and saves it. |
countPrimes(1000000) | Hit: returns the saved 78498 without running. | Hit: returns the saved 78498 without running. |
countPrimes(2000000) | Miss: runs, returns 148933, and saves it too. | Miss: runs, returns 148933, and saves it in place of 78498. |
countPrimes(1000000) | Hit: 78498 is still saved. | Miss: only the result for 2000000 is saved, so it runs again. |
Every saved result, with the arguments it was saved for, stays in memory until the cache lets go of it, and a cache that never does grows with every new argument. Memoize helpers deal with that in different ways: some let you clear the cache, some cap its size and drop the least recently used result when it's full, and the variant in the last column keeps only one. That one suits a value recomputed again and again from inputs that rarely change. React's useMemo works that way: it keeps the value from the last render and recomputes it only when one of its dependencies has changed.
A cache finds results by a key worked out from the arguments. Lodash's _.memoize uses the first argument as the key unless you pass a resolver, a function that turns the arguments into a key. Without one, a memoized power(base, exponent) called as power(2, 3) and then power(2, 10) returns 8 both times: both calls have the key 2. Lodash compares keys the way a Map does, so an object matches only the very same object: a different object with the same contents is a miss, and changing an object's contents doesn't make it miss. Other helpers build the key from every argument.
Only memoize pure functions: ones whose result depends on nothing but their arguments, and that don't change anything outside themselves. A hit skips the function entirely. If getPrice(id) reads a price that has since changed, the memoized version keeps returning the old one, and a function that logs something or sends a request doesn't do it on a hit.
For an async function, the result is a promise, so the promise is what gets saved. A second call with the same arguments gets the same promise, even while it's still pending, so two parts of a page asking for the same user share one request. A promise that rejects would be saved too, and every later call would get the same failure, unless the cache forgets keys whose promise rejects.
Besides useMemo, you meet memoization in React's memo, which skips re-rendering a component whose props haven't changed, in selector libraries such as Reselect, and in recursive algorithms that would otherwise solve the same smaller problem many times.
JavaScript frees memory for you. Its garbage collector, the part of the engine that reclaims memory, goes by reachability. An object is reachable if your code could still get to it, starting from a global variable or a variable of a function that's running, and following references from there. While an object is reachable, it stays in memory. Once nothing reachable references it, the garbage collector may free it, at a moment the engine chooses.
Most references are strong: they keep their target in memory. A variable, an array element, an object property, and a Map key or value are all strong references. A weak reference points to an object without keeping it alive. Picture each object as a balloon, and each strong reference as a hand holding its string: the balloon stays while at least one hand holds on. A weak reference is a note taped to the balloon. It doesn't hold the balloon down, and when the last hand lets go, the balloon floats away with the note.
Strong references are behind a classic memory leak: a Map keyed by objects. Say you keep a cache, or some extra data, for each DOM element or state object your code sees. The Map holds every key strongly, so each object stays in memory for as long as the Map does, even after it has left the page or been replaced and nothing else uses it. The Map keeps everything it has ever seen.
A WeakMap is the fix. It maps keys to values like a Map, but holds its keys weakly. While a key is still reachable some other way, its entry stays, and get finds it. Once the WeakMap is the only thing left referencing the key, the key can be freed, and its entry, value included, goes with it:
const strong = new Map();
const weak = new WeakMap();
let user = { name: "Ada" };
strong.set(user, { visits: 3 });
weak.set(user, { visits: 3 });
weak.get(user); // { visits: 3 }
user = null; // the rest of the program is done with Ada's object
strong.size; // 1: the Map's key still holds the object, so it can't be freed
// The WeakMap's key doesn't hold it, so the object can now be freed,
// and its entry in weak, { visits: 3 } included, goes with it.
| What | Map | WeakMap |
|---|---|---|
| Keys | Any value | Objects, functions and arrays included. A string or number key throws a TypeError: anyone can write 42 again, so its entry could never safely go. |
| An entry stays | Until you delete it | Until you delete it, or its key is no longer reachable any other way |
| Values | Held strongly | Held strongly while their key is alive. A value that refers back to its own key doesn't keep the key alive. |
size, clear(), and iterating | Yes | No: what it holds depends on when the garbage collector last ran, so it can't be counted or listed |
| Methods | get, set, has, delete, and more | Only get, set, has, and delete |
Two relatives hold objects weakly too. A WeakSet is a set of objects with only add, has, and delete: it marks objects, such as the elements you've already set up, without keeping them in memory. A WeakRef wraps one object: ref.deref() returns the object while it's still in memory, and undefined once it has been freed. When that happens is up to the engine, so code that uses a WeakRef has to work either way, and most code never needs one.
You meet WeakMap wherever code attaches data to objects it doesn't own. Vue 3 keeps the reactive proxy it makes for each object in a WeakMap, so the proxy goes when the object does. And when Babel or TypeScript compile a class's #private fields for older browsers, each field becomes a WeakMap from each instance to its value.
A cache that holds the objects it was called with keeps them in memory for as long as the cache lives, even when nothing else uses them. Write weakMapMemoize(fn), a memoize that avoids that. It returns a function that calls fn with the same arguments and returns its result, and remembers the result: a later call with the same arguments returns it without calling fn again.
Two calls count as the same when they have the same number of arguments and each argument matches the one in the same position. An object or a function matches only itself: a different object with the same contents doesn't match, and changing an object's contents doesn't stop it matching.
Other values match the way Map keys do: 1 and "1" are different, and NaN matches NaN. null and undefined count as these other values, not as objects.
The cache must not keep object or function arguments alive. Store each one only as a key of a WeakMap, never in a Map, a Set, an array, or a property, so that once nothing else references it, it and the results cached for it can be garbage-collected.
Results of undefined are remembered too. Each memoized function has its own cache.
const cartTotal = weakMapMemoize((cart, currency) => {
console.log("computing");
return cart.items.reduce((sum, item) => sum + item.price, 0) + " " + currency;
});
const cart = { items: [{ price: 5 }, { price: 7 }] };
cartTotal(cart, "EUR"); // logs "computing", returns "12 EUR"
cartTotal(cart, "EUR"); // returns "12 EUR", logs nothing
cartTotal(cart, "USD"); // logs "computing": a different currency
cartTotal({ items: [{ price: 5 }, { price: 7 }] }, "EUR"); // logs "computing": a different object
const fn = spy((user) => user.name.toUpperCase());
const shout = weakMapMemoize(fn);
const ada = { name: "ada" };
expect(shout(ada)).toBe("ADA");
expect(shout(ada)).toBe("ADA");
expect(fn).toHaveBeenCalledTimes(1);
const fn = spy((user) => user.name);
const getName = weakMapMemoize(fn);
const ada = { name: "Ada" };
getName(ada);
getName({ name: "Ada" });
expect(fn).toHaveBeenCalledTimes(2);
ada.name = "Grace";
expect(getName(ada)).toBe("Ada");
expect(fn).toHaveBeenCalledTimes(2);
const fn = spy((list, status) => list.filter((item) => item.status === status));
const select = weakMapMemoize(fn);
const todos = [{ status: "done" }, { status: "open" }];
const done = select(todos, "done");
expect(select(todos, "done")).toBe(done);
expect(select(todos, "open")).toEqual([{ status: "open" }]);
expect(fn).toHaveBeenCalledTimes(2);
const pair = spy((key, value) => [key, value]);
const memoPair = weakMapMemoize(pair);
const a = {};
const b = {};
memoPair("key", a);
memoPair("key", b);
memoPair("key", a);
expect(pair).toHaveBeenCalledTimes(2);
const fn = spy((x) => typeof x);
const kind = weakMapMemoize(fn);
expect(kind(1)).toBe("number");
expect(kind("1")).toBe("string");
kind(NaN);
kind(NaN);
expect(fn).toHaveBeenCalledTimes(3);
const fn = spy((x) => String(x));
const show = weakMapMemoize(fn);
expect(show(null)).toBe("null");
expect(show(null)).toBe("null");
expect(show(undefined)).toBe("undefined");
expect(show(undefined)).toBe("undefined");
expect(fn).toHaveBeenCalledTimes(2);
const fn = spy((...args) => args.length);
const count = weakMapMemoize(fn);
const obj = {};
expect(count(obj)).toBe(1);
expect(count(obj, undefined)).toBe(2);
expect(count()).toBe(0);
expect(count(obj)).toBe(1);
expect(fn).toHaveBeenCalledTimes(3);
const fn = spy(() => undefined);
const nothing = weakMapMemoize(fn);
const obj = {};
nothing(obj);
nothing(obj);
expect(fn).toHaveBeenCalledTimes(1);
const user = { name: "Ada" };
const upper = weakMapMemoize((u) => u.name.toUpperCase());
const lower = weakMapMemoize((u) => u.name.toLowerCase());
expect(upper(user)).toBe("ADA");
expect(lower(user)).toBe("ada");
const weakKeys = [];
const strongKeys = [];
const weakSet = WeakMap.prototype.set;
const mapSet = Map.prototype.set;
const setAdd = Set.prototype.add;
WeakMap.prototype.set = function (key, value) {
weakKeys.push(key);
return weakSet.call(this, key, value);
};
Map.prototype.set = function (key, value) {
strongKeys.push(key);
return mapSet.call(this, key, value);
};
Set.prototype.add = function (value) {
strongKeys.push(value);
return setAdd.call(this, value);
};
const user = { name: "Ada" };
const format = (u) => u.name;
let result;
try {
const render = weakMapMemoize((u, fmt, size) => fmt(u) + size);
result = render(user, format, 2);
render(user, format, 2);
} finally {
WeakMap.prototype.set = weakSet;
Map.prototype.set = mapSet;
Set.prototype.add = setAdd;
}
expect(result).toBe("Ada2");
expect(weakKeys).toContain(user);
expect(weakKeys).toContain(format);
expect(strongKeys.filter((key) => key === user || key === format)).toEqual([]);
Run tests runs every test on your code, here in your browser. The problem is solved when they all pass.
Ctrl + Enter runs the tests (⌘ + Enter on a Mac).
I'm here to help with Memoize object arguments with a WeakMap. I give hints, never the solution, so you get to solve it yourself. Ask for a hint, select code to ask about it, or press Ask Tuto why on a failing test.
Your first 3 answers need no account. for free to keep asking.