Blog | retzdev

Introduction

A while back I saw a complex memoization function in Javascript that I didn't understand. The function used Map and WeakMap: two objects I never used or even knew how to use.

Therefore, I set out to get a little closer to understanding the differences between the two and how they relate to writing memoization functions.

Terms

First, let's begin with what memoization is:

In computing, memoization or memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls to pure functions and returning the cached result when the same inputs occur again.

Wikipedia

Here is an example of a higher-order function that memoizes a different function:

// https://javascript.plainenglish.io/efficient-js-memoization-using-map-86f1f4735cc

function memo(fn) {
  const cache = new Map();
  
  return function(...args) {
    const key = args.map(arg -> `${arg}_${typeof arg}`).join('|');
    
    if (cache.has(key)) {
      return cache.get(key);
    }
    
    const result = fn(...args);
    
    cache.set(key, result);
    return result;
  }
}

I wanted to find an example that used Map():

The Map object holds key-value pairs and remembers the original insertion order of the keys. Any value (both objects and primitive values) may be used as either a key or a value.

MDN Web Docs

There are a lot of differences, actually, between a Map and a normal Object, to list a few (full list):

"A Map is an iterable, so it can be directly iterated."
"A map, Performs better in scenarios involving frequent additions and removals of key-value pairs."
"A Map's keys can be any value (including functions, objects, or any primitive)".

Finding a Function

I wanted to find an expensive function to demonstrate memoization, which took me longer than I had hoped. Anyway, I knew combination and permutation functions are expensive, and found one on SO:

const testFunc = (inputArr: string[]) => {
  let result: string[] = [];

  const permute = (arr: string[], m: string[]) => {
    if (arr.length === 0) {
      // @ts-ignore
      result.push(m);
    } else {
      for (let i = 0; i < arr.length; i++) {
        let curr = arr.slice();
        let next = curr.splice(i, 1);
        permute(curr.slice(), m.concat(next));
      }
    }
  };

  permute(inputArr, []);

  return result;
};

Performance

Memoization is a tradeoff between memory and performance. Consequently, it would be helpful if I could show the performance benefits. To do so, I used the following function:

function perf<T>(f: () => T): number {
  const start = performance.now();

  f();

  const stop = performance.now();

  return stop - start;
}

Memoizing a function in Typescript

Below is the memoization code, which was adapted from the original for Typescript:

function memo<T extends unknown[], A>(fn: (...args: T) => A) {
  const cache = new Map();

  return function (...args: T) {
    const key = args.map((arg) => `${arg}_${typeof arg}`).join("|");

    if (cache.has(key)) {
      return cache.get(key);
    }
    const result = fn(...args);

    cache.set(key, result);
    return result;
  };
}

Next, I passed the permutation function into the `memo` function.

const memoized = memo(testFunc);

I set up a CodeSandbox to execute the code in the browser. Running the permutation with an argument of:
const arr1 = ["luuxe", "hoebg", "qewmj", "zfpyb", "szvwh", "ndciu", "fwwdx", "pklwx", "ubrao", "pnpnn",];

The function execution took ~3 seconds the first time. However, as you might expect, running it a second time took close to ~0 milliseconds. There you have it. We memoized an expensive function.

const memoized = memo(testFunc);

// Memoize function runs
const firstRun = perf(() => memoized(arr1));
const secondRun = perf(() => memoized(arr1));

Memory

The resulting cache stores an array with 3628800 nested arrays. Assuming:

The average length of each array is five (there are ten items in the original array)
Each item in the arrays is a five-character string
Each character requires four bytes

We can roughly estimate the size of the one-item cache at 362 MB. We can now look at the trade-off that was made using numbers.

362 MB for ~ 3 seconds.

Although both of these numbers are estimates, it's nice to quantify the potential savings for comparison.

What about WeakMap?

Yes, back to WeakMap. Reading on MDN, a WeakMap is:

... a collection of key/value pairs whose keys must be objects or non-registered symbols, with values of any arbitrary JavaScript type, and which does not create strong references to its keys. That is, an object's presence as a key in a WeakMap does not prevent the object from being garbage collected.

MDN Web Docs

I want to put an emphasis on the last part about garbage collection:

... garbage collection is the process of removing any objects that are not being used by any other objects. Often abbreviated "GC," garbage collection is a fundamental component of the memory management system used by JavaScript.

MDN Web Docs

Bringing it full circle, we can further improve memory performance by storing objects or non-registered symbols in a WeakMap as opposed to a Map in our memoization function. This could be helpful if we have functions in our cache. Contextually, our cache may store functions if we are passing functions as keys to our cache.

Perhaps in a different article, I can demonstrate this with code. For now, it'll just have to be something we're aware of.

Typescript Memoization