PEP 848: Поколенческая инкрементальная сборка мусора

• Аннотация
• Мотивация
• Обоснование Текущий сборщик Дизайн сборщика
• Текущий сборщик
• Дизайн сборщика
• Спецификация Поколения Алгоритм Устаревший сборщик Конфигурация Производительность Пиковое потребление памяти Явные вызовы сборки Вызов gc.collect() Выбор устаревшего поколенческого сборщика
• Поколения
• Алгоритм
• Устаревший сборщик
• Конфигурация
• Производительность
• Пиковое потребление памяти
• Явные вызовы сборки Вызов gc.collect()
• Вызов gc.collect()
• Выбор устаревшего поколенческого сборщика
• Доказательство корректности Все недостижимые циклы в старом поколении будут собраны Все недостижимые циклы будут собраны
• Доказательство Все недостижимые циклы в старом поколении будут собраны Все недостижимые циклы будут собраны
• Все недостижимые циклы в старом поколении будут собраны
• Все недостижимые циклы будут собраны
• Обратная совместимость
• Дальнейшая работа Дальнейшее сокращение времени пауз Портирование для сборки с поддержкой свободных потоков
• Дальнейшее сокращение времени пауз
• Портирование для сборки с поддержкой свободных потоков
• Эталонная реализация
• Благодарности
• Авторские права

Аннотация

Данный PEP предлагает добавить в CPython новый сборщик циклического мусора. Новый сборщик будет одновременно поколенческим и инкрементальным. Сборки будут чередоваться: сборка молодых объектов, затем (инкрементальная) сборка старых объектов, затем снова сборка молодых, и так далее.

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

Цель нового сборщика мусора — сократить время пауз GC и уменьшить общее время, затрачиваемое на работу GC:

• Время пауз может быть значительно сокращено в программах с большими объемами кучи, в некоторых случаях до 100 раз, хотя для некоторых программ время пауз может вовсе не уменьшиться.
• Общая производительность улучшается на 3-5% в наборе тестов pyperformance.
• Пиковое потребление памяти должно снизиться для больших объемов кучи, но может увеличиться для небольших программ с коротким временем жизни.

Существующий поколенческий сборщик останется доступным в качестве опции. Подсчет ссылок остается неизменным и продолжит освобождать большинство объектов.

Мотивация

Сборщик циклов CPython в основном исследует «живые» объекты: объекты, не входящие в циклы, обычно немедленно освобождаются механизмом подсчета ссылок. Поэтому слишком частое или слишком раннее сканирование, скорее всего, будет пустой тратой ресурсов, так как циклы еще не успеют сформироваться и отделиться от остального графа объектов.

Текущий поколенческий сборщик сканирует каждый выживший объект дважды, прежде чем он будет перемещен в старое поколение. Это неэффективно, так как не существует циклов, которые были бы собраны первым сканированием, но не вторым.

Текущий сборщик также группирует молодые и старые объекты вместе, что означает, что некоторые объекты сканируются вскоре после их выделения, что вряд ли будет эффективно. Сканируя только более старые объекты, мы увеличиваем долю мертвых циклов, и GC будет работать эффективнее.

Текущий GC также выполняет сканирование всей кучи целиком, что приводит к длительным паузам при больших объемах кучи. Сканирование кучи небольшими инкрементами позволяет существенно сократить время пауз.

Обоснование

Текущий сборщик

Текущий сборщик имеет три поколения. Новые объекты создаются в «питомнике» (поколение 0). Когда количество чистых новых выделений (выделенные объекты минус освобожденные объекты) достигает порога (в настоящее время 2000), «питомник» собирается, и все выжившие объекты перемещаются в поколение старения (поколение 1). Когда должна произойти 10-я сборка «питомника», он объединяется с поколением старения, и вместо этого собирается поколение старения. Выжившие объекты затем перемещаются в старое поколение (поколение 2).

После 100 сборок поколение старения добавляется в старое поколение, и старое поколение (на этот момент — вся куча) потенциально собирается. Чтобы избежать квадратичного времени выполнения, самое старое поколение собирается только тогда, когда количество новых объектов, добавленных в него, превышает одну четверть его размера после последней полной сборки.

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

Дизайн сборщика

При реализации GC циклов необходимо учитывать три метрики:

• общее время выполнения программы
• максимальное время паузы GC
• пиковое потребление памяти

Повышение эффективности сборщика может улучшить 1. Инкрементальность может улучшить 2, а иногда и 3.

Мы можем сделать сборщик более эффективным, собирая только ту часть кучи, где концентрация мусора наиболее высока. Мы не можем знать, где находится мусор, но чем старше объекты, тем выше вероятность того, что они «умерли».

Непоколенческий инкрементальный сборщик, возвращенный в версии 3.14, был эффективнее текущего GC, но из-за того, что объекты оставались несобранными дольше, могло накапливаться много мусора, что приводило к чрезмерному пиковому потреблению памяти.

Повышение эффективности сборщика означает, что будет больше мусора и, следовательно, больше потребление памяти. Использование поколений помогает решить эту проблему.

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

Спецификация

В CPython будет добавлен новый поколенческий инкрементальный сборщик циклического мусора. Старый неинкрементальный сборщик будет сохранен как опция.

Куча будет разделена на три поколения, которые будут использоваться как инкрементальным, так и устаревшим сборщиком:

• Питомник (Nursery)
• Поколение старения (Aging)
• Старое поколение (Old)

Кроме того, поколения будут разделены на пространства. «Питомник» будет состоять из одного пространства. Поколение старения будет состоять из настраиваемого количества пространств (по умолчанию 5 в прототипе) для инкрементального сборщика и одного пространства для устаревшего сборщика. Старое поколение в инкрементальном сборщике разделено на два пространства: ожидающее (pending) и посещенное (visited). В устаревшем сборщике это одно пространство. Пространства старого поколения не имеют ограничения по размеру.

Поколения

Алгоритм

Новый GC чередует сборку наименее недавно просканированной части старого поколения и самого старого пространства в молодом поколении.

Когда «питомник» заполнен наполовину, собираются недостижимые циклы в инкрементах старого поколения. Каждый инкремент выбирается путем формирования транзитивного замыкания объектов, достижимых из объекта, который был просканирован в старом поколении раньше всех. Инкременты собираются до тех пор, пока не будет просканировано достаточно объектов, чтобы не отставать от скорости добавления объектов в старое поколение из сборок молодых объектов.

Когда «питомник» заполнен, собираются недостижимые циклы в самом старом пространстве старения (пространство 5 на схеме выше).

Устаревший сборщик

Устаревший сборщик продолжит работать так же, как и раньше:

Конфигурация

В настоящее время GC настраивается с помощью gc.set_threshold(). Это не изменится.

Общее назначение каждого порога остается в целом прежним для порогов 0 и 1, но их точное значение отличается. Порог 2 игнорируется.

Общий размер молодых поколений (nursery + aging) составляет threshold0 * (threshold1 + 2) КБ.

* Поскольку сборки молодых и старых поколений чередуются, пространства старения (aging spaces) собираются парами полупространств. По этой причине количество полупространств всегда округляется до четного числа.

Производительность

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

Пиковое потребление памяти

В целом, пиковое потребление памяти должно остаться примерно таким же, но оно будет зависеть от рабочей нагрузки.

Для небольших и кратковременных приложений потребление памяти, вероятно, увеличится из-за больших молодых поколений, но дополнительное пространство по умолчанию ограничено 24 МБ. В большинстве случаев увеличение использования памяти будет значительно меньше 24 МБ, так как этот лимит включает как живые, так и восстановленные объекты. Недостижимые циклы обычно составляют лишь малую часть этого пространства.

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

Явные сборки

Обычно сборка мусора (GC) запускается виртуальной машиной через определенные интервалы. Однако сборку мусора можно вызвать явно с помощью функции gc.collect(). Вызов gc.collect() с явным аргументом является устаревшим, так как это мешает плавной работе сборщика мусора. Вызов gc.collect() без аргумента по-прежнему поддерживается.

Вызов gc.collect()

Вызов gc.collect() эквивалентен вызову gc.collect(2).

Выбор устаревшего поколенческого сборщика

Алгоритм GC можно выбрать при запуске с помощью опции -X gc. Доступны варианты «incremental» для инкрементального GC или «legacy» для устаревшего поколенческого GC. По умолчанию используется «incremental».

Корректность

Циклический сборщик мусора должен быть способен собирать все недостижимые циклы.

Доказательство

Все недостижимые циклы в старом поколении будут собраны.

• Примем как данность, что сборка области кучи соберет все циклы, находящиеся целиком внутри этой области. Если бы это было не так, текущий GC был бы неисправен.
• Если объект является частью цикла и входит в транзитивное замыкание объектов, достижимых из любого объекта, то весь этот цикл должен находиться внутри транзитивного замыкания: это следует из того факта, что любой объект в цикле транзитивно достижим из любого другого объекта в этом цикле, и что все транзитивно достижимые объекты включены в транзитивное замыкание.
• Это следует из того факта, что любой объект в цикле транзитивно достижим из любого другого объекта в этом цикле, и что все транзитивно достижимые объекты включены в транзитивное замыкание.

Из этого мы можем сделать вывод, что если объект является частью цикла в ожидающем пространстве (pending space) в тот момент, когда ожидающее пространство является всем старым поколением, то этот цикл не может быть перемещен в посещенное пространство (visited space). Чтобы быть перемещенным в посещенное пространство, он должен был бы перемещаться как часть инкремента, но инкременты являются транзитивными замыканиями и, следовательно, должны содержать весь цикл, а все циклы, находящиеся целиком внутри области, собираются. Таким образом, когда ожидающее пространство становится пустым, цикл не может находиться ни в посещенном пространстве, ни в ожидающем пространстве, поэтому он должен был быть собран.

Все недостижимые циклы будут собраны

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

Обратная совместимость

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

Для большинства приложений существенных изменений быть не должно, но могут наблюдаться следующие различия:

• Меньше сборок GC во время запуска, по мере роста кучи.
• Больше сборок GC поколений 0 и 1 во время установившегося режима работы долгоживущих программ.
• Программы, создающие много крупных объектов, могут чаще вызывать сборку мусора.

Общее время, затрачиваемое на GC, должно остаться практически неизменным, так как более частые сборки обычно означают более короткие паузы на одну сборку.

Дальнейшая работа

Дальнейшее сокращение времени пауз

Хотя эталонная реализация на 1-2% быстрее основной (с поколенческим GC), она все еще может иметь длительные паузы на больших графах объектов. Многие тесты производительности имеют одно большое дерево в качестве графа объектов, и это может привести к длительным паузам, так как инкремент, начинающийся в корне дерева, будет содержать почти всю кучу.

Это можно улучшить несколькими способами:

• Сортировка инкрементов по мере их создания или отправки в старое поколение, чтобы объекты, наиболее удаленные от корня, выбирались первыми при следующей сборке.
• Обход стека перед формированием инкремента для пропуска достижимых объектов. Это усложнит алгоритм, но в некоторых случаях может сэкономить значительный объем работы.

Портирование на сборку с поддержкой свободных потоков (free-threaded build)

Портирование инкрементального GC на сборку с поддержкой свободных потоков потребует нескольких изменений:

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

Эталонная реализация

• Эталонная реализация
• Анализ производительности

Благодарности

Спасибо Сергею Мирьянову за проведение анализа производительности.

Авторские права

Этот документ передан в общественное достояние или доступен по лицензии CC0-1.0-Universal, в зависимости от того, какая из них является более разрешительной.