GC: golang и прочие

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

Последний месяц-два много шума из-за go. Команда разработчиков go рапортует о том, что в версии 1.5 их GC работает со средними паузами в районе сотен микросекунд, и максимальными < 10 миллисекунд ну и типа это "прорывное решение", "сборщик мусора для следующего десятилетия" и другие громкие заявления. В связи с этим хорошая статья Mike Hearn на medium: Modern Garbage Collection разбирает ситуацию (пока я писал, ее уже перевели на хабре).

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

В частности, нынешний "прорывной" сборщик мусора в go — это concurrent mark-sweep, прямой родственник и аналог OpenJDK-CMS в java. С той только разницей, что нет поколений — да, да, прямо сейчас в go (1.5) не используется сборка по поколениям (хотя это запланировано), собирается вся куча, как единый кусок. При этом, как и в OpenJDK-CMS, в асинхронном режиме нет compaction — куча дефрагментируется только в режим stop-the-world. Как результат: нужен довольно большой запас памяти, чтобы противостоять фрагментации (желательно примерно вдвое больше реально используемой), и на обход кучи тратится довольно заметная часть ресурсов CPU.

CMS в OpenJDK используется для старого поколения, в паре с копирующим сборщиком для молодого поколения. И наибольшие паузы (при правильной настройке), это паузы на сборку молодого поколения. Собирать молодое поколение в асинхронном режиме сложно, потому что сборщик молодого поколения — перемещающий (чтобы отслеживать асинхронно перемещаемые объекты понадобятся read barrier-ы). Но именно сборка молодого поколения позволяет снизить нагрузку на сам CMS — лишь небольшая доля объектов доживают до зрелости. Поэтому в джаве CMS (точнее, комбинация CMS + ParNew) в среднем более эффективен с точки зрения накладных расходов: какой избыток памяти нужен, и какую часть CPU time заберет GC.

В мире realtime java в свое время предлагался Metronome — сборщик мусора для систем реального времени, для которого можно доказать ограничения на величину вносимых им пауз (правда, паузы там все равно были в районе миллисекунд, но это 2003 год). Платить за это приходилось серьезными затратами CPU: сборка мусора съедала аж 50% процессорного времени. В go, вроде бы, все не настолько плохо, но и их GC отъедает десятки процентов CPU в нормальном режиме работы. В джаве нормально настроенный GC обычно ест ~5%

Gil Tene в дискуссии на mechanical sympathy справедливо замечает, что любому техническому решению нужно время, чтобы созреть. Неразумно выносить какие-то окончательные суждения про go GC сейчас, когда весь проект go еще очень молод — он еще 100 раз успеет мутировать. С его точки зрения, пока что главная опасность в нынешнем сборщике мусора go — это отсутствие перемещений объектов. Без перемещения объектов сборка мусора неизбежно будет приводить ко фрагментации, и это станет серьезным камнем преткновения по мере развития платформы. Опасность в том, что такое решение может оказаться зафиксированным просто де-факто — пока это так в нынешней реализации, авторы сторонних библиотек успеют заложиться на фиксированные адреса объектов в памяти, и уже нельзя будет поменять это, не поломав обратной совместимости для большого количества существующего кода.

Чтобы больше погрузиться в тему компромиссов при сборке мусора: хорошая статья A Unified Theory of Garbage Collection. Авторы задались целью показать, как различные подходы к автоматическому управлению памятью на на самом деле представляют собой полюса одного непрерывного спектра решений. И изначально различные реализации по мере обретения зрелости обрастают эвристиками, оптимизациями, становятся все более гибридными, и все меньше отличаются друг от друга. Авторы рассматривают подсчет ссылок (reference counting) и трассировку (tracing) объектов как своего рода взаимо-дополняющие методы управления памятью: где один из них хорош — другой плох. И любая зрелая реализация трассировки со временем обрастет оптимизациями, представляющими собой, по-сути, ограниченный подсчет ссылок — и наоборот. Например, card marking, который используется в generational GC чтобы отслеживать ссылки из старого поколения в молодое — это ни что иное, как вырожденная форма reference counting. Вообще, write barrier-ы — это прямое указание на какую-то форму подсчета ссылок.

Другая весьма старая (но не менее интересная) статья Hans Boehm-а на тему компромиссов: Mark-sweep vs. copying collection and asymptotic complexity. Ханс рассматривает Mark-Sweep и копирующий сборщики, и задается вопросом, насколько их общеизвестные теоретические свойства действительно реализуются в реальных условиях.

Например: считается, что время работы копирующего сборщика пропорционально количеству живых объектов, в то время как для Mark-Sweep это время пропорционально общему объему кучи. Такая оценка Mark-Sweep основана на том, что в sweep-фазе нужно обойти все "мертвые" объекты, чтобы добавить их во free-set. Ханс замечает, что sweep-фаза вообще не является обязательной: можно ставить пометки только на живых объектах, а при аллокации сканировать кучу напропалую, ищя первый кусок памяти без пометки "живой". Этот алгоритм будет эффективен, если значительная (бОльшая) часть кучи после сборки окажется пустой — но ровно же в этом случае и копирующий сборщик становится эффективным!

Ханс рассматривает несколько аналогичных "общепринятых" свойств, и показывает, что на практике не всегда все так очевидно, как кажется.