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

Причиной написания данной статьи стала регрессия производительности в реализации инкрементального GC в CPython 3.13-rc. По мере объяснения в Twitter я понял, что нужна более простая статья на тему дизайна GC, которая упростит понимание деталей управления памятью в приложениях Python.

Подсчет ссылок и роль GC в CPython

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

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

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

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

Подробнее про детали реализации вы можете прочитать в моей статье CPython’s reference counting internals

Аллокатор объектов CPython’s

Языкам с управлением памятью необходимо дешево создавать новые объекты. Вызов malloc и free для создания и удаления объектов может быстро стать неэффективным. Помимо оверхеда, вызванного увеличением количества системных вызовов это также может приводить к фрагментации памяти, понижая производительность. По этой причине большая часть рантаймов реализует пулы объектов и собственные аллокаторы объектов.

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

Однако, данный аллокатор используется только для объектов, размер которых меньше 512 байт. Для более крупных объектов CPython полагается на API системного malloc.

Вернемся к обсуждению GC в CPython.

Условия вызова GC

Языки, которые для управления памятью полагаются исключительно на GC, вызывают его с определенным фиксированным интервалом. Однако в CPython большая часть объектов очищается сразу после того, как они перестают быть нужными благодаря подсчету ссылок. Из-за этого нет необходимости постоянного запуска GC.

Так как же тогда рантайм CPython решает, когда вызвать GC? Это происходит на основе подсчета существующих объектов в молодом поколении кучи.

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

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

Когда число живых объектов достигает заданного порога (2000 по умолчанию в Python 3.12, может быть настроено), рантайм задает флаг в структуре данных потока текущего потока. Флаг устанавливается в поле eval_breaker вместе с другими флагами событий, например сигналов.

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

Введение в GC

Предположим, вы создаете достаточно долгоживущих объектов для достижения порога и задается флаг сборки мусора. Но это не сразу приводит к вызову GC. Виртуальная машина (VM) CPython проверяет данный флаг в определенные моменты выполнения байткода и вызывает GC если флаг установлен.

Проверка флага происходит в конце выполнения определенных инструкций байткода. Эти инструкции, по сути, различные вариации вызовов функций и инструкции обратных переходов (например, в конце итерации цикла).

Это значит, что если в конце итерации цикла или вызова функции была пересечена граница GC и задан флаг, VM перестанет выполнять дальнейшие инструкции байткода программы и переключится на выполнение GC для очистки памяти.

Если вы хотите узнать про работу и внутренности CPython подробнее, прочитайте статью про дизайн и реализацию VM CPython.

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

Алгоритм определения циклов требует от GC анализа входящих ссылок каждого объекта. Несмотря на то, что граф объектов обычно не особо плотный, это все равно требует большого количества переходов по указателям, что может быть затратно, если эти объекты не в кэше CPU. Для понимания алгоритма ознакомьтесь со статьей CPython GC implementation.

В конце цикла GC популяция молодого поколения должна достигнуть 0 (или близко к нему). Некоторые объекты, которые могли быть созданы в процессе работы цикла или функции автоматически убираются счетчиком ссылок. Недостижимые объекты с циклическими ссылками очищаются GC, а выжившие повышаются до старого поколения.

Сканирование старых поколений и полное сканирование кучи

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

Стандартный порог для двух старых поколений в CPython равен 10. После запуска GC для молодого поколения 10 раз, GC запустит сканирование первого старого поколения вместе с новым поколением в следующем цикле.

Аналогично, когда первое старое поколение было просканировано 10 раз, наиболее старое поколение становится доступно для сканирования. При сканировании наиболее старого поколения автоматически запускаются сканы всех более молодых поколений и называется полным сканированием кучи, поскольку по сути сканирует все объекты на куче и может быть достаточно затратной операцией.

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

Из-за этого в CPython помимо порога есть дополнительное условие для полного сканирования кучи. Оно отслеживает общее число объектов, затронутых прошлым полным сканированием (называется long_lived_total), а также отслеживает общее число новых объектов, ожидающих полного сканирования кучи (называется long_lived_pending). Только когда соотношение long_lived_pending к long_lived_total превысит 25%, CPython запустит полное сканирование кучи.

Инкрементальный GC

Инкрементальная сборка мусора - оптимизация, недавно добавленная в CPython после релиза 3.12 с целью снижения влияния полного сканирования кучи на производительность.

Как я уже упоминал ранее в начале статьи, добавление инкрементального GC было отменено (и может вернуться в релизе 3.14), но сама идея имеет смысл и я потрачу немного времени, чтобы объяснить ее.

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

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

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

Сама идея показала прирост производительности в бенчмарках, но, похоже, наткнулась на edge-кейс в Sphinx, приводя к значительно худшей производительности по сравнению с прошлым алгоритмом GC.

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

Понимание затрат на полное сканирование кучи на примере худшего случая

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

Предположения

• Порог GC: В CPython 3.12 порог для запуска GC в молодом поколении (поколение 0) составляет 2000 объектов. Порог для двух старых поколений составляет 10, что означает, что первое старое поколение будет запускаться после 10 сканирований молодого поколения, а второе старое поколение - после 10 сканирований первого старого.

• Трафик: Предположим, что наше приложение - веб-сервис, обрабатывающий по 100 запросов в секунду.

• Создание объектов: Каждый запрос создает 20 новых долгоживущих объектов, переживающих цикл сборки мусора.

• Размер объектов: Размер каждого объекта составляет примерно 24 байта. Обычно объекты в Python значительно больше, но оставим все как есть для упрощения.

Поколенческий GC в действии

• Запускается поколение 0 (молодое поколение):

  • При 100 запросах в секунду, каждый из которых создает 20 новых долгоживущих объектов, мы генерируем (100 x 20 = 2000) объектов в секунду.

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

• Повышение и сборка:

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

Анализ производительности

• Масштабируемость:

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

  • Обход связанного списка требует как минимум двух разыменований на ноду - одно на разыменование указателя текущей ноды, одно - на получение адреса следующей.

  • 2000 объектов размером 24 байта каждый займут 48000 байт, что умещается в L1 кэш. Однократный поиск по L1 кэшу требует 4 цикла процессора, так что два поиска для обхода потребуют 8 циклов.

  • Поскольку мы сканируем 2000 объектов, полное сканирование займет 16000 циклов.

  • При частоте в 1 Ггц это примерно 16 микросекунд на цикл GC.

• Последующие сборки:

  • Через 10 сканирований молодого поколения (т.е. всего через 10 секунд) будет достигнут порог сканирования первого старого поколения.

  • К этому момент в двух поколениях в сумме будет 22000 объектов.

  • 22000 объектов занимали бы 528000 байт, распределенных между L1 и L2 кэшем. Для упрощения предположим, что каждое разыменование все еще занимает 4 цикла.

  • Затраты на это сканирование: (22000 объектов x 2 разыменовывания x 4 цикла на разыменовывание) = 176000 циклов процессора, примерно 0.176 мс

• Дальнейшее увеличение затрат:

  • Через 10 сканирований первого старого поколения (т.е. через 100 секунд) будет достигнут порог второго старого поколения.

  • В трех поколениях в сумме будет 220000 объектов для сканирования.

  • Использование памяти: (220,000 x 24) bytes = 5.2 MB. Данный размер превышает типичную вместимость L1/L2 кэша.

  • Если мы предположим, что 20000 объектов умещаются в L1/L2 кэш, то проход по ним займет 160000 циклов.

  • Оставшиеся 200,000 объектов были бы в L3-кэше. Предполагая 30 циклов задержки для L3 кэша, обход 200000 объектов * 2 разыменования * 30 циклов на разыменование = 12000000 циклов.

  • Общая сумма использованных циклов процессора составит 160,000 + 12,000,000 = 12,160,000 циклов.

  • При частоте в 1 Ггц это составит примерно 12 мс, потраченных в сборщике мусора на полное сканирование кучи.

Влияние на производительность

Если веб-сервис обычно обрабатывает запрос за 12 мс, на момент полного сканирования кучи задержка может увеличиваться до 24 мс. Это на 100% более высокая задержка во время полного сканирования, что довольно существенно.

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

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

Применение внутренних механизмов GC для оптимизации производительности

Теперь, когда мы знаем, как CPython управляет памятью, как бы нам использовать это для повышения производительности приложений? Давайте завершим погружение в детали работы GC в CPython, рассмотрев некоторые способы снижения затрат на GC.

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

Учитывайте размер объекта при выделении памяти

CPython использует эффективный аллокатор объектов для объектов размером меньше 512 байт. Более крупные объекты создаются с использованием системной реализации malloc, что может быть более затратно.

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

Но у подобного подхода есть и недостатки:

• Это может увеличить общее использование памяти из-за лишних заголовков объектов и указателей.

• Это может привести к усложнению кода и возможному замедлению паттернов доступа, если нужные данные разбиты по нескольким объектам.

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

Всегда стоит использовать профилирование и замерять производительность перед тем, как внедрять подобные оптимизации. Данный подход стоит рассматривать только в случае, когда проблемы с производительностью соотносятся с частыми вызовами malloc/free или фрагментацией памяти.

В приложениях, для которых действительно важно использование большого количества крупных объектов стоит задуматься об использовании более эффективной реализации аллокатора, к примеру jemalloc, mimalloc или tcmalloc.

Используйте эффективные с точки зрения памяти структуры данных

• Используйте слот-классы. Для классов с большим количеством экземпляров использование __slots__ может снизить использование памяти и ускорить обращение к атрибутам. Это также предотвращает создание __dict__ на каждый экземпляр, который необходимо учитывать сборщику мусора.

• Задумайтесь об использовании модуля массива вместо списков, если вы знаете, что все данные будут численными. Модуль массива гораздо более эффективно упаковывает данные и снижает нагрузку на память.

Оптимизируйте время жизни объектов

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

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

• Раннее освобождение ресурсов - еще одна оптимизация. К примеру, используйте управление контекстом, где это возможно, чтобы достигать наиболее раннего освобождения объектов и ресурсов.

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

• Используйте слабые ссылки. При создании слабой ссылки на объект его счетчик ссылок не повышается. Это означает, что если он не используется где-либо еще, он будет освобожден, даже если на него создана слабая ссылка.

Минимизируйте количество циклических ссылок

На данном этапе вы должны уже знать, что основная причина существования сборщика мусора в CPython - очистка памяти, связанной с циклическими ссылками; остальные объекты автоматически очищаются за счет подсчета ссылок.

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

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

Настройте пороговые значения GC

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

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

Профилируйте и мониторьте

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

Используйте инструменты профилирования памяти, такие как tracemalloc, scalene, а также другие анализаторы производительности - perf, cProfile, py-spy. Чтобы узнать больше, ознакомьтесь с видео по профилировщикам python.

Заключение

Хотя люди выбирают Python за синтаксис и продуктивность, а не производительность, знание внутреннего устройства языка - единственный способ преодолеть проблемы с производительностью при их возникновении. В этой статье мы рассмотрели, как и при каких условиях запускается сборщик мусора CPython и какой оверхед это привносит. Пользуясь полученными знаниями, мы придумали ряд техник оптимизации использования памяти приложением, чтобы сборщик запускался реже.

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