Сборка мусора: подсчёт ссылок, mark-sweep, поколения, паузы

В предыдущей статье ВМ языка Mini начала исполнять байткод, и вместе с первой же строкой let s = "привет" + name; в ней появилась куча. Строка не помещается в 8-байтовое значение на стеке: под неё нужен блок памяти, который переживёт текущее выражение. То же самое с массивами, с объектами и — самое неприятное — с замыканиями, чьи захваченные переменные, как мы видели в семантическом анализе, обязаны пережить кадр, в котором они родились.

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

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

Что такое мусор, если говорить точно

Наивное определение — «объект, который больше не понадобится программе». Оно правильное по смыслу и абсолютно бесполезно на практике, потому что неразрешимо: вопрос «будет ли когда-нибудь прочитано поле x» сводится к проблеме остановки (см. вычислимость). Никакой сборщик не может ответить на него точно.

Поэтому все сборщики мира заменяют живость на её вычислимую консервативную аппроксимацию — достижимость.

Объект жив, если до него можно дойти по ссылкам, начиная с корней. Всё остальное — мусор.

Это надёжно в одну сторону: недостижимый объект точно не будет использован (программе неоткуда взять его адрес), значит освобождать его безопасно. И неточно в другую: достижимый объект вполне может быть уже не нужен — кеш, из которого никто не читает, список слушателей, забытая глобальная мапа. Такие «логические утечки» сборщик не лечит принципиально, о них будет отдельный разговор ниже.

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

• стек значений ВМ и локальные переменные всех активных кадров вызова;
• глобальные переменные и таблица констант;
• регистры процессора (для скомпилированного кода) — их придётся выгрузить в память в момент сборки;
• внутренние структуры рантайма: список открытых upvalue, очередь финализации, временные ссылки в реализации встроенных функций;
• дескрипторы, выданные наружу через FFI/JNI, и объекты, закреплённые (pinned) для доступа из C.

Обратите внимание на две циклические структуры на схеме. rows → row → rows — цикл, достижимый из корня: он жив, и любой корректный сборщик обязан его сохранить, не зациклившись при обходе. p ⇄ q — цикл, недостижимый ни откуда: это мусор, и вся драма подсчёта ссылок будет именно вокруг него.

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

Три с половиной способа управлять памятью

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

Арены заслуживают отдельного упоминания: мы уже применяли их в статье про AST, где узлы дерева лежат в одном массиве и освобождаются одним free. Это лучший в мире аллокатор — для тех задач, где время жизни объектов совпадает с фазой работы программы. У Mini такая задача была на этапе компиляции; у Mini как языка её нет: замыкание может пережить что угодно.

И ещё один важный факт против интуиции «GC — это медленно». Классическое измерение Hertz и Berger («Quantifying the Performance of Garbage Collection vs. Explicit Memory Management», OOPSLA 2005) показало: если сборщику дать в пять раз больше памяти, чем занимают живые данные, он обгоняет ручной malloc/free по времени работы; при трёхкратном запасе отстаёт на ~17%, при двукратном — на 70%. То есть GC не медленнее ручного управления, он обменивает память на время, и вся его настройка — про положение на этой шкале.

Подсчёт ссылок

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

Реализация для рантайма Mini

Рантайм Mini мы пишем на C (интерпретатор байткода из статьи 09), поэтому и заголовок объекта опишем на C:

// Общий заголовок всех объектов кучи Mini: он лежит в начале каждого блока.
typedef enum { OBJ_STRING, OBJ_ARRAY, OBJ_CLOSURE, OBJ_UPVALUE } ObjKind;

typedef struct Obj {
    uint32_t     rc;    // счётчик ссылок
    ObjKind      kind;  // тег для интерпретации тела
    struct Obj  *next;  // интрузивный список всей кучи — для финального сноса
} Obj;

static inline Obj *incref(Obj *o) {
    if (o != NULL) o->rc++;                 // в многопоточном рантайме — атомарно
    return o;
}

void decref(Obj *o) {
    if (o == NULL) return;
    if (--o->rc == 0) {
        for_each_child(o, decref);          // рекурсивно отпускаем детей
        free(o);
    }
}

// Присваивание поля: порядок операций имеет значение.
static inline void store_field(Obj **slot, Obj *value) {
    incref(value);        // сначала увеличиваем — иначе self-assign убьёт объект
    decref(*slot);
    *slot = value;
}

Порядок в store_field — не педантизм: при a.f = a.f перестановка decref и incref местами освобождает объект, который тут же понадобится. Эту ошибку делают все, кто пишет RC впервые.

Что подсчёт ссылок даёт и чего стоит

Плюсы — реальные и часто недооценённые. Память возвращается немедленно, в точке последнего decref, а не когда-нибудь потом: пик потребления ниже, поведение предсказуемо. Работа размазана по программе, длинных пауз нет. Детерминированное разрушение позволяет вешать на него освобождение внешних ресурсов — файлов, сокетов, блокировок (with в Python работает предсказуемо именно поэтому). И, что важно для учебного языка, RC пишется за вечер и не требует ни знания карт стека, ни точек безопасности.

Минусы серьёзнее, чем кажется.

Циклы не собираются никогда. p ⇄ q с рисунка выше держат счётчики друг друга на единице, и это утечка. Циклы в реальном коде вездесущи: двусвязный список, дерево с ссылками на родителя, граф, замыкание, захватившее объект, в котором само же лежит, — классический self.handler = lambda: self.update().

Каждая запись ссылки стоит денег. Не только два арифметических действия, но и запись в чужую кеш-линию: incref на разделяемый объект в многопоточной программе — это атомарный RMW и трафик когерентности между ядрами. Именно поэтому CPython десятилетиями жил с GIL, и именно поэтому переход к свободнопоточному режиму (PEP 703) потребовал переделки самого подсчёта ссылок.

Каскадное освобождение — та же пауза. decref на голову списка из миллиона элементов освобождает миллион объектов подряд; «нет пауз» превращается в «пауза в неожиданном месте». Плюс рекурсия по for_each_child переполняет стек C — CPython обходит это макросами Py_TRASHCAN, ограничивающими глубину.

Память на счётчик. 4–8 байт в каждом объекте; для мелких объектов это заметная доля.

Как это чинят в промышленных рантаймах

• Отложенный подсчёт (deferred RC). Не считать ссылки со стека вообще — они меняются чаще всего. Периодически останавливаться и сверять счётчики со стеком (алгоритм Deutsch — Bobrow).
• Объединение обновлений (coalesced RC). Если поле переписали десять раз между двумя сборками, важны только первое и последнее значения; остальные incref/decref можно не делать.
• Бессмертные объекты. None, True, малые целые, интернированные строки живут вечно — счётчик им не нужен, а запись в него портит кеш и copy-on-write после fork. Это PEP 683, реализованный в CPython 3.12.
• Смещённый подсчёт (biased RC). Разделить счётчик на «локальный для потока-владельца» (обновляется неатомарно) и «общий» (атомарно). На этом построен свободнопоточный CPython.
• Отдельный сборщик циклов. Раз в N аллокаций запускается трассирующий проход, который ищет именно циклический мусор. В CPython он поколенческий, с тремя поколениями и порогами 700, 10, 10; работает вычитанием внутренних ссылок: если после вычитания всех ссылок внутри подозрительной группы счётчик обнулился — группа недостижима извне (devguide).

Swift пошёл другим путём: ARC (automatic reference counting) вставляет retain/release на этапе компиляции, оптимизатор их массово выбрасывает — а сборщика циклов нет вовсе. Цикл в Swift — это ошибка программиста, которую надо разорвать вручную через weak или unowned. Прекрасная иллюстрация того, что выбор сборщика — это ещё и выбор того, чего язык требует от пользователя.

Практический вывод к разделу: подсчёт ссылок и трассировка — не соперники, а полюса одного спектра. Bacon, Cheng и Rajan в «A Unified Theory of Garbage Collection» (OOPSLA 2004) показали, что это двойственные алгоритмы: трассировка отслеживает живое, RC — мёртвое, и все реальные высокопроизводительные сборщики оказываются гибридами где-то между.

Трассирующая сборка: mark-sweep

Второй ответ, исторически первый (McCarthy, LISP, 1960): не считать ничего во время работы, а раз в N аллокаций пройти весь граф от корней и пометить достижимое. Что не помечено — мусор.

Псевдокод

collect():
    mark_from_roots()
    sweep()

mark_from_roots():
    worklist = пустой стек
    для каждого r из roots():
        если r != NULL и не r.marked:
            r.marked = true; worklist.push(r)
    пока worklist не пуст:
        obj = worklist.pop()
        для каждого child из children(obj):
            если child != NULL и не child.marked:
                child.marked = true      # красим ДО помещения в worklist —
                worklist.push(child)     # иначе цикл даст бесконечный обход

sweep():
    для каждого obj из all_objects:      # интрузивный список всей кучи
        если obj.marked: obj.marked = false      # готовим к следующему циклу
        иначе: unlink(obj); free(obj)

Три момента, на которых спотыкаются: пометка ставится в момент помещения в worklist (иначе циклы уводят обход в бесконечность); worklist — явный стек, а не рекурсия (глубина обхода равна длине цепочки объектов и легко переполняет стек C на длинном списке); флаг снимается на фазе sweep, чтобы не делать отдельный проход.

Работающая реализация

Модель кучи Mini на Python — её можно запустить и потрогать:

from dataclasses import dataclass, field
from typing import Any

@dataclass
class Obj:
    kind: str                                  # "string" | "array" | "closure"
    fields: list = field(default_factory=list) # ссылки на другие Obj
    payload: Any = None                        # полезная нагрузка
    size: int = 16                             # байт, включая заголовок
    marked: bool = False

class Heap:
    def __init__(self, threshold: int = 128):
        self.objects: list[Obj] = []   # интрузивный список всей кучи
        self.bytes = 0
        self.threshold = threshold     # порог следующей сборки
        self.stack: list[Any] = []     # стек значений ВМ — корень №1
        self.globals: dict[str, Any] = {}   # глобальные — корень №2

    def alloc(self, kind: str, payload: Any = None, size: int = 16) -> Obj:
        if self.bytes + size > self.threshold:
            self.collect()
        o = Obj(kind, [], payload, size)
        self.objects.append(o)
        self.bytes += size
        return o

    def roots(self):
        yield from self.stack
        yield from self.globals.values()

    def collect(self) -> int:
        # --- фаза mark: обход в глубину явным стеком ---
        worklist: list[Obj] = []
        for r in self.roots():
            if isinstance(r, Obj) and not r.marked:
                r.marked = True
                worklist.append(r)
        while worklist:
            o = worklist.pop()
            for child in o.fields:
                if isinstance(child, Obj) and not child.marked:
                    child.marked = True
                    worklist.append(child)
        # --- фаза sweep: линейный проход по всей куче ---
        live: list[Obj] = []
        for o in self.objects:
            if o.marked:
                o.marked = False
                live.append(o)
            else:
                self.bytes -= o.size
        freed = len(self.objects) - len(live)
        self.objects = live
        # цель следующей сборки: вдвое больше текущего живого — аналог GOGC=100
        self.threshold = max(128, self.bytes * 2)
        return freed

Проверка на том самом графе, где есть достижимый цикл и недостижимый:

h = Heap()
s = h.alloc("string", "привет")
h.stack.append(s)                     # строка достижима со стека

rows = h.alloc("array")
row = h.alloc("array")
rows.fields.append(row); row.fields.append(rows)   # достижимый цикл
h.globals["rows"] = rows

p, q = h.alloc("array"), h.alloc("array")
p.fields.append(q); q.fields.append(p)             # недостижимый цикл

print(h.collect())          # 2 — циклический мусор собран
print(len(h.objects))       # 3 — строка и живой цикл на месте

Подсчёт ссылок на этом примере утёк бы дважды: и на p ⇄ q, и (без специальных мер) он не отличил бы их от живого цикла. Трассировка отличает бесплатно — она вообще не смотрит на мусор.

Сложность и цена

Фаза mark — это обход графа: $O(L)$ по времени, где $L$ — объём живых данных вместе с рёбрами. Фаза sweep линейна по всей куче: $O(H)$. Память под worklist в худшем случае $O(L)$ — для встраиваемых систем существует трюк с обращением указателей (Deutsch — Schorr — Waite), дающий $O(1)$ дополнительной памяти ценой удвоения времени.

Самое важное свойство трассировки видно, если посчитать стоимость на один освобождённый байт:

$$C = \frac{c_m \cdot L + c_s \cdot H}{H - L}$$

Здесь $c_m$ и $c_s$ — константы фаз mark и sweep, $H$ — размер кучи, $L$ — объём живого. Отсюда два вывода, на которых стоит вся настройка GC. Первый: чем больше запас памяти сверх живых данных, тем дешевле сборка — при $H \to \infty$ стоимость освобождения байта стремится к константе фазы sweep, а при $H \to L$ уходит в бесконечность (это и есть «GC-спираль смерти», когда приложение почти упёрлось в лимит памяти и рантайм крутит сборки одну за другой). Второй: частота сборок равна

$$f = \frac{A}{H - L}$$

где $A$ — скорость аллокации. Отсюда главный практический совет всей статьи: дешевле всего чинить проблемы с GC уменьшением аллокаций, а не настройкой сборщика. Уменьшили $A$ вдвое — вдвое уменьшили число сборок, ничего не настраивая.

Mark-compact и копирование

У mark-sweep есть неприятное последствие: куча становится дырявой. Фрагментация означает, что 100 МБ свободной памяти могут не вместить массив на 1 МБ, а аллокация превращается в поиск по спискам свободных блоков вместо одного сложения. Два способа это вылечить — оба требуют перемещать объекты.

Mark-compact: после пометки сдвинуть живые объекты к началу кучи и починить все ссылки. Классический алгоритм Ленивого сдвига (Lisp2) делает это за три прохода по куче и требует места под адреса пересылки.

Копирующий сборщик (Чейни, 1970): куча делится на два полупространства; живые объекты эвакуируются из from-space в to-space, после чего полупространства меняются ролями. Мусор не посещается вообще.

Гениальность алгоритма Чейни в том, что он не нуждается ни в каком worklist: очередь обхода в ширину — это сам отрезок памяти между указателями scan и free. Реализация целиком:

class Semispace:
    """Копирующий сборщик Чейни. Объект в памяти: [tag, n, ref0, ..., ref_{n-1}]."""

    def __init__(self, size: int):
        self.size = size
        self.space = [None] * size     # активное полупространство
        self.other = [None] * size     # резервное
        self.free = 0                  # вершина bump-аллокатора
        self.to_free = 0               # вершина в to-space во время сборки
        self.roots: list[int] = []     # адреса-корни

    def alloc(self, tag: str, nfields: int) -> int:
        need = 2 + nfields
        if self.free + need > self.size:
            self.collect()
            if self.free + need > self.size:
                raise MemoryError("куча исчерпана даже после сборки")
        addr = self.free
        self.space[addr] = tag
        self.space[addr + 1] = nfields
        for i in range(nfields):
            self.space[addr + 2 + i] = None
        self.free += need              # аллокация = одно сложение
        return addr

    def set_field(self, addr: int, i: int, value: int | None) -> None:
        self.space[addr + 2 + i] = value

    def _evacuate(self, addr: int) -> int:
        """Копируем объект в to-space; на старом месте оставляем адрес пересылки."""
        if self.space[addr] == "FWD":          # уже переехал — вернуть новый адрес
            return self.space[addr + 1]
        n = self.space[addr + 1]
        new = self.to_free
        for i in range(2 + n):
            self.other[new + i] = self.space[addr + i]
        self.to_free += 2 + n
        self.space[addr] = "FWD"               # надгробие
        self.space[addr + 1] = new             # адрес пересылки
        return new

    def collect(self) -> None:
        self.to_free = 0
        scan = 0
        self.roots = [self._evacuate(r) for r in self.roots]   # 1. корни
        while scan < self.to_free:                             # 2. очередь = [scan, free)
            n = self.other[scan + 1]
            for i in range(n):
                ref = self.other[scan + 2 + i]
                if ref is not None:
                    self.other[scan + 2 + i] = self._evacuate(ref)
            scan += 2 + n
        self.space, self.other = self.other, [None] * self.size  # 3. смена ролей
        self.free = self.to_free

Проверка: аллоцируем цепочку, теряем половину, собираем.

h = Semispace(64)
a = h.alloc("cons", 2)
b = h.alloc("cons", 2)
garbage = h.alloc("cons", 2)     # ни на кого не ссылаемся
h.set_field(a, 0, b)
h.roots = [a]
before = h.free                  # 12 слотов занято
h.collect()
print(before, h.free)            # 12 8 — мусор исчез, живое лежит плотно

Ключевое свойство: время работы копирующего сборщика пропорционально объёму живых данных, а не размеру кучи. Если 95% объектов мертвы (а так обычно и бывает), сборщик делает 5% работы. Плата — двукратный расход адресного пространства и перемещение объектов, что запрещает наивные указатели из внешнего кода.

Поколения: главная эмпирика в управлении памятью

Слабая поколенческая гипотеза: большинство объектов умирают молодыми. Это не теорема, а наблюдение, но наблюдение исключительно устойчивое — в типичной программе 90–98% объектов не доживают до первой сборки. Временная строка, промежуточный список, объект-параметр, замыкание в колбэке — всё это живёт микросекунды.

Из гипотезы следует стратегия: разделим кучу по возрасту и будем часто собирать только молодую часть. Молодое поколение (nursery, Eden) невелико — от сотен килобайт до десятков мегабайт, — почти целиком мертво к моменту сборки, и копирующий сборщик обрабатывает его за время, пропорциональное горстке выживших. Такая сборка называется minor GC и укладывается в доли миллисекунды. Полная сборка (major GC) со старым поколением — редкое событие.

Приятный побочный эффект: аллокация в поколенческой куче — это free += size плюс проверка границы, две-три инструкции. Именно поэтому «аллокация в Java дешевле, чем в C» — не парадокс, а правда для типичного случая.

Проблема межпоколенческих ссылок

Чтобы собрать молодое поколение отдельно, нужно знать все ссылки на него извне. Ссылки из корней мы найдём. А ссылка из старого объекта в молодой (old.field = young) делает молодой объект живым — но искать её обходом всего старого поколения означало бы платить ровно ту цену, которую мы хотели не платить.

Решение — барьер записи: кусочек кода, который компилятор вставляет после каждой записи ссылки в поле объекта. Он запоминает место, где такая ссылка могла появиться. Самая дешёвая форма запоминания — карточная таблица.

# Барьер записи по карточной таблице — то, что вставляет кодогенератор
# после КАЖДОЙ записи ссылки в поле объекта, живущего в куче:
store_field(obj, offset, ptr):
    obj[offset] = ptr
    cards[(addr(obj) - heap_base) >> 9] = DIRTY   # карта = 512 байт, 1 байт на карту

# minor GC:
roots = стек + глобальные + все объекты в грязных картах

Две машинные инструкции (сдвиг и запись байта) на каждую запись ссылки — вот честная цена поколенческой сборки. Записи примитивов (int, bool) барьера не требуют, и это одна из причин, почему компилятору важно знать типы: проверка типов окупается ещё и здесь.

Вариант точнее и дороже — запоминаемое множество (remembered set): не «карта, где что-то писали», а список конкретных полей. G1 в HotSpot держит remembered set на каждый регион и платит за это заметной долей памяти.

Поколенческий сборщик для Mini

Добавим поколения к нашему mark-sweep — минимальная честная реализация:

class GenHeap(Heap):
    PROMOTE_AGE = 2

    def __init__(self, threshold: int = 128):
        super().__init__(threshold)
        self.remembered: list[Obj] = []   # старые объекты со ссылками на молодых

    def alloc(self, kind, payload=None, size=16) -> Obj:
        o = super().alloc(kind, payload, size)
        o.gen, o.age = 0, 0               # всё рождается молодым
        return o

    def write_field(self, obj: Obj, i: int, value: Any) -> None:
        """Единственный разрешённый способ записать ссылку — вместе с барьером."""
        while len(obj.fields) <= i:
            obj.fields.append(None)
        obj.fields[i] = value
        if obj.gen > 0 and isinstance(value, Obj) and value.gen == 0:
            self.remembered.append(obj)   # барьер записи

    def minor_collect(self) -> int:
        worklist = [r for r in self.roots() if isinstance(r, Obj)]
        worklist += self.remembered       # грязные карты как дополнительные корни
        for o in worklist:
            o.marked = True
        while worklist:
            o = worklist.pop()
            for ch in o.fields:
                # в старое поколение не спускаемся: его сейчас не собираем
                if isinstance(ch, Obj) and ch.gen == 0 and not ch.marked:
                    ch.marked = True
                    worklist.append(ch)
        survivors, freed = [], 0
        for o in self.objects:
            was_marked, o.marked = o.marked, False
            if o.gen > 0:                 # старое поколение сейчас не собираем
                survivors.append(o)
                continue
            if was_marked:
                o.age += 1
                if o.age >= self.PROMOTE_AGE:
                    o.gen = 1             # повышение в старое поколение
                survivors.append(o)
            else:
                self.bytes -= o.size
                freed += 1
        self.objects = survivors
        self.remembered = [o for o in self.remembered if o.gen > 0]
        return freed

Сложность minor GC: $O(L_{young} + R)$, где $L_{young}$ — выжившая молодёжь, $R$ — размер запоминаемого множества. При работающей гипотезе оба слагаемых крошечные — отсюда субмиллисекундные паузы.

Где гипотеза не работает

Поколения — не бесплатный обед, и знать границы полезно:

• Кеши и пулы объектов. Объект, специально созданный, чтобы жить долго, проходит весь путь копирований и повышений впустую. Пул объектов в языке с GC часто делает хуже, а не лучше — он превращает молодой мусор в долгоживущие данные, за которые платит major GC.
• Программы, где живёт почти всё. Загрузка большого графа в память: minor GC копирует выживших снова и снова.
• Go принципиально не поколенческий. Причина инженерная: escape-анализ и значения-структуры в Go убирают большую часть короткоживущего мусора ещё на этапе компиляции (см. оптимизации), а барьер записи в конкурентном непоколенческом сборщике дешевле. Обсуждение поколенческого режима идёт годами, и решающим аргументом остаётся цена барьера.
• BEAM (Erlang/Elixir) обходится вообще без глобального сборщика. У каждого процесса своя маленькая куча и свой копирующий сборщик, процессы недолговечны — пауза локальна для одного процесса и не видна системе. Это редкий случай, когда модель конкурентности языка (см. конкурентность в Elixir) решает проблему пауз архитектурно.

Паузы: откуда берутся и как от них уходят

Пауза stop-the-world — это время, в течение которого прикладные потоки (в терминологии GC — мутаторы) остановлены. Источников пауз три: сканирование корней (пропорционально числу потоков и глубине стеков), сама трассировка (пропорциональна живым данным), перемещение/зачистка (пропорциональна куче). Убирают их по-разному, и здесь важно не путать три независимые оси:

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

Трёхцветный инвариант

Формализм Дейкстры (1978), без которого не понять ни один современный сборщик. Каждый объект имеет цвет:

• белый — ещё не посещён, кандидат в мусор;
• серый — посещён, но его дети ещё не просмотрены (он в worklist);
• чёрный — посещён вместе со всеми детьми.

Сборка = «перекрашиваем корни в серый, пока есть серые — красим их детей в серый, а их самих в чёрный». В конце белое — мусор. Обход завершён, когда серых не осталось.

Опасность конкурентного режима — потерянный объект: мутатор записывает ссылку на белый объект в чёрный (тот уже просмотрен и повторно просмотрен не будет) и одновременно стирает последнюю ссылку на него из серого. Объект достижим, но останется белым и будет собран. Это ровно тот баг, который проявляется как случайное падение через десять минут после настоящей причины.

Сильный трёхцветный инвариант: не должно существовать ссылки из чёрного объекта в белый.

Держат его барьерами:

• Барьер вставки (Дейкстра): при записи obj.f = ptr красим ptr в серый. Консервативно — переживший цикл мусор соберётся в следующий раз («плавающий мусор»).
• Барьер удаления (Юаса, SATB): при записи запоминаем затираемое значение. Логически сборка идёт по снимку графа на момент старта — snapshot-at-the-beginning. Так работают G1 и Shenandoah.
• Гибрид Go (с версии 1.8): барьер удаления плюс окрашивание нового значения, что позволило убрать повторное сканирование стеков в конце цикла и опустить паузы ниже миллисекунды.

Отдельный сюжет — конкурентное перемещение. Если сборщик двигает объект, пока мутатор его читает, нужен барьер чтения. Shenandoah сначала использовал forwarding-указатель Брукса (лишнее слово в каждом объекте, всё чтение идёт через него), потом перешёл на самоисцеляющийся барьер загрузки ссылки. ZGC хранит метаданные прямо в цветных указателях — незанятых битах 64-битного адреса; барьер загрузки проверяет цвет и при необходимости чинит ссылку на месте. Именно поэтому у ZGC паузы не зависят от размера кучи: терабайтная куча даёт те же десятки микросекунд (ZGC wiki).

Точки безопасности и карты стека — счёт компилятору

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

Сборщик не может остановить поток в произвольном месте: посреди последовательности инструкций часть ссылок лежит в регистрах, часть — в промежуточных вычислениях, и понять, что из этого ссылка, а что число, невозможно. Поэтому компилятор расставляет точки безопасности (safepoints) — места, где состояние согласовано: входы в функции, вызовы, обратные дуги циклов. В точке безопасности поток проверяет флаг «GC просит остановиться» — в HotSpot это делается трюком с защитой страницы памяти, чтобы проверка стоила ноль в обычном режиме.

Для каждой точки безопасности компилятор генерирует карту стека (stack map): какие слоты кадра и какие регистры в этот момент содержат ссылки. Без карт остаётся только консервативное сканирование — считать ссылкой всё, что похоже на адрес внутри кучи. Так работает Boehm GC, которым пользуются программы на C и C++: он прост, но иногда удерживает мусор (случайное число выглядит как адрес) и запрещает перемещение объектов — нельзя чинить то, в чём не уверен.

Практический вывод для Mini: интерпретатору байткода повезло. Его стек значений — уже готовая карта корней, все слоты которой заведомо значения ВМ, а точка безопасности — граница между инструкциями. Точная перемещающая сборка для ВМ пишется в разы проще, чем для скомпилированного кода. Как только Mini обзаведётся JIT, вопрос карт стека встанет в полный рост — и, кстати, деоптимизация потребует почти таких же карт.

Из картинки видно правило: правый верхний угол пуст, и это не случайность. Конкурентность оплачивается барьерами, барьеры — это команды в горячем пути мутатора; сборщик с околонулевыми паузами отдаёт 10–20% пропускной способности. Выбор сборщика — это выбор, что вы готовы отдать.

Что делают промышленные рантаймы

Несколько деталей, которые чаще всего всплывают в реальной эксплуатации.

Go. GOGC=100 (по умолчанию) означает: следующая сборка запускается, когда куча вырастет вдвое относительно живых данных после предыдущей. GOMEMLIMIT (с 1.19) задаёт мягкий предел общего потребления и решает старую боль контейнеров: сборщик Go не знает про cgroup-лимит, и до появления GOMEMLIMIT его подпирали «балластом» — выделенным и никогда не используемым срезом. Классическое чтение — доклад Рика Хадсона «Getting to Go» и официальный гайд.

JVM. С JDK 9 умолчание — G1: куча режется на регионы, часть помечается молодыми, сборщик выбирает набор регионов так, чтобы уложиться в -XX:MaxGCPauseMillis. Отсюда правило: не выставляйте цель паузы в 10 мс на куче в 30 ГБ — G1 просто начнёт собирать слишком маленькими порциями и будет отставать. Для латентностных сервисов ZGC или Shenandoah, для пакетных задач Parallel GC даёт лучший throughput.

.NET. Три поколения плюс отдельная куча больших объектов (Large Object Heap, порог 85 000 байт), которая исторически не уплотнялась — отсюда фрагментация на больших массивах и совет переиспользовать буферы через ArrayPool<T>. Server GC даёт по потоку сборщика на ядро и заметно больше памяти под кучи.

V8. Scavenger — тот самый копирующий сборщик Чейни для молодого поколения, параллельный; старое поколение собирается конкурентной маркировкой с mark-compact (v8.dev/blog/trash-talk).

GC для Mini: что нужно сделать в компиляторе и ВМ

Сведём воедино чек-лист, по которому сборщик встраивается в наш язык.

1. Заголовок объекта. Тег типа, бит пометки, указатель next для интрузивного списка всей кучи. Бит пометки удобно хранить в младшем бите указателя next — объекты выровнены, младшие биты свободны.
2. Точный список корней. Стек значений ВМ, слоты всех кадров вызова, таблица глобальных, список открытых upvalue, стек компилятора (если компиляция идёт в том же процессе и создаёт объекты кучи).
3. Временные корни. Самая коварная ошибка: значение уже аллоцировано, но ещё не записано никуда, кроме локальной переменной C. Пример — конкатенация строк: выделили новую строку, и в этот момент вторая аллокация запускает сборку, а новая строка не видна ни из одного корня. Лечится явным стеком временных корней (push_temp_root / pop_temp_root) вокруг таких участков.
4. Порог и рост. Собирать после каждых N байт аллокаций, порог после сборки — живые × коэффициент. Ровно то, что делает GOGC.
5. Стресс-режим. Флаг MINI_GC_STRESS=1, запускающий сборку перед каждой аллокацией. Программа замедляется в сотни раз, но забытый корень падает не через неделю в продакшене, а на первом же тесте. Ни один сборщик не стоит писать без такого режима — это стандартный приём, описанный в Crafting Interpreters.
6. Логирование. MINI_GC_LOG=1: сколько байт было, сколько стало, сколько заняла пауза. Диагностика, написанная сразу, экономит часы позже.

Порядок внедрения такой же, как эволюция настоящих рантаймов: сначала mark-sweep с интрузивным списком (работает, собирает циклы, ничего не двигает), потом порог и стресс-тесты, потом — если понадобится — копирующий nursery. И только после этого имеет смысл смотреть в сторону конкурентности.

Утечки в языке со сборкой мусора

«В Java не бывает утечек памяти» — самое дорогое заблуждение в этом разделе. Сборщик гарантирует лишь то, что недостижимое будет освобождено. Достижимый мусор — целиком ответственность программиста:

• Кеш без ограничения. Map<Key, Value>, куда только кладут. Лечится ограничением размера, LRU или слабыми ссылками.
• Незакрытые подписки. Слушатель, зарегистрированный в долгоживущем объекте, держит весь граф вокруг себя. Классика утечек в UI и в EventEmitter.
• Замыкание захватило лишнее. Как мы видели в семантическом анализе, замыкание держит upvalue; если компилятор захватывает весь кадр вместо конкретных переменных, вместе с одной нужной переменной удерживается всё остальное. Такая ошибка была у ряда движков JS.
• Ссылка на кусок большого объекта. Указатель на элемент огромного среза в Go, подстрока в старой Java (до Java 7 substring разделяла массив символов) — маленькое значение держит мегабайты.
• Потоки и очереди. Живой поток — корень. Неограниченная очередь задач растёт, пока хватает памяти.

Инструменты языка: слабые ссылки (WeakReference, weakref, WeakMap) — ссылка, которую сборщик не считает, и эфемероны (ключ-значение, где значение живо, пока жив ключ; так устроен WeakMap в JS и ConditionalWeakTable в .NET). Финализаторы — соблазн, которому лучше не поддаваться: порядок вызова не определён, момент не определён, объект можно «воскресить», записав this в глобальную переменную, а исключение внутри финализатора рушит инварианты рантайма. Правильный ответ — явное освобождение: defer в Go, using/IDisposable в C#, try-with-resources в Java, контекстные менеджеры в Python.

Отдельно — RSS не равен размеру кучи. После сборки рантайм может не отдавать страницы ядру: Go долгое время использовал MADV_FREE (память числится за процессом, пока ядру не понадобится), потом вернулся к MADV_DONTNEED, чтобы графики RSS не пугали людей. Фрагментация неперемещающего сборщика тоже удерживает адресное пространство. Подробности механики страниц — в управлении памятью ОС.

Практика: как смотреть и что крутить

Правило номер один: сначала измерить, потом настраивать, и почти всегда правильный ответ — аллоцировать меньше.

# Go: строка на каждый цикл сборки
GODEBUG=gctrace=1 ./app
# gc 14 @2.084s 0%: 0.030+1.8+0.007 ms clock, ... 12->12->6 MB, 13 MB goal, 8 P
#   ^номер ^от старта ^доля CPU  ^STW+конкурентная маркировка+STW
#   12->12->6 MB: куча в начале -> в конце маркировки -> живые данные; 13 MB — цель

go tool pprof -alloc_objects http://localhost:6060/debug/pprof/heap   # кто аллоцирует
go build -gcflags='-m' ./...        # что убежало в кучу: escape-анализ

# JVM
java -Xlog:gc*:file=gc.log:time,uptime,level,tags -XX:+UseZGC -Xmx8g App
# .NET
dotnet-counters monitor --counters System.Runtime          # gen0/1/2 collections, % time in GC
# V8 / Node
node --trace-gc --max-old-space-size=4096 app.js

package main

import (
	"fmt"
	"runtime"
	"runtime/debug"
)

func main() {
	debug.SetGCPercent(100)       // цель кучи = живые данные × (1 + 100/100)
	debug.SetMemoryLimit(2 << 30) // мягкий предел 2 ГиБ: Go 1.19+, замена «балласту»

	var m runtime.MemStats
	runtime.ReadMemStats(&m)
	fmt.Printf("живых %d МиБ, циклов GC %d, суммарная пауза %.1f мс\n",
		m.HeapAlloc>>20, m.NumGC, float64(m.PauseTotalNs)/1e6)
}

Что реально помогает, в порядке убывания эффекта: убрать аллокации в горячем цикле (переиспользование буферов, значения вместо указателей, предвыделенные слайсы с make(..., 0, n)); дать процессу больше памяти — по формуле $f = A/(H-L)$ это линейно снижает частоту сборок; сменить сборщик на подходящий по профилю нагрузки; и лишь в последнюю очередь — крутить отдельные флаги. В Python отдельный трюк: gc.freeze() перед fork переносит все существующие объекты в «постоянное» поколение, и сборщик перестаёт трогать их счётчики — copy-on-write страницы не копируются, потребление памяти форк-воркеров падает в разы.

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

• Забыть корень. Значение достижимо только из локальной переменной интерпретатора — сборка его убивает. Ловится стресс-режимом, не ловится обычными тестами.
• Красить объект после помещения в worklist. Обход зацикливается на первой же циклической структуре.
• Аллокация внутри фазы mark. Рекурсивный вход в сборщик; заводите отдельный аллокатор для служебных структур GC или предвыделяйте worklist.
• Рекурсивный обход детей. Список из миллиона элементов кладёт стек C. Только явный worklist.
• Ключевать боковые таблицы адресом объекта. При перемещающем сборщике адрес меняется — см. ту же ошибку применительно к AST в статье 04.
• Отдать указатель на объект кучи в C и не закрепить его. Перемещающий сборщик сдвинет объект под ногами. В Go для этого есть правила передачи указателей в cgo, в .NET — fixed и GCHandle.
• Пул объектов «чтобы разгрузить GC». Часто делает хуже: превращает молодой мусор в долгоживущие данные и добавляет межпоколенческих ссылок.
• gc.disable() в долгоживущем процессе. Работает ровно до первого циклического графа.
• Настраивать флаги GC до профилирования аллокаций. Самая распространённая трата времени.
• Финализатор, освобождающий внешний ресурс. Файловые дескрипторы кончатся раньше, чем сработает сборщик: память под объект крошечная, а дескриптор — дефицитный ресурс, о котором сборщик не знает.

Мини-итог

• Живость неразрешима, поэтому все сборщики работают с достижимостью — консервативной, но вычислимой аппроксимацией. Отсюда же следует, что «утечка» достижимого мусора сборщиком не лечится.
• Подсчёт ссылок прост, детерминирован и даёт немедленное освобождение, но не собирает циклы, платит за каждую запись ссылки и превращается в паузу при каскадном освобождении.
• Трассирующая сборка решает проблему циклов и не платит за операции мутатора, но требует корней, точек безопасности и — в конкурентном режиме — барьеров.
• Копирование по Чейни делает работу пропорциональной живым данным, устраняет фрагментацию и превращает аллокацию в сложение указателя; цена — двойное адресное пространство и перемещение объектов.
• Поколения — эксплуатация эмпирики «объекты умирают молодыми». Ключевая деталь реализации — барьер записи и карточная таблица, ключевая ловушка — данные, живущие долго по построению.
• Цена сборки обратно пропорциональна запасу памяти: $C \sim L/(H-L)$, а частота сборок равна $A/(H-L)$. Поэтому уменьшение аллокаций и увеличение кучи работают лучше любой настройки флагов.
• Пауз не бывает бесплатных. Конкурентность оплачивается барьерами в горячем коде; правый верхний угол диаграммы «быстро и без пауз» пуст по фундаментальным причинам.
• Сборщик — это контракт с компилятором: карты стека, точки безопасности, барьеры записи и знание того, где лежат ссылки, генерируются на этапе кодогенерации.

Что почитать

• Richard Jones, Antony Hosking, Eliot Moss, The Garbage Collection Handbook — основная книга по теме, второе издание 2023 года; всё, что здесь изложено, там разобрано на сотнях страниц.
• John McCarthy, «Recursive Functions of Symbolic Expressions», CACM 1960 — статья, в которой mark-sweep появился впервые.
• C. J. Cheney, «A Nonrecursive List Compacting Algorithm», CACM 1970 — две страницы, породившие копирующие сборщики.
• Edsger Dijkstra и соавторы, «On-the-fly Garbage Collection: An Exercise in Cooperation» — истоки трёхцветной абстракции.
• Andrew Appel, «Simple Generational Garbage Collection and Fast Allocation», 1989 — почему аллокация может стоить одну инструкцию.
• Bacon, Cheng, Rajan, «A Unified Theory of Garbage Collection», OOPSLA 2004 — подсчёт ссылок и трассировка как двойственные алгоритмы.
• Hertz, Berger, «Quantifying the Performance of GC vs. Explicit Memory Management» — измеренная цена сборки мусора в памяти.
• Robert Nystrom, Crafting Interpreters, глава «Garbage Collection» — mark-sweep для ВМ на C, ровно в духе нашего Mini.
• Go GC Guide и «Getting to Go» — лучшая документация к конкретному сборщику из существующих.
• ZGC, Shenandoah, HotSpot GC Tuning Guide — конкурентная компактизация и настройка на практике.
• Fundamentals of garbage collection в .NET, CPython devguide, Erlang GC, V8 Orinoco — четыре очень разных промышленных решения.
• memorymanagement.org — словарь терминов управления памятью, полезен, когда в статьях встречается очередной «эфемерон».
• Связанные материалы портала: иерархия памяти, память в ОС, сложность и память, конкурентные структуры данных, функциональная парадигма — неизменяемые данные меняют профиль аллокаций сильнее любых флагов.

Что дальше

У Mini есть виртуальная машина и куча, которая сама себя убирает: язык стал полноценным — на нём можно писать программы, которые работают часами. Осталась последняя большая тема рантайма — скорость. Интерпретатор байткода проигрывает нативному коду в разы, и способ отыграть разрыв не в том, чтобы компилировать всё заранее, а в том, чтобы компилировать то, что реально исполняется часто, и пользоваться знанием, которого у AOT-компилятора нет никогда: фактическими типами и фактическими ветвлениями. Следующая статья — про счётчики вызовов и горячие циклы, инлайн-кеши, спекулятивные оптимизации и деоптимизацию, то есть про умение честно откатиться, когда предположение не сбылось. Заодно выяснится, что карты стека, которые мы обсуждали ради сборщика, нужны JIT ровно для того же.

JIT-компиляция: профилирование, горячие пути, деоптимизация