I had a great conversation with a friend about premature optimizations.
One thing led to another, and we have started talking about caching and Memoization.
Each of us had a very different perspective on the matter, but the one thing we both agreed upon is the importance of performance.
He asked me if I could explain my thoughts in a layman's terms, and as Barney Stinson used to say, challenge accepted!
So before we begin, let's talk about what Memoization is and why we even need it.
What is Memoization?
Memoization is an optimization technique used primarily to prevent the re-calculation of the save results for the same output.
Basically, it means that our software will run faster.
Why should we use Memoization?
We should use Memoization for better performance and faster results.
For example, if we use any client-side JavaScript code, we are less likely to choke the main thread and have laggy UI, and nobody likes that Β―\(γ)/Β―.
ENOUGH TALKING! LET ME SEE THE CODE!
You are right; I know that I would like to see some action before I keep reading.
Let's say that we have a simple function "add"; add takes two numbers and return the value of the bough of them;
const add = (a, b) => {
return a + b;
};
In this function, we re-evaluate a+b every single time it is called.
This is not an "expensive" calculation. Therefore, we would unlikely to use Memoization for something like that, but we could do something like that if we would.
const cachedAdd = memoizer(add);
cachedAdd(2,3); // 5 Not Cached
cachedAdd(2,3); // 5 Cached
cachedAdd(2,3); // 5 Cached
That's all nice and well, but how the heck does "memoizer" works?
Let's see if we can create a simple generic "memoizer" high-order function that we can reuse.
/**
* Cache function results for given params
*
* @param {function} func
* @returns {function(): (*)}
*/
function memoizer(func) {
const cache = {};
return function() {
const key = JSON.stringify(arguments);
if (cache[key] !== undefined) {
return cache[key];
}
const result = func(...arguments);
cache[key] = result;
return result;
};
}
There are many ways to go about writing this function, but let's go over this implementation step by step.
The "memoizer" takes a function, it uses the arguments object, and stringify it to create the key.
Once it has the key, the function checks to see if the key is available in the cache object; if it does, it returns the cached result, and we are done.
In case it does not, it will calculate the value, save it in the cache, and then return it.
Memoization exchanges time for space.
I know what you think, "I am not convinced that it worth the hassle."
Show me the money
Let's see some runtime results.
To see the following, I'll use the notorious Fibonacci Sequence function.
The Fibonacci Sequence is the series of numbers:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
The next number is found by adding up the two numbers before it;
We could implement such a function like so:
const fibonacci = n => {
if (n <= 1) return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
};
const getFibonacci = (limit = 1) => {
const arr = [];
for (let i = 0; i <= limit; i++) {
arr.push(fibonacci(i));
}
return arr;
};
We can call the function like so:
getFibonacci(30); // will result [ 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ...]
Lets will run a benchmark test when the limit is 30:
console.time("fibonacci");
for (let i = 0; i <= 100; i++) {
getCachedFibonacci(30);
}
console.timeEnd("fibonacci");
The first time we run it, it will result in 193.097ms;
The problem is that in case we will run this code 100 times, it will not get any better and might just get worst.
For example, this code ran 100 times in a total of 18357.116ms, which is shit tones.
Let's see if we could do better?
We will use the Memoization function that we wrote earlier to create a new cached Fibonacci function:
const cachedFibonacci = memoizer(fibonacci);
const getCachedFibonacci = (limit = 1) => {
const arr = [];
for (let i = 0; i <= limit; i++) {
arr.push(cachedFibonacci(i));
}
return arr;
};
console.time("cachedFibonacci");
for (let i = 0; i <= 100; i++) {
getCachedFibonacci(30);
}
console.timeEnd("cachedFibonacci");
This time around, we will get other results.
The first time we run it, it will result like before, and take around 193.509ms to resolve, but from the second time and beyond, the function resulted in an average of 0.027ms;
To a total of 199.988ms for the 100 iterations.
π That results is 7,000~ times faster for each iteration.
Now, I know what you are thinking; not every problem is a Fibonacci one;
I can not stress it enough, Memoization is not a silver bullet, and it is not suitable for every scenario.
On the other hand, it is another powerful tool that can help your application performance when using correctly.
Should I create my own Memoization function?
Of course, you can do it, but in case you wish to use one of the open-source, well tested, well-documented Memoization function, here is a short list:
If you have any questions or thoughts on the matter, I would love to hear them, and in the meantime, Keep Calm π Cache On.
Top comments (2)
Caching deterministic functions like this is great fun. For larger applications of this caching method, or to distribute the cache, you can also employ memcached or Redis.
What a fun read, thank you so much.
Hi Michael,
I agree with you! We are using Redis in production exactly for this purpose.
Of course there are many other ways to accomplish this.
It was my intention to explain how to do it in a very simple and easy way, without diving too deep to implementations where the memory is cashed, timeouts and so on.
Iβm so happy to hear that you enjoyed itπ€