Keep Calm and Cache On

I had a great conversation with a friend about premature optimizations.
One thing led to another, and we have started talking about caching and Memoization.

Each of us had a very different perspective on the matter, but the one thing we both agreed upon is the importance of performance.

He asked me if I could explain my thoughts in a layman's terms, and as Barney Stinson used to say, challenge accepted!

So before we begin, let's talk about what Memoization is and why we even need it.

What is Memoization?

Memoization is an optimization technique used primarily to prevent the re-calculation of the save results for the same output.
Basically, it means that our software will run faster.

Why should we use Memoization?

We should use Memoization for better performance and faster results.
For example, if we use any client-side JavaScript code, we are less likely to choke the main thread and have laggy UI, and nobody likes that \()/.

ENOUGH TALKING! LET ME SEE THE CODE!

You are right; I know that I would like to see some action before I keep reading.

Let's say that we have a simple function "add"; add takes two numbers and return the value of the bough of them;

const add = (a, b) => {  return a + b;};

In this function, we re-evaluate a+b every single time it is called.
This is not an "expensive" calculation. Therefore, we would unlikely to use Memoization for something like that, but we could do something like that if we would.

const cachedAdd = memoizer(add);cachedAdd(2,3); // 5 Not CachedcachedAdd(2,3); // 5 CachedcachedAdd(2,3); // 5 Cached

That's all nice and well, but how the heck does "memoizer" works?

Let's see if we can create a simple generic "memoizer" high-order function that we can reuse.

/** * Cache function results for given params * * @param {function} func * @returns {function(): (*)} */function memoizer(func) {  const cache = {};  return function() {    const key = JSON.stringify(arguments);    if (cache[key] !== undefined) {      return cache[key];    }    const result = func(...arguments);    cache[key] = result;    return result;  };}

There are many ways to go about writing this function, but let's go over this implementation step by step.
The "memoizer" takes a function, it uses the arguments object, and stringify it to create the key.
Once it has the key, the function checks to see if the key is available in the cache object; if it does, it returns the cached result, and we are done.
In case it does not, it will calculate the value, save it in the cache, and then return it.

Memoization exchanges time for space.

I know what you think, "I am not convinced that it worth the hassle."

Show me the money

Let's see some runtime results.
To see the following, I'll use the notorious Fibonacci Sequence function.

The Fibonacci Sequence is the series of numbers:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
The next number is found by adding up the two numbers before it;

We could implement such a function like so:

const fibonacci = n => {  if (n <= 1) return 1;  return fibonacci(n - 1) + fibonacci(n - 2);};const getFibonacci = (limit = 1) => {   const arr = [];   for (let i = 0; i <= limit; i++) {      arr.push(fibonacci(i));   }   return arr;};

We can call the function like so:

getFibonacci(30); // will result [ 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ...]

Lets will run a benchmark test when the limit is 30:

console.time("fibonacci");for (let i = 0; i <= 100; i++) {   getCachedFibonacci(30);}console.timeEnd("fibonacci");

The first time we run it, it will result in 193.097ms;
The problem is that in case we will run this code 100 times, it will not get any better and might just get worst.
For example, this code ren 100 times in a total of 18357.116ms, which is shit tones.

Let's see if we could do better?
We will use the Memoization function that we wrote earlier to create a new cached Fibonacci function:

const cachedFibonacci = memoizer(fibonacci);const getCachedFibonacci = (limit = 1) => {  const arr = [];  for (let i = 0; i <= limit; i++) {    arr.push(cachedFibonacci(i));  }  return arr;};console.time("cachedFibonacci");for (let i = 0; i <= 100; i++) {   getCachedFibonacci(30);}console.timeEnd("cachedFibonacci");

This time around, we will get other results.
The first time we run it, it will result like before, and take around 193.509ms to resolve, but from the second time and beyond, the function resulted in an average of 0.027ms;
To a total of 199.988ms for the 100 iterations.

That results is 7,000~ times faster for each iteration.

Now, I know what you are thinking; not every problem is a Fibonacci one;
I can not stress it enough, Memoization is not a silver bullet, and it is not suitable for every scenario.
On the other hand, it is another powerful tool that can help your application performance when using correctly.

Should I create my own Memoization function?

Of course, you can do it, but in case you wish to use one of the open-source, well tested, well-documented Memoization function, here is a short list:

1. memoizee
2. memoized
3. lodash.memoize

If you have any questions or thoughts on the matter, I would love to hear them, and in the meantime, Keep Calm Cache On.