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 ухитряется собирать мусор параллельно с работой приложения. Там хватает своих тонкостей и накладных расходов. Но вот региональную часть Шенандо получает практически на сдачу.

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