What is Memoization?
Memoization is a smart way to make your functions faster by storing and reusing their past results. In JavaScript, it's like using a memory system: if a function is asked the same question again, it quickly retrieves the answer from its memory instead of recalculating it. This saves time and makes your code more efficient.
Memoizing a Synchronous Function
Memoizing a synchronous function is a straightforward process. All you need to do is create a cache object and store the results of the function in it. Then, before calling the function, you can check if the cache contains the result for the given arguments. If it does, you can return the cached value. Otherwise, you can perform the computation and store the result in the cache.
Understanding the Fibonacci Function, the most common example of memoization
let functionCalled = 0;
const fibonacci = (n) => {
if (n <= 1) return 1;
functionCalled++;
return fibonacci(n - 1) + fibonacci(n - 2);
};
console.log(fibonacci(10)); // 89
console.log(functionCalled); // 88
Before we get into the finer details of memoization, it's important to understand the Fibonacci function. In our example, we've created a function called fibonacci which takes a number n and returns the nth number in the Fibonacci sequence.
The Fibonacci sequence is a mesmerizing mathematical series where each number is the sum of the previous two numbers. It all starts with 0 and 1, and from there, the sequence unfolds into an awe-inspiring pattern. Here are the first 10 numbers in the Fibonacci sequence to give you a taste: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89.
The Fibonacci Challenge
Now, let's put this into perspective with the Fibonacci function we've created. When we call the fibonacci function with the number 10, it miraculously returns 89. However, what's really surprising is that the function was called a mere 88 times to calculate this result. This number might seem small, but here's where it gets interesting.
If we decide to challenge the Fibonacci function by calling it with the number 20, it reveals a really surprising result – 10,946! This is indeed the 20th number in the Fibonacci sequence. However, here's the catch: the function was called a whopping 10,945 times to reach this result. Yes, you read that correctly! We only increased the input number by 10, but the number of function calls surged from 88 to 10,945. This exponential increase in function calls as the input number increases is a significant issue.
To tackle this issue, we can implement memoization. Take a look at the modified code below:
let functionCalled = 0;
const fibonacci = (n, memo = {}) => {
if (n in memo) return memo[n];
if (n <= 1) return 1;
functionCalled++;
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
return memo[n];
};
console.log(fibonacci(10)); // 89
console.log(functionCalled); // 9
Now, with memoization, when we call fibonacci(10), it still returns 89, but the function was only called 9 times. This is a significant improvement over the previous version, especially when dealing with larger numbers. If we call fibonacci(20), the function is called just 19 times. This is a massive improvement over the previous version, where the function was called 10,945 times.
Let's break down what's happening in the code for a clearer understanding:
- The function accepts two arguments:
nandmemo. The n argument is the number whose Fibonacci value we want to calculate. The memo argument is an object that stores the results of previous function calls. We'll use this object to store the results of the function and retrieve them when necessary. - The function checks whether the memo object contains the result for the given number. If it does, the function returns the cached value. Otherwise, it proceeds to calculate the result.
- If the number is less than or equal to 1, the function returns 1. This is the base case of the function.
Now, with this context in mind, let's proceed to explore the incredible world of memoization and how it can save the day by optimizing these calculations.
Memoizing an Async Function
Memoizing an asynchronous function presents unique challenges. Consider this async function simulating an API call:
const fakeAPICall = async (userId) => {
return new Promise((resolve, reject) => {
setTimeout(() => resolve({ userId, name: "John Doe" }), 100);
});
};
Promise.all([
fakeAPICall(1),
fakeAPICall(1),
fakeAPICall(1)
]).then(console.log);
// [{userId: 1, name: 'John Doe'}, ...]
Although it works as intended, running this code results in three separate API calls. This is inefficient, why make three API calls when we can make just one and reuse the retrieved data? To address this issue, we can store the data in a variable like fibonacci example, and return it from the cache if the function is called again with the same input.
Let's dig into a practical example to illustrate this improvement:
let cache = {};
const fakeAPICall = async (userId) => {
if (userId in cache) return Promise.resolve(cache[userId]);
return new Promise((resolve, reject) => {
setTimeout(() => {
const response = { userId, name: "John Doe" };
cache[userId] = response;
resolve(response);
}, 100);
});
};
Promise.all([
fakeAPICall(1),
fakeAPICall(1),
fakeAPICall(1)
]).then(console.log);
// [{ userId: 1, name: 'John Doe' }, ...]
This seems promising; we're successfully caching the data in the global cache variable. When the second and third API calls are made, we efficiently retrieve the cached data. However, there's a critical issue with this approach.
The problem persists when we make repeated API calls with the same userId. To demonstrate this issue, let's add a console.log statement within the fakeAPICall function and observe the behavior:
let cache = {};
const fakeAPICall = async (userId) => {
if (userId in cache) return Promise.resolve(cache[userId]);
console.log("API call made");
return new Promise((resolve, reject) => {
setTimeout(() => {
const response = { userId, name: "John Doe" };
cache[userId] = response;
resolve(response);
}, 100);
});
};
Promise.all([
fakeAPICall(1),
fakeAPICall(1),
fakeAPICall(1)
]).then(console.log);
// [{ userId: 1, name: 'John Doe' }, ...]
When we execute this code, we observe that "API call made" is logged three times, which is not the desired outcome. Ideally, we want to perform the API call just once and utilize the cached data for subsequent calls.
Before we dig into the solution, it's essential to understand why this issue arises. When we initiate three parallel API calls, the first call finds the cache empty, prompting it to make an API request to retrieve the data. Since the API call is asynchronous, it takes some time to complete. During this period, the second and third function calls are triggered. As the cache remains empty, these calls also initiate new API requests. Consequently, we witnessed "API call made" being logged three times in the console.
One possible solution might be making the API call synchronous, which would indeed address the problem. However, this is not an advisable approach. Synchronous API calls can block the main thread, leading to a less responsive application and a less than ideal user experience.
Try it yourself
Take a pause here and think about the solution to this problem. If you've already found the solution, that's fantastic. However, if you haven't, there's no need to worry. In the next section, I'll provide a clear and effective solution to address the issue.
The Solution: Memoizing Async Functions
The key to resolving this challenge lies in minimizing redundant API calls when we know that the required data is not yet available in the cache. To achieve this, we'll introduce a concept called a "promise queue."
Here's how it works:
- When the first API call is initiated, it checks the cache. If the data is not present, the call proceeds to fetch the data as usual.
- While the initial API call is in progress, any subsequent calls are not discarded. Instead, they are added to a queue of promises, patiently waiting for the data to become available.
- When the first API call completes and the data is obtained, it resolves not only the original promise but also all the promises in the queue. This ensures that all subsequent calls receive the data they were waiting for.
In this way, we make just one API call, and the cached data is efficiently shared with all pending requests.
For a more detailed understanding of this solution, let's explore a practical example.
let cache = {};
let promiseQueue = [];
let inProgress = false;
const fakeAPICall = async (userId) => {
if (userId in cache) return Promise.resolve(cache[userId]);
if (inProgress) {
return new Promise((resolve) => promiseQueue.push(resolve));
}
console.log("API call made");
inProgress = true;
return new Promise((resolve, reject) => {
setTimeout(() => {
const response = { userId, name: "John Doe" };
cache[userId] = response;
resolve(response);
// Process the promise queue
promiseQueue.forEach((resolve) => resolve(response));
// Reset the promise queue
promiseQueue = [];
inProgress = false;
}, 100);
});
};
Promise.all([
fakeAPICall(1),
fakeAPICall(1),
fakeAPICall(1)
]).then(console.log);
// [{ userId: 1, name: 'John Doe' }, ...]
When you run this code, you'll notice that the message "API call made" is only logged once. This is precisely the desired outcome. We've effectively minimized the API calls, executing them only once and efficiently utilizing cached data for all subsequent requests.
Let's break down what's happening in the code for a clearer understanding:
- Initial API Call: When the first API call is made, it checks whether the cache is empty. Since it is, the API request is triggered to fetch the data. Crucially, before making the API request, we set a variable called inProgress to "true." This serves as a signal to any subsequent function calls that the API request is already in progress.
- Queueing Subsequent Calls: As the second and third function calls come in, we don't reject or resolve them immediately. Instead, we return a promise for each and add the corresponding "resolve" function to a queue known as promiseQueue." This step is critical without explicitly resolving or rejecting a promise, it remains pending, and callers (in this case, the Promise.all` method) await its resolution or rejection.
- Resolution of Pending Promises: Once the first API call is successfully completed and the data is retrieved, we're ready to fulfil all the promises stored in the promiseQueue. This means that all the subsequent calls, which were patiently waiting, receive the same data they were waiting for. Subsequently, we clear the promiseQueue and set the inProgress variable back to "false."
Important Note: Handling Errors and Scalability
Before we conclude, it's vital to address a couple of crucial points to ensure the robustness and scalability of our solution.
- Error Handling: In the example provided, we have focused on the core functionality for simplicity. However, in a real-world scenario, it's essential to implement error handling. This includes dealing with situations where the API request fails or any unexpected errors occur. Proper error handling is crucial to maintaining the reliability of your application.
- User Scalability: As it stands, the current implementation is tailored for a single user ID, utilizing a global inProgress variable and queue. This design may lead to issues if you intend to use the function with different user IDs simultaneously. To make the solution scalable and applicable to multiple users, you'll need to consider a more dynamic approach that accounts for individual user requests and their corresponding queues.
Conclusion
In wrapping up, memoization proves to be a powerful tool for enhancing the performance of both synchronous and asynchronous functions. By understanding the challenges and implementing a promise queue, you can efficiently memorize your async functions, ultimately improving the efficiency of your JavaScript code. This optimization leads to faster execution, reduced resource consumption, and an overall smoother user experience. So, go ahead and apply these principles to your code, and you'll reap the rewards of more efficient and responsive applications. Thank you for reading!
Must Read If you haven't
More content at Dev.to.
Catch me on
Youtube Github LinkedIn Medium Stackblitz Hashnode HackerNoon
Top comments (8)
That sounds like a show-stopping bug to me. It's trivial to find cases that will break:
I also reject the idea that async functions need to be special-cased for memoizing. All you need to do is cache the promises returned from the async function, rather than caching the resolved values only once they're resolved. For example, with the following generic memoization function:
You can wrap your async function:
Then you'll get correct results in the minimal time and with the minimal number of API calls:
Thanks for the solution, This is the better and shorter solution for this problem.
Another option is to create a "promise cache" as well, and when requesting the same userId multiple times before it is available in the "normal cache", simply return the existing promise from the promise cache.
(One drawback though is if that one async call fails, all calls to the same promise will fail too)
That's a good point about handling promise failure. Here's an amended version of my
memoizefunction from my comment:I have a more efficient implementation in my lib:
If there are n items in memo , in the best case, O(n log n) units of time are used for each function call (given that there is a search). It is a very good method, but it does not always help to improve performance. The best case is the same RestFull APIs that are called in a limited number of applications..