DEV Community

Cover image for Optimize the hell out of your  Javascript programs with Memoization.
Ola' John Ajiboye
Ola' John Ajiboye

Posted on

Optimize the hell out of your Javascript programs with Memoization.

Many moons ago when I started learning algorithms, I had just learned recursion and was feeling like a Jedi. You know what they say?: "if all you have is a hammer, everything looks like a nail". I was trying to solve every task imaginable with some form of recursion. Turns out it was a terrible idea.

I got a rude awakening when I tried to solve a long sequence of Fibonacci series with Recursion, my computer just couldn't handle it. It still couldn't compute the result after a couple of hours. Full disclosure; it never did, I gave up, shut the whole damn thing down and started rethinking my decision to ever become a programmer. Why didn't I just learn how to rap, I could have become the next Jay-Z you know. I had no clue what was going on.

Confused now.gif

That was the first time I ever thought about the concept of optimization.

If you are the curious type, run the un-optimized recursive Fibonacci series with a sequence up to 50.....see you tomorrow!๐Ÿ˜ƒ

So what is optimization?

So what is optimization and why do you need to start thinking about it even as an inexperienced developer.

An optimization algorithm is a procedure which is executed iteratively by comparing various solutions till an optimum or a satisfactory solution is found.

For example in the optimization of a design, the design objective could be simply to minimize the cost of production or to maximize the efficiency of production.

And now, what is Memoization?

I know you are tempted to think that I misspelled "memorization". But no! , I am positive I meant memoization. Memoization is a term in computer science which means the technique or optimization pattern that speeds up the execution of a program by storing the results of complex function calls (functions that takes a lot of time and consumes lots of memory during the run of the function) and returning the result stored in memory when the same inputs or arguments occur again.

Urgh!!, enough of the computer science jargons!. I don't even have a CS degree why should you trust my definitions. Allow me to show you the codes.

I will stick to the Fibonacci series that nearly made me quit programming. We'll explore an example of an un-optimized Fibonacci function and another one optimized using memoization.

Set up

To be able to visualize the difference. We'll need a little bit of one-time setup. I am a Javascript guy, I will be using a Node environment. You could use whatever performance metrics you are familiar with.

A NodeJS code sandbox will suffice. Let's install and require perf-hooks. Simply require performance from perf-hooks like so:

const { performance } = require("perf_hooks");

Now let's write a function that calculates the Fibonacci sequence of nth number recursively.

function fibonacci(n) {
  if (n === 0 || n === 1)
    return n;
  else
    return fibonacci(n - 1) + fibonacci(n - 2);
}

This function performs well for small values of โ€œnโ€. However, performance quickly degrades as โ€œnโ€ increases. This is because the two recursive calls repeat the same work. For example, to compute the 50th Fibonacci number, the recursive function must be called over 40 billion times (40,730,022,147 times to be specific)! We'll see this visually later.

A memoized Fibonacci function.

In the memoized version of the Fibonacci function When f() is returned, its closure allows it to continue to access the โ€œmemoโ€ object, which stores all of its previous results. Each time f() is executed, it first checks to see if a result exists for the current value of โ€œnโ€. If it does, then the cached value is returned. Otherwise, the original Fibonacci code is executed. Note that โ€œmemoโ€ is defined outside of f() so that it can retain its value over multiple function calls.

var memoizeFibonacci = function() {
  var memo = {};

  function f(n) {
    var value;

    if (n in memo) {
      value = memo[n];
    } else {
      if (n === 0 || n === 1)
        value = n;
      else
        value = f(n - 1) + f(n - 2);

      memo[n] = value;
    }

    return value;
  }

  return f;
};

Comparing performance with perf-hooks.

Let's visualize the time it takes to compute 30th Fibonacci number with both functions.

//un-optimized
// time before function is executed
const startTime = performance.now();
fibonacci(20);
// time after function has completed computation
const endTime = performance.now();

console.log("Un-optimized time", endTime - startTime);

// memoized
const startTime2 = performance.now();
memoizeFibonacci(20);
// time after function has completed computation
const endTime2 = performance.now();

console.log("Optimized time", endTime2 - startTime2);
//result

Un-optimized:  1020.0609370004386
Optimized:  0.049122998490929604

You can see we already increased the time to compute by a magnitude of over 20000. That's just for a sequence of 30 numbers. This example is quite simple and may not look similar to your everyday tasks, but if you looked deeply there are a couple of things that can be optimized in your program. Keep in mind that memoization is just one optimization method, there are countless different strategies. Don't be the hammer guy that treats every problem like a nail.

Note also that we have barely scratched the surface of memoization, this is just to open our minds to the possibilities.

The fact that it works does not mean it can't be improved. Go forth and optimize!

PS: The title is a bit of an exaggeration. It just happened to be the 97th title that crossed my mind๐Ÿ˜ƒ

Top comments (9)

Collapse
 
mvoloskov profile image
Miloslav ๐Ÿณ๏ธโ€๐ŸŒˆ ๐Ÿฆ‹ Voloskov

The point about people not using it is not quite right.

But people don't quite use it in JavaScript indeed. JavaScript is a frontend language after all, at least it was initially meant for it. Right before React, frontend was driven by "dirty", functionally impure things like jQuery.

Memoization is only possible in pure environments. Thus, it was receiving almost no traction whatsoever.

Aside of JavaScript, look at the functional landscape โ€“ people thrive on memoization in lisps, as well as on lazy evaluation, pattern-matching and other good old functional things.

Good things to come โ€“ย modern frontend is moving towards functional concepts.

Memoization and other good things are to be resurfaced.

@akashkava

Collapse
 
mongopark profile image
Ola' John Ajiboye

Thanks a bunch for your input. You nailed the point. Because Javascript is easier to get started with it, it's easier to keep doing the dirty stuffs. But even at the moment React implements meomoization with React.Memo and stuffs.

Collapse
 
akashkava profile image
Akash Kava

I believe the word is called caching and its very old technique, but yes, people don't use it !!

Collapse
 
elmuerte profile image
Michiel Hendriks

Caching and memoization are related, but not the same. Caching is mutable, and generally constraint in size or time.

Catch invalidation is a thing, memoization invalidation is not.

In most cases you want caching. Only in certain algebraic cases you want memoization.

Collapse
 
mongopark profile image
Ola' John Ajiboye • Edited

Yea, you are correct. It's similar to caching but not exactly the same.

Collapse
 
luispa profile image
LuisPa

Great post!

Collapse
 
selahattinunlu profile image
Selahattin รœnlรผ

Wow, there is so huge difference between them.
I've never heard the memoization term before. Thanks, it was great!

Collapse
 
jamesthomson profile image
James Thomson

Great write up and use case for memoization. Amazing to see what a difference it can make when used in a use case like this. ๐Ÿคฏ

Collapse
 
monicat profile image
Monica Macomber

Urgh!!, enough of the computer science jargons!. I don't even have a CS degree why should you trust my definitions.

I love all the personality in your article ๐Ÿ˜‚ Very helpful too, thanks.