предисловие

Недавно я читал "Алгоритмы и реализации сборки мусора", где рассказывалось о некоторых часто используемых алгоритмах сборки мусора (Garbage Collect), таких как: маркировка-очистка, подсчет ссылок, сборка по поколениям и так далее. Стратегия сборки мусора Python упоминается позже, поэтому я запишу ее здесь.

Четыре элемента для измерения производительности GC

пропускная способность

Пропускная способность — это выходная мощность ГХ в единицу времени. Формула расчета: объем кучи, обработанный сборщиком мусора / время, затраченное сборщиком мусора. Как правило, люди предпочитают алгоритмы GC с высокой пропускной способностью.

максимальное время паузы

Максимальное время для приостановки пользовательских потоков во время выполнения GC. Если время GC слишком велико, это повлияет на нормальное выполнение программы. Большая пропускная способность и более короткое максимальное время паузы часто несовместимы.

эффективность использования кучи

GC — это функция автоматического управления памятью, поэтому в идеале она не должна занимать слишком много места в куче, пока GC. На эффективность использования кучи влияют два фактора: размер заголовка и использование кучи. Чем больше доступная куча, тем быстрее будет работать сборщик мусора; и наоборот, чем эффективнее используется ограниченная куча, тем больше времени займет сборщик мусора.

место доступа

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

Python использует алгоритм GC с подсчетом ссылок.Преимущество алгоритма с подсчетом ссылок заключается в том, что он может сократить最大暂停时间, недостаток заключается в том, что он сталкивается с большими трудностями при поддержании увеличения и уменьшения счетчика (если вы забудете выполнить операцию уменьшения, объект не будет освобожден).

Где существует счетчик ссылок

Для данных Python, таких как List, Set, Tuple, Dict, Str, Int, в базовой структуре данных будетPyObjectЧлен типа, используемый для поддержания счетчика ссылок объекта.

typedef struct _object {
    _PyObject_HEAD_EXTRA
    Py_ssize_t ob_refcnt;
    struct _typeoject *ob_type;
} PyObject;

один из нихob_refcntУчастники несут ответственность за ведение подсчета ссылок Таким образом, все встроенные конструкции сохраняются в началеPyObjectstruct для ведения счетчиков ссылок.

распределитель памяти

Python — это не простой вызов при выполнении выделения памятиmalloc/freeфункция запроса памяти у операционной системы. Вместо этого ради эффективности системные вызовы максимально сокращены, а распределитель памяти разделен на три уровня.

    Object-specific allocators
    _____   ______   ______       ________
   [ int ] [ dict ] [ list ] ... [ string ]       Python core         |
+3 | <----- Object-specific memory -----> | <-- Non-object memory --> |
    _______________________________       |                           |
   [   Python's object allocator   ]      |                           |
+2 | ####### Object memory ####### | <------ Internal buffers ------> |
    ______________________________________________________________    |
   [          Python's raw memory allocator (PyMem_ API)          ]   |
+1 | <----- Python memory (under PyMem manager's control) ------> |   |
    __________________________________________________________________
   [    Underlying general-purpose allocator (ex: C library malloc)   ]
 0 | <------ Virtual memory allocated for the python process -------> |
   =========================================================================
    _______________________________________________________________________
   [                OS-specific Virtual Memory Manager (VMM)               ]
-1 | <--- Kernel dynamic storage allocation & management (page-based) ---> |
    __________________________________   __________________________________
   [                                  ] [                                  ]
-2 | <-- Physical memory: ROM/RAM --> | | <-- Secondary storage (swap) --> |

Уровень от 0 до уровня 3 — это уровни распределения, управляемые реализацией Python.Если мы возьмем в качестве примера объекты словаря,

PyDict_New()             ----3层
  PyObject_GC_New()      ----2层
  PyObject_Malloc()      ----2层
    new_arena()          ----1层
      malloc()           ----0层

0-й уровень предназначен для прямого вызова функции распределения, предоставляемой операционной системой, напримерmalloc. Python не вызывает уровень 0 для генерации всех объектов, а выбирает другую схему распределения в зависимости от размера выделяемой памяти:

Запрошенная память больше 256 байт, используйте уровень 0
Запрошенная память меньше 256 байт при использовании первого и второго слоев.

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

for x in range(100):
  print(x)

Во время этого процесса, если часто вызываетсяmallocа такжеfree, эффективность будет очень низкой. Python добавляет уровни 1 и 2, и на первом уровне он будет заранее применять для некоторого резервирования пространства и управления из уровня 0. Когда выделенная объектная память меньше 256, эта часть пространства используется.

Структура памяти, управляемая Python, состоит из 3 частей:block,pool,arena, а связь между ними следующая:

arena используется для управления пулами хранения
пул используется для управления блоками хранения
Наименьшая единица, доступная для блокирования претендентов на память

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

Распределитель уровня 2 отвечает за управление блоками в пуле. Вернуть стартовый адрес блока заявителю, снять блок и т.д. Распределитель разделит пул в соответствии с размером, кратным 8 байтам, и создаст несколько блоков, таких как: 8-байтовый блок, 16-байтовый блок, 24-байтовый блок, ... 256-байтовый блок. При выделении памяти будет возвращен блок подходящего размера.

Третий уровень — объектно-специфичный аллокатор.Различные встроенные типы в Python, такие как list, dict и т. д., будут иметь свои собственные уникальные аллокаторы.Например, аллокатор dict выглядит так:

#ifndef PyDict_MAXFREELIST
#define PyDict_MAXFREELIST 80
#endif
static PyDictObject *free_list[PyDict_MAXFREELIST];
static int numfree = 0;

При размещении объекта словаря сначала проверяется свободный списокfree_listЕсть ли доступный объект, если он исчерпан, то проходим уровень 2PyObject_GC_Newприменять для.

В целом взаимодействие, когда Python генерирует объект словаря, выглядит следующим образом:

подсчет ссылок

Метод подсчета ссылок, реализованный в Python, фактически заключается в выполнении соответствующих операций над количеством ссылок на каждый объект: если количество ссылок на объект увеличивается, к счетчику прибавляется 1, а если количество ссылок уменьшается, то 1 вычитается со стойки.

Инкрементная операция

Фактическая операция подсчета выполняется макросомPy_INCREFреализовать

#define Py_INCREF(op) (                  \
    ((PyObject*)(op))->ob_refcnt++)

ob_refcntТип int в 32-битной среде и long в 64-битной среде. Из-за бита со знаком только половина значений может быть представлена неотрицательными целыми числами. Но поскольку указатель в основномвыравнивание по 4 байтам, так что даже если на счетчик ссылок ссылаются все указатели, он не переполнится. Он предназначен для использования отрицательных чисел для облегчения отладки.Когда в счетчике ссылок есть отрицательные числа, существует вероятность того, что операция уменьшения является избыточной или операция увеличения остается позади.

Операция уменьшения

Фактическая операция подсчета выполняется макросомPy_DECREFреализовать

#define Py_DECREF(op)                          \
    if (--((PyObject*)(op))->ob_refcnt != 0)        \
        _Py_CHECK_REFCNT(op)                  \
     else                                \
        _Py_Dealloc((PyObject*)(op))


# define _Py_Dealloc(op) (              \
        (*Py_TYPE(op)->tp_dealloc)((PyObject*)(op)))

Сначала установите счетчик, если он не равен 0, вызовите макрос_Py_CHECK_REFCNTПроверьте, не стал ли счетчик ссылок отрицательным. Если счетчик равен 0, то вызывается макрос_Py_Dealloc,пройти черезPy_TYPEОпределите тип объекта и вызовите соответствующий указатель функции, ответственный за освобождение каждого объекта.Например, указатель функции, ответственный за освобождение объекта кортежа,tupledealloc.

static void
tupledealloc(register PyTupleObject *op)
{
    register Py_ssize_t i;
    register Py_ssize_t len = Py_Size(op);
    
    if (len > 0) {
        i = len;
        /* 将元组内的元素进行减量 */
        while(--i >= 0)
            Py_XDECREF(op->ob_item[i]);
    }
    /* 释放元组对象 */
    Py_TYPE(op)->tp_free((PyObject *)op);
    
    Py_TRASHCAN_SAFE_END(OP);
}

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

void
PyObject_GC_Del(void *op)
{
    PyGC_Head *g = AS_GC(op);
    /* ... */
    Pyobject_FREE(g)
}

Граф вызова операции декремента кортежа выглядит следующим образом:

Py_DECREF
  _Py_Dealloc              ———— 减量操作
    tupledealloc
      PyObject_GC_Del      ———— 元组释放处理
        PyObject_FREE
          PyObject_Free    ———— 释放内存

указанное право собственности

Выше было разъяснено, что основными операциями подсчета ссылок являются подсчет +1 и подсчет -1. Должно быть ясно, кто отвечает за операцию, например: объект A вызывает функцию, вызываяfunc1После получения объекта B кто должен нести ответственность за счетчик ссылок объекта B +1? Здесь задействовано «владение ссылкой», то есть тот, кто владеет ссылкой, несет ответственность за уменьшение счетчика ссылок объекта, когда ссылка не нужна.

передать право владения ссылкой (возвращаемое значение)

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

PyObject *dict = PyDict_New();
/* 进行一些操作， 结束后*/
Py_DECREF(dict);
dict = NULL;

Предоставить право собственности на ссылку (возвращаемое значение)

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

PyObject *
PyTuple_GetItem(register PyObject *op, register Py_ssize_t i)
{
    /*检查操作*/
    return ((PyTupleObject *)op) -> ob_item[i]
}

стать владельцем ссылки (параметра)

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

PyObject *tuple, *dict;

tuple = PyTuple_New(3);
dict = PyDict_New();    /*用所有权返回给了dict*/
PyTuple_SetItem(tuple, 0, dict);    /*引用所有权被tuple占据了*/
dict = NULL;

Одолжить ссылку на право собственности (параметр)

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

Циклическая сборка мусора

Метод подсчета ссылок имеет недостаток и не может решить проблему циклических ссылок: когда два объекта ссылаются друг на друга, счетчик ссылок не может быть очищен, то есть не может быть выполнен сборщик мусора. Поэтому для циклических ссылок Python передает部分标记-清除算法решать.

Принцип алгоритма: частичный алгоритм маркировки-развертки

Например, на рисунке ниже есть циклические ссылки на три объекта слева, что делает их невозможными для повторного использования при обычном подсчете ссылок.Сначала мы копируем их текущие счетчики ссылок в другой блок для последующих операций.Существует предпосылка: объекты Python генерируются, прикрепляя себя к对象链表in (соединены друг с другом двунаправленным указанием), обозначенные двунаправленной стрелкой на рисункеНа основании этого проходим对象链表для всех объектов в , уменьшить количество копий всех объектов, на которые они ссылаются, на единицув настоящее время标记После операции мы помечаем все объекты, количество копий которых все еще больше 0 после предыдущего шага, как «достижимые объекты», то есть другие активные объекты ссылаются на них, а объекты, на которые они ссылаются, помечаем как достижимые объекты, и соединяем их в связанный список доступных объектов; затем объект, число копий которого равно 0, записывается как «недостижимый объект» и подключается к связанному списку недоступных объектов.Видно, что недостижимый объект является объектом циклической ссылки, а затем переходим к清除операции, мы освобождаем память объектов в списке недоступных объектов и повторно подключаем объекты в списке доступных объектов.对象链表серединаНа данный момент мы завершили сборку мусора объекта циклической ссылки.

Не все объекты будут иметь циклические ссылки

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

tyepdef union _gc_head {
    struct {
        union _ge_head *gc_next; /*用于双向链表*/
        union _gc_head *gc_prev; /*用于双向链表*/
        Py_ssize_t gc_refs;      /*用于复制计数*/
    } gc;
    long double dummy;
} PyGC_Head;

Как упоминалось ранее, при создании объекта-контейнера он будет подключен к对象链表, возьмем в качестве примера объект словаря, посмотрим на код, когда он его генерирует

PyObject *
PyDict_New(void)
{
    regiseter PyDictObject *mp;
    /*生成对象的操作*/
    _PyObject_GC_TRACK(mp);
    return (PyObject *)mp;

}

_PyObject_GC_TRACKотвечает за подключение к对象链表операции в

#define _PyObject_GC_TRACK(o) do { \
    PyGC_Head *g = _Py_AS_GC(o); \
    g->gc.gc_refs = _PyGC_REFS_REACHABLE;  \
    g->gc.gc_next = _PyGC_generation0; \
    g->gc.gc_prev = _PyGC_generation0->gc.gc_prev; \
    g->gc.gc_prev ->gc.gc_next = g;  \
    _PyGC_generation0->gc.gc_prev = g; \
    } while (0);

Управление генерацией контейнерных объектов

Python делит связанный список объектов-контейнеров, упомянутых выше, на «поколение 0», «поколение 1» и «поколение 2», которые управляются следующей структурой.

struct gc_generation {
    PyGC_Head head;   /* 头指正 */
    int threshold;    /* 开始GC的阈值 */
    int count;        /* 改代的对象数 */
}

# define GEN_HEAD(n) (&generations[n].head)

PyGC_Head *_PyGC_generation0 = GEN_HEAD(0); /* 0代的容器对象 */

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

удалить исключение

Во время круговой сборки мусора мы будем иметь终结器объект удален из списка недоступных

static void
move_finalizers(PyGC_Head *unreachable, PyGC_Head *finalizers)
{
    PyGC_Head *gc;
    PyGC_Head *next;
    
    for (gc = unreachable->gc.gc_next; gc != unreachable; gc = next) {
        PyObject *op = FROM_GC(gc);
        next = gc->gc.gc_next;
        if (has_finalizer(op)) {
            gc_list_move(gc, finalizers);
            gc->gc.gc_refs = GC_REACHABLE;
        }
    }
}

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

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

import gc
gc.grabage

Суммировать

GC Python разделен на две части:

пройти через引用计数算法управлять сборкой мусора обычных объектов и минимизировать GC с оптимизированными структурами памяти
пройти через分代+清除-标记для управления сборкой мусора объектов циклических ссылок