About Teletype
Join
Андрей Жаркевич
@azhark
Yesterday

Сборка мусора: кто убирает за разработчиками

В 1959 году Джон Маккарти работал над языком Lisp в MIT и столкнулся с проблемой, которая преследует программистов по сей день. Программы на Lisp создавали сложные структуры из связанных ячеек — списки, деревья, графы. Некоторые из этих структур переставали быть нужными по ходу вычислений, но определить какие именно и когда — задача, которую Маккарти не хотел перекладывать на человека.

Его решение было радикальным: пусть сама программа периодически находит неиспользуемые объекты и освобождает память. Маккарти назвал это garbage collection — «сборка мусора» — и реализовал алгоритм mark-and-sweep: пометь всё живое, остальное выброси. С тех пор прошло почти 70 лет. Сборщики мусора превратились в сложнейшие инженерные системы с десятками тысяч строк кода. Но фундаментальный вопрос остаётся тем же: как понять, что объект больше никому не нужен?

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

Подсчёт ссылок: простое и элегантное решение

Идея подсчёта ссылок (reference counting, RC) появилась в 1960 году в работе Джорджа Коллинза. Каждый объект в памяти хранит счётчик — число указателей, которые на него ссылаются. При создании новой ссылки счётчик увеличивается на единицу. При уничтожении ссылки — уменьшается. Когда счётчик достигает нуля, объект гарантированно никому не нужен и немедленно освобождается.

Простой пример. Функция создаёт строку и возвращает её вызывающему коду. В момент создания счётчик строки равен 1 (локальная переменная ссылается на неё). Функция возвращает строку — вызывающий код сохраняет результат, счётчик становится 2. Локальная переменная выходит из области видимости — счётчик снова 1. Наконец, вызывающий код перестаёт использовать строку — счётчик обнуляется, память освобождается.

У подсчёта ссылок два важных преимущества. Во-первых, детерминизм: объект освобождается в тот момент, когда последняя ссылка на него исчезает. Не «когда-нибудь потом», не «при следующей сборке», а прямо сейчас. Это критично для ресурсов, которые нужно освобождать вовремя: файловых дескрипторов, сетевых соединений, блокировок. Во-вторых, равномерность нагрузки: работа по управлению памятью размазана по всему времени выполнения программы — нет пиковых пауз.

Так работают CPython, Swift, Objective-C, PHP, Perl и Nim.

Но у подсчёта ссылок есть фатальный изъян — он не видит циклов. Представьте: объект A содержит ссылку на объект B, а объект B — ссылку обратно на A. Счётчик A равен 1 (ссылка из B). Счётчик B тоже 1 (ссылка из A). Теперь допустим, что никакой другой код больше не ссылается ни на A, ни на B — оба объекта недоступны извне, оба являются мусором. Но оба счётчика равны единице, и подсчёт ссылок никогда их не освободит. Утечка памяти.

Циклические ссылки — не экзотика. Они возникают естественно: узлы дерева ссылаются на родителя и на детей, элементы двусвязного списка — на соседей, обработчики событий замыкаются на объект, который их содержит, async/await в большинстве реализаций порождает замыкания, ссылающиеся друг на друга. Любая сколько-нибудь сложная программа создаёт циклы.

Трассировка: взгляд с другой стороны

Подсчёт ссылок спрашивает: «кто указывает на этот объект?» Трассировка (tracing) задаёт другой вопрос: «можно ли добраться до этого объекта от корней?»

Корни (roots) — это переменные, которые заведомо живы: локальные переменные на стеке каждого потока, глобальные переменные, регистры процессора. Алгоритм mark-and-sweep, придуманный Маккарти, работает в два этапа. На этапе маркировки (mark) сборщик начинает от корней и рекурсивно обходит все объекты, доступные по цепочкам ссылок, помечая каждый как «живой». На этапе подметания (sweep) сборщик проходит по всей куче: всё, что не помечено, — мусор.

Циклы перестают быть проблемой. Если A ссылается на B, а B на A, но ни до A, ни до B нельзя добраться от корней — оба остаются непомеченными, оба удаляются. Трассировка решает задачу, перед которой подсчёт ссылок бессилен.

Но за это приходится платить. Пока сборщик обходит граф объектов, программа должна быть приостановлена — иначе она может изменить граф прямо в процессе обхода. Это называется stop-the-world — «остановить мир». Для программы с кучей в несколько гигабайт пауза может длиться сотни миллисекунд. Для веб-сервера, обрабатывающего тысячи запросов в секунду, каждая такая пауза — сотни подвисших клиентов.

Два следующих десятилетия после Маккарти были посвящены одному вопросу: как сократить эти паузы?

Гипотеза о поколениях: не все объекты одинаковы

Первый прорыв совершил Дэвид Унгар из Стэнфорда. В 1984 году он опубликовал работу «Generation Scavenging», в которой сформулировал наблюдение, ставшее фундаментом для всех современных трассирующих сборщиков. Унгар заметил, что подавляющее большинство объектов в программе живут очень недолго. Временная переменная в цикле, промежуточная строка при форматировании, объект запроса в HTTP-сервере — всё это создаётся и становится мусором за миллисекунды.

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

Из гипотезы следует мощная оптимизация: кучу нужно разделить на поколения. Новые объекты попадают в молодое поколение (nursery, young generation) — небольшую область, которая собирается часто и быстро. Большинство объектов в ней уже мертвы — сборка проходит за микросекунды. Если объект пережил несколько сборок молодого поколения, он повышается (promotes) в старшее поколение, которое собирается гораздо реже.

Java HotSpot использует три области: Eden (создание), Survivor (промежуточная) и Old (долгоживущие). Python — три поколения с настраиваемыми порогами. .NET — тоже три. Идея Унгара оказалась настолько продуктивной, что сегодня практически каждый трассирующий сборщик — поколенческий. За одним знаменитым исключением, о котором ниже.

Трёхцветная маркировка: собирать мусор на ходу

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

В 1978 году Эдсгер Дейкстра (тот самый — автор алгоритма кратчайших путей и знаменитого письма «Go To Statement Considered Harmful») вместе с Лесли Лэмпортом и другими соавторами опубликовал алгоритм «On-the-Fly Garbage Collection» — трёхцветную маркировку. Каждый объект в любой момент окрашен в один из трёх цветов:

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

Алгоритм начинает с того, что окрашивает корни в серый. На каждом шаге берёт серый объект, проверяет все его ссылки (окрашивая найденные белые объекты в серый) и перекрашивает себя в чёрный. Когда серых не осталось — все оставшиеся белые гарантированно мусор.

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

Решение — барьер записи (write barrier). При каждом обновлении указателя в программе барьер перехватывает изменение и перекрашивает объект в серый. Это накладные расходы: каждое присваивание указателя стоит на несколько наносекунд дороже. Но взамен программа не замирает на сотни миллисекунд. Для подавляющего большинства приложений этот компромисс выгоден.

Теперь, когда у нас есть поколения Унгара и конкурентная маркировка Дейкстры, можно посмотреть, как эти идеи реализованы в конкретных языках. Начнём с Go — языка, который сделал ставку на минимальные паузы и добился результата, поразившего индустрию.

Go: три порядка улучшения за два года

Go использует конкурентный трёхцветный сборщик, основанный на алгоритме Дейкстры. Главный архитектор — Рик Хадсон из команды Go в Google. История GC в Go — одна из самых драматичных в индустрии.

Эпоха stop-the-world

До Go 1.5 (август 2015) сборщик останавливал все горутины на время сборки. Паузы достигали 300–400 миллисекунд. Инженер Twitter Брайан Хэтфилд публиковал графики пауз GC в реальном времени — они выглядели как кардиограмма тяжелобольного. Для серверного языка, который позиционировался как замена C++ и Java в инфраструктуре, это было неприемлемо.

Конкурентная маркировка (Go 1.5)

Go 1.5 принёс конкурентную маркировку: основная фаза сборки теперь выполнялась параллельно с работой программы. Паузы упали до 30–40 мс — на порядок лучше, но всё ещё заметно для сервисов с жёсткими требованиями к задержке.

Гибридный барьер (Go 1.8)

Go 1.8 (февраль 2017) добавил гибридный барьер записи — комбинацию барьеров Дейкстры и Юасы. До этого сборщику приходилось в stop-the-world фазе повторно сканировать стеки горутин, потому что горутины могли перемещать указатели между стеком и кучей. Гибридный барьер убрал эту необходимость. Паузы стали субмиллисекундными — обычно 100–500 микросекунд.

Итого: от 300 мс до 0,5 мс — три порядка улучшения за два года.

Почему Go обходится без поколений?

Практически все трассирующие сборщики используют поколения. Go — знаменитое исключение. Это осознанное решение, основанное на нескольких особенностях языка.

Компилятор Go хорошо делает escape-анализ: если объект не «убегает» из функции — не присваивается глобальной переменной, не возвращается наружу, не передаётся по указателю в другую горутину — он размещается на стеке горутины, а не в куче. Стек горутины начинается с 4 КБ и растёт по необходимости — это дёшево. Короткоживущие объекты, которые в Java попали бы в nursery, в Go часто вообще не доходят до кучи. Гипотеза о поколениях выполняется «бесплатно» — на уровне компилятора, а не рантайма.

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

Наконец, поколения требуют барьера записи, работающего постоянно — даже когда сборка не идёт. Go активирует барьер только во время сборки. Вне сборки присваивание указателя — одна машинная инструкция без накладных расходов.

GOGC и GOMEMLIMIT

GOGC (по умолчанию 100) управляет частотой сборки: новые аллокации могут достичь 100 % размера живой кучи, прежде чем запустится следующая сборка. GOGC=50 — сборки чаще, памяти меньше. GOGC=200 — реже, но памяти больше.

С Go 1.19 появился GOMEMLIMIT — мягкий лимит общей памяти рантайма. Установив GOGC=off и GOMEMLIMIT=4GiB, можно сказать рантайму: «собирай мусор только когда приближаешься к 4 ГБ». Полезно в контейнерах с жёстким лимитом памяти — рекомендация устанавливать GOMEMLIMIT на 90–95 % от лимита контейнера.

Green Tea GC (Go 1.26)

В Go 1.25 (август 2025) появился экспериментальный сборщик Green Tea, включаемый через GOEXPERIMENT=greenteagc. В Go 1.26 (февраль 2026) он стал сборщиком по умолчанию. Вместо сканирования отдельных объектов Green Tea сканирует память блоками (spans). Для маленьких объектов (до 512 байт) — а их подавляющее большинство — это даёт 10–40 % снижения накладных расходов GC и вдвое меньше промахов кеша процессора. Авторы — Майкл Кнышек и Остин Клементс.

Java: эволюция на ходу

Если Go — история одного решения, доведённого до совершенства, то Java — история непрерывной эволюции. Каждое поколение JVM приносило новый сборщик, решавший проблемы предыдущего.

Serial GC — первый сборщик, однопоточный, с полной остановкой. В 1990-х, на одноядерных машинах с кучей в десятки мегабайт, его было достаточно.

Parallel GC (по умолчанию в Java 8) стал ответом на многоядерную эпоху: несколько потоков собирают мусор одновременно. Пропускная способность выросла, но программа по-прежнему замирает на время сборки. Паузы — от десятков миллисекунд до секунд.

G1 (Garbage First, по умолчанию с Java 9) — первый шаг к предсказуемости. G1 делит кучу на сотни маленьких регионов и собирает в первую очередь те, где больше всего мусора (отсюда название). Цель — удерживать паузы в заданных рамках, обычно 50–200 мс. Не субмиллисекундный, но предсказуемый.

ZGC (экспериментальный в Java 11, стабильный в Java 17, поколенческий с Java 21) — прорыв. Субмиллисекундные паузы независимо от размера кучи — хоть 1 ГБ, хоть 16 ТБ. Ключевая техника — цветные указатели (colored pointers): часть бит в 64-битном указателе используется не для адреса, а для кодирования состояния объекта. Когда сборщик перемещает объект в новое место (компактификация), он обновляет метаданные в указателе. При следующем чтении указателя барьер нагрузки обнаруживает устаревшую метку и обновляет адрес. Это позволяет ZGC перемещать объекты конкурентно, без остановки программы. Цена: ~15–30 % дополнительной памяти и ~5–10 % CPU.

Shenandoah (Red Hat, стабильный с Java 17, поколенческий с Java 25) — альтернативный путь к тем же целям. Вместо цветных указателей использует барьеры нагрузки другой конструкции. Паузы обычно менее 5 мс.

В Java 24 (март 2025) непоколенческий ZGC был удалён — остался только поколенческий вариант. В Java 25 (сентябрь 2025) стабилизировался поколенческий Shenandoah. Индустрия пришла к консенсусу: субмиллисекундные паузы — не экзотика, а норма.

Подсчёт ссылок наносит ответный удар

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

Swift: ARC без рантайма

Apple выбрала для Swift Automatic Reference Counting (ARC) — подсчёт ссылок, управляемый компилятором. Компилятор анализирует код и вставляет вызовы retain (увеличить счётчик) и release (уменьшить) в нужных местах на этапе компиляции. Никакого фонового потока, никаких пауз, никакой трассировки. Момент освобождения памяти полностью детерминирован.

ARC применяется только к экземплярам классов (ссылочным типам); структуры и перечисления — типы-значения, копируются. Циклы — ответственность программиста: weak (слабая ссылка, автоматически обнуляется при удалении целевого объекта) и unowned (не обнуляется — крашится при доступе к удалённому объекту, используется когда время жизни гарантировано). В замыканиях — capture lists: [weak self] или [unowned self].

Для мобильных устройств, где энергопотребление критично, а фоновые потоки GC расходуют батарею, ARC оказался идеальным выбором.

Nim: путь через три алгоритма

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

Первоначальным сборщиком был refc — отложенный подсчёт ссылок. «Отложенный» — потому что ссылки со стека не учитывались, что упрощало генерацию C-кода. Для обнаружения циклов поверх refc работал классический mark-and-sweep — полная трассировка кучи. У каждого потока была собственная куча, передавать GC-объекты между потоками напрямую было нельзя. Кроме refc, Nim предлагал на выбор --gc:markAndSweep, --gc:boehm (консервативный сборщик Бёма), --gc:go и --gc:none. Обилие вариантов говорило о том, что ни один из них не был по-настоящему удовлетворительным.

В 2019 году Андреас Румпф, создатель Nim, предпринял амбициозный эксперимент: owned ref — Rust-подобная система владения. Идея: owned ref работает как unique_ptr в C++, обычный ref становится неуправляемой ссылкой. Эксперимент наткнулся на множество ошибок — двойные освобождения, некорректная деструктуризация обобщённых типов — и был свёрнут. Но идеи деструкторов и семантики перемещения легли в основу следующего шага.

ARC появился в Nim 1.2 (апрель 2020) — автоматический подсчёт ссылок с деструкторами и семантикой перемещения. Компилятор вставляет вызовы =destroy в конце областей видимости, а операции копирования по возможности заменяет на перемещения. В отличие от Swift, ARC в Nim не использует атомарные операции — целые подграфы объектов перемещаются между потоками целиком. Все потоки работают с общей кучей, межпоточный обмен стал простым. Но одну проблему ARC не решил: циклы по-прежнему вызывали утечки. Для async/await это было критично — реализация асинхронности в Nim неизбежно создаёт замыкания, ссылающиеся друг на друга.

ORC (Nim 1.4, октябрь 2020; по умолчанию — с Nim 2.0, август 2023) — это ARC плюс сборщик циклов. Название — каламбур: O — визуальный символ цикла (кольцо), RC — Reference Counting.

Алгоритм ORC основан на пробном удалении (trial deletion), описанном Линсом (1992) и развитом Бэконом и Раджаном (2001). Когда счётчик ссылок уменьшается, объект запоминается как потенциальный корень цикла. При запуске сборщик берёт все запомненные корни, временно вычитает из графа их рёбра (имитирует удаление) и смотрит, у каких объектов счётчик дошёл до нуля. Если дошёл — объект жив только благодаря циклу, и его можно удалить. Если нет — у объекта есть внешние ссылки, он восстанавливается.

Ключевое отличие от классической трассировки: ORC не обходит всю кучу. Он работает только с окрестностью потенциальных корней. Производительность не зависит от размера кучи — только от количества циклических структур. Компилятор помогает: статический анализ типов определяет, может ли тип участвовать в цикле. Если не может, объект вообще не регистрируется. Программист может дополнительно аннотировать тип прагмой {.acyclic.}.

На бенчмарке HTTP-сервера с ~135 МБ JSON-данных в памяти ORC показал средние задержки 320 мкс против 65 мс у mark-and-sweep — в 200 раз быстрее — и при этом потреблял меньше памяти.

Nimony: будущее без вариантов

Андреас Румпф не остановился на ORC. Nimony — переписанный с нуля компилятор Nim, который должен стать основой Nim 3.0. Текущая версия — v0.2 (ранний превью). Одно из ключевых решений: все варианты управления памятью убраны. Никаких --gc:refc, --mm:orc, --gc:boehm. Единственный режим — mm:atomicArc — атомарный подсчёт ссылок с деструкторами и семантикой перемещения.

Для обработки циклов Nimony вводит явную аннотацию .cyclic: программист размечает типы, которые могут участвовать в циклах. Это делает управление циклами явным, а не магическим. Подход продиктован целевой аудиторией: Nimony нацелен на системы реального времени и встраиваемые платформы, где гарантированное время выполнения (WCET, Worst Case Execution Time) важнее удобства. Это, как указано в документе проектирования, «исключает JIT-компиляторы и трассирующие сборщики мусора».

Единая теория

В 2004 году Дэвид Бэкон опубликовал работу «A Unified Theory of Garbage Collection», в которой показал, что подсчёт ссылок и трассировка — дуалы одного и того же алгоритма. Трассировка — это «отложенный подсчёт ссылок от корней»: вместо того чтобы реагировать на каждое изменение указателя, трассировщик периодически пересчитывает достижимость. Подсчёт ссылок — это «немедленная трассировка от изменённых объектов»: каждое изменение указателя запускает мини-обход. Чистая трассировка и чистый RC — два полюса спектра. ORC в Nim, CPython с детектором циклов, Swift ARC — все они находятся где-то между полюсами, комбинируя оба подхода.

Python: прагматичный гибрид

CPython — наглядный пример точки на этом спектре. Основной механизм — подсчёт ссылок: каждый объект содержит поле ob_refcnt. Когда счётчик падает до нуля, объект удаляется немедленно — и это нельзя отключить, на этом основана семантика языка. Файлы закрываются при выходе из with-блока, деструкторы вызываются предсказуемо — код CPython полагается на детерминизм RC.

Поверх этого работает поколенческий детектор циклов (модуль gc). Он проверяет только объекты-контейнеры — списки, словари, экземпляры классов, кортежи — то есть те, которые могут содержать ссылки. Целые числа, строки и другие простые типы не отслеживаются. Три поколения с настраиваемыми порогами.

Детектор можно отключить через gc.disable(). Instagram сделал именно это в продакшне: в 2017 году инженеры обнаружили, что после fork() детектор циклов вызывал копирование страниц памяти (Copy-on-Write), раздувая потребление. Отключение gc сэкономило ~10 % памяти на каждом воркере. Грязный приём — но он работал.

Без сборщика мусора

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

Rust: владение вместо рантайма

Rust решает задачу на этапе компиляции через систему владения (ownership) с тремя правилами:

  1. У каждого значения ровно один владелец.
  2. Когда владелец выходит из области видимости, значение уничтожается.
  3. В каждый момент допустима либо одна изменяемая ссылка, либо любое количество неизменяемых — но не оба одновременно.

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

Для разделяемого владения есть Rc<T> (подсчёт ссылок, однопоточный) и Arc<T> (атомарный, многопоточный). Как и в Swift, циклы — ответственность программиста: Weak<T> разрывает цикл. В Rust нет детектора циклов — цикл из Rc<T> утечёт навсегда.

Цена — более крутая кривая обучения. Двусвязные списки, произвольные графы и другие структуры с циклическими ссылками требуют unsafe или обхода через индексы в массиве (arena allocation).

Zig: аллокатор как параметр

Zig занимает другой край: никакого автоматического управления, но продуманная эргономика. Главная идея — аллокатор как параметр. Каждая функция, которая выделяет память, принимает std.mem.Allocator как аргумент. Нет глобального malloc — каждая аллокация видна явно:

  • page_allocator — напрямую из ОС через mmap/VirtualAlloc;
  • GeneralPurposeAllocator — отладочный, обнаруживает утечки и двойное освобождение;
  • ArenaAllocator — выделяйте сколько угодно, освобождайте всё разом одним вызовом;
  • FixedBufferAllocator — из заранее выделенного буфера, без системных вызовов.

defer allocator.free(buf) гарантирует освобождение при выходе из блока. Каждый вызов, способный выделить память, возвращает ошибку — скрытых аллокаций не бывает. Zig не делает управление памятью проще — он делает его явным.

Discord: когда теория встречает продакшн

В феврале 2020 года Discord опубликовал статью «Why Discord is switching from Go to Rust». Сервис Read States — один из самых нагруженных компонентов, отслеживающий прочитанные каналы и сообщения каждого пользователя — страдал от периодических всплесков задержки.

Причина оказалась в фундаментальном конфликте между сборщиком мусора и кешем с вытеснением давно не используемых элементов (LRU-кеш). Сборщик Go должен был сканировать весь кеш — миллионы объектов — чтобы определить, какие из них живые. Сканирование почти ничего не освобождало: кеш по определению хранит нужные данные. Но обход занимал десятки миллисекунд и вызывал пилообразные скачки задержки каждые несколько минут.

Переход на Rust решил проблему: при вытеснении элемента из LRU-кеша память освобождается немедленно, без обхода графа. По словам инженеров Discord, «даже без оптимизаций Rust-версия работала быстрее тщательно настроенной Go-версии».

Справедливости ради: Go 1.12, вышедший позже, улучшил подметание для больших живых куч — проблема была бы менее острой. А с Green Tea GC в Go 1.26 накладные расходы на сканирование снизились ещё на 10–40 %. Но кейс остаётся каноническим примером конфликта между GC и крупными кешами.

Сравнение пауз

Индустрия пришла к компромиссу: ~7–15 % снижения пропускной способности ради 1000-кратного улучшения предсказуемости задержки. В микросервисных архитектурах, где один запрос проходит через 5–10 сервисов, паузы GC каскадируются: задержка в одном сервисе блокирует все вызывающие. Субмиллисекундные сборщики — уже не роскошь, а необходимость.

Примеры кода

В файлах — три примера:

  • gc_demo.rs — RAII, Drop, Rc<T>, циклические ссылки, передача владения;
  • gc_demo.go — runtime.MemStats, принудительная сборка, финализаторы, статистика пауз;
  • gc_demo.zig — page_allocator, defer, ArrayList с ручным управлением, арена-аллокатор.

Источники

Андрей Жаркевич
Yesterday, 19:24
0 views
0 reactions
0 replies
0 reposts