Memoize-Immutable: efficient memoizer for Redux and other immutable environments
We’ve started working on a new app that creates parametric letters to be used inside Prototypo. We’ve adopted Redux to manage its state, and embraced the principle of data-normalization by making extensive use of memoization. When we hit our first performance issues, we realized that the memoizer we used had a very inefficient way to cache results, so we built our own. Today we release memoize-immutable and explain why it’s ideal for Redux and other immutable environments.
What is a memoizer?
The role of a memoizer is to increase the efficiency of a function:
- it wraps a function to intercept the arguments it receives and the results it produces,
- each time the function is executed, it associates the arguments to the result in a cache,
- so next time the same arguments are received, the results are returned immediately from the cache, without executing the original function.
What does it look like?
Here’s a basic implementation of a memoizer and usage example.
The main limitation of this memoizer is that it only works for functions that take a single primitive argument, such as one number or one string.
Memoizers that accept any number of arguments of any kind usually rely on JSON.stringify() and .toString() methods to serialize each arguments, then concatenate all these strings to generate a unique cache key (see Ramda’s memoize.js and dependencies for example).
This serialization can take a lot of time, especially for complex and deep objects. But this is usually the only way to create a reliable cache key, unless you’re working with immutable data…
Detecting changes in Redux and other immutable environments
Modern frontend frameworks help you manage the state of your application, and update its UI when the state changes. Consider an application that displays the family tree of the House of Windsor:
Where each member of the family is represented as a plain object:
If prince William was to be beheaded this year (excuse my French), in AngularJS and similar frameworks, the state would be mutated with:
houseWindsor[“William”].life.push(2016);
And inside the framework, detecting that change would basically require:
- making a deep copy of the complete state before the change occurs,
- and then making a recursive comparison of every property of every object between the previous state and the current state.
Both operations can be quite complex, this is why Redux opted for an immutable state: when a property deep in the state has to change, instead of modifying it directly, you re-create all “parent” objects that contain that property:
Detecting changes is then much easier:
- keep a reference to the previous state of the object,
- compare values using ===, as long as a value is === to the previous one, you don’t need to recurse into it.
An added benefit of an immutable environment is that the same === operator can be used to compare the arguments of a memoized function!
Map and the nested-maps dead-end
In our case, the fact that our memoizer used to serialize arguments was making memoization less efficient than no memoization at all. This was especially frustrating when we knew that arguments could be compared with ===.
Fortunately, ES2015 has brought us a new kind of object that can leverage immutability to solve a part of our problem: Map, a simple key/value map that accepts non-primitive values as keys, without serializing them:
Perfect! Although this could only be used as a cache when memoizing a function that accepts a single argument. Using the `arguments` array as the cache key wouldn’t work, as it will never be === to the next `arguments` passed to the function.
The first solution we came up with was to cache results in nested maps:
And it worked …except for one detail.
a memoization cache is a blatant memory leak, until you’ve found a way to control and limit its size.
Controlling the size of a Map is straightforward, but controlling the size of nested Maps is much more complicated and inefficient! Worse, by using a Map, all arguments would be kept in memory, even if they correspond to a part of the state that is no longer used in the app.
Serializing the reference of immutable objects
I exposed my problem to @LasseFister, and he soon suggested to use two different maps:
- One WeakMap used to map any non-primitive argument to a unique auto-incrementing id (the “Weak”ness of this Map allows forgetting about these arguments as soon as they’re no longer used),
- and then one Map used as a normal cache, where the cache keys would be a concatenation of primitive arguments and non-primitive identifiers.
This allowed us to build a single-level cache map whose size can be controlled very easily.
Bonus: limiting the size of a Map used as a cache
We compared different strategies to limit the size of the cache used by our memoize functions. We realized that, when using a native Map as a cache, we could use our app for a long while without noticing any increase in the memory used by the browser tab. We then compared the performances of this native Map with the performances of two different LRU cache implementations (one built on top of Map, and one built with a simple object and a double linked list).
Try our cache benchmark in your browser.
The results show that the two LRU solutions have comparable performances, but are 4 to 6 times slower than a native Map. So we decided not to implement any cache limiting algorithm in memoize-immutable, and leave this up to the user.
In our app, we provide our own native Map to the memoizer function, but keep a reference to it and clear it entirely every thirty minutes. You can start by having a look at our implementation and giving this solution a try!
Thanks Francois Poizat, Nicolas Chambrier, Lasse Fister, Paul Mougel, David Bruant and Matthieu Lux, for their reviews and suggestions on the module and this article.
Do you share our interest in using JS to create simple tools for creative people out there? Drop us an email: jobs@prototypo.io
