Привет, Хабр!

Меня зовут Егор Козельский. Я фулстек-разработчик, в основном занимаюсь backend-системами и производительностью графических приложений. В этой статье разберу один вопрос из устройства реактивных систем: как хранить связь между источником данных и её потребителем.

Само понятие реактивности используется в очень широком списке самых разных систем: от игровых движков и графов зависимостей до систем с логикой подписок и фронтенда.

Предполагаю, что сравнение реактивности игровых движков и фронтенда многих может насторожить. Но лично в моей практике было несколько успешных проектов, где на единой системе реактивности были написаны и высокопроизводительный фронт, и движок для 2D-графики «больших» данных. Это не означает, что я настаиваю, будто так нужно делать всем. Это лишь мой личный эксперимент, который в публичных бенчмарках показывал себя достойным кандидатом наравне с React/PixiJS и подобными системами. Если вам, дорогой читатель, будет интересен такой формат, с удовольствием расскажу про эту разработку и выложу бенчмарки, исходники и пакет. Также принимается любая критика - это делает нас только лучше :D

Для входа в тему возьму знакомые фронтенд-примеры с signal и effect, а для сравнения контейнеров – небольшую модель пользователей и каналов.

Это учебный разбор одного вопроса: устройства контейнеров для связей графа. Мы рассмотрим их сложность, расход памяти и результаты локальных замеров. Динамическое обновление зависимостей и планировщик оставлю для отдельной статьи.

Для чтения достаточно базового представления о состоянии и подписке на его изменения. Знакомство с Vue, Solid или MobX поможет, но не обязательно.

Вопрос, который мы сегодня обсудим: в какой структуре данных хранить одну связь между сигналом и эффектом?

Мы реализуем связь четырьмя способами. У трёх вариантов удаление уже известной связи занимает O(1). Но одинаковая асимптотика не означает одинаковую стоимость операции – это покажут измерения.

---

Точка 0: зачем это нужно

Начнём с самого начала, где у нас пока нет удобных инструментов, но есть задача и наивное решение.

Представим обычный счётчик. У нас есть значение count, которое одновременно отображается на странице и выводится в консоль. Предположим, что элемент #counter уже есть на странице:

let count = 0

const counterElement = document.querySelector('#counter')!

function increment() {
  count += 1
  counterElement.textContent = String(count)
  console.log(count)
}

Само значение меняется только в одной строке: count += 1.

Но после этого мы должны вручную обновить всех потребителей count:

• изменить текст в DOM;

• вывести новое значение в консоль;

• а в реальном приложении, возможно, пересчитать другие данные, обновить Canvas-сцену или сохранить состояние.

Пока потребителей два, это выглядит несложно. Но приложение растёт, состояние начинает изменяться из разных мест, а зависимых от него частей становится всё больше. Разработчику приходится самостоятельно помнить, что именно нужно обновить после каждого изменения.

Например, у нас есть веб-приложение, где контент в разных частях зависит от того, являетесь ли вы администратором. При наивной реализации нам придётся вместо того, чтобы сконцентрироваться на логике приложения, управлять тем, как приложение будет отрисовываться. Когда таких зависимостей становится много, ручное обновление усложняет поддержку: после каждого изменения нужно помнить, какие части интерфейса затронуты.

Пример игрушечный. В приложении таких зависимостей может быть гораздо больше, и часть вычислений будет зависеть от других.

Очень быстро возникнут вопросы:

• Как системе узнать, какие части зависят от изменившегося состояния?

• Как запускать связанные с изменениями действия и не выполнять лишнее?

• Как контролировать производительность, когда зависимостей становится много?

Именно здесь и появляется необходимость в системе, которая будет делать это за вас. Чтобы понять, как она это делает, начнём с самых базовых понятий.

Точка 1: базовые определения

Начнём с трёх понятий, на которых построены будущие примеры.

Реактивность - это способ автоматически поддерживать связь между состоянием и кодом, который от него зависит. Когда состояние меняется, система находит связанные с ним части и запускает их обновление.

Сигнал (signal) - это реактивное значение. Его можно прочитать и изменить. Когда сигнал читают внутри отслеживаемого эффекта или вычисления, система может запомнить эту зависимость, чтобы позже понять, что нужно обновить при изменении значения.

Эффект (effect) - это функция, которая выполняет какое-либо действие и может читать сигналы. Например, она выводит значение в консоль или обновляет текст в DOM. Когда прочитанный сигнал меняется, система запускает эффект снова.

Например:

const count = signal(0)

effect(() => {
  console.log(count.get())
})

count.set(1)

Похожий паттерн встречается во многих реактивных библиотеках, хотя конкретные API различаются.

При первом запуске эффект читает count, и система запоминает эту связь. Когда значение сигнала меняется, эффект выполняется снова. Так разработчик описывает, что нужно сделать с данными, а система сама отслеживает, когда это действие следует повторить.

Внутри движку приходится запомнить связь:

Когда count меняется, движок должен быстро найти effect. Если effect уничтожается или перестаёт читать count, связь нужно удалить.

Если источников и эффектов несколько, перед нами уже обычный граф:

На уровне контейнера задача сводится к простому вопросу:

В какой структуре данных хранить одно ребро такого графа?

Массив? Двусвязный список? Интрузивный список? Массив с обратным индексом?

Возьмём одну и ту же связь и реализуем её четырьмя способами: обычным массивом, двусвязным списком, интрузивным списком и массивом с обратным индексом (swap-remove).

Пойдём постепенно. Начнём с массива, затем рассмотрим два направления ускорения удаления: связные списки и массив с обратными индексами. Так проще увидеть, за что мы платим памятью, порядком элементов или дополнительными объектами.

Здесь ограничимся фундаментом: как хранить связи графа и сколько стоит каждый способ хранения.

---

Содержание

1. Что именно хранит реактивный движок

2. Учебная модель: Alice, Bob, News и Sport

3. Что именно будем сравнивать

4. Вариант 1 - простые массивы

5. Вариант 2 - обычные двусвязные списки

6. Вариант 3 - интрузивные двусвязные списки

7. Вариант 4 - массивы с обратными индексами

8. Что в итоге лежит в памяти

9. Сравнение сложности

10. Как эти связи хранят реальные runtime

11. Бенчмарк: что скрывается за одинаковой Big O

12. Как выбирать структуру

13. Что осталось за рамками: динамические зависимости

---

1. Что именно хранит реактивный движок

На схемах выше уже появились слова, которыми я буду пользоваться дальше. Сигнал - это источник (source), эффект - потребитель (consumer), а связь между ними - ребро графа (edge).

Для обслуживания графа обычно нужна навигация в обе стороны.

Со стороны signal:

Со стороны effect:

Здесь легко перепутать направление зависимости и устройство контейнера. Реактивное влияние всегда идёт в одну сторону: от источника к потребителю. А вот структуре хранения нужен и обратный проход:

В нашем примере обратный путь нужен для удаления и обновления зависимостей. В реактивных движках его также могут использовать для проверки актуальности вычислений. Список потребителей источника я буду называть subs (subscribers), а список зависимостей потребителя - deps (dependencies).

computed совмещает обе роли: читает другие источники как потребитель и сам становится источником для следующих вычислений.

Для этой статьи достаточно простейшей модели source → consumer: поведение computed на сам контейнер связей пока не влияет.

Реактивность даёт знакомый frontend-пример, но сама задача встречается намного шире:

• event bus - нужно быстро вызвать всех подписчиков события и быстро удалить конкретную подписку;

• граф зависимостей сборщика - нужно знать как зависимости модуля, так и его потребителей;

• игровой движок или редактор сцены - один ресурс используется несколькими объектами: при удалении объекта его связи нужно очистить, а при изменении ресурса - найти всех потребителей;

• наблюдатели, плагины, подписки, графы задач.

Во всех этих примерах остаётся одна и та же базовая модель:

---

2. Учебная модель: Alice, Bob, News и Sport

Для сравнения контейнеров перейдём от фронтенд-примера к небольшой модели пользователей и каналов.

Представим маленький сервис с пользователями и каналами. Пользователь может подписаться на несколько каналов, а у канала может быть несколько подписчиков:

Alice ──→ Sport
Alice ──→ News
Bob   ──→ News

Здесь стрелка Alice → News означает „Alice подписана на News“, а не направление уведомления в реактивном графе.

Нам нужны четыре операции:

subscribe(user, channel)
unsubscribe(subscription)
unsubscribeAll(user)
publish(channel, message)

Опишем предметную модель:

type User = {
  name: string
}

type Channel = {
  name: string
}

type Subscription = {
  user: User
  channel: Channel
}

Subscription - это наше ребро графа.

На схеме это Subscription S2. Для операций над графом один и тот же объект нужен в двух контейнерах.

Чтобы удалить все подписки Alice:

Alice.deps

S1: Alice ──→ Sport
S2: Alice ──→ News

Чтобы разослать сообщение подписчикам News:

News.subs

S2: Alice ──→ News
S3: Bob   ──→ News

S2 в обоих представлениях - один и тот же объект.

Эту связь и будем хранить четырьмя разными способами.

---

3. Что именно будем сравнивать

Сначала зафиксируем операции, которые будем сравнивать:

1. Добавить новую связь - subscribe(user, channel).

2. Удалить уже известную связь - unsubscribe(subscription). Под известной связью я имею в виду, что ссылка на Subscription уже есть. Поиск самой предметной связи в эту операцию не входит.

3. Удалить все связи одной стороны - unsubscribeAll(user).

4. Последовательно пройти вторую сторону - publish(channel, message).

Кроме Big O будем смотреть на свойства, которые асимптотика не отражает:

• сколько объектов создаётся на одну связь;

• нужно ли делать лишнее разыменование;

• насколько плотный последовательный обход;

• сохраняется ли порядок;

• сколько данных приходится хранить прямо в связи.

Во всех учебных вариантах subscribe() сначала проверяет существование связи, и этот поиск остаётся линейным. Оценки O(1) ниже относятся к операциям контейнера с уже известной позицией или связью. Поиск существующей зависимости и отдельные индексы для него оставим для продолжения.

Схематично наш путь будет таким:

Обратите внимание: четвёртый вариант - это не «следующая версия» интрузивного списка, а отдельная ветка. Мы вернёмся к обычному массиву и починим его по-другому.

---

4. Вариант 1. Простые массивы

Первый вариант - обычные массивы. С них я бы начал в большинстве прикладных задач.

type User = {
  name: string
  deps: Subscription[]
}

type Channel = {
  name: string
  subs: Subscription[]
}

type Subscription = {
  user: User
  channel: Channel
}

При подписке один объект кладём сразу в два массива:

function subscribe(
  user: User,
  channel: Channel,
): Subscription {
  const existing = user.deps.find(subscription => {
    return subscription.channel === channel
  })

  if (existing) {
    return existing
  }

  const subscription: Subscription = {
    user,
    channel,
  }

  user.deps.push(subscription)
  channel.subs.push(subscription)

  return subscription
}

Структура максимально простая:

Alice.deps = [S1, S2]
News.subs  = [S2, S3]

push() в конец - амортизированное O(1).

Обход тоже очень приятный:

for (const subscription of channel.subs) {
  console.log(subscription.user.name)
}

На каждую связь нужен один объект Subscription, а ссылки на него лежат в двух массивах. Обход одного из этих массивов выражается обычным циклом.

Проблема начинается при удалении. Мы знаем объект Subscription, но не знаем его индекс:

function removeFromArray<T>(items: T[], item: T): void {
  const index = items.indexOf(item)

  if (index !== -1) {
    items.splice(index, 1)
  }
}

Удаление состоит из двух операций:

1. indexOf → найти позицию
2. splice  → сдвинуть хвост

Пример:

до:

[S1, S2, S3, S4]

удаляем S2

[S1, S3, S4]
     ←── ←──

Удаление - O(n). При массовом удалении известных связей линейная операция повторяется снова и снова:

найти → удалить
найти → удалить
найти → удалить
...

Линейное удаление само по себе ещё не делает массив плохим выбором. Для небольших коллекций и редких удалений у массива много плюсов:

• минимальный код;

• нет дополнительных объектов на каждую связь;

• простой последовательный обход;

• произвольный доступ по индексу;

• сами ссылки лежат в памяти подряд.

Последний пункт - с оговоркой: подряд лежат именно ссылки. Сами объекты Subscription могут быть разбросаны по куче как угодно, и в бенчмарке это ещё сыграет.

Следующий вопрос получается конкретным: можно ли удалить известную связь без поиска позиции и сдвига хвоста?

---

5. Вариант 2. Обычные двусвязные списки

Попробуем обычный универсальный связный список.

type ListNode<T> = {
  value: T

  prev: ListNode<T> | null
  next: ListNode<T> | null
}

type LinkedList<T> = {
  first: ListNode<T> | null
  last: ListNode<T> | null
}

Каждая нода знает двух соседей:

Если ссылка на Node 2 уже есть, искать её не нужно.

Следующие функции показывают внутренние операции удаления. Каждая вызывается для элемента, который ещё находится в соответствующем контейнере; повторно вызывать её для того же элемента нельзя. Публичная unsubscribe() следит за этим условием.

function remove<T>(
  list: LinkedList<T>,
  node: ListNode<T>,
): void {
  if (node.prev) {
    node.prev.next = node.next
  }
  else {
    list.first = node.next
  }

  if (node.next) {
    node.next.prev = node.prev
  }
  else {
    list.last = node.prev
  }

  node.prev = null
  node.next = null
}

Удаление затрагивает только соседей и границы списка, поэтому его стоимость не растёт вместе с длиной контейнера. Получили удаление известной ноды за O(1).

Но у нашей предметной модели есть дополнительное требование. Одна Subscription одновременно находится в двух списках:

user.deps
channel.subs

Соседи у неё в этих списках разные. Например, S2:

Alice.deps:

S1 ↔ S2

News.subs:

S2 ↔ S3

Одна универсальная ListNode не может иметь одновременно два разных prev/next. Значит, для одной предметной связи нужны две ноды-контейнера:

type Subscription = {
  user: User
  channel: Channel

  depNode: ListNode<Subscription> | null
  subNode: ListNode<Subscription> | null
}

В памяти получается:

На одну связь приходится:

1 × Subscription
2 × ListNode

Удаление стало быстрым, но появился новый налог:

• дополнительные объекты;

• дополнительные ссылки;

• дополнительное разыменование при обходе:

ListNode → Subscription → User

Отсюда появляется следующий шаг:

Если Subscription по смыслу и есть элемент этих списков, зачем нам вообще отдельная ListNode?

---

6. Вариант 3. Интрузивные двусвязные списки

Третий вариант - интрузивный связный список (intrusive linked list).

В интрузивной структуре служебные указатели контейнера находятся прямо в предметном объекте. Отдельная ListNode исчезает. В этом варианте User хранит границы списка firstDep/lastDep, а Channel – firstSub/lastSub.

type Subscription = {
  user: User
  channel: Channel

  prevDep: Subscription | null
  nextDep: Subscription | null

  prevSub: Subscription | null
  nextSub: Subscription | null
}

Одна Subscription теперь одновременно является нодой двух независимых списков.

Для user.deps используются:

prevDep / nextDep

Для channel.subs:

prevSub / nextSub

На нашем примере:

На схеме подписки обозначены буквами: A, B и C - это наши S1, S2 и S3.

У этой схемы есть одна терминологическая ловушка. nextDep обозначает соседний Subscription внутри контейнера Alice.deps. nextSub указывает на соседа того же объекта внутри News.subs.

Можно мысленно представить S2 так:

Удаление из стороны deps:

function removeDep(subscription: Subscription): void {
  const user = subscription.user
  const prev = subscription.prevDep
  const next = subscription.nextDep

  if (prev) {
    prev.nextDep = next
  }
  else {
    user.firstDep = next
  }

  if (next) {
    next.prevDep = prev
  }
  else {
    user.lastDep = prev
  }

  subscription.prevDep = null
  subscription.nextDep = null
}

Для subs алгоритм тот же, только используются другие указатели.

В полной реализации у Subscription есть ещё флаг active. По одним только указателям нельзя понять, состоит ли подписка в списке: у единственного элемента все четыре указателя равны null.

Что получили:

• удаление известной связи за O(1);

• порядок сохраняется;

• дополнительной ListNode нет;

• один объект участвует сразу в двух списках;

• можно эффективно идти и по зависимостям, и по подписчикам.

Цена тоже есть:

4 указателя на каждую связь

Последовательный обход теперь идёт по ссылкам между объектами в куче, а не по массиву. Формально и там, и там O(n), но фактическая стоимость этих двух O(n) может заметно отличаться - причём, как покажет бенчмарк, не обязательно в пользу массива.

---

7. Вариант 4. Массивы с обратными индексами

Связный список даёт удаление за O(1), но это не единственный способ получить такую сложность. Есть и другая ветка решения.

Вернёмся к обычному массиву. В первом варианте Subscription не хранила собственную позицию в массиве. Можно сохранить эту позицию прямо в Subscription:

type Subscription = {
  user: User
  channel: Channel

  depIndex: number
  subIndex: number
}

Теперь:

То же самое хранится для News.subs.

Теперь позиция известна сразу. Но обычный splice() всё ещё сдвигает хвост массива. Значит, меняем алгоритм удаления: вместо сдвига переносим последний элемент на освободившееся место - swap-remove. Для примера возьмём отдельный массив channel.subs из четырёх условных подписок.

Ниже показано удаление из channel.subs:

function removeSub(subscription: Subscription): void {
  const subs = subscription.channel.subs
  const index = subscription.subIndex
  const lastIndex = subs.length - 1
  const last = subs[lastIndex]

  if (index !== lastIndex) {
    subs[index] = last
    last.subIndex = index
  }

  subs.pop()
  subscription.subIndex = -1
}

Удаление из этого контейнера выполняется за O(1). Полная unsubscribe() также убирает эту Subscription из user.deps. При этом обход остаётся обычным проходом по массиву.

Цена swap-remove - нестабильный порядок:

было:
S1, S2, S3, S4

стало:
S1, S4, S3

Если для алгоритма порядок наблюдаем, такой контейнер уже может не подойти.

Небольшое уточнение по термину. «Обратный индекс» здесь означает только сохранённую позицию объекта в контейнере (depIndex, subIndex); к поисковому inverted index это отношения не имеет.

---

8. Что в итоге лежит в памяти

Теперь четыре решения можно поставить рядом.

Последняя строка - не оценка, а замер: скрипт создаёт 200 000 связей между уже существующими пользователями и каналами и смотрит, насколько выросла куча. В число входит сам объект Subscription и всё, что появляется вместе с ним: слоты в двух массивах или ноды списков. Флаг active из полных реализаций вариантов 3 и 4 тоже посчитан.

Числа получены в использованной сборке Node.js v24.18.0 без сжатия указателей V8. В других сборках, в том числе браузерных, представление значений и размеры объектов могут отличаться; переносить эти байты напрямую нельзя.

По этой таблице массив - самый экономный вариант. Но у него есть цена, которую в пересчёте на одну связь не видно: сам массив - тоже объект. В этом замере пустой [] дал около 32 байт, а массив после первого push() - около 184 байт суммарно: V8 выделил хранилище с запасом. Это результат данной сборки и сценария, а не постоянный размер массива во всех версиях V8.

Рассмотрим сценарий, где у каждого пользователя ровно одна подписка. Тогда на пару «пользователь + подписка» (вместе с объектом пользователя и строкой с его именем) уходит:

В этом сценарии замер дал около 306 байт на пользователя со связью у варианта с массивами и 160 байт у интрузивного списка. Пользователь хранит границы списка, а сама Subscription - четыре указателя. К этому наблюдению мы ещё вернёмся в бенчмарке.

---

9. Сравнение сложности

Сведём контейнерные операции в таблицу.

По таблице три последних варианта удаляют связь за одинаковое O(1).

Дальше одной Big O уже недостаточно.

O(1) может означать:

пару присваиваний соседних ссылок

или:

перенос последнего элемента + обновление индекса

а O(n) может быть:

проход по массиву ссылок

или:

прыжки по указателям между объектами в куче

Одинаковая асимптотика здесь скрывает разную работу процессора, аллокации и характер доступа к памяти.

---

10. Как эти связи хранят реальные runtime

Теперь, когда все четыре варианта перед глазами, посмотрим на несколько реальных runtime.

У них нет единого представления зависимостей: разные runtime используют разные структуры.

Vue: одно ребро сразу в двух двусвязных списках

В приведённой ревизии Vue связь между Dep и подписчиком представлена отдельным Link.

В комментарии исходников прямо написано, что один Link является нодой двух двусвязных списков: списка зависимостей подписчика и списка подписчиков источника.

Минимально структура выглядит так:

nextDep?: Link
prevDep?: Link
nextSub?: Link
prevSub?: Link

Исходник: packages/reactivity/src/dep.ts, строки 20–50.

Это наш третий вариант - интрузивные списки. Структура появилась в переработке реактивности Vue 3.5 вместе со счётчиками версий (version counting).

Alien Signals: практически та же форма ребра

В alien-signals базовый Link также хранит сразу четыре указателя:

prevSub
nextSub
prevDep
nextDep

Исходник: src/system.ts, строки 1–16.

Такой Link показывает, что интрузивный вариант используется в реальном реактивном ядре.

Solid: массивы + позиции элементов

Solid выбрал другую схему.

У источника есть массив наблюдателей и параллельный массив слотов:

observers: Computation<any>[] | null
observerSlots: number[] | null

У вычисления симметрично хранятся:

sources: SignalState<Next>[] | null
sourceSlots: number[] | null

Исходник: signal.ts, строки 85–109.

При очистке Solid делает тот самый swap-remove: переносит последнего наблюдателя на освободившееся место и поправляет его слот (см. cleanNode, строки 1700–1717). По форме это наш четвёртый вариант, только позиции лежат не в объекте связи, а в параллельных массивах.

MobX: массивы в одну сторону, Set в другую

В Reaction MobX зависимости хранятся в массивах:

observing_: IObservable[] = []
newObserving_: IObservable[] = []

Исходник: reaction.ts, строки 61–63.

Дальше поверх них работает собственный алгоритм сверки зависимостей.

А вот обратная сторона - наблюдатели источника - лежит уже не в массиве, а в Set:

observers_: Set<IDerivation> | null = null

Исходник: atom.ts, строки 33–34.

Set можно считать пятым вариантом, которого в нашем сравнении нет. Он сохраняет порядок вставки, а в распространённых реализациях обеспечивает быстрое удаление. Стандарт JavaScript не предписывает ему хеш-таблицу и не гарантирует именно O(1). Сравнение с Set и Map я сознательно оставил для продолжения: там важен не только контейнер, но и поиск уже существующей связи.

Что в итоге

Картина получается показательная: Vue и Alien Signals используют интрузивные двусвязные списки, Solid работает с массивами и слотами, MobX держит массивы зависимостей и Set наблюдателей.

React не включён в это сравнение: его модель обновлений не даёт прямого аналога рассматриваемой Subscription между сигналом и эффектом. Поэтому он не подходит в качестве пятого варианта хранения такой связи.

Выбор зависит от операций, которые конкретный runtime считает горячими, и от ограничений его модели данных.

---

11. Бенчмарк: что скрывается за одинаковой Big O

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

Проверим базовые сценарии: создание, удаление, очистку и последовательный обход.

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

Перед измерениями выполняются 4 прогревочных раунда, затем берётся медиана 11 замеров. В штатном запуске используется --expose-gc: перед подготовкой каждого замера скрипт вызывает gc(). Порядок реализаций между раундами сдвигается, чтобы один вариант не оказывался постоянно первым.

В тесте обхода считается контрольная сумма по пользовательским данным. Так цикл действительно читает элементы структуры, а JIT сложнее свести измерение к пустому счётчику.

Удаление проверяется в трёх порядках:

1. в порядке добавления
2. в обратном порядке
3. в детерминированно-псевдослучайном порядке

Порядок удаления заметно влияет на стоимость операций - и, как мы увидим, не только у массива, - поэтому одного сценария здесь мало.

Результаты

Машина - Apple M5 Pro, macOS 26.6.2, Node v24.18.0. Сам бенчмарк я запускал пять раз; в таблице - медиана по запускам.

Абсолютные числа зависят от CPU и версии V8, поэтому полезнее смотреть на форму результата.

Создание - самая скучная строка: все четыре варианта укладываются в миллисекунду, варианты с массивами в 1.3–1.8 раза медленнее списков.

Удаление: здесь Big O не обманула

Простой массив проигрывает трём остальным вариантам в 40–200 раз. На этом размере данных результат согласуется с различием O(n) и O(1): простой массив заметно проиграл вариантам с удалением известной связи за постоянное время.

Интереснее посмотреть на три варианта, у которых в таблице стоит одно и то же O(1):

• в этой серии интрузивный список удалял пакет из 20 000 связей за 0,14–0,30 мс, два других варианта с O(1) – за 0,17–0,61 мс. Отдельную задержку одного вызова этот тест не измеряет;

• при псевдослучайном порядке все три варианта с O(1) заняли больше времени. Возможные причины – характер доступа к памяти и поведение ветвлений; этот тест не выделяет вклад каждой из них.

Строку «Очистка» нужно читать с оговоркой. В учебной реализации массивов unsubscribeAll сделан в лоб: он вызывает unsubscribe для каждой подписки, и каждый такой вызов сдвигает весь оставшийся хвост user.deps. Отсюда квадратичное время и 4 мс. В этом сценарии у каждого канала один подписчик: если пройти deps один раз, убрать подписки из каналов и обнулить массив целиком, квадратичность исчезнет. Когда в канале много подписчиков, удаление из его массива всё ещё может требовать линейного поиска и сдвига. Так что эта строка сравнивает не столько структуры, сколько наивную и аккуратную реализацию.

Обход: результаты меняются с конфигурацией V8

Теперь последняя строка. По ней интрузивный список обходится быстрее всех, а оба варианта с массивами - медленнее всех, даже медленнее обычного списка с обёртками. Для «плотного» массива результат, мягко говоря, неожиданный.

На той же машине под Node 22 массивы в этой серии вышли быстрее списков. Код при этом не менялся. Похожее изменение результата наблюдалось и при смене флагов V8 без смены Node. Ниже – четыре проверенные конфигурации.

Обход 100 000 × 20, мс:

В первой и четвёртой строке молодое поколение маленькое, во второй и третьей - большое. Списки во всех четырёх строках показывают примерно одно и то же. А варианты с массивами меняются в три с лишним раза и успевают побывать и на первом месте, и на последнем.

В проверенных сборках Node 22 и Node 24 значение --scavenger-max-new-space-capacity-mb по умолчанию различается: 8 и 32 МБ. Смена этих ограничений совпала с заметным изменением времени обхода массивов. Возможное объяснение – разная частота сборок и размещение объектов, но эти замеры не показывают, сколько объектов перенёс GC и какой вклад это внесло отдельно.

А создаются они вперемешку: строка с именем, User, его массив deps, Subscription, хранилище массива - и так сто тысяч раз. Отдельный диагностический запуск повторяет подготовку сценария обхода и измеряет расстояния для выборки соседних Subscription. Это не измерение адресов внутри прогонов времени. Медианные расстояния с флагами размера молодой области по умолчанию получились такими:

У списков раскладка в обеих версиях практически одинаковая - и время обхода тоже. У массивов соседние подписки в Node 24 лежат в три-пять раз дальше друг от друга - и обход втрое медленнее.

Моя гипотеза: дополнительные массивы deps меняют размещение создаваемых Subscription. В конфигурациях, где измеренное расстояние между соседними по обходу объектами больше, обход массива оказался медленнее. Это согласуется с влиянием локальности данных, но отдельный вклад кэша и GC мы здесь не измеряли.

Что из этого следует:

• Во всех четырёх проверенных конфигурациях обычный список обходился медленнее интрузивного. Дополнительная нода и разыменование могут вносить вклад, но тест не выделяет его отдельно;

• Относительный результат массива и интрузивного списка менялся с конфигурацией. На него могут влиять и структура, и размещение объектов, и работа V8; измерения не разделяют эти факторы.

В приложении объекты могут жить и размещаться иначе: этот тест не моделирует долгоживущий граф с перемежающимися вставками и удалениями. Поэтому результат не стоит переносить на произвольный runtime. Из этого бенчмарка я бы вынес такой вывод:

Одинаковая Big O может скрывать разные компромиссы по памяти, порядку элементов и стоимости обхода. На стоимость операции могут влиять размещение объектов и конфигурация V8.

Ограничения бенчмарка: здесь измеряются конкретные учебные реализации, а результат зависит от V8, CPU, размеров коллекций, порядка операций, JIT и GC - в чём мы только что убедились. Короткие замеры особенно чувствительны к шуму. Коллекции в тесте большие: один канал на десятки тысяч подписчиков. В реактивном графе у узла обычно единицы связей, и там соотношения могут оказаться другими - это отдельный замер. Наконец, в полном реактивном ядре поверх контейнера появятся распространение изменений, динамическое отслеживание зависимостей, планировщик, версии и другие расходы, которых в этом тесте нет.

---

12. Как выбирать структуру

Универсального правила выбора здесь не получилось. Проще отталкиваться от горячих операций и требований к порядку.

Массив подходит по умолчанию для небольших коллекций

У массива минимальная сложность реализации и самый простой код обхода.

Если у вас:

• десяток связей;

• редкие удаления;

• много обходов;

• код не находится в горячем runtime;

в большинстве случаев дополнительная структура не окупится.

Стоит помнить только про цену самого массива: если узлов много, а связей у каждого одна-две, память уйдёт в основном на полупустые хранилища.

Обычный связный список полезен как универсальная структура

Если нужно:

• стабильное O(1) при удалении известной ноды;

• сохранение порядка;

• универсальный контейнер, не вторгающийся в предметный объект;

то отдельная ListNode абсолютно нормальна.

Цена - лишние объекты: в нашем сравнении это самый тяжёлый по памяти вариант в пересчёте на связь и стабильно более медленный обход, чем у интрузивного списка.

Интрузивный список подходит для ребра, которое уже является частью runtime

Если объект уже представляет ребро графа и участвует в нескольких списках, отдельная нода-обёртка добавляет ещё один объект и разыменование.

Тогда поля вроде:

prevDep / nextDep
prevSub / nextSub

становятся частью представления самого ребра.

Такое представление хорошо ложится на граф зависимостей реактивного движка. В бенчмарке этот вариант оказался самым ровным: быстрое удаление в любом порядке, меньше всего памяти на узел с короткими списками; в наших четырёх конфигурациях время обхода менялось меньше, чем у вариантов с массивами.

Массив + обратный индекс подходит, если порядок не является контрактом

Такой вариант особенно интересен, когда:

• удаление горячее;

• порядок элементов после удаления не является контрактом;

• хочется остаться на обычных массивах - с доступом по индексу и привычным кодом обхода.

В итоге свойства контейнера такие:

Чего я бы по этому бенчмарку не обещал - что обход такого массива обязательно быстрее обхода списка. Раздел 11 показал, что в наших сценариях массив не всегда выигрывал по обходу: результат менялся с конфигурацией V8.

---

13. Что осталось за рамками: динамические зависимости

На этом уровне мы разобрали только хранение связи.

В реактивном ядре поверх контейнера появляется динамическое обновление графа.

Набор зависимостей effect может меняться между запусками. Такое происходит уже при обычном ветвлении:

effect(() => {
  if (enabled.get()) {
    first.get()
  }
  else {
    second.get()
  }
})

Предположим, что при первом запуске enabled.get() возвращает true. Тогда граф выглядит так:

После смены ветки и повторного выполнения эффекта:

Чтобы получить такой граф, при повторном запуске движку приходится сопоставить старый набор связей с новым.

Отсюда появляются уже более узкие вопросы по устройству реактивного ядра:

• удалять ли все старые рёбра и создавать заново;

• можно ли переиспользовать уже существующее ребро;

• нужен ли курсор по зависимостям;

• что такое tailDep и зачем он двигается при чтениях;

• можно ли перенацелить ребро на другой источник без аллокации;

• что делать, когда быстрый путь не сработал и остаётся поиск за O(n);

• почему бы просто не добавить Map<Source, Edge>;

• в какой момент индекс начинает окупать собственную память и поиск по хешу;

• зачем реактивным ядрам счётчики версий;

• как битовые флаги помогают сократить состояние узла;

• как совместить push-инвалидацию и pull-стабилизацию;

• где должен находиться планировщик;

• когда эффект стоит запускать синхронно, а когда отдавать внешнему runtime.

Этому хочу посвятить следующую часть.

Рассмотренные Vue, Solid и MobX решают задачу хранения зависимостей по-разному. Это повод оценивать компромиссы отдельно: расход памяти, стоимость удаления, порядок элементов и обход. Конкретный выигрыш от изменения структуры зависит от нагрузки и требует измерения.

Итоги и продолжение

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

В следующей части покажу практические демонстрации для DOM и Canvas: большие диаграммы Ганта, графы и уже работающую сцену с количеством до 500 000 спрайтов. Расскажу об условиях запуска и результатах замеров.

Если у вас есть конкретный сценарий с проблемой производительности в DOM, Canvas или 2D-графике, расскажите, на каких данных и масштабах она проявляется. Такие примеры помогут выбрать задачи для следующих демонстраций.