Как я написал самую быструю функцию мемоизации
На самом деле я писал возможно самую медленную функцию мемоизации, да получилась быстрая. Моей вины тут нет. Все дело в балансе.
В балансе между тем насколько долго будет исполнятся мемоизируемая функция, сколько дополнительного времени потребует сахар мемоизации, и (про это все забывают) сколько програмистов потребуется, чтобы эту мемоизацию правильно прикрутить.
Но начнем с простого — что же это за слово такое странно — «мемоизация».
Мемоизация (от англ. memoization) — это один из способов оптимизации, применяемый для увеличения скорости выполнения компьютерных программ —сохранение результатов выполнения функций для предотвращения повторных вычислений .– Спасибо Википедия.
Библиотек которые обеспечивают эту самую мемоизацию — ОЧЕНЬ много, но у всех есть свои различные детали реализации — то как они работают с колличеством аргументов, то как они хранят результаты и сколько, ну, конечно же, насколько они быстры.
По скорости работы библиотеки ОЧЕНЬ сильно различаются — в тысячи раз. Но весь секрет в том что и как они измеряют, конечно же каждый автор найдет случай, который для его творения подходит лучше всего, найдет свои хитрости.
Lodash.memoize, например, по умолчанию работает с одним аргументом функции. Fast-memoize — имеет разный код для фунций одного или более чем одного аргумента. Memoize-one или reselect молча сохраняют один последний ответ, и сравнивают только с ним. Что очень плохо в одних случаях (расчет чисел фибоначи, например), и очень хорошо в других (React/Redux), за исключением некоторых особенностей (больше одного экземляра компонента).
В общем — везде есть свои хитрости. Без этого было бы не интересно. Давайте остановимся на последнем кейсе, который за последние пару лет был ОЧЕНЬ хорошо расжеван — Redux. Да вот не до конца.
В мире React/Redux есть функция mapStateToProps, которая «выбирает» из большого общего стейта некоторые значения для конткретного элемента. Если результат работы функции отличается от ранее сохраненного — компонент будет перерисован с новыми данными.
const mapStateToProps = state => ({
todos: state.todos.filter(todo => todo.active)
});
^ вот тут я немного накосячил. Я хотел отфильтровать только активные TODO, но буду получать уникальный массив (с неуникальными значениями), при каждом вызове функции. Это очень, очень плохая идея.
const filterTodos = memoize(todos => todos.filter(todo => todo.active));
const mapStateToProps = state => ({
todos: filterTodos(state.todos)
});
^ вот тут я это поправил, и теперь ответ будет меняться только если сам массив поменяется.
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))
});
^, а вот тут бы я очень хотел, чтобы ответ менялся только при изменении текста в активных TODO, но хотеть не вредно. Это практически не возможно сделать.
Redux — очень хороший инструмент, и я его люблю всем сердцем. Но когда дело доходит до разбора стейта на каскад селекторов, с последущей сборкой в ответ, с одной только целью — мемоизировать результат так чтобы лишний раз React не дергать. Нет ребят — я в такие игры не играю.
Тут дело уже не в скорости работы функции мемоизации, а в самом процессе «правильной» мемоизации, времени на нее затраченом и ожидаемом конечном результате.
Ну и конечно не стоит забывать, что далеко не все должно быть мемоизированно. Очень часто проще что-то посчитать «по-настоящему», чем посчитать что считать ничего не надо. Сахар мемоизации далеко не бесплатен.
Но! В среде React/Redux скорость мемоизации практически ничего не значит. Важем сам факт мемоизации. Если вы смогли вовремя понять, что результат у вас уже есть, и ничего обновлять не надо — вы пропускаете гиганский кусок React кода, который впустую обновил бы часть приложения.
И даже самая маленькая оптимизация будет в десятки раз превышать «лишние» вычисления в сахаре мемоизации, который сделал эту оптимизацию возможной.
Ну, а если получается, что использовать «сложные» функции мемоизации очень даже можно, когда не фибоначи считаем, а что-то попроще, — то давайте поиспользуем.
Memoize-state
Memoize-state — библиотека мемоизации, основанная на немного других принципах, которая делает мемоизацию проще, и быстрее. Несмотря на то, что кода в ней раз в 10 больше чем в обычной функции мемоизации.
Начнем с примеров
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))
});
^ конечный результат будет меняться только если изменился текст в активных TODO.
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))
}));
^ совершенно индентичный результат. Неожиданно?
Memoize-state работает на принципах схожих с MobX или Immer.js — ES6 Proxy, WeakMaps, Reflection и другая современная лабуда, которая и делает эту магию возможной.
В кратце — memoize-state следит за тем как вы используете переданные аргументы, и что возвращаете как ответ. После чего понимает на какие изменения ей следует реагировать, а на какие — нет. (потребовался почти месяц, чтобы понять как это на самом деле должно работать)
Другими словами — вы можете написать любую функцию, обернуть ее в memoize-state (хоть 10 раз), и они будет мемоизированна по теоритическому максимуму.
PS:!!! функция должна быть pure, иначе фокус не получится. Функция должна принимать на вход «обьекты», работать с ключами в обьектах и возвращать обьект, иначе будет фигня, а не фокус.
memoize-state идеально походит для сложных случаев, и особенно для mapStateToProps и любых аналогов. Не пытайтесь использовать ее для расчета фибоначи — в недрах СЛИШКОМ много логики, многократно превышающей сложность самого расчета фибоначи.
Скорость
Раз разговор про скорость, давайте сравним:
1. Расчет чисел фибоначи. Тест из библиотеки fast-memoize
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
Ну — не самый худший вариант.
2. Расчет «медленной» функции от трех integer аргументов. Тест из библиотеки memoize-state
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
Уже лучше.
3. Расчет «mapStateToProps» — обьект на вход, рандомно меняются (или не меняются) значения.
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
Совсем хорошо. memoize-state просто рвет в клочья. fast-memoize и lodash.memoize, как основанные на JSON.stringify обрабатывают случаи когда обьект дали новый, но значения в нем старые.
Там еще тест, когда на вход подается просто большой обьект, и накладные расходы на JSON.stringify взлетают до небес. Там разница еще больше.
В итоге получается — самая медланная, потому что самая сложная, функция мемоизации совсем не такая уж медленная. Да и накладные расходы на обеспечение своей работы позволяют ей запускаться 16 миллионов в секунду, что конечно же не так круто как 200 для лидеров мемоизации, но в сто тысяч раз больше чем нужно react/redux приложению.
Memoize-state отличается от обычных функций мемоизации тем, что не требует настройки, дружит в мемоизациями которые вы уже имеете (они же будут выбирать из общего state нужные им ключи), что в итоге позволяет назвать ее «внешней мемоизацией».
В результате становиться возможным еще более магическая магия — beautiful-react-redux.
beautiful-react-redux — это врапер для react-redux, который молча обернет mapStateToProps два раза в memoize-state, тем самым обеспечит автоматическую мемоизацию, как для одного, так и для множества компонентов (до свидания re-reselect). Одна строчка — и все приложение стало немного (или много) быстрее. Без какой либо работы с вашей стороны, и это главное.
PS: beautiful-react-redux так же предоставляет инструмент для тестирования приложение на «правильность» мемоизации БЕЗ активации memoize-state. Те можно использовать эту магию для проверки более низкоуровнего, более сложного, но более быстрого подхода — стандартных билблиотек. Подробнее в репозитации.
Второй прекрасный пример использования — react-memoize — библиотека на основе твита Дэна Абрамова (и так бывает), которая мемоизирует рендер, позволяя фактически отказаться от какой либо логики в componentWillReceiveProps.
По факту реализация немного отличается. Просто потому что «селекторы» более не нужны, и повилась возможность «просто писать код».
Просто передайте какие-то пропсы, просто как-то что-то на их основе посчитатайте, и дело в шляпе.
heavyComputation(state[prop1])}
>
{ result => {result} }
И это опять таки работает просто, и полностью автомагически.
Второй важный вариант — оригинальные тесты memoize-state не только сравнивают скорость, но и сравнивают cache hit/miss. Так вот — мемоизируются 99 из 100 случаев когда нужно мемоизировать, и 0 случаев из 100 когда не надо. Работает почти идеально. И конечно же это все покрыто тестами в три слоя, так как memoize-state состоит из трех частей — memoize-state для самой мемоизации, proxyequal для заворачивания, разворачивания и сравнения обьектов и search-trie для ускорения поиска тех использованных частей обьектов, которые следует сравнивать по значения, и тех которых не следует.
Совместимость
Минус у всего этого только один — для IE11 и Android (React Navite) требует полифил для прокси, что несколько замедляет работу. Но лучше уж так, чем никак.
Время действовать
Впереди еще непаханное поле, например можно увеличить скорость проверки на мемоизацию раза в два. Да и react-redux интеграцию можно избавить от каких либо расчетов в некоторых случаях.
В общем — все заинтересованные приглашаются к yarn add memoize-state, и экспериментам.
github.com/theKashey/memoize-state
