Персистентность и структурное разделение

Разбираемся, почему неизменяемость в Clojure не означает медленное копирование.

Персистентная структура данных — неизменяемая структура, которая при «изменении» создаёт новую версию, переиспользуя большую часть старой через структурное разделение.

Проблема наивной неизменяемости

Если бы каждое «добавление» элемента копировало весь вектор, неизменяемость была бы непрактичной: вектор из миллиона элементов копировался бы целиком при добавлении одного. Clojure решает это иначе.

Структурное разделение

Когда вы делаете (conj v x), новый вектор не копирует старый — он делит с ним почти всю память и хранит только различие. Старая и новая версии сосуществуют, обе валидны, и обе быстры.

(def v1 [1 2 3])
(def v2 (conj v1 4))   ; v2 = [1 2 3 4]
(def v3 (conj v1 99))  ; v3 = [1 2 3 99]

v1  ; => [1 2 3]    исходный цел
v2  ; => [1 2 3 4]
v3  ; => [1 2 3 99]

Вывод:

[1 2 3]
[1 2 3 4]
[1 2 3 99]

Внутри v1, v2 и v3 делят общие узлы дерева, где хранятся 1, 2 и 3. Память расходуется только на различия.

Наглядная схема

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

        старый корень        новый корень
            |                    |
        +---+---+            +---+---+
        |       |            |       |
     [узел A] [узел B]    [узел A] [узел B']
   (общий, переиспользован)  ^ новый только этот путь

Почему это важно

Структурное разделение даёт сразу три выгоды:

Скорость: операции почти такие же быстрые, как у изменяемых структур (логарифмическая, на практике почти константная сложность).
Безопасность: старую версию никто не испортит — её можно свободно передавать в другие потоки.
Дешёвая история: хранить много версий данных недорого, ведь они делят память.

Как работает под капотом

Векторы Clojure реализованы как деревья с ветвлением 32: каждый узел хранит до 32 потомков. Глубина такого дерева для миллиона элементов — всего 4 уровня, поэтому доступ и обновление затрагивают лишь несколько узлов. Обновление создаёт новые узлы только вдоль пути от корня к изменённому элементу — остальные 99,9% дерева общие. То же относится к map и set, построенным на хэш-деревьях (HAMT).

Частые ошибки

Думать, что неизменяемость = тормоза. Структурное разделение убирает копирование; разница с изменяемыми структурами мала.
Бояться хранить много версий. Версии делят память, поэтому это дёшево и часто полезно (undo, снимки состояния).
Ожидать мутацию на месте. Исходная коллекция никогда не меняется — всегда работайте с возвращённой версией.

Итоги

Персистентные структуры при изменении создают новую версию без полного копирования.
Структурное разделение переиспользует общие узлы старой версии.
Это даёт скорость, потокобезопасность и дешёвое хранение многих версий.
Векторы — деревья с ветвлением 32, поэтому операции почти константны.