Memoization is the principle to put in cache (memorize) output values according to inputs parameters of a function.

Before coding a javascript memoization, it’s important to understand the concept of pure function.

Avant de voir comment faire de la mémoïsation en javascript, il est important de comprendre le concept de fonction pure.

A pure function is a function with the following properties:

• for same input parameters, the output result is the same
• does not depend on external variables (we can merge this condition with the first one)
• it does not have any side effect: do not edit any external variables

let prefix = 'Hello';
let anotherExternalVariable;

function impureFunction(suffix) {
  // Depends on external variable
  const result = `${prefix} ${suffix}`;

  // Reassign of an external variable
  anotherExternalVariable = result;

  return result;
}

const parameter = 'Rainbow';

console.log(impureFunction(parameter)); // Bonjour Rainbow

prefix = 'Goodbye';
console.log(impureFunction(parameter)); // Goodbye Rainbow

In this case we don’t have the same result for a same input parameter because we depends on a external variable. Moreover we reassign an external variable.

function pureFunction(suffix) {
  const prefix = 'Hello';

  return `${prefix} ${suffix}`;
}

const parameter = 'Rainbow';

console.log(pureFunction(parameter)); // Hello Rainbow

console.log(pureFunction(parameter)); // Hello Rainbow

We agree that such a methode would probably not be in any project, it’s just an example of how to transform the previous example of impure function into a pure function.

Now that we have seen pure function, we can focus on how to do memoization in javascript.

As a reminder, memoization will directly send the result if we have previously calculated ir for the same input parameters. So it is necessary that the function memoized is a pure function.

Let’s begin we memoization on the last value calculated then we will see how to do with multiple results.

The implementation is based on giving a function as parameter to another function which send us an other function overridden.

If you are used to use High Order Components, you will not be lost by this implementation. Otherwise it can be a little blurry in your mind so let’s take a look at some code:

// The memoization function take as input parameter an other function name callback
function memoizeLast(callback) {
  // Here we can define local variables to the function memoizeLast

  // It returns a mthod that can memoize
  // We destructure to get all parameters and not only the first one
  return function memoizeCallback(...parameters) {
    // Here we can have access to the potential local variables of memoizeLast and to the callback function
    // We can also define local variables to memoizeCallback
    // And we have access to parameters
    // We can execute the callback function giving it the parameters as input
  };
}

// This is the method we want to to memoiz: a simple function which sum 2 values
function add(value1, value2) {
  return value1 + value2;
}

// We memoize our add function, and get the method memoizeCallback of memoizeLast
const memoizedAdd = memoizeLast(add);

// We call 2 times the method. Spoiler alert: right now it does not work ^^
console.log(memoizedAdd(1, 2));
console.log(memoizedAdd(1, 2));

Now we have seen the structure of the memoization method, our pure function, the memoization and the call. We can now focus on the implementation of the memoizeLast function:

import shallowEquals from './shallowEquals';

function memoizeLast(callback) {
  // We keep the last paremeters and the result in memory
  let lastMemoizedParameters;
  let lastMemoizedResult;

  return function memoizeCallback(...parameters) {
    // If the input parameters are the same as the last one memorized
    // we return the last result without executing the callback
    if (shallowEquals(lastMemoizedParameters, parameters)) {
      return lastMemoizedResult;
    }

    // We have new parameters let's memorize them
    // and we execute the callback, then we memorize the result
    lastMemoizedParameters = parameters;

    // We spread the parameters
    lastMemoizedResult = callback(...parameters);

    return lastMemoizedResult;
  };
}

In the previous snippet, I chosed to compare input parameters with shallow equal. But a user could want to compare them differently. For example if we want to memoize a function with object as input parameters, we could want to do deep equals.

Let’s allow the user to configure the comparison:

import shallowEquals from './shallowEquals';

// By default I want to compare parameters with shallowEquals
// The user is not forced to pass a comparison method
// if he is satisfied of this one
function memoizeLast(callback, isEqual = shallowEquals) {
  let lastMemoizedParameters;
  let lastMemoizedResult;

  return function memoizeCallback(...parameters) {
    // We use the isEqual function
    if (isEqual(lastMemoizedParameters, parameters)) {
      return lastMemoizedResult;
    }

    lastMemoizedParameters = parameters;
    lastMemoizedResult = callback(...parameters);

    return lastMemoizedResult;
  };
}

If we want to memoize a function that uses this, we can see that there is some problems with the actual implementation:

function getName() {
  return this.name;
}

const memoizedGetName = memoizeLast(getName);

const rainbowUser = { name: 'Rainbow' };
const johnUser = { name: 'John' };

console.log(memoizedGetName.call(rainbowUser)); // Error: cannot read name of undefined in getName
console.log(memoizedGetName.call(johnUser)); // Not executed because of the error

The error is that we do not propagate the value of this from the function memoizeCallback to the function getName. Let’s change the way how we call the method callback in memoizeCallback:

import shallowEquals from './shallowEquals';

function memoizeLast(callback, isEqual = shallowEquals) {
  let lastMemoizedParameters;
  let lastMemoizedResult;

  return function memoizeCallback(...parameters) {
    if (isEqual(lastMemoizedParameters, parameters)) {
      return lastMemoizedResult;
    }

    lastMemoizedParameters = parameters;
    // We pass the actual this to callback
    // in addition to parameters
    lastMemoizedResult = callback.apply(this, parameters);

    return lastMemoizedResult;
  };
}

Let’s try again with these changes:

function getName() {
  return this.name;
}

const memoizedGetName = memoizeLast(getName);

const rainbowUser = { name: 'Rainbow' };
const johnUser = { name: 'John' };

console.log(memoizedGetName.call(rainbowUser)); // Rainbow
console.log(memoizedGetName.call(johnUser)); // Rainbow (ouch we have another problem, we should get John)

The problem is that at the first call we execute the method getName, and the second times we get the memoized result because parameters do not have changed because there is none. (The first call do not pass inside the if block because lastMemoizedParameters is initialized to undefined).

To solve this problem we have to memorize the value of this to compare it to know if we have to re-execute the function callback or not:

import shallowEquals from './shallowEquals';

function memoizeLast(callback, isEqual = shallowEquals) {
  let lastMemoizedParameters;
  let lastMemoizedResult;
  let lastThis;

  return function memoizeCallback(...parameters) {
    // We check if the value of this to know it's the same
    if (
      lastThis === this &&
      isEqual(lastMemoizedParameters, parameters)
    ) {
      return lastMemoizedResult;
    }

    lastThis = this;
    lastMemoizedParameters = parameters;
    lastMemoizedResult = callback.apply(this, parameters);

    return lastMemoizedResult;
  };
}

And now we get the wanted result:

function getName() {
  return this.name;
}

const memoizedGetName = memoizeLast(getName);

const rainbowUser = { name: 'Rainbow' };
const johnUser = { name: 'John' };

console.log(memoizedGetName.call(rainbowUser)); // Rainbow
console.log(memoizedGetName.call(johnUser)); // John

import shallowEquals from './shallowEquals';

function memoizeLast(callback, isEqual = shallowEquals) {
  let lastMemoizedParameters;
  let lastMemoizedResult;
  let lastThis;

  return function memoizeCallback(...parameters) {
    if (
      lastThis === this &&
      isEqual(lastMemoizedParameters, parameters)
    ) {
      return lastMemoizedResult;
    }

    lastThis = this;
    lastMemoizedParameters = parameters;
    lastMemoizedResult = callback.apply(this, parameters);

    return lastMemoizedResult;
  };
}

Previously we have seen how to do memoization of the last value, we now take a look at how to adapt this implementation to memorize all the values.

To do that we will have to store al the values corresponding to the pair parameters/this. The data sturcture corresponding to this case is the Map. We will implementat a class CacheKey haveing the attributes that (corresponding to this) and parameters. And a class CacheMap which will contains all the data, this one will also implement the functions has and get to compare keys as we want (with the method equals of CacheKey).

class CacheKey {
  constructor(parameters, that) {
    this.parameters = parameters;
    this.that = that;
  }

  // This method allows us to compare CacheKey to know if they are the same
  equals(cacheKey, isEqual = shallowEqual) {
    return (
      cacheKey.that === this.that &&
      isEqual(cacheKey.parameters, this.parameters)
    );
  }
}

class CacheMap {
  constructor(isEqual) {
    this.isEqual = isEqual;
    this.map = new Map();
    this.lastSearch = undefined;
  }

  put(parameters, that, value) {
    this.map.set(new CacheKey(parameters, that), value);
  }

  has(parameters, that) {
    const cacheKeySearched = new CacheKey(parameters, that);

    for (let [key, value] of this.map) {
      if (key.equals(cacheKeySearched, this.isEqual)) {
        // We memorize this value because we want to get it back right after that
        this.lastSearch = { key, value };
        return true;
      }
    }
    return false;
  }

  get(parameters, that) {
    const cacheKeySearched = new CacheKey(parameters, that);

    // We check if the lastSearch value  is the same
    // as the wanted one
    const lastSearch = this.lastSearch;

    // If the keys are the same we return directly the value in lastSearch
    if (
      lastSearch?.key.equals(cacheKeySearched, this.isEqual)
    ) {
      return lastSearch.value;
    }

    for (let [key, value] of this.map) {
      if (key.equals(cacheKeySearched, this.isEqual)) {
        return value;
      }
    }

    // In our case, we know if we try to get a value, it has to exist
    // Because this method will be called right after the has function
    throw new Error('The key does not exist');
  }
}

You’re maybe asking why we do not just call the get function and delete the has function? Actually if we do this, we will not be able to know if the value has been already calculated or not when the function to memoize returns undefined value.

Let’s get a quick of the performances of this implementation, compare the function has of CacheMap to the one of Map.

We’re gonna fill Maps with different values numbers. We’re gonna check that the last key inserted is here with the method has. For all values number we execute 1_000 times and we get the average number, we get a duration in millisecond.

The thing to know is that Map use the strict equal on the keys to know if two keys are equal.

We notice that the search with the Map is quite stable and largely inferior to 1ms.

The search with shallow equal is correct until 1_000 values.

The search with strict equal is correct until 10_000 values.

The use of the CacheMap will be:

import shallowEquals from './shallowEquals';

function memoize(callback, isEqual = shallowEquals) {
  let cacheMap = new CacheMap(isEqual);

  return function (...parameters) {
    if (cacheMap.has(parameters, this)) {
      return cacheMap.get(parameters, this);
    }

    const result = callback.apply(this, parameters);
    cacheMap.put(parameters, this, result);

    return result;
  };
}

---

You can find me on Twitter if you want to comment this post or just contact me. Feel free to buy me a coffee if you like the content and encourage me.