Как я написал самую быструю функцию мемоизации

На самом деле я писал возможно самую медленную функцию мемоизации, да получилась быстрая. Моей вины тут нет. Все дело в балансе.

В балансе между тем насколько долго будет исполнятся мемоизируемая функция, сколько дополнительного времени потребует сахар мемоизации, и (про это все забывают) сколько програмистов потребуется, чтобы эту мемоизацию правильно прикрутить.

Но начнем с простого — что же это за слово такое странно — «мемоизация».

Библиотек которые обеспечивают эту самую мемоизацию — ОЧЕНЬ много, но у всех есть свои различные детали реализации — то как они работают с колличеством аргументов, то как они хранят результаты и сколько, ну, конечно же, насколько они быстры.

По скорости работы библиотеки ОЧЕНЬ сильно различаются — в тысячи раз. Но весь секрет в том что и как они измеряют, конечно же каждый автор найдет случай, который для его творения подходит лучше всего, найдет свои хитрости.

Lodash.memoize, например, по умолчанию работает с одним аргументом функции. Fast-memoize – имеет разный код для фунций одного или более чем одного аргумента. Memoize-one или reselect молча сохраняют один последний ответ, и сравнивают только с ним. Что очень плохо в одних случаях (расчет чисел фибоначи, например), и очень хорошо в других (React/Redux), за исключением некоторых особенностей (больше одного экземляра компонента).

В общем — везде есть свои хитрости. Без этого было бы не интересно. Давайте остановимся на последнем кейсе, который за последние пару лет был ОЧЕНЬ хорошо расжеван – Redux. Да вот не до конца.

^ вот тут я немного накосячил. Я хотел отфильтровать только активные TODO, но буду получать уникальный массив (с неуникальными значениями), при каждом вызове функции. Это очень, очень плохая идея, так как потом возвращаемое значение сравнивается по shallowequal, а оно не equal.

^ вот тут я это поправил, и теперь ответ будет меняться только если сам массив поменяется.

^ а вот тут бы я очень хотел, чтобы ответ менялся только при изменении текста в активных TODO, но хотеть не вредно. Это практически не возможно сделать.

Redux — очень хороший инструмент, и я его люблю всем сердцем. Но когда дело доходит до разбора стейта на каскад селекторов, с последущей сборкой в ответ, с одной только целью – мемоизировать результат так чтобы лишний раз React не дергать. Нет ребят – я в такие игры не играю.

Тут дело уже не в скорости работы функции мемоизации, а в самом процессе «правильной» мемоизации, времени на нее затраченом и ожидаемом конечном результате.

Ну а если получается, что использовать «сложные» функции мемоизации очень даже можно, когда не фибоначи считаем, а что-то попроще,– то давайте поиспользуем.

Memoize-state – библиотека мемоизации, основанная на немного других принципах, которая делает мемоизацию проще, и быстрее. Несмотря на то, что кода в ней раз в 10 больше чем в обычной функции мемоизации.

Начнем с примеров

^ конечный результат будет меняться только если изменился текст в активных TODO.

^ совершенно индентичный результат. Неожиданно?

Memoize-state работает на принципах схожих с MobX или Immer.js – ES6 Proxy, WeakMaps, Reflection и другая современная лабуда, которая и делает эту магию возможной.

Вкратце — memoize-state следит за тем как вы используете переданные аргументы, и что возвращаете как ответ. После чего понимает на какие изменения ей следует реагировать, а на какие — нет. (потребовался почти месяц, чтобы понять как это на самом деле должно работать) Другими словами — вы можете написать любую функцию, обернуть ее в memoize-state(хоть 10 раз), и они будет мемоизированна по теоритическому максимуму.

memoize-state идеально походит для сложных случаев, и особенно для mapStateToProps и любых аналогов. Не пытайтесь использовать ее для расчета фибоначи – в недрах СЛИШКОМ много логики, многократно превышающей сложность самого расчета фибоначи.

Раз разговор про скорость, давайте сравним:

1. Расчет чисел фибоначи. Тест из библиотеки fast-memoize

Ну — не самый худший вариант.

2. Расчет «медленной» функции от трех integer аргументов. Тест из библиотеки memoize-state

3. Расчет «mapStateToProps» — обьект на вход, рандомно меняются(или не меняются) значения.

Совсем хорошо. 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). Одна строчка — и все приложение стало немного(или много) быстрее. Без какой либо работы с вашей стороны, и это главное.

Второй прекрасный пример использования — react-memoize — библиотека на основе твита Дэна Абрамова(и так бывает), которая мемоизирует рендер, позволяя фактически отказаться от какой либо логики в componentWillReceiveProps.

По факту реализация немного отличается. Просто потому что «селекторы» более не нужны, и повилась возможность «просто писать код».

Просто передайте какие-то пропсы, просто как-то что-то на их основе посчитатайте, и дело в шляпе.

И это опять таки работает просто, и полностью автомагически.

Второй важный вариант — оригинальные тесты 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, и экспериментам.