In this post I am going to walk through when you might want to use memoization for your JavaScript functions and how you can easily memoize any function. Before we can go much further, let's define what memoization is.

What is memoization?

Memoization is an optimization technique where expensive function calls are cached such that the result can be immediately returned the next time the function is called with the same arguments. This method of optimization is not unique to JavaScript and is quite common in many programming languages. It is especially useful in recursive functions as calls are more likely to call with the same arguments while recursing. Take a recursive factorial function for example:

function factorial(num) {
  if(num === 1) { return 1 };
  return num * factorial(num - 1);
}

If we call factorial(3), the function calls factorial(3), factorial(2), and factorial(1) will be called. If we memoize this function, another call to factorial(3) will not need to recurse, it can simply return the result that it has cached. The real benefit is if we call factorial(4), we will short circuit our recursion, because factorial(3) is already cached, so we do not need to recurse any further, we can just use that result.

Sounds great, sign me up!

We can simply create a memoize function that takes another function and modifies it to memoize calls.

function memoize(func) {
  var cache = {};
  return function() {
    var key = JSON.stringify(arguments);
    if(cache[key]) {
      return cache[key];
    }
    else {
      var val = func.apply(this, arguments);
      cache[key] = val;
      return val;
    }
  };
}

Now we can easily memoize any pure function, like our factorial function.

var factorial = memoize(function(num) {
  console.log('working for factorial(' + num + ')');
  if(num === 1) { return 1 };
  return num * factorial(num - 1);
});

// first call
console.log(factorial(3));
//=> working for factorial(3)
//=> working for factorial(2)
//=> working for factorial(1)
//=> 6

// successive calls
console.log(factorial(3)); //=> 6
console.log(factorial(3)); //=> 6

// short circuit higher factorial calls
console.log(factorial(4));
//=> working for factorial(4)
//=> 24

Play with this example in Babel

Advanced usage

Right now we have memoization working by simply wrapping a given function with our memoization function. The results are cached for calls with the same arguments. This is great, but what if the arguments are not our only dependencies. What if we are memoizing a method on an object and that method relies on both the arguments AND other properties on the object? How do we account for these other dependencies? If we do not do anything different, memoizing a function might actually cause it to produce incorrect values (if the other dependencies have changed). We need a way to invalidate the cache for these dependencies as well.

The good news is that we can easily take other dependencies into account. Earlier you might have been wondering why I am using JSON.stringify to create my cache keys, and soon you will see how this helps make it extremely easy to add any number of dependencies in addition to a function's arguments.

Let's say we have a Person model with a firstName and lastName as well as a method, fullName, that takes an optional argument, title and outputs the person's full name.

function memoize() { ... }

function Person(firstName, lastName) {
  this.firstName = firstName;
  this.lastName = lastName;

  this.fullName = memoize(function(title) {
    return title + ' ' + this.firstName + ' ' + this.lastName;
  });
}

All we need to do to memoize this function on the Person object, is to update the memoize function to take a second argument, depsFunc. depsFunc will be a function that returns an array of the dependencies. We can then use depsFunc as well as func to calculate the unique key in our hash.

function memoize(func, depsFunc) {
  var cache = {};
  return function() {
    var key = JSON.stringify([depsFunc(), arguments]);
    if(cache[key]) {
      return cache[key];
    }
    else {
      var val = func.apply(this, arguments);
      cache[key] = val;
      return val;
    }
  };
}

function Person(firstName, lastName) {
  this.firstName = firstName;
  this.lastName = lastName;

  this.fullName = memoize(
    // calculation
    function(title) {
      console.log('working...');
      return title + ' ' + this.firstName + ' ' + this.lastName;
    },
    // dependencies
    function() {
      return [this.firstName, this.lastName];
    }.bind(this));
}

// create a new Person
var person = new Person('Jonathan', 'Lehman');

// first call to our memoized function does the work
console.log(person.fullName('Mr.'));
//=> working
//=> Mr. Jonathan Lehman

// successive calls
console.log(person.fullName('Mr.'));
//=> Mr. Jonathan Lehman

// work must be done if dependencies or arguments change

// change arguments
console.log(person.fullName('Mister'));
//=> work
//=> Mister Jonathan Lehman

// change deps
person1.firstName = 'Jon';
console.log(person.fullName('Mr.'));
//=> work
//=> Mr. Jon Lehman

Play with this example in Babel

Careful, memoization is not a magic bullet

Keep in mind that memoization does not make sense for all function calls. There is a higher memory overhead since we must store our cached results so that we can later recall them as well as an added complexity of using memoization, so it really only makes sense for functions that are computationally expensive.

Also, memoization does not work well for functions that are not pure, that is functions that have side effects. Memoizing only allows us to cache a result, so any other side effects get lost on successive calls. That said, you can get around this constraint, by returning a function that includes your side effects that you will need to execute after getting the result.