Comments 20
Статья понравилась - красивое оформление, без лишнего, и видно много ручной работы, а не просто нейрослоп.
"оценивать компромиссы отдельно: расход памяти, стоимость удаления, порядок элементов и обход" - как правило в реальных проектах это экономия на спичках, разные форматы хранения графов и производительность обхода влияют очень незначительно. Условно один медленный api-запрос или неоптимизированный компонент могут затормозить рендеринг и съесть памяти намного больше, чем большой граф. Поэтому если используется достаточно популярная система реактивности, можно не думать о таких нюансах, но в теории знать полезно.
Спасибо за отзыв! Для обычной страницы согласен: медленный API-запрос или тяжёлый компонент могут влиять на результат гораздо сильнее, чем устройство реактивного графа. Здесь сначала стоит профилировать приложение.
Моя задача выходит за пределы DOM: это же реактивное ядро используется в интерактивных 2D-сценах - таймлайнах, картах и больших графах. При частых изменениях там важно, сколько работы успевает выполниться за кадр. Планирую сегодня-завтра опубликовать продолжение со сценами/ссылками и отдельными замерами реактивности. Ссылку добавлю в статье - думаю, на примерах будет понятнее, зачем я разбираю эти компромиссы.
PS: изучаю ваши статьи - очень понравилась Ваша подача :)
Что там с локальным кэшем
O(алгоритм) <->O(память) особенно при наличии рекурсии содержащей неявный стек
Хеширование и всякие хитрости с двоично-десятичными значениями отданными на усмотрение компилятору (наподобие 256 Integer Cache Optimization у Питона)
Локальные или условно-глобальные переменные отданные на усмотрение компилятора особенно при многопоточке, по-разному аллоцируемые кучи в зависимости от контекста
Неявное копирование данных при наличии всяких им- или мутабельных объектов или "случайно" занесённых с внешней структурой даже в простые описания
Спасибо, это полезные аспекты для анализа производительности :)
По применимости к статье:
Если под локальным кешем имеется в виду кеш процессора, локальность данных обсуждается в разделе про обход. При этом влияние кеша отдельно не измерялось, поэтому объяснение результатов через локальность обозначено как гипотеза.
Временную сложность и дополнительную память действительно нужно оценивать отдельно, включая стек вызовов. В показанных операциях контейнеров рекурсии нет. Для рекурсивного обхода графа глубину стека пришлось бы учитывать.
Кеш малых целых в CPython - отдельный механизм повторного использования объектов. Здесь примеры и замеры на JavaScript/V8, а размеры объектов привязаны к конкретной сборке движка.
Размещение объектов и оптимизации JIT могут влиять на результаты. В статье показано, что соотношение времени меняется с конфигурацией V8. Многопоточная работа с общим графом выходит за рамки рассматриваемых примеров.
Объекты
Subscriptionв примерах не клонируются: контейнеры хранят ссылки на них. Но операции с массивами могут сдвигать элементы или перевыделять хранилище - эти расходы входят в работу сравниваемых реализаций.
Если вы видите конкретное место, где один из этих факторов делает оценку сложности или вывод неверным, укажите его - тогда можно разобрать предметно.
Вот смотрю я на это все и вспоминаю свои мысли на тему подобных пепелацев. На странице очень ограничено число реальных данных и элементов управления - буквально десятки, и все фреймворки супер круто такое обслуживают из коробки. И когда я столкнулся бы с такими проблемами - я бы старался оглянуться и понять что что то таки делается не так. Если на одну кнопку есть десяток классов и куча реактивно-функционального кода в котором ломаются зубы фреймворка, разраба и браузера, а цена поддержки превышает ручное создание всех версий страницы - то пора бы уже охладить подходы и более просто писать код отказавшись от реактивных космолетов там где велосипеда за глаза
С простой страницей согласен. Я не предлагаю строить сложный реактивный граф ради кнопки.
Моя задача возникла в том числе из интерактивной 2D-графики - таймлайнов, карт и больших графов, где связанное состояние обновляется во время взаимодействия и важно время кадра. Для таких нагрузок я и развиваю ядро.
Я уже заканчиваю подготовку отдельной статьи со сценами и замерами реактивности. Думаю, сегодня-завтра опубликую. Это позволит предметно обсудить, где подход полезен. Стоимость разработки и поддержки тоже важна, и одними бенчмарками её не доказать.
Прикол в том что вы нарушили границы применимости фреймворка и героически решаете проблемы которые решать не нужно. Игры реактивными не принято делать - делается все влоб руками. И опять же не на таких системах. Игра всегда рендерится целиком весь кадр, там ничего не выиграть толком вычисляя изменения
А кто устанавливает эти границы?
Управлять состоянием можно и вручную. По мере усложнения приложения могут появляться свои механизмы отслеживания изменений, зависимостей, группировки обновлений и освобождения ресурсов. Когда они повторяются в нескольких проектах, возникает смысл собрать их в общую библиотеку.
Именно эту общую часть я заранее выделяю в Raph. Это ядро, которое служит «мозгами» для разных моих приложений: поддерживает зависимости, планирует обновления и управляет жизненным циклом ресурсов. Так эти механизмы можно развивать и проверять в одном месте. А обслуживает Raph уже под 10 графических приложений. В таком случае вы бы не поступили так же?
То что границы не вычислил никто заранее хорошо - тоже косяк документации - не видел никогда целевые характеристики на которые ориентируются авторы любой технологии. Но глобально очевидно что именно браузерные технологии идеальны под верстку вещей что человек способен окинуть взглядом - десятки и сотни элементов. Выход в десятки тысяч очевидное превышение и выгоднее уходить в ручной рендер или как минимум уйти от фреймворков и либ типового веба. Думаю стоит смотреть как с таким справляются приложения типа миро, гугл доков и каких-нибудь онлайн CAD, думаю те ребята собаку съели на этом поприще и там под капотом в реактивность не играется никто понимая цену
В $mol_wire используется один массив вместо 4 в Solid. Это даёт всего 64 байта на узел графа состояний и 16 байт на связь между ними. Всё это с учётом сжатия ссылок. Подробнее тут: https://mol.hyoo.ru/#!section=docs/=tfhz4w_v33vsu
Нейросеть вас такому не научит.
Спасибо за ссылку. Компактность хранения действительно полезна. При этом в моих замерах $mol_wire заметно уступает по времени выполнения в ряде сценариев. Поэтому размер структуры для меня важен вместе с тем, сколько времени занимает работа с ней.
Для моих задач с частыми обновлениями большого графа дополнительный расход памяти может быть приемлемым компромиссом, если он даёт измеримый выигрыш по скорости. Например, в условном приложении с миллионом связей дополнительные 16 байт на каждую связь означают 16 МБ дополнительной памяти на связи.
Для моих настольных приложений такой расход может быть приемлемым, если он позволяет быстрее обрабатывать обновления.
Это обычный компромисс между временем выполнения и расходом памяти. Выбирать его стоит по тому, во что упирается конкретное приложение :)
Нейросеть вас такому не научит.
замеры показать сможете ?
В продолжении статьи привожу демо + бенчмарки
https://habr.com/ru/articles/1092612/
В каких сценариях?
Отдельно ценно, что вы не стали прятать разброс между конфигурациями V8 — именно на этом месте обычно рождается миф «массив всегда быстрее списка». По вашим же цифрам видно, что разницу между Node 22 и Node 24 (112 против 320 байт медианного расстояния) скорее даёт не структура, а момент промоушена Subscription в старое поколение: при --max-size-semi-space 8 и 32 МБ объекты переселяются в разные моменты, и внутри измеряемого цикла меняется ещё и число скавенджей. Это разводится без большого стенда: построить граф до замера, вызвать gc() под --expose-gc, прогнать обход и отдельно снять --trace-gc (сколько скавенджей и промоушенов на итерацию). Если после вычитания GC-времени разрыв между массивами и интрузивным списком сократится, значит в замере обхода вы измеряли в основном работу молодого поколения, а не локальность данных. Вопрос: пробовали ли такой контроль с прогревом и явным gc() перед циклом — и устоял ли после него вывод про 4 мс на массовом удалении?
Спасибо, это хороший контроль для результатов обхода. В текущем тесте есть четыре прогревочных раунда, но gc() вызывается перед построением графа, а не между построением и измеряемым обходом. Трассировку GC в этом интервале я не снимал. Значения 112 и 320 байт получены в отдельном диагностическом запуске, поэтому пока не могу приписать разницу именно промоушену или числу scavenges.
А 4,37 мс - результат другого сценария, очистки 10 000 зависимостей. Там учебная реализация массива многократно удаляет элементы со сдвигом оставшейся части, что даёт квадратичную работу. Дополнительный контроль может изменить конкретное время, но саму причину этого результата он не устранит. Согласен, что для выводов о причинах разницы при обходе трассировка GC была бы полезна.
Тогда промоушен всё равно успевает разъехаться: gc() перед построением графа не трогает объекты, созданные во время сборки, и к началу обхода часть из них уже в старом поколении, часть ещё в молодом. Если вызвать gc() между построением и циклом, обе конфигурации стартуют из одинакового состояния, и разница в обходе будет уже про раскладку, а не про молодое поколение (или исчезнет, что тоже результат). Ещё момент: Node 22 и 24 различаются сразу двумя вещами, версией и дефолтным размером молодой области, так что чище смотреть свип только по --max-semi-space-size на одной версии. Про 4,37 мс согласен, вы сами это оговорили в разделе 11, но в таблице цифра всё равно читается как сравнение структур, хотя там у наивного массива квадратичная очистка, а не свойство контейнера.
Да, согласен: GC после построения графа - дополнительный контроль, которого в этой серии замеров не было. Влияние размера молодой области лучше проверять на одной версии Node. И замечание к таблице принимаю: 4,37 мс относятся к показанной наивной реализации очистки массива, а не к массиву как контейнеру. Спасибо за уточнение.
Почему O(1) не гарантирует высокую скорость
Тут сразу ошибка. "О" нотация это не про скорость, а про время выполнения относительно входных данных. О(1) лишь означает что время константное, функцию можно оптимизировать и время выполнения будет меньше, однако оно будет константным относительно входных данных.
Да, O(1) описывает зависимость времени от размера входа, а не абсолютную длительность операции. В этом и мысль заголовка: в статье несколько способов удалить уже известную связь имеют O(1), но по замерам выполняются за разное время. Поэтому оценка сложности полезна, однако сама по себе не гарантирует высокую скорость конкретной реализации.
Почему O(1) не гарантирует высокую скорость: четыре структуры данных для графа signal – effect