Codementor Events

2 Separate Strategies for Memoization

Published Sep 17, 2019
2 Separate Strategies for Memoization

Check out the original version of this article on my Developer Blog.

When you first learn about memoization in JavaScript, it looks like the magic tool that solves all your performance problems. People tend to start applying memoize over everything without thinking too much about what it is really doing. (I know I did)

There are a load of different memoization libraries out on npm, many of them are built on really great ideas. I am not aiming to cover the different libraries here, that would make a really long article. One important thing to realize, is that there are actually two really different strategies for memoization, and most likely at some point you'll have a usecase for both in your application. So most of the time, you should be using at least two different memoization helpers (or a single library with 2 distinct configurations).

Strategy 1 - only the latest input matters

In this strategy only one result (and one input) is remembered by the helper. If the memoized function is called with a new (set of) arguments, the old result is thrown away, and the new result is stored.

const complexCalculation(input) = memoize(...);

complexCalculation(1); // NOT memoized
complexCalculation(1); // memoized
complexCalculation(2); // NOT memoized
complexCalculation(1); // NOT memoized
complexCalculation(2); // NOT memoized
complexCalculation(2); // memoized

This is great for scenarios where there is a single source of truth, and where results based on new inputs invalidate the old results. For example for indices over Redux stores, a transformation of session/user data, etc. Once Redux is updated, I know that no selector will query the old store, so it is safe (and efficient) to discard the old results.

Advantages:

  • Constant and predictable memory usage. The memory used is always at most the size of the latest result plus the size of the latest input.
  • Speed. There is no hashtree lookup here, the only performance impact of going through the memoization helper is the cost of comparing the inputs. Which - if using reference equality - is virtually zero.
  • Simplicity. These libraries are really easy to both implement and use. memoize-one for example is literally 36 lines of (non minified, easy-to-read) TypeScript code. When using it you don't have to worry about cache invalidation and its hurdles, it will just work™.

Disadvantages:

  • Does not memoize when multiple different inputs are used in an alternating fashion. This could be the case when multiple different modules of your code (e.g. multiple React components, or multiple instances of the same React component) are calling the same memoized function differently.
  • Most of these libraries compare inputs using reference equality (for speed), which need consideration.

Examples of single-item memoization by default: memoize-one, reselect, React.memo, React's useMemo hook.

Strategy 2 - Cache based memoization

This is the case where there is a need to remember multiple results. Taking the same example as above:

const complexCalculation(input) = memoize(...);

complexCalculation(1); // NOT memoized
complexCalculation(1); // memoized
complexCalculation(2); // NOT memoized
complexCalculation(1); // memoized
complexCalculation(2); // memoized
complexCalculation(2); // memoized

Now there is a much greater variety of implementations of cache based memoization, but in general this is a much more complicated case and as we all know:

With great power comes great responsibility.

The main consideration when using cache based memoization is memory leaks. Usually a function can be called with an infinite number of possible arguments. If we cache the result of each call into a simple object or Map we will - if we are not careful - allocate an ever growing amount of memory in doing so. You either need to make sure that only an acceptably small number of different calls will be made, or you need to implement / use a memoization helper that has some sort of eviction policy. (See the documentation for memoize-immutable which has a great supply of different underlying stores for different use cases.) This is a fairly simple task but failing to do so can cause significant headaches. Memory leak related problems are always hard to debug.

There is also the consideration whether you'd like to:

  • Stick with reference equality. This is very fast to look up, but can cause cache misses & garbage creation when called with an inline object literal (for example: memoizedFunction({someInput: 1}) will always miss.)
  • Implement some deep-equality check, mostly using JSON.stringify. This solves the problem above, but creating JSON strings every time is slower by about an order of magnitude, and will not handle functions as arguments.

Advantages:

  • Remembers multiple values.
  • Can be configured to use value equality.
  • More difficult to misuse and cause misses (when using value equality)

Disadvantages:

  • Slower, especially when using value equality.
  • Easy to accidentally cause memory leaks.
  • Therefore needs careful planning to be done right.

Examples of cache-based memoization:

  • fast-memoize (by default uses JSON.stringify with a simple object, which is actually slow, so interesting name choice)
  • re-reselect (made specially for reselect, has multiple cache options)
  • _.memoize (uses Map and reference equality by default)
  • memoize-immutable (has multiple powerful cache options)

Use the right tool for the job

All the strategies and libraries mentioned above (and many others) can be very useful to drastically improve the performance of your application. As with most other aspects of programming (especially in optimization) you have to first thoroughly understand your problem, and dedicate some time to select the right solution for your exact situation.

Feedback

If you enjoyed this article, feel free to check out my Developer Blog where I share more stories like this.

If you have any feedback or wish to learn more about a topic with me in a 1:1 mentoring session, feel free to contact me anytime!

Discover and read more posts from Marcell Toth
get started