Компиляторы
Сборка мусора: алгоритмы
Программа на Java аллоцирует миллиард объектов в секунду. Как runtime знает, какие из них ещё нужны? Наивный ответ - посчитать ссылки. Реальный ответ - обходить граф объектов от известных живых точек. Разные алгоритмы GC делают этот обход по-разному: Mark-Sweep оставляет дырки, Copying перемещает объекты, Generational делает ставку на то, что молодые умирают быстро. Выбор алгоритма определяет pauses, throughput и memory footprint приложения.
- **JVM G1 GC** в Kafka broker (heap 6GB): Minor GC каждые 2-3 секунды по 5-15ms, Major GC раз в час по 200ms - это предсказуемые паузы за счёт generational гипотезы
- **CPython Reference Counting**: удаление большого дерева объектов в Python освобождает память немедленно и детерминированно - `with open()` гарантирует закрытие файла без ожидания GC
- **Swift ARC** в iOS UIKit: объекты UIViewController освобождаются детерминированно при `deinit`, что упрощает управление ресурсами по сравнению с JVM, где finalizer вызывается не определённо
Mark-Sweep
Mark-Sweep - двухфазный алгоритм GC. Фаза Mark: обход графа объектов от GC roots (стек, глобальные переменные, регистры), пометка достижимых объектов. Фаза Sweep: линейный проход по heap, освобождение непомеченных объектов. Простой и надёжный, но создаёт фрагментацию - живые объекты разбросаны по heap, free blocks между ними.
JVM Serial GC (однопоточный Mark-Sweep) до сих пор используется для небольших приложений (heap < 256MB) где throughput важнее latency. Go GC использует concurrent tri-color mark-sweep: три цвета (white/grey/black) позволяют маркировать параллельно с мутатором. Go 1.14 достиг pause time < 1ms для большинства heap размеров.
Почему Mark-Sweep создаёт фрагментацию heap?
Copying Collection
Copying collector (Cheney, 1970) делит heap на две half-spaces: from-space и to-space. При GC: живые объекты копируются в to-space в порядке обхода, мёртвые игнорируются. Spaces меняются местами. Результат: нет фрагментации, аллокация straightforwardly быстрая (bump pointer). Цена: половина heap всегда пустая.
JVM Young Generation использует Copying collector (Eden + два Survivor spaces). Большинство объектов в Java живут очень короткое время (weak generational hypothesis), поэтому Young GC копирует мало живых объектов и работает быстро: обычно 1-10ms. V8 New Space (для молодых объектов) - также Copying collector с двумя semi-spaces по 1-8 MB.
Почему аллокация объекта в Copying collector быстрее, чем в обычном аллокаторе с free list?
Generational GC
Generational hypothesis: большинство объектов умирают молодыми (weak generational hypothesis). Generational GC разделяет heap на поколения: Young (новые объекты) и Old (выжившие). Young GC часто и быстро - копирует маленькую young generation. Old GC редко и медленно - mark-sweep или mark-compact. Объекты, пережившие N Young GC циклов, промотируются в Old generation.
G1 GC (JDK 9+ default) делит heap на ~2000 regions по 1-32MB вместо фиксированного разделения Young/Old. Это позволяет собирать наиболее заполненные regions первыми (Garbage First). G1 добивается pause time goal: `-XX:MaxGCPauseMillis=200`. ZGC и Shenandoah идут дальше - sub-millisecond pauses.
Что такое 'remembered set' (card table) в Generational GC?
Reference Counting
Reference Counting (RC) - каждый объект хранит счётчик ссылок. При копировании ссылки +1, при удалении -1, при 0 объект немедленно освобождается. Детерминированное освобождение памяти, нет stop-the-world. Фундаментальная проблема: циклы ссылок (A -> B -> A) дают счётчик > 0 у оба недостижимых объектов.
Swift ARC (Automatic Reference Counting) использует compile-time вставку retain/release вызовов - нет рантайм GC паузы. Проблема циклов решается через `weak` и `unowned` ссылки. Rust использует Rc/Arc только по явному запросу; обычные ссылки управляются borrow checker без счётчиков. Apple перешла с manual retain/release на ARC в iOS 5 (2011), это одно из крупнейших изменений в экосистеме Apple.
Reference Counting всегда детерминированнее и быстрее трассирующего GC
RC детерминировано освобождает ациклические объекты, но тратит время на атомарные increment/decrement при каждом копировании ссылки, что создаёт overhead в многопоточном коде
Arc<T> в Rust или AtomicInteger в Java при каждом клонировании Arc делает atomic fetch-and-add - это cache line invalidation на всех CPU cores. Для объектов с короткой жизнью накладные расходы RC могут превысить GC-паузы
Почему Reference Counting не справляется с циклическими ссылками?
Итоги
- Mark-Sweep: обход графа + освобождение непомеченных; фрагментация heap, stop-the-world pause proportional to heap size
- Copying: копирование живых объектов в новую area; нет фрагментации, bump pointer аллокация, но 50% overhead памяти
- Generational: young objects умирают быстро - Minor GC быстрый и частый, Major GC редкий; Reference Counting детерминирован но не справляется с циклами
Связанные темы
Алгоритмы GC - основа для понимания продвинутых техник:
- Продвинутый GC: concurrent и real-time — ZGC, Shenandoah, Go GC строятся поверх базовых алгоритмов с concurrent marking
- Управление памятью — malloc/free, arena аллокаторы и Rust borrow checker - альтернативы GC
- JIT-компиляция — GC barriers (write barriers) влияют на JIT-генерацию кода для каждой записи в heap
Вопросы для размышления
- Почему Copying collector эффективен для Young Generation, но неприменим для Old Generation с большим heap?
- Go GC достигает sub-millisecond pauses используя concurrent Mark-Sweep без Generational hypothesis. Почему Go не использует Generational GC как JVM?
- Rust исключает GC через ownership/borrow checker. Что это означает для паттернов программирования - какие структуры данных сложно выразить в Rust без Rc/Arc?