В балансе между тем насколько долго будет исполнятся мемоизируемая функция, сколько дополнительного времени потребует сахар мемоизации, и (про это все забывают) сколько програмистов потребуется, чтобы эту мемоизацию правильно прикрутить.
Но начнем с простого — что же это за слово такое странно — «мемоизация».
Мемоизация (от англ. 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, но буду получать уникальный массив (с неуникальными значениями), при каждом вызове функции. Это очень, очень плохая идея, так как потом возвращаемое значение сравнивается по shallowequal, а оно не equal.
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.
По факту реализация немного отличается. Просто потому что «селекторы» более не нужны, и повилась возможность «просто писать код».
Просто передайте какие-то пропсы, просто как-то что-то на их основе посчитатайте, и дело в шляпе.
<Memoize
prop1 = "theKey"
state = {this.state}
compute={({prop1, state}) => heavyComputation(state[prop1])}
>
{ result => <Display>{result}</Display>}
</Memoize>И это опять таки работает просто, и полностью автомагически.
Второй важный вариант — оригинальные тесты 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
Комментарии (43)
Klimashkin
06.03.2018 06:18Еще пару вопросов:
- Необходимость писать много селекторов используя reselect дает неплохую инкапсуляцию — каждый контейнер имеет свои специфические селекторы, а другие просто их используют, ничего не зная о реальных путях в state. Что рекомендуется в случае Memoize-state?
- Proxy создается на каждый вызов mapStateToProps?
kashey Автор
06.03.2018 06:361. Можно использовать селекторы. Можно использовать просто различные helper функции без мемоизации. Можно использовать вообще все что угодно, и оно будет работать, но не всегда эффективно, посколько рано или поздно мемоизация в reselect «скроет» доступ к конкретным значениям, и memoize-state начнет агриться на более «высокоуровневые» значения.
2. И да и нет. Для того чтобы возможная «другая» мемоизация работала требуется предоставлять «одинаковые» обьекты завернутые в «однаковые» прокси. В общем там внутри все созданные прокси храняться в WeakMap, и без надобности не создаются.
Почему нет — потому что сам state между вызовами будет разный, и для него прокси будет создаваться каждый раз.
Как говорилось выше — без проблем пару миллионов в секунду.
napa3um
06.03.2018 07:42+1Забавно, как React с помощью обвесов превращается в дедушку Knockout. Забава в том, что изначально pull-концепция (вытягивания данных всеми ветками из корня модели) была выбрана как более простая против push-концепции (проталкивание данных из корня в ветки, которые задеты изменениями), вместо запутанных и многословных observables (см. Knockout-mapping). Мол, у нас виртуальный DOM, он сам отметёт то, что не нужно менять, не заморачивайтесь (640 килобайт хватит всем). Создатель Vue.js в этом смысле оказался чуть прозорливее.
kashey Автор
06.03.2018 08:06+1Это все еще pull, просто у любого инструмента есть свои ограничения. Я так думаю где-то глубоко в глубинах Vue живет что-то похожее, ну а в MobX (@computed) живет вообще почти что тоже самое.
В итоге и получается, что и коробки Vue, да и Angular, могут работать сильно быстрее. Ну просто потому что програмисты такие програмисты. Глаз за глаз за ними нужен. Ну или костыль. И memoize-state – фабрика костылей. Подопрет где нужно и все окей.
vintage
06.03.2018 10:29Изначально концепция редукса — именно push. Селекторы просто вырезают из огромного стейта кусочек. Собственно это та же концепция, что и у RxJS — у вас есть стрим глобального состояния. И есть зависимые стримы, получаемые маппингом и фильтрацией оригинального. И пока кто-то не запушил данные, вы не можете их отфильтровать. А вот концепция knockout/mobx/vue как раз pull — пока вы данные не запросили, никто их и готовить не станет, а как запросили, так сразу пойдут вычисления по их подготовке. И в том числе загрузка.
chirkin
06.03.2018 09:19Сломал мозг пытаясь понять таблички которые должны были сравнить скорость библиотек. В первой таблице по два-три числа через запятую, в других по несколько точек на число, какие-то множители посередине, строки не упорядочены по значению… :)
kashey Автор
06.03.2018 09:25А ведь специально старался разделить порядки, чтобы понятнее было. Все тесты лежат в репе, просто запустите их и получите более нормальный вариант.
RifleR
06.03.2018 11:35А вы пробовали работу в IE11 на практике? Не совсем понятно, как это возможно, ведь Proxy не полифиллится. Если поддержки одного Reflect достаточно, то зачем тогда там Proxy?
kashey Автор
06.03.2018 11:39На самом деле Reflect был вчера выпилен. А насчет прокси
— полифил примерно для всего — github.com/tvcutsem/harmony-reflect
— полифил только для прокси — github.com/GoogleChrome/proxy-polyfill
Оба достаточно просты — используют дескрипторы для перехвата доступа к полям обьектов, что в принципе не медленно, но сильно медленнее чем прямой доступ к обьектам.
К сожалению скрипт который измеряет скорость работает не в браузере, и показать чиселки для сравнения я сейчас не могу. Но то что работает — 100%RifleR
06.03.2018 14:58Спасибо за ссылки. Я раньше читал страницу https://babeljs.io/learn-es2015/#proxies и там указано, что
Due to the limitations of ES5, Proxies cannot be transpiled or polyfilled.
Исходя из этого, думал что совсем нельзя.
Оказывается, Proxy таки возможно заполифиллить, но только частично
The polyfill supports just a limited number of proxy 'traps'.
kashey Автор
06.03.2018 15:02В данном случае требуется только геттеры, для чего дескриптопы просто идеально подходят.
Moxa
06.03.2018 11:37Сорри, я всё ещё не понимаю, зачем все эти движения, отдельные библиотеки, почему бы просто не считать ничего в mapStateToProps, передать сырые данные, а потом в том же рендере сделать с ними все что нужно?
kashey Автор
06.03.2018 11:44Исключительно чтобы атмосферу не греть. Потому что рендер ДОРОГО! Если что-то начинает пересовываться — оно не остановиться пока в PureComponent не упрется.
Основная задача mapStateToProps — быть pure и idempotent. А если вы с этим не согласны — лучше вообще redux не использовать.Moxa
06.03.2018 11:51+1Так рендер не вызовется, пока данные не изменятся
kashey Автор
06.03.2018 12:03Возьмем redux-form, который будет дергать стейт на каждое нажатие клавиши. Или react-beautiful-dnd, который будет делать все тоже самое на каждое движение мышкой.
Всегда есть куча событий, которые изменяют стор, и дергают mapStateToProps, но совершенно не относятся к ВСЕМУ приложению — что-то одно маленькое должно обновиться, а все остальное — нет.Moxa
06.03.2018 12:17mapStateToProps и так вызовется у каждого компонента на каждый экшен, если ничего не изменилось и результат вызова mapStateToProps такой же, то редакс не будет дергать реакт, что нам и нужно. Но чем больше логики мы кладем в mapStateToProps тем медленнее наше приложение, да, можно использвать кеши, но их вызовы и проверки тоже не бесплатные
kashey Автор
06.03.2018 12:20> если ничего не изменилось и результат вызова mapStateToProps такой же
Вот именно этот момент мемоизация и обеспечивает. Именно этот момент является источником проблем. Совсем чуть чуть повычисляли значения — map/filter или просто getInitialProps() какой либо вызвали — и до свидания.Moxa
06.03.2018 12:23так я и говорю что не нужно ничего вычислять, просто переложить данные из стейта в пропс, а вычислять потом в рендере, да, он тяжелый, но он по дизайну тяжелый, и он не будет дергаться если ничего не изменилось
kashey Автор
06.03.2018 12:26Ну в рендере точно не надо. Он должен быть тупой по определению. Обычно это делается в componentWillReceiveProps, что не всегда удобно.
И да — react-memoize про который я в этой статье добавил сноску именно «там» и работает.Moxa
06.03.2018 12:36componentWillReceiveProps может дергаться без изменения данных, так что туда класть что-либо тяжелое не очень прикольно
kashey Автор
06.03.2018 12:44Наверное надо было указать на этот момент — если у вас есть state, и вы из этого state запросили state.todos[0].id — то memoize state будет агриться на изменения только в state.todos[0].id. Одновременно с этим — если сам стейт или state.todos или state.todos[0] остались без изменения — более глубокие проверки не будут производится в принципе.
В начале производиться shallow сравнение тех частей которые могут быть «flexible», и если они не изменились — значит можно вернуть закешированный результат.
Если же они изменились — можно пойти глубже проверять. В планах есть немного передумать этот алгоритм и сильно-сильно ускорить.
Пока только есть незарелизенная автомагия beautiful-react-redux, который areStatesEqual настроить чтобы полностью и «быстро» игнорировать изменения которые не нужны, а потом уже «сравнивать» долго и упорно прошедшие.
Klimashkin
06.03.2018 12:24Рендер вызовется сменой локального стейта или рендером родителя (если не ставить везде PureComponent что бывает еще медленнее или ручным sCU) вне зависимости от изменений куска данных в сторе, который нужен данному компоненту. Поэтому reselect и придумали
Moxa
06.03.2018 13:35попробовал более магическую магию (beautiful-react-redux), время отрисовки страницы поднялось с 2.0 секунд до 2.7. Не все так радужно как кажется
kashey Автор
06.03.2018 13:46Ээээ… красота требует жертв. Но можно узнать что за примерчик 2 секунды рендерится, я думал что обычно в 60 FPS, или 16 мс уложится надо.
Moxa
06.03.2018 14:02дашборд с кучей карточек, 425 реквестов к бекенду, 1043 экшена прокидывается через редакс, 84 компонента, слушающие стейт
kashey Автор
06.03.2018 14:23Возможно постоянные изменения убивают возможность что либо мемоизировать, тем самым время затраченное на сахар сильно выпирает, но тут надо смотреть конкретный пример — по тестам 160000 вызовов (1000 экшенов на 84 компонента на двойную обертку) должны занять доли секунды.
Был бы очень признателен увидеть ваш mapStateToProps. Возможно другая моя подделка — redux restate — сможет исправить ситуацию.Moxa
06.03.2018 14:34вот наверно самый жирный
const mapStateToProps = (state, ownProps) => { return { ...ownProps, tasks: state.tasks, news: state.news.data, announcements: state.announcements.data, loading: (!!state.tasks.loading || !state.tasks.data) || (!!state.announcements.loading || !state.announcements.data) || (!!state.news.loading || !state.news.data) } };kashey Автор
06.03.2018 14:39Ок, и таких 80 чтук? А что меняется посредством 1043 ивентов? Я бы ожидал, что они на основе своих props что-то из state таскают, но вроде как нет.
Что будет если ownProps не спредить? (редакс всеравно передаст их в компонент) Поскольку они НЕ используются для доступа в стейт их вообще не надо использовать и в аргументы не просить.
В крайнем случае у connect есть mergeProps опция.Moxa
06.03.2018 14:50с ownProps не заморачивался, есть — есть, нет — пустой объект будет, что сильно не мешает.
есть вариант, когда из стейта более конкретные данные вытягиваются
const mapStateToProps = (state, ownProps) => { return ({ ...ownProps, item: state.tasks[ownProps.id] }); };kashey Автор
06.03.2018 14:52Я общем почти гарантирую что если убрать ...ownProps то для вас ничего не изменится (mergeProps сделает тоже самое), а в прокси прилетит сильно меньше данных.
"...ownProps" заставляет прокси думать что вам нужны все значения в ownProps, что многократно увеличивает накладные расходы и вообще не совсем правда.Moxa
06.03.2018 15:22спасибо, уберу ...ownProps, будет чуть быстрее… я еще посмотрел, mapStateToProps дергаются примерно 8000 раз на рендере страницы
kashey Автор
06.03.2018 15:25Вообщем надо будет будет подумать о том как НЕ мемоизировать функции, которые мемоизировать не надо. Например как все ваши.
faiwer
06.03.2018 16:36Честно говоря главного в статье я и не заметил. А где описание того, как оно работает? Ну кроме того, что там Proxy. Это же самое интересное. Да и всякие шаманства вроде двойного оборачивания тоже можно было пояснить на примере, имхо ;)
Оно детектирует все поля к которым происходит обновление, складирует пути в некое древо путей, а потом при последующем просчёте пробегается по этому древу, по его ветвям, вплоть до листьев, в поисках единственного отличия? И если ничего не найдено, то возвращает кеш? Как-то так работает? Дескать если какая-то промежуточная коллекция не изменилась, то и листья не изменились, и можно вглубь не копать, а если таки изменилась, то возможно не изменилось то, что нас интересовало, и можно пойти вглубь и проверить наверняка, т.к. функция чистая?
Если я всё правильно понял, то звучит просто и сердито. Но боюсь, такой инструмент надо очень с умом использовать, не перейти грань, когда сравнений/аллокаций/прочей магии не получится сильно больше, чем самих вычислений.
kashey Автор
07.03.2018 00:11Спасибо что описали как оно работает. Единственное отличие — функция должна следить за тем что она возвращает, так как если какой-то промежуточные значение, которое вообще можно проигнорировать, оказалось в результате — «ниже» этого ключа ходить не надо.
И насчет грани все правильно написали. Очень тонкая грань. Но! в рамках react/redux на самом деле можно использовать функции пожирнее без особых проблем.
ETCDema
06.03.2018 16:37- Расчет чисел фибоначи. Тест из библиотеки fast-memoize
- base line x 123.592
- fast-memoize x 203.342.420
- lodash x 25.877.616
- underscore x 20.518.294
- memoize-state x 16.834.719
- ramda x 1.274.908
Ну — не самый худший вариант.Хотелось бы уточнить единицу измерения и какое значение (min/max) считается лучшим + не самый худший вариант для кого?
staticlab
06.03.2018 18:18Единица измерения — число операций в секунду. Больше — лучше. Не самый худший вариант, очевидно, для рассматриваемой memoize-state.
- Расчет чисел фибоначи. Тест из библиотеки fast-memoize
OldVitus
07.03.2018 10:06После нескольких упражнений, я в конце концов отказался от React, Virtual DOM и шаблонов, в пользу реального DOM и макетов. Написал маленькую библиотеку и построение UI опять стало весёлым развлечением.
Современные браузеры уже настолько сами заоптимизированы, что не аффектят rendering если свойство реально не поменялось, и вместо того чтобы оптимизировать оптимизацию, можно просто назначать свойства и устанавливать атрибуты.
Время на скриптинг падает в несколько раз при неизменном времени на рендеринг.
Klimashkin
Получается что producer от immer идет в редьюсер, а
Memoize-stateвmapStateToProps.Не очень понятно с
beautiful-react-redux— что значит:Хотелось бы более подробной информации.
За библиотеку спасибо
kashey Автор
У reselect есть одна проблема — он помнит только один последний результат.
Если у вас есть два инстанса компонента, то в начале первый что-то возьмет из state на основе своих props, а потом второй, а потом опять первый. И всегда кеш будет чистый, так как то что там храниться — «не подходит».
Полуофициальное решение проблемы — re-reselect, который позволяет указать как «разделять» компоненты.
Второе полуофициальное решение — завернуть createSelector в замыкание, так чтобы проблемы с кешом не будет. Но тогда они не смогут «шарить» кеш между инстансами.
beautiful-react-redux оборачивает mapStateTopProps в memoize-state «снаружи», и еще раз «внутри». Те для каждого отдельного элемента, и для всех целиком, на случай если разницы между ними нет.
В общем универсальное решение.