July 4, 2017 at 15:31

JS Memoization and Function Acceleration

Original author: Divyanshu Maithani
  • Transfer
In pursuit of productivity, developers invent a variety of ways to optimize programs. In our case, we are talking about increasing the speed of functions. Perhaps in JavaScript they can rightfully be called one of the cornerstones of the language. In particular, functions are a means of breaking down programs into modules and a tool for reusing code.

Some functions are performed so quickly that calling them repeatedly, although it puts a strain on the system, is not a problem. Some of them are very "heavy", each call to such functions leads to serious overhead of computing resources. If the expenses are justified, the calculations are optimized, then there is nowhere to go. But what if, upon 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 increase productivity?



Factorial Computation and Caching


The factorial calculation function is an example of a resource-intensive function that, almost guaranteed, during several calls, performs some part of the same calculations many times. This opens up opportunities for optimization through caching.

For example, here is a function factorialthat 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. All this is good, but now let's find the factorial of the number 51 with her help. The computer will perform the calculations again, and what we need will be found. However, you may notice that, when you call again, the function performs a lot of calculations that have already been performed previously. Let's try to optimize the function. Let’s think about how, having the value factorial(50)to go to factorial(51)without calling the function again. If you follow the formula for calculating factorial, it turns out that factorial(51)this is the same as factorial(50) * 51.

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

It would be nice, if the function factorial()could remember the results of calculations performed at its previous calls and use them at the next calls to speed up performance.

Memoization Basics


Asking the question of saving the results of previous function calls, we come to the idea of ​​memoization. This is a technique that functions can use to store (or, in other words, cache) results. Now that you, in general terms, understand what we want to achieve, here is a more rigorous definition of memoization :
Memoization - saving the results of the execution of functions to prevent repeated calculations. This is one of the optimization methods used to increase the speed of computer programs.

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

Here's what a simple memoization function might look like. This code is on CodePen , so you can experiment with it right away.

// простая функция, прибавляющая 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 fragment, we can draw the following conclusions:

  • The function memoizeAddreturns another function that we can call when necessary. This is possible because functions in JavaScript are first-class objects, which allows you to use them as higher-order functions and return other functions from them.

  • A variable cachecan store data between function calls, since it is defined in a closure .

  • The important thing is that the function with memoization is a pure function. This function, in particular, returns the same for the same arguments passed to it, regardless of how many times it was called before. Therefore, the variable cachebehaves exactly as expected.

Writing a function with memoization


The above code works as it should, but what if we would like to turn any function into its version with memoization. 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));  // взято из кэша

Excellent! Our function memoizeis able to turn other functions into their equivalents with memoization. Of course, this code is not universal, but it is not difficult to redo it so that the function memoizecan work with functions that have any number of arguments.

You can write this yourself, but there are library solutions:


Memoization of recursive functions


If you try to pass a recursive function to the function considered above memoize, or to a function _.memoizefrom Lodash, then what happens will not work correctly, since recursive functions call themselves, and not what happens after adding memoization capabilities. As a result, the variable cachein this situation does not fulfill its purpose. In order to solve this problem, a recursive function must call its own variant with memoization. Here's how to add memoization to a recursive factorial calculation function . 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, но для предыдущих значений взято из кэша

Having analyzed this code, we can draw the following conclusions:

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

About Memoization and Caching


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

Results: when to resort 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 use. Here are some considerations regarding the use of memoization.

  • In order for a function to be subject to memoization, it must be clean, always returning the same values ​​in response to the same arguments.

  • Memoization is a trade-off between performance and memory consumption. Memoization is good for functions that have a relatively small range of input values, which often allows you to use the values ​​found earlier when calling functions repeatedly, without wasting too much memory.

  • It might seem that your own implementation of memoization should be used, for example, when accessing certain APIs from browser code. However, this is not necessary, as 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 . Here a selector with memoization is used. This allows you to perform calculations only if changes have occurred in the corresponding part of the state tree.

  • Perhaps, memoization functions are best shown where complex, resource-intensive calculations are performed. Here, this technique can significantly increase the performance of a solution. It should be noted that something like calculating factorial or Fibonacci numbers are good training 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 that many will be interested to know about them.
Tags:

Also popular now: