As I wrote the fastest memoization feature

In fact, I wrote perhaps the slowest function of memoization, but it turned out fast. My guilt is not here. It's all about balance.

In the balance between how long the function being memorized will be fulfilled, how much extra time will be required by the sugar of memoization, and (everyone will forget about it) how many programmers will need to be properly screwed up this memoization.


')
But let's start with a simple one - what kind of a word is so strange - “memoization”.

Memoization (from the English memoization) is one of the optimization methods used to increase the speed of computer program execution — saving the results of functions to prevent recalculations. Thanks to Wikipedia.

There are a LOT of libraries that provide this very memory, but everyone has their own different implementation details - how they work with the number of arguments, how they store the results and how much, well, of course, how fast they are.

The speed of the library is very different - thousands of times. But the whole secret is how they measure and how, of course, every author will find a case that suits his creation best of all, will find his own tricks.

Lodash.memoize , for example, works by default with one function argument. Fast-memoize - has a different code for the functions of one or more than one argument. Memoize-one or reselect silently saves one last answer, and is compared only with it. Which is very bad in some cases (calculation of fibonacci numbers, for example), and very good in others (React / Redux), with the exception of some features (more than one instance of the component).

In general, there are tricks everywhere. Without this, it would not be interesting. Let's look at the last case, which over the past couple of years has been VERY well chewed - Redux. Yes, that's not the end.

In the world of React / Redux, there is a mapStateToProps function that “selects” some values ​​for a specific element from a large common state. If the result of the function is different from the previously saved one, the component will be redrawn with new data.

const mapStateToProps = state => ({ todos: state.todos.filter(todo => todo.active) }); 

^ here I am a little nosyachil. I wanted to filter only active TODOs, but I will get a unique array (with non-unique values), with each function call. This is a very, very bad idea, since then the return value is compared by shallowequal, but it is not equal.

 const filterTodos = memoize(todos => todos.filter(todo => todo.active)); const mapStateToProps = state => ({ todos: filterTodos(state.todos) }); 

^ I corrected it here, and now the answer will change only if the array itself changes.

 const filterTodos = memoize(todos => todos.filter(todo => todo.active)); const getTodos = memoize(todos => todos.map(todo => todo.text )) const mapStateToProps = state => ({ todos: getTodos(filterTodos(state.todos)) }); 

^ and here I really wanted the answer to change only when the text was changed in the active TODO, but to want is not harmful. It is almost impossible to do.

Redux is a very good tool, and I love it with all my heart. But when it comes to parsing the state on the cascade of selectors, with the subsequent assembly in response, with the sole purpose - to memorize the result so that once again React does not pull. No guys - I do not play such games.

Here the matter is not in the speed of the function of the memoization, but in the process of the “correct” memoisation itself, the time spent on it and the expected final result.

And of course, we should not forget that not everything should be memosized. It is often easier to find something “for real” than to think that it is not necessary to count anything. Sugar memoization is far from free.

But! In the React / Redux environment, the speed of memoization means practically nothing. The very fact of memoisation is important. If you were able to understand in time that you already have the result, and you don’t need to update anything - you miss the giant piece of React code that would have wasted a part of the application.

And even the smallest optimization will be dozens of times greater than the "extra" calculations in the sugar memoization, which made this optimization possible.

Well, if it turns out that it is even possible to use the “complex” functions of memoization, when we consider not fibonacci, but something simpler, then let's search.

Memoize-state

Memoize-state is a library of memoization, based on slightly different principles, which makes memorization easier and faster. Despite the fact that the code in it is 10 times more than in the usual memoization function.

Let's start with examples

 const filterTodos = memoizeState(todos => todos.filter(todo => todo.active)); const getTodos = memoizeState(todos => todos.map(todo => todo.text )) const mapStateToProps =state => ({ todos: getTodos(filterTodos(state.todos)) }); 

^ The end result will only change if the text in the active TODO has changed.

 const filterTodos =todos => todos.filter(todo => todo.active); const getTodos = todos => todos.map(todo => todo.text ) const mapStateToProps = memoizeState (state => ({ todos: getTodos(filterTodos(state.todos)) })); 

^ completely identical result. Suddenly?

Memoize-state works on the principles similar to MobX or Immer.js - ES6 Proxy , WeakMaps, Reflection and other modern crap, which makes this magic possible.

In short, a memoize-state keeps track of how you use the passed arguments, and what you return as an answer. Then she understands what changes she should react to, and which changes shouldn’t. (it took almost a month to understand how this really should work)
In other words, you can write any function, wrap it in a memoize-state (at least 10 times), and they will be memorated to the theoretical maximum.

PS: !!! the function must be pure, otherwise the focus will fail. The function must accept "objects" as input, work with keys in objects and return the object, otherwise there will be garbage, not focus.

memoize-state is ideal for complex cases, and especially for mapStateToProps and any analogs. Do not try to use it to calculate fibonacci - there is TOO much logic in the depths too many times more than the complexity of the fibonacci calculation itself.

Speed

Once the conversation about speed, let's compare:

1. Calculation of fibonacci numbers. Fast-memoize library test

 0. base line x 123.592 (  ) 2. fast-memoize x 203.342.420 3. lodash x 25.877.616 4. underscore x 20.518.294 5. memoize-state x 16.834.719 6. ramda x 1.274.908 

Well - not the worst option.

2. The calculation of the "slow" function of the three integer arguments. A test from the memoize-state library

 0. base line x 10.646 (  ) 1. memoize-one x 4.605.161 2. memoize-state x 2.494.236 3. lodash.memoize x 2.148.475 4. fast-memoize x 647.231 

Already better.

3. Calculation of "mapStateToProps" is an object at the input, values ​​change randomly (or do not change).

 0. base line x 2.921 (  ) 1. memoize-state x 424.303 3. fast-memoize x 29.811 2. lodash.memoize x 20.664 4. memoize-one x 2.592 

Very good. memoize-state just rips to shreds. fast-memoize and lodash.memoize, like those based on JSON.stringify, handle cases when the object was given a new one, but the values ​​in it are old.

There's another test, when just a large object is served at the input, and the overhead of JSON.stringify takes off to the skies. There the difference is even greater.

The result is the slowest, because the most difficult, the function of memoization is not so slow at all. Yes, and the overhead of ensuring its work allows it to run 16 million per second, which of course is not as cool as 200 for the leaders of memoization, but a hundred thousand times more than the react / redux application needs.

Memoize-state differs from the usual functions of memoization in that it does not require configuration , it is friendly with memoizations that you already have (they will choose the keys they need from the general state), which ultimately allows you to call it “external memoization”.

As a result, even more magical magic becomes possible - beautiful-react-redux .
beautiful-react-redux is a wrapper for react-redux that silently wraps the mapStateToProps two times in a memoize-state, thereby providing automatic memoization for both one and many components (bye re-reselect ). One line - and the whole application has become a little (or a lot) faster. Without any work on your part, and this is important.

PS: beautiful-react-redux also provides a tool for testing the application for the "correctness" of memoization WITHOUT activating memoize-state. Those can use this magic to test a lower-level, more complex, but faster approach — standard libraries. More in repository.

The second excellent example of use is react-memoize - a library based on Dan Abramov’s tweet (and so it is), which memorizes the render, allowing you to actually abandon any logic in componentWillReceiveProps.



In fact, the implementation is slightly different. Just because the "selectors" are no longer needed, and the possibility of "just writing code."

Just pass some kind of props, just somehow count something based on them, and the trick is in the bag.

 <Memoize prop1 = "theKey" state = {this.state} compute={({prop1, state}) => heavyComputation(state[prop1])} > { result => <Display>{result}</Display>} </Memoize> 

And this again works simply, and completely automagically.

The second important option is the original memoize-state tests not only compare the speed, but also compare cache hit / miss. So - 99 out of 100 cases when you need to memoize, and 0 cases out of 100 when not necessary. It works almost perfectly. And of course, this is all covered in tests in three layers, as the memoize-state consists of three parts - a memoize-state for memoization itself, a proxyequal for wrapping, expanding and comparing objects and a search-trie to speed up the search for those parts of objects that follow. compare by value, and those which should not be.

Compatibility

There is only one minus for all this - for IE11 and Android (React Navite) it requires a polyfil for a proxy, which slows down somewhat. But it’s better that way.

It's time to act

There is still an untapped field ahead, for example, you can increase the speed of checking for memoization twice. Yes, and the react-redux integration can be freed from any calculations in some cases.

In general - all interested are invited to yarn add memoize-state , and experiments.

Github