Персистентные структуры: иммутабельность без копирования

В первом уроке ФП-серии иммутабельность была правилом гигиены: не мутируй, возвращай новое. Честный вопрос, который там остался висеть: если на каждое изменение копировать массив из ста тысяч элементов, кто заплатит за этот праздник? Ответ этого урока: копировать не нужно. Персистентная структура отдаёт новую версию за O(log n), а старую оставляет живой, потому что обе версии делят почти все узлы. Эта идея несёт на себе Clojure и Scala, Immer и Redux, и даже Git, который ты используешь каждый день.

Цена наивной иммутабельности

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

const rows = Array.from({ length: 100_000 }, (_, i) => ({ id: i, value: i }));

// точечное обновление одной строки
const next = rows.map((row) => (row.id === 50_000 ? { ...row, value: -1 } : row));

Изменилась одна строка, а map создал новый массив на сто тысяч слотов и прошёл по каждому элементу. Каждое точечное изменение стоит O(n). Пока обновления редкие, цена незаметна. Поставь её в цикл, и арифметика взрывается: десять тысяч обновлений по сто тысяч слотов это миллиард скопированных ссылок на одно действие пользователя. Самая частая форма этой ловушки, спред-аккумулятор:

let acc: ReadonlyArray<number> = [];
for (const x of source) {
  acc = [...acc, x]; // копия всего накопленного на каждом шаге
}

Выглядит как линейный проход, работает за O(n²): каждый шаг заново копирует всё, что собрано до него.

Соблазн понятен: вернуться к мутации, она стоит O(1). Но мутация забирает три вещи, ради которых иммутабельность и затевалась:

• Сравнение по ссылке. prev === next за O(1) отвечает на вопрос, изменилось ли поддерево состояния. На этом стоят React.memo, селекторы Redux и вся стратегия “перерендери только то, что поменялось”. С мутацией остаётся deep equal за O(n) или ручная бухгалтерия грязных флагов.
• История версий даром. Старая версия никуда не девается: undo, time travel в Redux DevTools, оптимистичные обновления с откатом сводятся к списку ссылок на прошлые состояния.
• Свобода передавать. Иммутабельную структуру можно отдать в любой код, кэш или замыкание без страха, что её исподтишка поменяют. Это та самая ссылочная прозрачность из урока про основы ФП.

Хочется и того и другого: цену, близкую к мутации, и гарантии иммутабельности. Для этого придётся перестать копировать всё подряд.

Structural sharing

Ключевое наблюдение: представь версию данных деревом, и после точечного изменения почти всё дерево совпадает со старым. Зачем копировать то, что не изменилось?

до set                        после set

      A                          A'
    /   \                      /    \
   B     C         ->         B      C'
  / \   / \                 (общий) /  \
 D   E F   G                       F    G'
                                (общий)

Мы поменяли значение в листе G. Новая версия A’ состоит из трёх новых узлов: G’ с новым значением, C’ с обновлённой ссылкой на G’ и корень A’ с обновлённой ссылкой на C’. Узлы B, D, E, F никто не копировал: обе версии ссылаются на одни и те же объекты в памяти. Приём называется path copying: копируется только путь от изменённого листа до корня. Само свойство, когда новая версия делит память со старой, называется structural sharing.

Теперь арифметика играет за иммутабельность. Возьми дерево с ветвлением 32 и миллионом элементов: его глубина 4, узлов в нём около 32 тысяч. Точечное изменение копирует 4 узла по 32 слота, то есть 128 ссылок вместо миллиона. Старая версия при этом полностью жива и пригодна для undo.

Пощупай path copying руками на маленьком дереве с ветвлением 4:

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

Ты пользуешься этой схемой каждый день. Git хранит коммит как дерево: blob для содержимого файлов, tree для каталогов. Когда ты меняешь один файл в глубине проекта, новый коммит создаёт новый blob и новые tree-объекты по пути от файла до корня, а все остальные поддеревья переиспользует по хешу. Сотни коммитов истории делят между собой почти все объекты, поэтому каталог .git не весит размер проекта, умноженный на число коммитов.

Демо показывает механику, но пальцами она запоминается лучше: собери path copying на обычном дереве и проверь ссылочным равенством, что нетронутые ветки действительно общие.

Persistent vector

Осталось придумать, как превратить плоский массив в дерево, где path copying работает. Ответ нашёл Рич Хики для Clojure, а серия hypirion из ресурсов урока разобрала его по косточкам: bit-partitioned trie. Каждый узел держит 32 ребёнка, индекс режется на 5-битные куски (2⁵ = 32), и каждый кусок выбирает ребёнка на своём уровне. Путь к элементу не хранится и не ищется: он вычисляется из самого индекса битовыми операциями.

В домашнем задании ты соберёшь 4-битный вариант с ветвлением 16, на нём и покажу механику. Возьмём вектор на пару сотен элементов, дерево из двух уровней:

индекс 37 = 0b0010_0101, режем по 4 бита: [2] и [5]

           корень (shift = 4)
         /    |    \
       n0    n1    n2  ...        шаг 1: (37 >> 4) & 0b1111 = 2
                  /  \
                ...   лист
                     / | \
                   v4 v5 v6 ...   шаг 2: 37 & 0b1111 = 5, берём v5

Тот же путь в коде:

const BITS = 4; // у Clojure и Immutable.js BITS = 5, ветвление 32
const WIDTH = 1 << BITS; // 16 детей у узла
const MASK = WIDTH - 1; // 0b1111, маска одного куска индекса

// внутренний узел хранит детей, лист хранит значения
type VNode<T> = ReadonlyArray<VNode<T> | T>;

type PVec<T> = {
  readonly size: number;
  readonly shift: number; // на сколько бит сдвигать индекс на уровне корня
  readonly root: VNode<T>;
};

const get = <T>(vec: PVec<T>, index: number): T => {
  let node = vec.root;
  for (let level = vec.shift; level > 0; level -= BITS) {
    node = node[(index >> level) & MASK] as VNode<T>;
  }
  return node[index & MASK] as T;
};

Ни сравнений, ни поиска: индекс сам и есть путь. Глубина дерева растёт как log₁₆(n), у настоящего ветвления 32 ещё медленнее: миллион элементов это 4 уровня, а 2³² элементов, потолок массивов JS, всего 7. Поэтому про доступ говорят “на практике константа”: хуже семи переходов по ссылкам не бывает.

set добавляет path copying, который ты уже видел на картинке:

const set = <T>(vec: PVec<T>, index: number, value: T): PVec<T> => {
  const copyPath = (node: VNode<T>, level: number): VNode<T> => {
    const copy = [...node]; // копия ровно одного узла: 16 слотов
    if (level === 0) {
      copy[index & MASK] = value;
    } else {
      const slot = (index >> level) & MASK;
      copy[slot] = copyPath(node[slot] as VNode<T>, level - BITS);
    }
    return copy;
  };
  return { ...vec, root: copyPath(vec.root, vec.shift) };
};

На каждом уровне копируется один узел, в копии меняется одна ссылка, спуск продолжается. Корень новый, путь новый, все остальные поддеревья общие. Старый vec жив и не изменился, что твои тесты в ДЗ и докажут.

Почему ветвление именно 32? Это торг между глубиной и ценой копии узла. Шире узел: мельче дерево и быстрее get, но дороже path copying (копия узла на 1024 слота уже больно бьёт по памяти). Уже узел: дешевле копия, но глубже спуск. 32 слота держат глубину в пределах 7 уровней, а копия узла остаётся парой кэш-линий.

Две оптимизации боевых реализаций, о которых стоит знать:

• Tail. Последние до 32 элементов лежат в плоском буфере рядом с корнем, не в дереве. push чаще всего копирует только этот маленький буфер и не трогает дерево вовсе; дерево пополняется целым листом, когда tail переполнился. Так push становится почти таким же дешёвым, как arr.push.
• Новый корень при переполнении. Когда дерево заполнено целиком, старый корень становится первым ребёнком нового, а shift вырастает на BITS. В ДЗ тебе хватит этого правила без tail: спустись к последнему листу с path copying, при переполнении добавь уровень.

Ровно так устроен List в Immutable.js и вектор Clojure. Дальше идею развивает RRB-tree, расслабленный вариант trie, который добавляет дешёвые concat и вставку в середину; на нём построена библиотека list от funkia.