Introduction

Hi, and welcome to another article. I'm glad you're back!

During software development, not a small amount of time is spent fixing issues that emerged while building an application. Usually, you are fixing either syntax errors or semantical (logical) errors. After you fix all of those, you ship your code to the test environment and walk around proud of yourself how you did it, and that the required functionality has been implemented...

--

After coming back from your lunch break with a cup of coffee, you see that there is a problem. The tester is complaining that the application is too slow, in other words, your code is too slow, which is not acceptable. Now, you must revisit your implementation and rethink what could be done differently to improve the performance.

--

This is a common situation in software development, especially if you are building software involved in some kind of calculations for example.

In this article, I will show you one of the many steps you can take to improve the overall performance of your application.

What is Memoization?

In computing, memoization 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

The text quoted from Wikipedia is straight-forward and basically means that our function is not going to be executed more than once and the result of it is going to be stored for future use. Let's back up the statement with an example.

Example

An important thing to mention is that this technique is not a part of any programming language, meaning that it can be used in any language you prefer. In our example, we will be using JavaScript. The reason for this is simple, we can easily use any text editor and perform quick tests in the browser console.

First, let's create a problematic function. For this purpose, we can use the Fibonacci Array implementation for example or create nested loops to pow or square a number.

Inefficient Function

const fibonnaci = (n) => {
  if (n < 2) return 1;
  return fibonnaci(n - 1) + fibonnaci(n - 2);
}

console.time("First run");
fibonnaci(42);
console.timeEnd("First run");

console.time("Second run");
fibonnaci(42);
console.timeEnd("Second run");

// First run: 2853.337890625ms
// Second run: 2854.5107421875ms

The above code runs for quite some time, almost 3 seconds. Note that this time could vary depending on the power of your PC, but nevertheless it will be longer than it should be. You've probably noticed that we've called the fibonnaci function twice with the same parameter, and even though we know that the output is going to be the same, we still need to wait for another 3 seconds for the code to gives us the result.

Here is where our memoization comes into the picture.

Memoization Function

Below, you can see a simple implementation of the memoization function. This function:

  • Takes a function to memoize as a parameter
  • Creates a wrapper function handling the cache logic described below
    • Defines a local cache (Map object)
    • Checks if the cache has a value with a specific key created based on the arguments
    • If there is no value with that key, stores the value
    • Returns the value from the cache
  • Returns the wrapper function
const memoize = (func) => {
  const cache = new Map();
    
  return (...args) => {
    const key = args.join('-');

    if(!cache.has(key)) {
      cache.set(key, func(args))
    }

    return cache.get(key);
  }
}

Now, we can update our code to memoize the fibonacci function and try it again.

const fibonnaciMemo = memoize(fibonnaci);

console.time("First run");
fibonnaciMemo(42);
console.timeEnd("First run");

console.time("Second run");
fibonnaciMemo(42);
console.timeEnd("Second run");

console.time("Third run");
fibonnaciMemo(42);
console.timeEnd("Third run");

// First run: 2858.337158203125ms
// Second run: 0.005859375ms
// Third run: 0.003173828125ms

Voila! We wait for 3 seconds only after the first call and every next time we simply return the value from our cache.

What's important here is to mention the way we are creating the keys for our cache. Our key is built by joining the function arguments and placing a dash between each of them. This is fine, but it is also a limitation. You wonder why? Well, if the function is not a pure one, meaning that it depends on more than its input, the output will not be the same each time we invoke it and our memoization function stores the result after the first call. In this scenario, our memoized function will not provide the correct result every time.

Conclusion

This short article should give you the idea of how and when to use memoization in your application. It can boost your performance significantly, but it can also be a bottleneck, and possibly create hard-to-find issues that will give you a headache.

If you liked what you've read, please consider supporting me by buying me a coffee. To stay tuned, follow me on twitter or subscribe here on devinduct.

Of course, feel free to leave a comment and express your opinion about this.

Thank you for reading and see you in the next article!