Memoization in JS and function acceleration

In pursuit of productivity, developers invent various ways to optimize programs. In our case we are talking about increasing the speed of the functions. Perhaps in JavaScript they can rightly be called one of the cornerstones of the language. In particular, functions are a means of breaking programs into modules and a tool for reusing code.

Some functions are executed so quickly that their multiple calls, although it creates a load on the system, is not a problem. Some are very “heavy”, each call to such functions leads to serious computational resources. If expenses are justified, calculations are optimized, then there is no place to go. But what if during repeated calls, the function sometimes (or, perhaps, quite often) performs the same calculations that were performed during its previous calls? Can this be used to improve performance?

Factorial calculation function and caching

The factorial calculation function is an example of a resource-intensive function that, almost guaranteed, during several calls, performs some of the same calculations many times. This opens up opportunities for optimization through caching.
')
For example, here is the factorial function, which calculates and returns the factorial of a number. If you do not go into details of its implementation, it will look like this:

 function factorial(n) {   // : n * (n-1) * (n-2) * ... (2) * (1)   return factorial } 

Call it as follows: factorial(50) . She, as expected, will find and return the factorial of the number 50. Everything is good, but now let's find the factorial of the number 51 with its help. The computer will again perform the calculations, and what we need will be found. However, it can be noted that, when the call is repeated, the function performs a lot of calculations that have already been performed. Let's try to optimize the function. Let's think about how, having the value factorial(50) go to factorial(51) without re-calling the function. If you follow the formula for calculating factorial, it turns out that factorial(51) is the same as factorial(50) * 51 .

With this approach, however, performance gains will not be obtained. Namely, first, inside the factorial() function, a complete chain of calculations is performed to find factorial 50, and then what happened is multiplied by 51. That is, using this function, the factorial calculation for the number 51 in any case looks like multiplication of all numbers from 1 to 51.

It would be nice if the factorial() function knew how to memorize the results of calculations performed during its previous calls and use them with the next calls to speed up performance.

Basics of memoisation

Asking about the preservation of the results of previous function calls, we come to the idea of ​​memoization. This is a technique that functions can use to memorize (or, in other words, cache) results. Now that you, in general terms, understand what we want to achieve, here is a stricter definition of memoization :

Memoization - saving the results of performing functions to prevent recalculations. This is one of the optimization methods used to increase the speed of execution of computer programs.

Simply put, memoization is memorization, the preservation of something in memory. Functions that use memoization usually work faster, because when they are repeated calls with the same parameters, instead of performing some calculations, they simply read the results from the cache and return them.

This is how a simple memo-based function might look. This code is on CodePen , so you can immediately experiment with it.

 //  ,  10     const add = (n) => (n + 10); add(9); //     const memoizedAdd = () => { let cache = {}; return (n) => {   if (n in cache) {     console.log('Fetching from cache');     return cache[n];   }   else {     console.log('Calculating result');     let result = n + 10;     cache[n] = result;     return result;   } } } //    memoizedAdd const newAdd = memoizedAdd(); console.log(newAdd(9)); //  console.log(newAdd(9)); //    

Function code analysis with memoization

After analyzing the above code snippet, we can draw the following conclusions:

• The function memoizeAdd returns another function that we can call when needed. This is possible because functions in JavaScript are first-class objects, which allows them to be used as higher-order functions and return other functions from them.
  
  
• The cache variable can store data between function calls, as it is defined in the closure .
  
  
• It is important that the memorized function is a pure function. This function, in particular, returns the same for the same arguments passed to it, regardless of how many times before it was called. Therefore, the cache variable behaves exactly as expected.
  

Writing a memorized function

The above code works as it should, but what if we would like to turn any function into its memorized version. Here's how to write such functions. This code, again, is on CodePen .

 //   ,      10 const add = (n) => (n + 10); console.log('Simple call', add(3)); //  ,     //   ,    const memoize = (fn) => { let cache = {}; return (...args) => {   let n = args[0];  //        if (n in cache) {     console.log('Fetching from cache');     return cache[n];   }   else {     console.log('Calculating result');     let result = fn(n);     cache[n] = result;     return result;   } } } //        'add' const memoizedAdd = memoize(add); console.log(memoizedAdd(3));  //  console.log(memoizedAdd(3));  //    console.log(memoizedAdd(4));  //  console.log(memoizedAdd(4));  //    

Fine! Our memoize function is able to turn other functions into their equivalents with memoization. Of course, this code is not universal, but it is easy to remake it so that the memoize function can work with functions that have any number of arguments.

You can write this on your own, but there are also library solutions:

• Lodash has a _.memoize(func, [resolver]) function _.memoize(func, [resolver])
  
  
• In ES7, you can use the decorators @memoize from decko .
  

Memoisation of recursive functions

If you try to transfer the recursive function of the memoize function above, or the _.memoize function from Lodash, what you get will not work correctly, since the recursive functions call themselves, not what you get after adding memoization capabilities. As a result, the cache variable in this situation does not fulfill its purpose. In order to solve this problem, the recursive function must call its own variant with memoization. Here's how to add memoization to the recursive factorial function. The code, as usual, can be found on CodePen .

 //     memoize const memoize = (fn) => { let cache = {}; return (...args) => {   let n = args[0];   if (n in cache) {     console.log('Fetching from cache', n);     return cache[n];   }   else {     console.log('Calculating result', n);     let result = fn(n);     cache[n] = result;     return result;   } } } const factorial = memoize( (x) => {   if (x === 0) {     return 1;   }   else {     return x * factorial(x - 1);   } } ); console.log(factorial(5)); //  console.log(factorial(6)); //   6,        

After analyzing this code, we can draw the following conclusions:

• The factorial function recursively calls its version with memoization.
  
• The memoization function caches the results of the factorial calculation, which, on subsequent calls, significantly improves performance. That is, in the example above, it turns out that instead of multiplying the numbers from 1 to 6 to find the factorial of 6, we only have to multiply by 6 what was returned by the previous call to factorial(5) .
  

About memoisation and caching

Memoisation is a type of caching. Usually, caching is a fairly wide range of ways to save something for later use. For example, it may be HTTP caching. Memoisation usually means caching the return values ​​of functions.

Results: when it is worth resorting to memoization

Although it may seem that the memoization technique is so good that it can and should become part of all the functions, it actually has limited application. Here are some considerations regarding the use of memoization.

• In order for a function to be memorated, it must be clean, always return the same values ​​in response to the same arguments.
  
  
• Memoization is a trade-off between performance and memory consumption. Memoisation is good for functions that have a relatively small range of input values, which allows quite often, when repeated calls of functions, to use the values ​​found earlier, without spending too much memory on storing data.
  
  
• It may seem that your own implementation of memoization should be applied, for example, when accessing certain APIs from browser code. However, this is not necessary, since the browser automatically caches them, using in particular the HTTP cache .
  
  
• If you are working with React / Redux, you can take a look at reselect . It uses a selector with memoization. This allows you to perform calculations only if changes occurred in the corresponding part of the state tree.
  
  
• Perhaps, best of all, functions with memoization show themselves where complex, resource-intensive calculations are performed. Here, this technique can significantly improve the performance of the solution. It should be noted that something like the calculation of factorial or Fibonacci numbers are good learning examples, but in the real world everything is much more interesting and complicated.
  

Dear readers! If you have examples of using memoization in real projects - please share. We are sure many will be interested to know about them.