23 июня 2017 г.

Shenandoah на JPoint 2017

Запоздалый отклик на рассказ о Shenandoah на JPoint 2017 и последокладные разговоры. Я не буду пересказывать Алексея — лучше Алексея никто Алексея не перескажет, видео наше все. Здесь мои размышления после, и что мне показалось интересным.

Интересного в Shenandoah много. Для меня в первую очередь интересно, что Шенандо — первый GC в джаве, который не основан на гипотезе о поколениях.

Я начну издалека. Базовый алгоритм для сборки мусора это трассировка ссылок: определяем GC Roots, от них идем по ссылкам, и помечаем достижимые объекты как живые. Но на большой куче трассировка потребует много времени. Если мусор собирать в режиме паузы (Stop The World, SWT), то паузы будут долгими.

Как сделать паузы короче? Логично разбить работу на изолированные кусочки, и обрабатывать их по одному. Однако определение достижимости объектов разбить на изолированные задачки оказывается не так-то просто: в общем случае нельзя проанализировать достижимость какого-то подмножества объектов без того, чтобы протрассировать все остальные объекты в куче. Почему? Потому что, в общем случае, на любой объект из нашего подмножества потенциально может ссылаться любой другой объект. Априори нет способа ограничить поиск входящих ссылок каким-то подмножеством кучи.

В общем случае это так, да. Но реальные графы ссылок почти никогда не бывают настолько плотные, чтобы все ссылались на всех. (Хотя бы уже потому, что количество исходящих ссылок из каждого объекта ограничено его размером, и очень мало по сравнению с общим количеством объектов в куче). Кажется вероятным, что реальную кучу все-таки можно разбить на регионы, которые сильно связаны внутри себя, но слабо связаны с другими регионами (связность в смысле входящих ссылок). Когда куча разбита на регионы так, что между собой регионы связаны слабо, то GC сможет быстро собирать такие регионы инкрементально, по одному: чтобы собрать регион Х достаточно просканировать сам регион Х, плюс те регионы, из которых есть ссылки в Х — а таких регионов немного, потому что связность низкая.

Остается придумать, как же разбить кучу на такие удобные регионы?

Один из способов решения этой задачи дают generational GC. Generational GC основаны на паре эмпирических наблюдений: "гипотезах о поколениях". Первая (слабая) гипотеза о поколениях утверждает, что большинство объектов умирает молодыми, вторая (сильная) гипотеза утверждает, что старые объекты редко ссылаются на молодые.

...Когда я впервые познакомился с generational hypothesis, я был уверен, что первая гипотеза самая важная. Ну, не зря же она — первая? Вторая гипотеза несколько лет жила в моей памяти в виде "ну там еще какие-то дополнительные условия, но они не критичны". Именно так я несколько лет отвечал на собеседованиях, и никто не придирался. С тех пор у меня осталось убеждение, что большинство разработчиков тоже так и думает :)

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

Сильная гипотеза как раз дает подсказку, как собрать мусор в молодом регионе не трассируя всю остальную кучу. Сильная гипотеза говорит, что ссылок из старых регионов в молодые — мало. Это то самое утверждение о структуре графа связности регионов, которого не хватает. Если ссылок из старых регионов в молодые мало, то их достаточно отслеживать каким-нибудь грубым но дешевым способом (например: card marking), и при сборке молодого региона останется просмотреть лишь небольшой кусок старых регионов. Так мы получаем знакомую схему NewGen + OldGen

Что изменилось с приходом G1? G1 претендовал на то, чтобы уменьшить паузы при сборке старого поколения (актуально на больших кучах). Для этого и старое и молодое поколение разбито на регионы одинакового размера, G1 отслеживает ссылки между регионами, так что и в старом, и в молодом поколении возможна инкрементальная сборка. В идеале это позволило бы очищать кучу слой за слоем, как луковицу.

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

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

Чтобы уменьшить проблему пришлось увеличивать подробность отслеживания ссылок между регионами: не просто "регион А ссылается на регион Б", а из какой конкретно области региона А есть ссылки на объект из Б (RememberedSet). Чтобы отслеживать ссылки с такой подробностью пришлось написать много хитрого кода, который потребяет ресурсы. Подробная информация о ссылках между регионами занимает много места (до 40% кучи в G1 бывает занято этими RememberedSet-ами). Все это в сумме тратит время и нервы разработчиков — сколько лет уже G1 полируют, и только в 9-ке он, наконец, станет выбором по-умолчанию.

Где в этой картине Shenandoah? Shenandoah делает практически же самое, что G1 только хорошо: разбивает кучу на регионы, отслеживает ссылки между ними, очищает регионы инкрементально. Разница в том, что Shenandoah очищает мусор не в паузах, а параллельно с приложением. И те сценарии, которые для G1 патологические — то есть вызывают неприемлемые паузы в работе приложения — для Shenandoah патологическими уже не являются. Для Shenandoah такие сценарии будут не самыми эффективными по CPU — да, возможно, но не патологическими, потому что паузы в работе приложения остаются минимальными, а повышенное потребление CPU сейчас как правило не критично.

Shenandoah заимствует у G1 всю красоту идеи регионального сборщика мусора, но выбрасывает весь геморрой с RememberedSet-ами, заменяя их на старый-добрый card mark. Конечно, заплатить все равно приходится — в той части, где Shenandoah ухитряется собирать мусор параллельно с работой приложения. Там хватает своих тонкостей и накладных расходов. Но вот региональную часть Шенандо получает практически на сдачу.

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

10 января 2017 г.

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-фаза вообще не является обязательной: можно ставить пометки только на живых объектах, а при аллокации сканировать кучу напропалую, ищя первый кусок памяти без пометки "живой". Этот алгоритм будет эффективен, если значительная (бОльшая) часть кучи после сборки окажется пустой — но ровно же в этом случае и копирующий сборщик становится эффективным!

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