DEV Community

Cover image for Memoization in Javascript
Anish Kumar
Anish Kumar

Posted on • Edited on

Memoization in Javascript

Memoization is a useful concept. It helps avoid time taking or expensive calculations, after it's been done once. Applying memoization to a synchronous function is relatively straightforward. This article aims to introduce the overall concept behind memoization and then dive into the problems and their solutions while trying to memoize async functions.

Memoization

Let's start with memoizing a pure function. Let's say we have a function called getSquare, which returns square of the given:

  function getSquare(x){
     return x * x
  }

Enter fullscreen mode Exit fullscreen mode

To memoize this we can do something like this:


const memo = {}

function getSquare(x){
    if(memo.hasOwnProperty(x)) {
      return memo[x]
    }
    memo[x] = x * x
    return memo[x]
}

Enter fullscreen mode Exit fullscreen mode

So, with few lines of code we've memoized our getSquare function.

Let's create a memoize helper. It would accept a pure function as the first argument and agetKey function (which returns a unique key given argument of the function) as the second argument, to return a memoized version of the function:

function memoize(fn, getKey){
  const memo = {}
  return function memoized(...args){
     const key = getKey(...args)
     if(memo.hasOwnProperty(key)) return memo[key]

     memo[key] = fn.apply(this, args)
     return memo[key]
  }
}
Enter fullscreen mode Exit fullscreen mode

We can apply this function to getSquare as follows:

const memoGetSquare = memoize(getSquare, num => num) 
Enter fullscreen mode Exit fullscreen mode

Memoizing a function accepting multiple arguments:

const getDivision = (a, b) => a/b

// memoizing using the helper
const memoGetDivision= memoize(getDivision, (a, b) => `${a}_${b}`)
Enter fullscreen mode Exit fullscreen mode

Memoizing async functions

Let's say there' a function called expensiveOperation(key) which accepts a key as an argument and performs some async operation before returning the final result via a callback:

// does some async operation and invokes the callback with final result

expensiveOperation(key, ( data) => {
   // Do something
})
Enter fullscreen mode Exit fullscreen mode

Let's use similar notion as above to memoize this function:

const memo = {}

function memoExpensiveOperation(key, callback){
  if(memo.hasOwnProperty(key)){
    callback(memo[key])
    return
  } 

  expensiveOperation(key, data => {
   memo[key] = data
   callback(data)
  })
}
Enter fullscreen mode Exit fullscreen mode

So that was pretty easy. But wait! It doesn't solve the whole problem yet. Consider the following scenario:

1- Invoked expensiveOperation with key 'a'

2- While #1 is still in progress, invoked it again with same key

The function would run twice for the same operation, because #1 is yet to save the final data in memo. That's not something we wanted. We would instead want concurrent calls to be resolved at once, after the earliest call is complete. Let's see how we can accomplish this:

const memo = {}, progressQueues = {}

function memoExpensiveOperation(key, callback){
     if(memo.hasOwnProperty(key)){
       callback(memo[key])
       return
      }

     if(!progressQueues.hasOwnProperty(key)){
        // processing new key, create an entry for it in progressQueues
        progressQueues[key] = [callback]

      } else {
       // processing a key that's already being processed, enqueue it's callback and exit. 
        progressQueues[key].push(callback);
        return
      }

      expensiveOperation(key, (data) => {
           // memoize result
           memo[key] = data 
           // process all the enqueued items after it's done
           for(let callback of progressQueues[key]) {
                callback(data)
           }
           // clean up progressQueues
           delete progressQueue[key]
       })

}
Enter fullscreen mode Exit fullscreen mode

We can go a step further, just like the last section, and create a re-usable helper say memoizeAsync:

function memoizeAsync(fn, getKey){
   const memo = {}, progressQueues = {}

   return function memoized(...allArgs){
       const callback = allArgs[allArgs.length-1]
       const args = allArgs.slice(0, -1)
       const key = getKey(...args)

        if(memo.hasOwnProperty(key)){
            callback(key)
            return
        }


        if( !progressQueues.hasOwnProperty(key) ){
           // processing new key, create an entry for it in progressQueues
           progressQueues[key] = [callback]
        } else {
           // processing a key that's already being processed, enqueue it's callback and exit. 
           progressQueues[key].push(callback);
           return
        }

        fn.call(this, ...args , (data) => {
           // memoize result
           memo[key] = data 
           // process all the enqueued items after it's done
           for(let callback of progressQueues[key]) {
                callback(data)
           }
           // clean up progressQueues
           delete progressQueue[key]
       })
   }
}

// USAGE

const memoExpensiveOperation = memoizeAsync(expensiveOperation, key => key)

Enter fullscreen mode Exit fullscreen mode

Promises

Let's say we have a function processData(key) which accepts a key as argument and returns a Promise. Let's see how it can be memoized.

Memoizing the underlying promise:

Simplest way would be to memoize the promise issued against the key. Here's how it would look like:

const memo = {}
function memoProcessData(key){
  if(memo.hasOwnProperty(key)) {
    return memo[key]
  }

  memo[key] = processData(key) // memoize the promise for key
  return memo[key]
}
Enter fullscreen mode Exit fullscreen mode

The code is fairly simple and self explanatory here. In fact, we can use the memoize helper we created a while ago:

 const memoProcessData = memoize(processData, key => key)
Enter fullscreen mode Exit fullscreen mode

Can we memoize the value returned by Promise?

Yes. We can apply the same approach as the callback here. Though it might be an overkill for the sake of memoizing such a function:

  const memo = {},  progressQueues = {}

  function memoProcessData(key){

    return new Promise((resolve, reject) => {
      // if the operation has already been done before, simply resolve with that data and exit
      if(memo.hasOwnProperty(key)){
        resolve(memo[key])
        return;
      }

      if( !progressQueues.hasOwnProperty(key) ){
        // called for a new key, create an entry for it in progressQueues
        progressQueues[key] = [[resolve, reject]]

      } else {
       // called for a key that's still being processed, enqueue it's handlers and exit.         
        progressQueues[key].push([resolve, reject]);
        return;
      }


      processData(key)
        .then(data => {
            memo[key] = data; // memoize the returned data
            // process all the enqueued entries after successful operation
            for(let [resolver, ] of progressQueues[key])
              resolver(data)
        })
        .catch(error => {
           // process all the enqueued entries after failed operation
           for(let [, rejector] of progressQueues[key])
              rejector(error);
         })
        .finally(() => {
          // clean up progressQueues
           delete progressQueues[key]
         })
    })
  }
Enter fullscreen mode Exit fullscreen mode

Further improvement

Since we're using an memo object to keep track of memoized operations, with too many calls to expensiveOperation with various keys(and each operation returning a sizeable chunk of data post processing) the size of this object may grow beyond what's ideal. To handle this scenario we can use a cache eviction policy such as LRU (Least Recently Used). It would ensure we're memoizing without crossing memory limits!


This article has been originally published at StackFull.dev. If you enjoyed reading this, you may want to opt for my newsletter. It would let me reach out to you whenever I publish a new thought!

Top comments (9)

Collapse
 
nombrekeff profile image
Keff

Good stuff! I like that you pointed out the posible memory problems and LRU

Collapse
 
gerardolima profile image
Gerardo Lima • Edited

I'd recommend using a Map or a WeakMap as memo, instead of object. Also, I'd recommend using some sort of lock to avoid executing the underlying "expensive" function while another instance is running for the same parameters.

Collapse
 
anishkumar profile image
Anish Kumar • Edited

Yes. WeakMap would be a good choice if you are using objects as keys, it would facilitate better garbage collection in this case. If your keys are strings, using object should be fine.

Collapse
 
johandalabacka profile image
Johan Dahl

Why do the keyed value need to be handled by a promise? Isn’t the keyed value already calculated? An async function can both return a value or a promise.

Collapse
 
anishkumar profile image
Anish Kumar • Edited

I guess you're re-iterating the "Memoizing the underlying promise" section. Yes, for promises memoizing the actual value itself is bit of an overkill, but this approach goes beyond just promises, as explained in the article.
Also re-ordered the sections to convey the idea a bit better.

Collapse
 
johandalabacka profile image
Johan Dahl

Thanks, the new order was much clearer and the last example was really interesting and enlightning. Promises are really a powerful tool then you can wrap your head arounds them.

Collapse
 
jdforsythe profile image
Jeremy Forsythe

Instead of keeping a progress queue, you could just store the Promise itself in the cache.

Collapse
 
anishkumar profile image
Anish Kumar

Yes. That's already covered in "Memoizing the underlying promise:" section.

Collapse
 
invincible1388 profile image
Vilash Varghese

We can also benefit from closures by currying the functions with an argument.