JavaScript – Memoize

What is memoization and why is it important? How do you do it in JavaScript? This post will hopefully answer these questions.

Memoization is a topic which has come up in most technical interviews I have been a part of. I have been asked some variant of this question in four different interviews from four different companies I was interviewing for throughout my career. And for good reason, because this is a great way to potentially optimize your web app.

Let’s tackle the first question above: What is memoization and why is it important?

If we reference Wikipedia.com, it says: “In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.”

So, basically, it is a technique to enable a function to remember what it previously had computed or returned. The famous example you’ll probably see all over the internet is the classic Fibonacci generator recursive function. When computing the Fibonacci sequence to a high level, you are asking a lot of your web browser. Memoization can help with this immensely.

But I don’t want to use the good ‘ol Fibonacci sequence example in this post. Instead, I will be using a more real world example of how memoization can be useful – caching the results of repeated asynchronous web service calls.

How do you do it in JavaScript?

Let’s get right into it – memoization:

function memoize(fn) {
let cache = {};

return (payload, cb) => {
let payloadStr = JSON.stringify(payload);

if (cache[payloadStr]) {
cb(cache[payloadStr]);
} else {
fn(payload, response => {
cache[payloadStr] = response;
cb(response);
});
}
};
}


There’s a lot going on here. We have a function named memoize, which accepts a function as it’s only argument. First we’re creating an empty object which will hold all our cached results from the various web service calls we will be making. Then we’re going to return a function which takes two arguments, the first being the payload which will be sent to the server, and the second the callback function to be invoked after the server returns with our response. This inner function, once invoked, will convert the payload argument to a string, then check whether it exists in our cache object or not. If it does exist, then it means we have previously made this exact web service call, and so we can immediately invoke the callback function, and pass the cached response (no waiting on the server).

If it does not exist in the cache object, then we will invoke the function we originally passed into memoize(), passing the payload, and a callback function to be called once the server responds with our response. Within this callback function, we will add the response to the cache object, and invoke the original callback function.

You may have to read that three times before it starts to make sense. Let’s use an example to help understand it better. Let’s say we have an API which accepts an integer as the payload, and it will square it, and return the result as a response. Let’s encapsulate the call to our API within a function named “getSquare()” (I’m using a timeout with a 1 second delay to mimic a web service call):

let getSquare = (arg, callback) => {
// this timeout function will "act" as our web service call (ajax call)
setTimeout(() => {
let square = Math.pow(arg, 2);
callback(square);
}, 1000);
};


Now, we can invoke our memoize function, pass to it the getSquare function, and store the resultant function into a new variable “squareIt”:

let squareIt = memoize(getSquare);


Now, our squareIt variable is holding a function which accepts two arguments. Remember our inner function inside of memoize()? Now we can invoke squareIt by passing the payload (an integer), and a callback function to run after we get our response (the square of our integer). Use it like so:

squareIt(2, data => {
console.log('got ' + data);
}); // after a 1 sec delay, prints "got 4" to the console

squareIt(16, data => {
console.log('got ' + data);
}); // after a 1 sec delay, prints "got 256" to the console

// **** pretend a few minutes later....
// Now if we call squareIt() with 2 or 16 again, at a later time, we have no more delay - because the response is cached!

squareIt(16, data => {
console.log('got ' + data);
}); // prints "got 256" to the console - no delay!


This doesn’t seem very special as is, but imagine we have a gigantic database with a complete taxonomy of every song ever recorded in the history of humanity. For each song, we have the title, artist, band, genre, and year recorded. Millions of songs. Also imagine we have an API which, given a song title, will return the artist, band, genre, and year recorded. Finally imagine we have a website with a free form text field where a user can enter a song title and expect to get back the song information. Let’s say we have a user who searches for the song titled “Fade to Black” and hits enter.

We fire off our API call, our server queries the database, the database runs through millions of songs finally finding Metallica’s Fade to Black, and returns the song info in the response. Our user is pleased, but our web server was just computationally taxed. Next our user searches for “Stairway to Heaven”, again our API call is fired off, our user waits a second or so, our web server is taxed, and again the user is pleased with the info for Stairway to Heaven.

Now, our user would like to see the info for “Fade to Black” again, so again they search, and again our web server is taxed just to return the exact same info we previously had showed to the user. Why not cache the results of Fade to Black on the front end with our memoize() function? This is a win win because not only do our users not have to wait the 1 second or so to see their song info when searching for the same song twice, or thrice, but our web server only needs to be taxed once per song title (I’m of course omitting the real world fact of multiple songs having the same title).

I hope this helps, and at least makes some sense. You can see a pen of it here.

Please, as always, also educate me on better ways to code in the comments.