Привет, сегодня будем разбираться в том, как Python обращается с памятью, ведет подсчет прямых∕циклических ссылок и вот это вот все. Подготовил для этого перевод статьи с devguide.python. Завариваем себе чайку с пироженкой, берем любимый плед и начинаем.
Главный алгоритм, который используется сборщиком мусора в CPython - это подсчет ссылок. Основная идея - посчитать сколько мест нашей программы ссылается на какой-то объект. Это может быть какой-то другой объект, глобальная или локальная C переменная. Когда счетчик ссылок становится равен 0, то объект удаляется (высвобождается определенная под него память). Если он содержал ссылки на другие объекты, то их счетчики уменьшаются. Это может вызвать цепную реакцию для следующих объектов. Можно проверить количество ссылок на объект с помощью функции sys.getrefcount (учтите, что значение всегда будет на 1 больше, т.к. когда функция проверяет значение, она сама ссылается на объект):
Главная проблема в том, что простой подсчет ссылок не может обработать циклические ссылки. Например, посмотрим на этот код:
В этом примере, контейнер содержит ссылку на себя, так что даже если мы удалим нашу ссылку (переменную "container") счетчик ссылок никогда не опустится до 0, потому что он все еще содержит ссылку на себя же. Если быть более точным, с этим не справится обычный подсчет ссылок. Поэтому необходимы дополнительные инструменты, чтобы разбить циклы между объектами как только они станут недосягаемы. Это циклический сборщик мусора, чаще всего называемый просто сборщиком мусора (Garbage collector или GC).
Распределение памяти и структура объекта
Обычная структура С, поддерживающая стандартные Python объекты выглядит так:
object -----> +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ \
| ob_refcnt | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | PyObject_HEAD
| *ob_type | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ /
| ... |
Чтобы поддерживать сборщик мусора, структура памяти должна быть немного изменена. Перед стандартной информацией помещаются дополнительные данные.
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ \
| *_gc_next | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | PyGC_Head
| *_gc_prev | |
object -----> +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ /
| ob_refcnt | \
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | PyObject_HEAD
| *ob_type | |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ /
| ... |
При таком подходе, с объектом можно обращаться как со стандартным Python объектом большую часть времени и когда понадобится информация для сборщика мусора, к ней будет легко обратиться ((PyGC_Head *)(the_object)-1).
Как будет объяснено дальше в главе "Оптимизация: переиспользование полей для сохранения памяти", эти 2 дополнительных поля обычно используются в двусвязных списках объектов, отслеживаемых сборщиком мусора ( внутри эти списки реализованы как GC поколения, чуть больше о них будет рассказано в части "Оптимизация: поколения"). Эти поля так же используются для других целей, что позволяет оптимизировать расходуемую память.
Двусвязные списки используются т.к. они эффективно поддерживают наиболее частые операции. В большинстве случаев, коллекции объектов, отслеживаемых сборщиком мусора разбиты на непересекающиеся множества, каждое в своем двусвязном списке. В коллекциях объекты разбиты на "поколения", отражающие количество пережитых попыток сбора. Во время сбора объекты разделяются на досягаемые и недосягаемые. Двусвязные списки поддерживают перемещение объектов из одной партиции в другую, добавление новых объектов, полное удаление объектов (объекты отслеживаемые сборщиком мусора часто утилизируются системой подсчета ссылок, даже без его полноценного запуска!), слияние партиций и все это с небольшим количеством операций по изменению указателей. Если подходить разумно, они так же поддерживают итерацию по партициям, в которые были добавлены объекты или из которой они были удалены. Это часто требуется при работе сборщика мусора.
Спецификации API, управляющие аллокацией, деаллокацией, инициализацией, отслеживанием объектов с поддержкой сборщика можно прочитать в Официальной документации API сборщика мусора.
Отдельно от своей структуры, для поддержки сборщика мусора тип объекта должен включать флаг Py_TPFLAGS_HAVE_GC в слоте tp_flags и обеспечивать реализацию обработчика tp_traverse. Если тип объекта не иммутабелен (неизменяем) или нет доказательств, что объект не может сформировать циклические ссылки только из объектов своего типа (как в примере, показанном в начале), необходимо так же реализовать tp_clear.
Определение циклических ссылок
Алгоритм, который CPython использует для определения циклических ссылок, реализован в модуле gc. Сборщик мусора фокусируется только на очистке контейнеров-объектов (т.е. объекты, которые могут содержать ссылки на один или более других объектов). Это могут быть массивы, словари, списки, пользовательские классы, расширения и т.д. Можно подумать, что циклические ссылки появляются нечасто, но на самом деле сложная структура внутренних ссылок заставляет интерпретатор создавать циклы практически везде. Наиболее частые примеры:
Исключения содержат информацию для отслеживания (traceback) который содержит список фреймов, которые содержат исключение.
Функции уровня модуля ссылаются на словарь модуля (в котором должны быть объявлены глобальные переменные), который в свою очередь содержит ссылки на модульные функции.
Экземпляры класса ссылаются на класс, который ссылается на свой модуль. Модуль содержит внутри большое количество информации и вполне может ссылаться на экземпляр класса.
Если вы использовали графы, то знаете, что ссылка узла на себя - достаточно частая ситуация.
Чтобы правильно отделять недосягаемые объекты, как только они стали недосягаемыми, нужно научиться их идентифицировать. Внутри функции, идентифицирующей циклы есть 2 двусвязных списка: один содержит все объекты, а второй " недосягаемые".
Чтобы понять, как алгоритм работает, давайте рассмотрим список, который содержит ссылку от переменной А и объект с циклической ссылкой:
Когда сборщик начинает работу, все приготовленные для сканирования объекты находятся в первом списке. Цель - отделить все недосягаемые объекты. Предполагается, что большая часть объектов все-таки досягаемая, а значит перемещая только недосягаемые объекты мы используем меньше операций на изменение указателей.
Каждый объект, который поддерживает сборщик мусора, содержит временное поле, предназначенное для подсчета ссылок (на рисунке gc_ref), которое создается в момент активации алгоритмов сборщика мусора. Это необходимо, чтобы алгоритм мог изменять количество ссылок и проводить свои вычисления не модифицируя основное поле подсчета ссылок (ref_count), используемое интерпретатором.
Сборщик мусора итерируется по всем контейнерам в первом списке и снижает значение поля gc_ref на 1 для всех контейнеров на который ссылается текущий. Для этого он использует слот tp_traverse в классе контейнера (реализованный с помощью C API или унаследованный от суперкласса), чтобы узнать на какой объект каждый контейнер ссылается. После того как все проверено, только объекты, у которых есть ссылки от внешних контейнеров остаются со значением gc_ref > 0.
Нужно отметить, что сам по себе факт gc_ref == 0 еще не означает, что объект недосягаем. Другой объект, доступный снаружи (gc_ref > 0) все еще может ссылаться на какой-то объект цепочки. Например ink_2 в примере имеет показатель gc_ref == 0, но на него все ещё ссылается link_1, на который в свою очередь есть ссылка другой переменной снаружи сканируемого списка. Чтобы выделить действительно недосягаемые объекты сборщик мусора еще раз сканирует контейнеры, используя слот tp_traverse; В этот раз используется другая функция, которая помечает объекты с gc_ref == 0 как "ориентировочно недосягаемые" и перемещает их в отдельный список. Этот момент вы можете увидеть на следующем изображении: link_3, link_4 уже перемещены, тогда как link_1, link_2 еще в первом.
Затем сборщик сканирует link_1, замечает его показатель gc_ref == 1 и отмечает досягаемым (перемещать этот объект никуда не нужно, он и так находится в своем списке).
Когда сборщик находит объект с gc > 0, он пройдет по всем объектам, на которые ссылается этот объект, перенесет их в список досягаемых (где они и были изначально) и устанавливает gc_ref на 1. Поэтому в списке остается link_2, по этой же причине в финале link_3 переносится назад. Чтобы не проводить повторных вычислений, сборщик мусора отмечает все объекты, которые посетил (для этого убирается флаг PREV_MASK_COLLECTING), так что если объект уже был обработан, сборщик не будет заново запускать алгоритмы.
Нужно отметить, что если объект был помечен как "возможно недосягаемый" и затем возвращен в лист досягаемых, сборщику нужно будет еще раз посетить и обработать. Этот процесс похож на поиск в ширину в графах. После того как все объекты просканированы, сборщик знает какие из "возможно недосягаемых" на самом деле недосягаемы и могут быть переработаны.
Важно, что для этих вычислений не требуется рекурсии как и дополнительной памяти, дополнительных указателей или построения длинных цепей. Кроме О(1) хранилища для внутренних нужд С, все объекты уже содержат необходимые для расчетов данные.
Почему выгоднее перемещать недосягаемые объекты
Звучит логичным перемещать именно недосягаемые объекты, если исходить из предположения, что большая их часть обычно досягаема. Но если вы попробуете разобраться в этом глубже, то поймете, что причина не настолько очевидна.
Предположим, мы создали объекты А, В, С (именно в таком порядке). Они появились в новом "поколении" в том же порядке. Пусть В указывает на А, С на В и С достижим снаружи. В таком случае счетчики ссылок на первом шаге алгоритма будут 0,0 и 1, т.к. снаружи есть ссылки только на С.
На следующем шаге алгоритм переместит А и В в лист недосягаемых объектов. Затем он дойдет до С и увидит ссылку на В, переместит его назад, просканирует В и переместит назад объект А.
Почему бы тогда не перемещать досягаемые объекты? Ведь вместо того, чтобы просто остаться на месте, А и В были перемещены дважды. В чем выгода? Прямой алгоритм перемещения досягаемых объектов переместит А, В, С лишь один раз. Секрет кроется в порядке, в котором объекты остаются после перемещения. С, В, А - он противоположен изначальному. На всех последующих сканированиях ни один из них не будет перемещен. Т.к. большая часть объектов не находится в циклах это может сохранить неограниченное количество операций при неограниченном количестве элементов в коллекциях ценой повышения стоимости первичного сканирования.
Разрушение объектов
После того, как сборщик определяется со списком неиспользуемых объектов, начинается очень деликатный процесс их разборки и уничтожения. Грубо, этот процесс можно разбить на следующие шаги:
- Обработать и вычистить слабые ссылки (если таковые имеются). Если объект должен быть уничтожен, необходимо обработать его ссылки с обратным вызовом. Это очень важный процесс, любая ошибка в котором может вызвать "воскрешение" объекта уже в неконсистентном состоянии или получение какой-то неверной информации из обратного вызова. Если слабые ссылки принадлежат тому же множеству, которому принадлежит удаляемый объект, то они могут быть вычищены без выполнения вызова. Иначе они были бы вызваны позже со слотом tp_clear порождая хаос. Игнорирование вызова в этом случае оправданно, т.к. и обьект и ссылка должны быть удалены. Можно сказать, что ссылка будет удалена первой.
- Если у объекта есть деструкторы (tp_del слот), их необходимо переместить в список gc.garbage.
- Вызвать финализаторы (tp_finalize слот) и отметить объект финализированным, чтобы избежать повторного их вызова, в случае когда финализатор должен уничтожить объект первым.
- Разобраться с воскресшими объектами. Если какой-то объект был воскрешен, сборщик создаст новое подмножество все еще недосягаемых объектов и продолжит работу с ними.
- Вызвать слот tp_clear для каждого объекта чтобы разрушить все внутренние ссылки и снизить счетчик до 0. Это уничтожит все неиспользуемые объекты.
Оптимизация: поколения
Чтобы сократить время, которое занимает обработка каждой коллекции с мусором, сборщик использует один из популярных способов оптимизации - поколения. Главная идея кроется за предположением, что большая часть объектов имеет очень короткий цикл жизни и может быть собрана через небольшое время после их создания. Это доказано большим количеством Python программ, в которых временные объекты создаются и уничтожаются очень быстро. Чем старше объект, тем меньше шансов что на него перестанут ссылаться.
Чтобы получить выгоду из этих знаний, все объекты-контейнеры разделяются на 3 поколения. Каждый новый объект начинает в первом поколении (поколение 0). Алгоритмы сборки предназначены для работы с объектами только одного поколения. Если объект переживает сборку, он перемещается в следующее (поколение 1), которое проверяется менее часто. То же самое происходит с теми, кто переживет сборку в поколении 1. Они будут перемещены в поколение 2, где будут проверяться реже всего.
Проверка поколения начинается, когда количество объектов в них достигнет определенного порога. Он индивидуален для каждого поколения и становится ниже, чем старше поколение. Можно получить пороговые значения с помощью функции gc.get_treshold:
Можно изучить содержимое поколений с помощью функции gc.get_objects(generation=NUM) или вручную вызвать сборку мусора gc.collect(generation=NUM).
Обследование долгожителей
В дополнение к запуску по пороговым значениям, сборщик начинает собирать мусор со старшего поколения если отношение количества долгоживущих объектов ∕всем объектам превышает 25%. Причина в том, что стоимость проверки коллекции пропорциональна количеству долгоживущих объектов, чье число практически не ограничено. Было доказано, что создание полных коллекций какого-то <константного числа> объектов начинает очень сильно проседать в производительности из-за нагрузки связанной с созданием и хранением множества объектов-долгожителей. (например постройка большого списка объектов отслеживаемых сборщиком мусора показала квадратичную сложность а не линейную, как ожидалось). Использование порога проверок показывает амортизированную линейную сложность при конечном количестве объектов. (Можно описать эффект так: "каждая следующая полная сборка мусора становится все более и более сложной из-за возрастающего количества объектов, но мы делаем их все меньше и меньше.")
Оптимизация: переиспользование полей для сохранения памяти
Для экономии памяти, связные списки с указателями в каждом объекте со сборщиком мусора переиспользуются для нескольких целей. Это достаточно распространенный прием оптимизации, называемый "жирные указатели": указатели, которые переносят дополнительные данные. Это стало возможным, благодаря тому, что большинство архитектур выравнивают размер указателей, содержащих слова, что оставляет место под дополнительную информацию. Так в 32-битной архитектуре (для адреса и слов), текст занимает 32 бита = 4 байта. Словесные адреса всегда кратны 4 и заканчиваются на 00, что оставляет эти 2 бита под дополнительную информацию. В 64-битной архитектуре, адреса кратны 8 байтам, заканчиваются на 000 и оставляют доступными 3 бита.
Сборщик мусора в CPython использует эти биты для размещения дополнительной информации, как было сказано выше в секции "распределение памяти и структура объекта".
Предупреждение.
Т.к. в них присутствует дополнительная информация, такие указатели не могут быть просто разыменованы. Чтобы получить настоящий адрес в памяти, необходимо извлечь дополнительную информацию. Особенно это важно при работе с функциями, которые напрямую манипулируют связными списками. Они предполагают, что указатели находятся в согласованном состоянии.
- Поле _gc_prev` обычно используется как указатель "предыдущего элемента" для управления в двусвязных списках. Но его младшие 2 бита используются для хранения флагов PREV_MASK_COLLECTING и _PYGC_MASK_FINALIZED. Между сборками используется только _PYGC_MASK_FINALIZED, который отвечает был ли объект уже финализирован. Во время сборки _gc_prev временно используется для хранения копии значения счетчика ссылок (gc_refs), вдобавок к уже указанным двум флагам. На время, пока _gc_prev не будет восстановлено, список с объектами для сборщика мусора становится однонаправленным.
- Поле _gc_next используется как указатель "следующего элемента" при управлении двусвязным списком. Но во время сборки его младшие биты хранят флаг NEXT_MASK_UNREACHABLE, который показывает был ли объект помечен как возможно недосягаемый во время работы алгоритма. Это недостаток вызванный использованием двусвязных списков. Хотя большинство необходимых операций выполняется за константное время, нет эффективного пути определить в какой группе объектов мы находимся в текущий момент, поэтому приходится использовать некоторые хитрости (вроде флага NEXT_MASK_UNREACHABLE)
Оптимизация отсроченное отслеживание контейнеров
Некоторые типы объектов не могут попасть в циклические ссылки и поэтому нет необходимости отслеживать их сборщиком мусора. Это позволяет уменьшить ресурсы, необходимые для его работы. Однако определение стоит ли отслеживать какой-то объект тоже требует ресурсов и необходимо знать выигрываем ли мы что-то экономя на сборке. Есть 2 возможных стратегии, когда можно перестать отслеживать контейнер:
- Когда он создан.
- Когда он исследован сборщиком мусора.
Как правило, экземпляры не атомарных типов (контейнеры, определенные пользователем объекты и т.д.) отслеживаются, а экземпляры атомарных объектов нет. Но есть несколько специальных приемов зависящих от типов данных, которые помогут подавить∕отключить флаг сборщика мусора для простых экземпляров. Некоторые примеры нативных типов, которые может быть выгодно отслеживать в отложенном режиме:
- Кортежи, содержащие только иммутабельные объекты (целые числа, другие кортежи с иммутабельными объектами) не нуждаются в отслеживании. Интерпретатор создает большое количество кортежей, большая часть из которых не доживает до сборки мусора. Все кортежи кроме пустых помечаются как отслеживаемые в момент создания. В ближайшую сборку сборщик мусора обследует кортеж и определяет нужно ли отслеживать его содержимое. Если все объекты неотслеживаемые, то кортеж так же больше не будет отслеживаться. Полная проверка кортежа может занять больше одного цикла.
- Так же нет смысла отслеживать словари, которые содержат только иммутабельные объекты. Словари перестают быть отслеживаемыми сразу, когда создаются. Если какой-то отслеживаемый объект помещается в словарь, то и словарь становится отслеживаемым. Во время полной сборки мусора (проходящей по всем поколениям), сборщик перестает отслеживать все словари, содержимое которых больше не отслеживается.
Можно использовать функцию is_tracked(obj) из модуля сборщика мусора, которая покажет статус отслеживания объекта. Последующие сборки могут менять статус отслеживания.
_________________________________________________________________________________________
Чтож, мы это осилили, а значит стали чуточку умнее и осведомленнее во внутренней Python-кухне. Всего доброго)