- Аннотация
- Мотивация
- Обоснование Текущий сборщик Дизайн сборщика
- Текущий сборщик
- Дизайн сборщика
- Спецификация Поколения Алгоритм Устаревший сборщик Конфигурация Производительность Пиковое потребление памяти Явные вызовы сборки Вызов gc.collect() Выбор устаревшего поколенческого сборщика
- Поколения
- Алгоритм
- Устаревший сборщик
- Конфигурация
- Производительность
- Пиковое потребление памяти
- Явные вызовы сборки Вызов gc.collect()
- Вызов gc.collect()
- Выбор устаревшего поколенческого сборщика
- Доказательство корректности Все недостижимые циклические ссылки в старом поколении будут собраны Все недостижимые циклические ссылки будут собраны
- Доказательство Все недостижимые циклические ссылки в старом поколении будут собраны Все недостижимые циклические ссылки будут собраны
- Все недостижимые циклические ссылки в старом поколении будут собраны
- Все недостижимые циклические ссылки будут собраны
- Обратная совместимость
- Дальнейшая работа Дальнейшее сокращение времени пауз Портирование на сборку без глобальной блокировки интерпретатора (free-threaded)
- Дальнейшее сокращение времени пауз
- Портирование на сборку без глобальной блокировки интерпретатора (free-threaded)
- Эталонная реализация
- Благодарности
Аннотация
Этот PEP предлагает добавить новый циклический сборщик мусора в CPython. Новый сборщик будет одновременно поколенческим и инкрементальным. Сборки будут чередоваться: сборка молодого поколения, затем (инкрементальная) сборка старого поколения, затем сборка молодого поколения и так далее.
Каждая сборка будет обрабатывать только часть кучи, фокусируясь на областях, где мусор наиболее вероятно сконцентрирован.
Цель нового сборщика мусора — сократить время пауз 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 игнорируется.
Общий размер молодых поколений (питомник + стареющие области) составляет threshold0 * (threshold1 + 2) КБ.
* Поскольку сборки молодого и старого поколений чередуются, области старения собираются парами полупространств. По этой причине количество полупространств всегда округляется до четного числа.
Производительность
Производительность повышена по сравнению с текущим сборщиком мусора. Прирост производительности достигается за счет выполнения меньшего объема работы в молодых поколениях (одна сборка на объект, а не две) и меньшего объема работы в старом поколении из-за более низкой доли выживших объектов из молодых поколений.
Пиковое потребление памяти
В целом пиковое потребление памяти должно остаться примерно на прежнем уровне, но оно будет зависеть от рабочей нагрузки.
Для небольших и кратковременных приложений потребление памяти, вероятно, увеличится из-за большего размера молодых поколений, но это дополнительное пространство по умолчанию ограничено 24 МБ. В большинстве случаев увеличение использования памяти будет намного меньше 24 МБ, так как этот лимит включает как живые, так и собранные объекты. Недостижимые циклы обычно составляют лишь небольшую часть этого пространства.
Для более крупных и долго работающих приложений пиковое использование памяти может снизиться, так как инкрементальный сборщик препятствует росту старого поколения до таких размеров, как в текущем поколенческом сборщике, однако разница, скорее всего, будет небольшой.
Явные сборки мусора
Обычно сборщик мусора запускается виртуальной машиной через определенные интервалы времени. Тем не менее, сборку мусора можно инициировать явно, вызвав gc.collect(). Вызов gc.collect() с явным аргументом устарел, так как он мешает плавной работе сборщика мусора. Вызов gc.collect() без аргументов продолжает поддерживаться.
Вызов gc.collect()
Вызов gc.collect() эквивалентен вызову gc.collect(2).
Выбор устаревшего поколенческого сборщика
Алгоритм сборщика мусора можно выбрать при запуске с помощью опции -X gc. Возможные варианты: «incremental» для инкрементального сборщика мусора или «legacy» для устаревшего поколенческого сборщика мусора. По умолчанию используется «incremental».
Корректность
Сборщик циклитического мусора должен иметь возможность собирать все недостижимые циклы.
Доказательство
Все недостижимые циклы в старом поколении будут собраны
- Будем считать заданным, что сборка области купы приведет к сборке всех циклов, находящихся целиком внутри этой области. Если бы это было не так, текущий сборщик мусора был бы неисправен.
- Если объект является частью цикла и входит в транзитивное замыкание объектов, достижимых из любого объекта, то весь этот цикл должен находиться внутри транзитивного замыкания: это следует из того факта, что любой объект в цикле транзитивно достижим из любого другого объекта в этом цикле, и что все транзитивно достижимые объекты включены в транзитивное замыкание.
- Это следует из того факта, что любой объект в цикле транзитивно достижим из любого другого объекта в этом цикле, и что все транзитивно достижимые объекты включены в транзитивное замыкание.
Отсюда мы можем заключить, что если объект является частью цикла в пространстве ожидания в тот момент, когда пространство ожидания представляет собой все старое поколение, то этот цикл не может быть перемещен в посещенное пространство. Чтобы быть перемещенным в посещенное пространство, его нужно было бы переместить как часть приращения, но приращения являются транзитивными замыканиями и, следовательно, должны содержать весь цикл целиком, а все циклы, находящиеся целиком внутри какой-либо области, собираются. Следовательно, когда пространство ожидания становится пустым, цикл не может находиться ни в посещенном пространстве, ни в пространстве ожидания, поэтому он должен был быть собран.
Все недостижимые циклы будут собраны
Все объекты в молодом поколении будут продвинуты в старое поколение, если они не собраны с помощью подсчета ссылок. Следовательно, для любого цикла, охватывающего как молодое, так и старое поколения, молодые объекты будут продвинуты в старое поколение, после чего цикл окажется целиком внутри старого поколения и к нему применимо приведенное выше доказательство.
Обратная совместимость
Даже если используется устаревший сборщик, произойдут некоторые небольшие изменения в поведении, поскольку триггер сборки мусора меняется с чистого числа выделенных объектов на общий объем памяти, выделенной с момента последней сборки.
Для большинства приложений не должно быть существенных изменений, однако могут наблюдаться следующие различия:
- Меньше сборок мусора во время запуска по мере роста кучи.
- Больше сборок мусора поколения 0 и 1 во время работы долгоживущих программ в установившемся режиме.
- В программах, создающих множество крупных объектов, сборка мусора может происходить чаще.
Общее время, затрачиваемое на сборку мусора, должно остаться практически неизменным, так как более частые сборки обычно означают более короткие паузы для каждой сборки.
Дальнейшие работы
Дальнейшее сокращение времени пауз
Хотя эталонная реализация на 1–2% быстрее версии main (с поколенческим сборщиком мусора), в ней все еще могут возникать длительные паузы на больших графах объектов. Во многих тестах в качестве графа объектов выступает одно большое дерево, и это может приводить к долгим паузам, поскольку приращение, начинающееся с корня дерева, будет содержать почти всю кучу.
Эту ситуацию можно улучшить несколькими способами:
- Сортировка приращений по мере их создания или отправки в старое поколение, чтобы объекты, наиболее удаленные от корня, выбирались первыми при следующей сборке.
- Обход стека перед формированием приращения для пропуска достижимых объектов. Это усложнит алгоритм, но в некоторых случаях может сэкономить значительный объем работы.
Перенос на сборку со свободной многопоточностью
Перенос инкрементального сборщика мусора на сборку со свободной многопоточностью потребует нескольких изменений:
- Каждый поток получит собственный питомник.
- Питомники будут значительно меньше и по мере заполнения будут объединяться в области старения.
- Обход старого пространства потребует сканирования всей купы, независимо от того, в каком пространстве находится объект. Объекты, не находящиеся в пространстве ожидания, будут пропускаться, но это добавляет определенные накладные расходы.
- Двусвязные списки, используемые для управления пространствами, нужно будет заменить внешними массивами для молодого поколения и приращений. Сборщику мусора со свободной многопоточностью уже требуется это делать для разделения мусора и выживших объектов.
Эталонная реализация
Благодарности
Спасибо Сергею Мирьянову за проведение анализа производительности.
Этот документ передан в общественное достояние или под лицензию CC0-1.0-Universal, в зависимости от того, какая из них является более мягкой.