Memoization in Javascript
Tags: javascript, memoization, algorithms, api
Published: 2021-08-29 04:06:22

---
title: Memoization in Javascript
published: true
description: 
tags: Javascript, Memoization, Algorithms, API
cover_image: https://images.unsplash.com/photo-1564325724739-bae0bd08762c?ixid=MnwxMjA3fDB8MHxwaG90by1wYWdlfHx8fGVufDB8fHx8&ixlib=rb-1.2.1&auto=format&fit=crop&w=1050&q=80
---


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:

```javascript
  function getSquare(x){
     return x * x
  }

```

To memoize this we can do something like this:
```javascript

const memo = {}

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

```

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 a`getKey` function (which returns a unique key given argument of the function) as the second argument, to return a memoized version of the function:

```javascript
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]
  }
}
```

We can apply this function to `getSquare` as follows:

```javascript
const memoGetSquare = memoize(getSquare, num => num) 
```

Memoizing a function accepting multiple arguments:

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

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

## 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:
```javascript
// does some async operation and invokes the callback with final result

expensiveOperation(key, ( data) => {
   // Do something
})
```

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

```javascript
const memo = {}

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

  expensiveOperation(key, data => {
   memo[key] = data
   callback(data)
  })
}
```
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:

```javascript
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]
       })
  
}
```

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

```javascript
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)

```

## 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:

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

  memo[key] = processData(key) // memoize the promise for key
  return memo[key]
}
```
The code is fairly simple and self explanatory here.  In fact, we can use the `memoize` helper we created a while ago:

```javascript
 const memoProcessData = memoize(processData, key => key)
```

### 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:

```javascript
  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]
         })
    })
  }
```

## 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](https://en.wikipedia.org/wiki/LRU) (Least Recently Used). It would ensure we're memoizing without crossing memory limits!

---

This article has been originally published at [StackFull.dev](https://stackfull.dev/memoizing-async-functions-in-javascript). If you enjoyed reading this, you may want to opt for my [newsletter](https://stackfull.dev). It would let me reach out to you whenever I publish a new thought!