Javascript Tips: Memoization

What is Memoization?

Memoization is a programming technique that caches the results of expensive function calls. This means that if a function is called with the same input more than once, the second and subsequent calls will return the cached result, rather than re-evaluating the function. This can significantly improve the performance of a function, especially if the function is computationally expensive. Memoization is relatively straightforward to apply to synchronous functions. However, it can be more challenging to apply to asynchronous functions. This is because asynchronous functions can potentially return results at any time, which makes it difficult to cache their results.

Memoization Use Cases

In this blog, we’ll show how a common caching implementation exposes a race condition. We’ll then show how to fix it, and (unlike most optimizations) we’ll simplify our code in the process. We’ll do this by introducing the Promise Memoization pattern, which builds on the Singleton Promise pattern.

Use Case: Caching Asynchronous Results

Consider the following simple API client:

const getUserById = async (userId: string): Promise => {
   const user = await request.get(`https://users-service/${userId}`); return user;
};

But, what should we do if performance is a concern? Perhaps it is slow to resolve user details, and maybe we’re frequently calling this method with the same set of user IDs. We’ll probably want to add caching. How might we do this? Here’s the naive solution I frequently see:

const usersCache = new Map();
const getUserById = async (userId: string): Promise => {
   const user = await request.get(`https://users-service/${userId}`); return user;
};
usersCache.set(userId, user); }
return usersCache.get(userId); };

It’s pretty better now. After we resolve the user details from users-service, we populate an in-memory cache with the result. However, it will make duplicate network calls in cases like the following:

await Promise.all([
   getUserById(user1),
   getUserById(user1)
]);

The problem is that we don’t assign the cache until after the first call resolves. But wait, how can we populate a cache before we have the result? Singleton Promises to the Rescue What if we cache the promise for the result, rather than the result itself? The code looks like this:

const userPromisesCache = new Map>();
const getUserById = (userId: string): Promise => { 
   if (!userPromisesCache.has(userId)) {
      const userPromise = request.get(`https://users-service/v1/${userId}`);
      userPromisesCache.set(userId, userPromise);
   }
   return userPromisesCache.get(userId)!;
}; 

Very similar, but instead of awaiting the network request, we place its promise into a cache and return it to the caller (which will await the result). Note that we no longer declare our method async, since it no longer calls await. Our method signature hasn’t changed though - we still return a promise, but we do so synchronously. This fixes the race condition. Regardless of timing, only one network request fires when we make multiple calls to getUserById("user1"). This is because all subsequent callers receive the same singleton promise as the first. Problem solved!

Best Solution: Promise Memoization

Seen from another point, our last caching implementation is literally just memoizing getUserById! When given an input we’ve already seen, we simply return the result that we stored (which happens to be a promise). So, memoizing our async method gave us caching without the race condition. The upside of this insight is that there are many libraries that make memoization dead-simple, including lodash memoization: https://lodash.com/docs/4.17.15#memoize. This means we can simplify our last solution to:

import memoize from "lodash/memoize";
const getUserById = memoize(async (userId: string): Promise => {
   const user = await request.get(`https://users-service/${userId}`);
   return user;
}); 

We took our original cache-less implementation and dropped in the memoize wrapper! Very simple and noninvasive.

Please note that in production, you should absolutely be using memoizee with the promise: true flag to avoid caching errors.

import memoize from "lodash/memoize";
const getUserById = memoize(async (userId: string): Promise => {
   const user = await request.get(`https://users-service/${userId}`);
   return user;
}, { promise: true });

Thanks for reading!