Персистентные структуры данных и их реальная стоимость

Задача, из которой всё выросло

Вы пишете редактор. Пользователь набрал 200 страниц текста и нажал Ctrl+Z. Нужно вернуть предыдущее состояние документа. Как?

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

Второй инстинкт — хранить снимки всего документа. Логика тривиальна: Ctrl+Z берёт предыдущий снимок целиком, и никакой «обратной операции» не нужно. Но 200 страниц — это мегабайт, а нажатий клавиш за сессию — десятки тысяч. Гигабайты мусора за час работы.

И вот здесь появляется третий вариант, который и есть тема статьи: структура данных, у которой каждая версия остаётся доступной, но новая версия стоит не O(n), а O(log n) памяти. Снимок целиком — по цене одной строки. Тогда undo — это просто указатель на предыдущее значение, а вся хитрая машинерия обратных команд не нужна.

Такие структуры называются персистентными. Мы уже трогали их по касательной в статье про https://courses.digitable.life/post/functional-programming/02-immutability/ — там мы выяснили, что структурное разделение делает неизменяемость практичной. Здесь разберёмся, как оно устроено внутри, где ломается и сколько стоит по-настоящему.

Терминология, в которой все путаются

Слово «персистентный» в мире баз данных значит «сохраняется на диск». В мире структур данных оно значит совсем другое: старые версии остаются валидными и доступными после обновления. Никакого диска. Пожалуйста, не путайте — это разные слова-омонимы, и путаница между ними стоила многим часов непонимания.

Классификация (её ввели Driscoll, Sarnak, Sleator и Tarjan в статье «Making Data Structures Persistent», 1989):

Последняя строка — самая строгая: чисто функциональная структура автоматически полностью персистентна, но не наоборот. Можно построить персистентную структуру на мутабельной памяти (метод fat nodes из той же статьи 1989 года именно так и работает: узел хранит список версий своих полей с временными метками), и такая структура будет персистентной, но не чистой.

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

Git — это конфлюэнтно персистентное дерево каталогов. Коммит неизменяем, дерево переиспользует неизменившиеся blob-объекты, ветка — просто именованный указатель на версию, а merge сливает две ветви истории в одну новую версию. Всё, что мы будем разбирать дальше, — про ту же самую идею на уровне структур в оперативной памяти.

Базовый приём: path copying

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

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

Посмотрим на самом простом дереве поиска.

from typing import NamedTuple, Optional, Any

class Node(NamedTuple):
    key: Any
    value: Any
    left: Optional["Node"]
    right: Optional["Node"]

def insert(node: Optional[Node], key, value) -> Node:
    """Возвращает НОВЫЙ корень. Старый остаётся полностью валидным."""
    if node is None:
        return Node(key, value, None, None)
    if key < node.key:
        # копируем только текущий узел, правое поддерево переиспользуем по ссылке
        return Node(node.key, node.value, insert(node.left, key, value), node.right)
    if key > node.key:
        return Node(node.key, node.value, node.left, insert(node.right, key, value))
    return Node(key, value, node.left, node.right)

def lookup(node: Optional[Node], key):
    while node is not None:
        if key < node.key:   node = node.left
        elif key > node.key: node = node.right
        else:                return node.value
    return None

v1 = None
for k in [50, 30, 70, 20, 40, 60, 80]:
    v1 = insert(v1, k, str(k))

v2 = insert(v1, 65, "шестьдесят пять")

lookup(v1, 65)          # None  — версия 1 не изменилась
lookup(v2, 65)          # "шестьдесят пять"
v1.left is v2.left      # True  — левое поддерево общее, ни одного байта не скопировано

Стоимость: время O(h), память O(h) новых узлов, где h — высота. Для сбалансированного дерева это O(log n). Семь узлов было — три скопировали, четыре переиспользовали.

Тонкость, которая ломает наивные реализации: балансировка тоже должна быть чистой. AVL-повороты и красно-чёрные перекраски в персистентном варианте не крутят указатели на месте, а строят новые узлы — но крутятся они всё равно только вдоль пути вставки, так что асимптотика сохраняется. Именно поэтому в чисто функциональном мире так любят красно-чёрные деревья в формулировке Окасаки: балансировка выражается четырьмя случаями сопоставления с образцом и умещается в десять строк (см. https://courses.digitable.life/post/functional-programming/06-adt-and-pattern-matching/).

data Color = R | B
data Tree a = E | T Color (Tree a) a (Tree a)

insert :: Ord a => a -> Tree a -> Tree a
insert x s = makeBlack (ins s)
  where
    ins E = T R E x E
    ins t@(T color a y b)
      | x < y     = balance color (ins a) y b
      | x > y     = balance color a y (ins b)
      | otherwise = t
    makeBlack (T _ a y b) = T B a y b
    makeBlack E           = E

-- вся балансировка — четыре симметричных случая «красный под красным»
balance :: Color -> Tree a -> a -> Tree a -> Tree a
balance B (T R (T R a x b) y c) z d = T R (T B a x b) y (T B c z d)
balance B (T R a x (T R b y c)) z d = T R (T B a x b) y (T B c z d)
balance B a x (T R (T R b y c) z d) = T R (T B a x b) y (T B c z d)
balance B a x (T R b y (T R c z d)) = T R (T B a x b) y (T B c z d)
balance color a x b                 = T color a x b

Этот код из книги Криса Окасаки «Purely Functional Data Structures» — канонической работы по теме — стал притчей во языцех: императивная реализация red-black insert занимает страницу с лишним и славится тем, что её невозможно написать без бага с первого раза.

Почему ветвление 32, а не 2

Path copying даёт O(log n). Проблема в том, что при ветвлении 2 логарифм по основанию 2 — это 20 уровней на миллион элементов. Двадцать разыменований указателя на каждое чтение и двадцать новых узлов на каждую запись. Это работает, но медленно и грязно.

Решение, ставшее индустриальным стандартом: широкое ветвление. Возьмём узел на 32 ребёнка вместо 2.

Шесть уровней на миллиард элементов. Отсюда популярный (и слегка жульнический) слоган «эффективно константное время»: логарифм по основанию 32 на реальных размерах данных упирается в потолок 6–7 и перестаёт расти заметно.

Почему именно 32, а не 64 или 1024? Тут сходятся три соображения:

1. Стоимость обновления линейна по ширине узла. Копирование узла на 32 ссылки — это memcpy 128–256 байт. При ширине 1024 копировать пришлось бы 8 КБ на каждую запись. Ширина — это торговля между глубиной (стоимость чтения) и объёмом копирования (стоимость записи).
2. Кеш-линия. 32 ссылки по 4 байта (сжатые указатели на JVM) — это 128 байт, ровно две кеш-линии по 64 байта. Узел читается двумя обращениями к памяти.
3. Битовая арифметика. 32 = 2^5, значит индекс делится на пятибитные куски сдвигами и масками, без деления. Это ключ к скорости.

Последний пункт — самое красивое место во всей теме, и его стоит разобрать подробно.

Персистентный вектор: индекс как маршрут

В bit-partitioned vector trie (изобретён Филом Бэгвеллом, реализован Ричем Хикки в Clojure в 2007-м) индекс элемента — это уже готовый путь по дереву. Никакого поиска, никаких сравнений: разбиваем целое число на пятибитные группы и спускаемся.

BITS = 5
WIDTH = 1 << BITS      # 32
MASK = WIDTH - 1       # 0b11111

class PVector:
    __slots__ = ("root", "shift", "count")

    def __init__(self, root, shift, count):
        self.root, self.shift, self.count = root, shift, count

    def get(self, i: int):
        if not 0 <= i < self.count:
            raise IndexError(i)
        node, shift = self.root, self.shift
        while shift > 0:                      # спуск: shift = 5*(глубина-1), 5*(глубина-2), ...
            node = node[(i >> shift) & MASK]  # выбор слота на этом уровне
            shift -= BITS
        return node[i & MASK]                 # лист

    def set(self, i: int, value):
        """Персистентное обновление: возвращает новый вектор, старый цел."""
        if not 0 <= i < self.count:
            raise IndexError(i)
        return PVector(self._assoc(self.root, self.shift, i, value), self.shift, self.count)

    def _assoc(self, node, shift, i, value):
        new = node.copy()                     # копируем ОДИН узел: 32 ссылки
        if shift == 0:
            new[i & MASK] = value
        else:
            slot = (i >> shift) & MASK
            new[slot] = self._assoc(node[slot], shift - BITS, i, value)
        return new

Разберём стоимость set честно, без округления логарифма до константы:

• Аллокаций: глубина дерева, то есть 1–7 списков по 32 ссылки.
• Скопированных байтов: глубина × 32 × размер указателя. На миллионе элементов (глубина 4) при 8-байтовых указателях — примерно 1 КБ на одну запись.
• Мусора: те же 1 КБ уходят в GC при следующей записи.

Сравните с мутабельным list[i] = value — одна запись в память, ноль аллокаций. Разрыв на одну операцию получается в десятки раз. Он окупается только тогда, когда вам действительно нужна старая версия. Если не нужна — вы платите за то, чем не пользуетесь, и это главный практический вывод статьи.

Оптимизация хвоста. В реальных реализациях (Clojure, pyrsistent, Scala) последние до 32 элементов живут не в дереве, а в отдельном плоском массиве — «хвосте». Добавление в конец в 31 случае из 32 копирует только этот массив и вообще не трогает дерево. Именно поэтому conj/push в персистентный вектор на практике почти так же быстр, как в мутабельный список: амортизированно копируется около 32 ссылок вместо полного пути.

# Аналог в Elixir — списки растут с головы, и это тот же принцип «дёшево там,
# где структура позволяет не копировать»
old = [3, 2, 1]
new = [4 | old]     # O(1): одна ячейка, хвост общий

# а вот так — O(n) на каждом шаге, потому что копируется весь левый список
bad = Enum.reduce(1..100_000, [], fn x, acc -> acc ++ [x] end)   # O(n^2), не делайте так
good = Enum.reduce(1..100_000, [], fn x, acc -> [x | acc] end) |> Enum.reverse()  # O(n)

HAMT: тот же трюк, но для словарей

С вектором повезло: индекс — это готовое число. А если ключ — строка? Ответ Бэгвелла в работе «Ideal Hash Trees» (2001): возьмём хеш ключа и будем использовать его как индекс. Так родился HAMT — Hash Array Mapped Trie.

Наивно это дало бы узлы по 32 ссылки, из которых заняты одна-две — чудовищный перерасход памяти на разреженном дереве. Спасает битовая карта.

Узел хранит uint32-битмап (какие из 32 слотов заняты) и плотный массив ровно по числу занятых детей. Чтобы найти позицию слота в плотном массиве, считаем единицы в битмапе ниже этого слота — одной инструкцией POPCNT.

def popcount(x: int) -> int:
    return bin(x).count("1")   # в C/JVM/Rust — одна процессорная инструкция

class BitmapNode:
    __slots__ = ("bitmap", "entries")

    def find(self, slot: int):
        bit = 1 << slot
        if not (self.bitmap & bit):
            return None                                  # слот пуст — ключа нет
        idx = popcount(self.bitmap & (bit - 1))          # позиция в плотном массиве
        return self.entries[idx]

    def assoc(self, slot: int, value) -> "BitmapNode":
        bit = 1 << slot
        idx = popcount(self.bitmap & (bit - 1))
        new = BitmapNode()
        if self.bitmap & bit:                            # замена существующего
            new.bitmap = self.bitmap
            new.entries = self.entries[:idx] + [value] + self.entries[idx + 1:]
        else:                                            # вставка нового
            new.bitmap = self.bitmap | bit
            new.entries = self.entries[:idx] + [value] + self.entries[idx:]
        return new

Поиск ключа: берём hash(key), режем на пятибитные куски, спускаемся, пока не встретим лист.

Отдельная неприятность — коллизии хешей. Пятибитных кусков в 32-битном хеше всего шесть; если два разных ключа дали одинаковый хеш целиком, дерево не может их развести, и нужен специальный узел коллизий с линейным перебором. На хорошей хеш-функции это событие исчезающе редкое, но реализацию усложняет заметно, и на враждебных данных (hash-flooding) деградация до O(n) вполне реальна — как и в обычной хеш-таблице.

CHAMP — эволюция HAMT из статьи Штайндорфера и Винью «Optimizing Hash-Array Mapped Tries» (OOPSLA 2015). Главная идея: держать в узле два раздельных битмапа — для данных и для подузлов — и хранить пары рядом, компактно. Это улучшает локальность при обходе, ускоряет проверку равенства и сокращает память. CHAMP лежит в основе иммутабельных коллекций Scala 2.13 и ряда JVM-библиотек.

Где ломается амортизация — самая тонкая часть темы

Вот момент, о котором молчат туториалы, а он определяет реальную стоимость.

Классическая очередь на двух списках: очередь — это пара (front, back). push кладёт в back за O(1). pop берёт из front; если front пуст — разворачиваем back и делаем его новым front. Амортизированно O(1): каждый элемент разворачивается ровно один раз.

data Queue a = Queue [a] [a]

push :: a -> Queue a -> Queue a
push x (Queue f b) = Queue f (x : b)

pop :: Queue a -> Maybe (a, Queue a)
pop (Queue [] [])      = Nothing
pop (Queue [] b)       = pop (Queue (reverse b) [])   -- дорогой шаг, O(n)
pop (Queue (x : f) b)  = Just (x, Queue f b)

Амортизационный анализ строится на «банке»: дешёвые операции откладывают кредиты, дорогая их тратит. Но у него есть скрытая предпосылка — каждое состояние используется ровно один раз. Персистентность эту предпосылку убивает.

Пусть q — очередь, у которой front пуст, а в back лежит n элементов. Тогда:

q1 = pop q   -- разворот O(n)
q2 = pop q   -- РАЗВОРОТ СНОВА, ещё O(n) — мы взяли ту же самую версию
q3 = pop q   -- и снова

Это законная персистентная структура: q никуда не делась, брать из неё можно сколько угодно раз. И каждый раз мы платим полную цену. Кредиты, накопленные один раз, потрачены k раз. Амортизированная оценка O(1) превращается в O(n) на операцию, а на k повторов — в O(n·k). Такой паттерн не выдуман: он возникает сам собой при бэктрекинге, при обходе дерева версий и в любом коде, который ветвится от одного состояния.

Окасаки посвятил этому основную часть своей работы и дал два лекарства.

Лекарство первое — ленивость с мемоизацией. Если дорогой reverse не выполняется сразу, а становится отложенным вычислением (thunk), то первый, кто его затребует, оплачивает работу, а результат запоминается в самом thunk. Все остальные версии, разделяющие этот thunk, получают результат бесплатно. Ленивость превращает «оплатить k раз» в «оплатить один раз и разделить» — ровно то, чего требует амортизация под персистентностью. Отсюда неочевидный, но важный вывод: ленивое вычисление — не украшение Haskell, а необходимый механизм для амортизированных персистентных структур (подробнее про механику — в https://courses.digitable.life/post/functional-programming/11-laziness-and-streams/).

Лекарство второе — scheduling, размазывание работы. В real-time-вариантах структур дорогая операция принудительно дробится: каждая обычная операция выполняет фиксированный кусочек отложенного разворота. Тогда оценка становится не амортизированной, а worst-case O(1) — никакая отдельная операция не тормозит. Цена — заметно более сложный код и больший постоянный множитель. Именно так устроены real-time queues и real-time deques Окасаки.

Практический вывод для инженера: если ваш язык строгий (Elixir, TypeScript, Python, Scala по умолчанию), амортизированные персистентные структуры в нём небезопасны при разветвлённом использовании версий. Смотрите на гарантии в документации: O(1) amortized в строгом языке означает «O(1), если вы используете каждую версию линейно». Структуры с worst-case-гарантиями (сбалансированные деревья, finger tree в ленивой реализации) от этой ловушки свободны.

Finger tree: универсальный ответ

Data.Sequence в Haskell построен на finger tree — конструкции из статьи Хинце и Патерсона «Finger trees: a simple general-purpose data structure» (JFP, 2006). Идея: дерево с «пальцами» — быстрым доступом к обоим концам, при этом середина остаётся сбалансированной.

import qualified Data.Sequence as Seq
import Data.Sequence (Seq, (|>), (<|), (><))

s :: Seq Int
s = Seq.fromList [1 .. 1000000]

a = 0 <| s              -- добавить в начало: O(1) амортизированно
b = s |> 42             -- добавить в конец:  O(1) амортизированно
c = Seq.index s 500000  -- доступ по индексу: O(log(min(i, n-i)))
d = s >< s              -- конкатенация:      O(log(min(n, m)))
(l, r) = Seq.splitAt 300000 s   -- разрез:    O(log(min(i, n-i)))

Обратите внимание на конкатенацию за логарифм — то самое свойство, которого нет ни у списка (O(n)), ни у классического vector trie. Конкатенация превращает структуру в конфлюэнтно персистентную, а это ровно то, что нужно для параллельных вычислений: разбили работу, посчитали независимо, склеили результаты дёшево.

RRB-деревья (Relaxed Radix Balanced, Bagwell & Rompf, 2011) решают ту же задачу с другой стороны. Строгий vector trie требует, чтобы все узлы кроме крайних были заполнены ровно на 32 — из этого и следует индексирование сдвигами, но из-за этого же конкатенация ломается: приходится перестраивать всё дерево. RRB ослабляет требование: узлы могут быть заполнены не полностью, а частично заполненные несут дополнительный массив размеров. Индексирование становится чуть дороже (иногда нужен бинарный поиск по размерам вместо чистого сдвига), зато concat и slice работают за O(log n). Реализации: im в Rust, immer в C++, векторы Clojure с RRB-расширением.

Собираем выбор структуры в одну схему:

Зиппер: когда логарифм лишний

Есть класс задач, где даже O(log n) на операцию — перебор. Редактор текста, обход AST в компиляторе, навигация по дереву файлов: вы делаете сотни правок вокруг одной точки, а каждое обновление честно спускается от корня.

Ответ — зиппер (Жерар Юэ, «The Zipper», JFP 1997): вывернуть структуру наизнанку так, чтобы «текущая позиция» оказалась корнем, а путь обратно к настоящему корню хранился как контекст.

-- Зиппер для списка: фокус на элементе, слева — пройденное (в обратном порядке)
data ListZipper a = LZ [a] a [a]

right :: ListZipper a -> Maybe (ListZipper a)
right (LZ _ _ [])          = Nothing
right (LZ ls x (r : rs))   = Just (LZ (x : ls) r rs)      -- O(1)

left :: ListZipper a -> Maybe (ListZipper a)
left (LZ [] _ _)           = Nothing
left (LZ (l : ls) x rs)    = Just (LZ ls l (x : rs))      -- O(1)

modify :: (a -> a) -> ListZipper a -> ListZipper a
modify f (LZ ls x rs) = LZ ls (f x) rs                    -- O(1), без спуска от корня

toList :: ListZipper a -> [a]
toList (LZ ls x rs) = reverse ls ++ [x] ++ rs             -- O(n), только когда нужно наружу

Ровно так работает курсор в текстовом редакторе: «текст слева от курсора» и «текст справа от курсора» — два разных списка, вставка символа стоит O(1) и не трогает ничего, кроме точки фокуса. В Elixir тот же приём используется в парсер-комбинаторах и обходах AST:

defmodule Zipper do
  # {пройденное_в_обратном_порядке, оставшееся}
  def from_list(list), do: {[], list}

  def right({left, [x | rest]}), do: {[x | left], rest}    # O(1)
  def right(z), do: z

  def update({left, [x | rest]}, fun), do: {left, [fun.(x) | rest]}   # O(1)
  def update(z, _fun), do: z

  def to_list({left, right}), do: Enum.reverse(left) ++ right         # O(n)
end

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

Реальная стоимость: без рекламы

Теперь честная арифметика. Все цифры ниже — порядки величин, а не обещания; на вашем железе и вашем рантайме меряйте сами.

Память. Персистентный HAMT-словарь на JVM занимает примерно в 2–4 раза больше, чем HashMap с тем же содержимым, а плотный int[] против персистентного вектора проигрывает ещё драматичнее: массив на миллион int — это 4 МБ подряд лежащих байтов; персистентный вектор — это тысячи объектов-узлов с заголовками, ссылками и обёртками Integer, суммарно легко 20–40 МБ. Персистентные структуры плохо совместимы с примитивами: боксинг съедает всё.

Локальность кеша. Главная и наименее заметная статья расходов. Промах в L1 стоит около 4 нс, поход в оперативную память — 60–100 нс. Плоский массив читается префетчером и по сути бесплатен на последовательном проходе. Дерево из указателей на каждом уровне спуска — это потенциальный промах, а узлы, аллоцированные в разное время, могут лежать в памяти сколь угодно далеко друг от друга. Отсюда стабильно наблюдаемая картина: чтение по индексу из персистентного вектора медленнее массива в 2–10 раз, полный последовательный проход — в 3–20 раз.

Аллокации и GC. Каждое обновление порождает мусор размером с путь. Молодое поколение на JVM и в V8 собирается очень дёшево, и короткоживущие узлы почти бесплатны — до тех пор, пока частота обновлений не выходит за миллионы в секунду. На BEAM ситуация особая: у каждого процесса своя куча, GC локальный и не останавливает систему целиком — это одна из причин, почему в Elixir неизменяемость не ощущается как налог.

Где персистентность выигрывает асимптотически, а не в процентах:

Именно на второй строке построена мемоизация в React: если ссылка на props та же — данные заведомо те же, перерисовывать нечего. Мутабельная структура такой возможности не даёт в принципе.

Микробенчмарк, который стоит написать самому. Замерьте на своих данных четыре вещи: точечное чтение, точечная запись, полный проход, построение с нуля. Соотношения между ними скажут больше, чем любая статья. Типичная картина: построение и проход — терпимо, точечная запись — проигрыш в разы, точечное чтение — проигрыш заметный, но переносимый, снимок и сравнение — победа на порядки.

Transient: как вернуть скорость мутации, не потеряв гарантии

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

Из этого выросли transient-коллекции Clojure и withMutations в Immutable.js.

Механика внутри честнее, чем кажется: у transient-версии есть идентификатор владельца (edit-поле в узле). Узлы, созданные этим владельцем, мутируются на месте; узлы, унаследованные от исходной персистентной структуры, при первом касании копируются — и дальше уже мутируются. Первые изменения платят полную цену, последующие бесплатны.

import { List, Map } from "immutable";

// 100 000 промежуточных версий, 100 000 путей скопировано
const slow = data.reduce((l, x) => l.push(x), List<number>());

// одна версия наружу, внутри — почти обычный мутабельный проход (кратно быстрее)
const fast = List<number>().withMutations((l) => {
  for (const x of data) l.push(x);
});

// то же для словаря
const index = Map<string, number>().withMutations((m) => {
  data.forEach((x, i) => m.set(x.id, i));
});

Immer подходит к задаче с другого конца: он даёт вам мутабельный на вид draft-объект под Proxy, записывает все касания и на выходе строит новую неизменяемую структуру, разделяя всё нетронутое. Синтаксис императивный, семантика персистентная.

import { produce } from "immer";

const next = produce(state, (draft) => {
  draft.orders[42].status = "paid";      // выглядит как мутация
  draft.counters.paid += 1;              // но state не изменится
});
// next !== state, при этом next.users === state.users — нетронутые ветки общие

Тот же принцип на уровне языка встречается в трёх разных формах, и полезно видеть их вместе:

• Линейные / уникальные типы (Clean, Rust, Roc, Austral): система типов гарантирует единственность ссылки, поэтому мутация на месте безопасна по построению. Rust — самый известный пример: &mut T уникален статически.
• Подсчёт ссылок с переиспользованием (Perceus в Koka, Swift copy-on-write, Roc): в рантайме проверяется счётчик ссылок; если он равен единице, обновление делается на месте, иначе копированием. Это динамический аналог линейных типов, «бесплатный» для программиста.
• Монада ST в Haskell: мутабельные массивы, запертые внутри области видимости фантомным типом. Компилятор гарантирует, что мутабельная ссылка не утечёт наружу, поэтому runST возвращает чистое значение. Подробнее — в https://courses.digitable.life/post/functional-programming/13-effects-and-io/.

Что реально используется в каждом языке

Elixir / Erlang. Списки — классические cons-ячейки, [h | t] за O(1). Кортежи — плоские неизменяемые массивы, чтение O(1), обновление O(n) (копируется весь кортеж — поэтому кортежи для мелких фиксированных структур). Карты — двухрежимные: до 32 ключей это плоская упорядоченная структура (flatmap) с линейным поиском, что на малых размерах быстрее любого дерева; выше порога карта превращается в HAMT. Для упорядоченных множеств и словарей — :gb_trees и :gb_sets (сбалансированные деревья общего вида), для больших бинарных данных — refc-бинарники со счётчиком ссылок и разделением подстрок без копирования. Когда персистентность мешает — есть :ets, мутабельная таблица вне кучи процесса. Подробности по языку — в треке https://courses.digitable.life/post/elixir/00-overview/.

# карта: до 32 ключей — flatmap, дальше — HAMT; переход автоматический и незаметный
small = Map.new(1..30, &{&1, &1})     # flatmap
big   = Map.new(1..100_000, &{&1, &1}) # HAMT
updated = Map.put(big, 42, :changed)   # O(log32 n), big не изменилась

# кортеж: чтение O(1), но put_elem копирует целиком — O(n)
t = {1, 2, 3}
put_elem(t, 1, :two)   # {1, :two, 3}, новый кортеж

# для «мутабельного» состояния между вызовами — ETS, вне персистентной модели
:ets.new(:cache, [:set, :public, :named_table])
:ets.insert(:cache, {:key, :value})

Haskell. Data.Map и Data.Set — взвешенно-сбалансированные деревья, worst-case O(log n) на всё, отличные для упорядоченных данных. Data.HashMap из unordered-containers — HAMT с ветвлением 16, быстрее на точечных операциях, порядок ключей не гарантирован. Data.Sequence — finger tree. Для числодробилок — Data.Vector (плоские массивы, с unboxed-вариантом) и Data.Vector.Mutable внутри ST/IO. Это важный сигнал: даже в самом чистом языке для производительности предусмотрен явный выход в мутабельность.

TypeScript / JavaScript. Штатные Array, Map, Set — мутабельные. Персистентность даёт Immutable.js (vector trie и HAMT), Immer (structural sharing поверх обычных объектов через Proxy) и mori. Практический совет: для состояния UI спред-операторы над небольшими объектами дешевле и понятнее любой библиотеки; тяжёлую артиллерию тащите, когда коллекции измеряются десятками тысяч элементов и обновляются часто.

Python. pyrsistent даёт PVector (vector trie с ветвлением 32), PMap, PSet, PRecord. Библиотека immutables — HAMT на C, и это не экзотика: тот же алгоритм используется внутри самого CPython для contextvars (PEP 567). Каждый асинхронный контекст получает снимок переменных за O(1) именно благодаря HAMT. Штатные tuple и frozenset неизменяемы, но не персистентны: обновление копирует всё.

from pyrsistent import pvector, pmap, freeze

v1 = pvector(range(1_000_000))
v2 = v1.set(500_000, -1)        # O(log32 n), скопировано 4 узла
v1[500_000], v2[500_000]        # (500000, -1) — обе версии живы

m1 = pmap({"a": 1, "b": 2})
m2 = m1.set("c", 3)             # m1 не изменилась

# evolver — тот же transient-приём: пакет изменений без промежуточных версий
e = v1.evolver()
for i in range(10_000):
    e[i] = 0
v3 = e.persistent()             # одна новая версия вместо 10 000

JVM и .NET. Clojure — эталонная реализация (vector trie, HAMT, transients). Scala 2.13+ использует CHAMP для иммутабельных Map/Set и радикс-сбалансированный Vector. В Java есть Vavr и PCollections; штатные List.of/Map.of неизменяемы, но не персистентны — withX там нет вовсе. В .NET — System.Collections.Immutable (AVL-деревья под капотом, не HAMT, поэтому константы выше) и ImmutableArray для случая «редкие обновления, частые чтения», где просто копируется весь массив, зато чтение идёт со скоростью обычного массива. Последнее — прекрасный пример инженерного компромисса: иногда правильный персистентный контейнер это просто плоский массив с полным копированием.

Типичные ошибки

1. Тащить персистентную коллекцию туда, где хватило бы [...arr, x]. На 50 элементах дерево из указателей проигрывает плоскому копированию по всем статьям, включая читаемость.
2. Оставлять цепочку push в цикле без transient. Каждый шаг — новая версия и новый путь. Именно этот паттерн порождает 90 % жалоб «иммутабельность тормозит».
3. Ожидать O(1) от amortized O(1) в строгом языке при ветвлении версий. Разобрано выше: одна и та же версия, использованная k раз, оплачивает дорогую операцию k раз.
4. Хранить примитивы в персистентном контейнере в горячем цикле. Боксинг умножает и память, и промахи кеша. Числодробилки — на плоских массивах, точка.
5. Забывать про persistent!/asImmutable и продолжать пользоваться transient. Clojure бросит исключение, Immutable.js молча даст мусор.
6. Считать персистентность гарантией потокобезопасности логики. Гонок данных нет, гонки логики остаются: два потока читают одну версию и создают две расходящиеся. Нужен арбитр — atom, STM, актор, оптимистичная блокировка (см. https://courses.digitable.life/post/functional-programming/14-concurrency/).
7. Мерить структуру не тем бенчмарком. Замер построения коллекции ничего не говорит о стоимости точечных обновлений, и наоборот.
8. Хранить ссылки на все версии подряд. Персистентность обещает дешёвую новую версию, а не бесплатную. Если вы держите указатели на миллион версий, вы держите в памяти миллион путей — undo-стек надо ограничивать.
9. Строить неизменяемый граф с циклами. Path copying требует ацикличности: обновление узла в цикле требует обновить того, кто на него ссылается, — и так до бесконечности. Решение — идентификаторы вместо ссылок, то есть отдельная таблица узлов.

Как это выглядит в проде

• Git. Дерево каталогов с path copying, коммит — версия, ветка — указатель. Конфлюэнтная персистентность в чистом виде.
• MVCC в PostgreSQL. UPDATE создаёт новую версию строки; старая живёт, пока её видит хоть одна транзакция. Отсюда же и обратная сторона — распухание таблиц и необходимость VACUUM: документация по MVCC.
• Copy-on-write файловые системы. ZFS и Btrfs — персистентные B-деревья на диске. Снимок тома за O(1) — это ровно то же самое «взять старый указатель на корень».
• LSM-деревья (RocksDB, Cassandra, LevelDB): данные пишутся неизменяемыми сегментами, старые версии живут до компакции. Подробнее — в треке https://courses.digitable.life/post/databases/00-overview/.
• Datomic доводит идею до предела: база — неизменяемое множество фактов во времени, запрос «как выглядела база во вторник» бесплатен по построению.
• React и Redux. Всё дерево состояния неизменяемо, сравнение по ссылке даёт мемоизацию и time-travel debugging.
• contextvars в Python. HAMT внутри CPython обеспечивает копирование контекста за O(1) на каждую задачу asyncio.
• Компиляторы. Персистентные окружения типов и таблицы символов позволяют бэктрекинг при выводе типов: откатиться к предыдущему состоянию — это просто взять старую ссылку.
• CRDT для совместного редактирования: неизменяемая история операций плюс детерминированное слияние версий.

Мини-итог

• Персистентность — это «старые версии остаются валидными», а не «сохраняется на диск».
• Персистентность бывает частичной, полной и конфлюэнтной; Git — конфлюэнтная.
• Базовый приём один — path copying: копируем путь до изменения, боковые ветки переиспользуем. Стоимость O(высоты).
• Ветвление 32 сводит логарифм к 4–6 уровням на реальных объёмах; индекс режется битовыми сдвигами и работает как готовый маршрут по дереву.
• HAMT переносит тот же трюк на произвольные ключи через хеш; битовая карта с popcount убирает пустые слоты. CHAMP — его оптимизированная версия.
• Амортизированные оценки под персистентностью ломаются при повторном использовании одной версии; спасают ленивость с мемоизацией или явный scheduling.
• Finger tree и RRB дают дешёвую конкатенацию и разрез; зиппер даёт O(1) на локальные правки.
• Реальная цена — память в 2–4 раза, промахи кеша, боксинг примитивов и мусор для GC. Выигрыш — снимок, сравнение версий, откат и параллельное чтение за O(1).
• Transient, линейные типы и подсчёт ссылок возвращают скорость мутации там, где структура заведомо ничья.
• Персистентные структуры — не всегда правильный выбор. Правильный выбор — тот, который вы измерили на своих данных.

Источники

• Chris Okasaki, «Purely Functional Data Structures» (диссертация, 1996): https://www.cs.cmu.edu/~rwh/students/okasaki.pdf
• Driscoll, Sarnak, Sleator, Tarjan, «Making Data Structures Persistent» (1989): https://www.cs.cmu.edu/~sleator/papers/making-data-structures-persistent.pdf
• Phil Bagwell, «Ideal Hash Trees» (2001): https://lampwww.epfl.ch/papers/idealhashtrees.pdf
• Bagwell & Rompf, «RRB-Trees: Efficient Immutable Vectors» (2011): https://infoscience.epfl.ch/record/169879/files/RMTrees.pdf
• Steindorfer & Vinju, «Optimizing Hash-Array Mapped Tries» (OOPSLA 2015): https://michael.steindorfer.name/publications/oopsla15.pdf
• Hinze & Paterson, «Finger trees: a simple general-purpose data structure» (JFP 2006): https://www.staff.city.ac.uk/~ross/papers/FingerTree.pdf
• Gérard Huet, «The Zipper» (JFP 1997): https://www.st.cs.uni-saarland.de/edu/seminare/2005/advanced-fp/docs/huet-zipper.pdf
• Reinking, Xie, de Moura, Leijen, «Perceus: Garbage Free Reference Counting with Reuse» (2020): https://www.microsoft.com/en-us/research/publication/perceus-garbage-free-reference-counting-with-reuse/
• Rich Hickey, «Are We There Yet?» — про identity, state и value: https://github.com/matthiasn/talk-transcripts/blob/master/Hickey_Rich/AreWeThereYet.md
• Документация Clojure по transients: https://clojure.org/reference/transients
• Immutable.js: https://immutable-js.com/ и Immer: https://immerjs.github.io/immer/
• pyrsistent: https://github.com/tobgu/pyrsistent и immutables: https://github.com/MagicStack/immutables
• PEP 567 (contextvars, HAMT в CPython): https://peps.python.org/pep-0567/
• Data.Sequence в Haskell: https://hackage.haskell.org/package/containers/docs/Data-Sequence.html
• Обзорная статья о ФП в треке парадигм: https://courses.digitable.life/post/paradigms/03-functional/
• Базовые структуры и их анализ — в треке https://courses.digitable.life/post/data-structures/00-overview/

Что дальше

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

Эффекты и ввод-вывод: как чистый код общается с грязным миром