Проектирование системы управления памятью Python    167

ПРОЕКТИРОВАНИЕ СИСТЕМЫ УПРАВЛЕНИЯ ПАМЯТЬЮ PYTHON

Система CPython была построена на базе C, поэтому ей приходится использовать ограничения статического, динамического и автоматического выделения памяти. Из-за некоторых особенностей проектирования языка Python эти ограничения создают еще больше проблем:

1.Python является языком с динамической типизацией. Размер переменных не может быть вычислен во время компиляции.

2.Размеры большинства базовых типов Python определяются динамически. Тип list может иметь произвольный размер, dict может содержать любое число ключей, и даже int является динамическим. Пользователю никогда не приходится задавать размер этих типов.

3.Имена в Python могут повторно использоваться для значений разных типов:

>>>a_value = 1

>>>a_value = "Now I'm a string"

>>>a_value = ["Now" , "I'm", "a", "list"]

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

Вместо того чтобы заставлять Python-разработчика заниматься выделением памяти, память объектов в Python выделяется автоматически через один унифицированный API. Архитектура требует, чтобы вся стандартная библиотека CPython и базовые модули (написанные на C) использовали этот API.

Области выделения памяти

CPython поддерживает три области динамического выделения памяти:

1.Область сырой (raw) памяти — используется для выделения памяти из системной кучи и больших объемов памяти, а также если она выделяется не для объектов Python.

2.Область объектной (object) памяти — используется для выделения памяти для всех объектов Python.

Книги для программистов: https://t.me/booksforits

168    Управление памятью

3.Область PyMem — то же, что PYMEM_DOMAIN_OBJ. Этот тип существует для обеспечения совместимости со старыми API.

Все эти типы реализуют один и тот же интерфейс функций:

zz _Alloc(size_t size) выделяет память размером bytes и возвращает указатель.

zz _Calloc(size_t nelem, size_t elsize) выделяет память для nelem

элементов, каждый из которых имеет размер elsize, и возвращает указатель.

zz _Realloc(void *ptr, size_t new_size) выделяет память размером new_size.

zz _Free(void *ptr) освобождает память по указателю ptr и возвращает ее в кучу.

PyMemAllocatorDomain представляет три области выделения памяти в CPython именами PYMEM_DOMAIN_RAW, PYMEM_DOMAIN_OBJ и PYMEM_DOMAIN_MEM.

Аллокаторы

CPython использует два аллокатора1:

1.malloc: аллокатор операционной системы для выделения сырой памяти.

2.pymalloc: аллокатор CPython для выделения объектной памяти и PyMem.

ПРИМЕЧАНИЕ

В CPython по умолчанию компилируется аллокатор CPython, pymalloc. Его можно удалить,для этого следует перекомпилировать CPython после установки параметраWITH_PYMALLOC = 0 вpyconfig.h.При его удалении API Object и PyMem будут использовать системный аллокатор.

Если вы скомпилировали CPython с поддержкой отладки (--with-pydebug в macOS или Linux, или цель Debug в Windows), то каждая функция-алло- катор будет входить в отладочную реализацию. Например, с включенной

1 Механизм распределения памяти. — Примеч. ред.

Книги для программистов: https://t.me/booksforits

Аллокаторы памяти CPython    169

отладкой вызовы выделения памяти будут выполнять _PyMem_DebugAlloc()

вместо _PyMem_Alloc().

АЛЛОКАТОРЫ ПАМЯТИ CPYTHON

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

zz В большинстве запросов выделения памяти используется небольшой фиксированный размер: для PyObject 16 байт, для PyASCIIObject 42 байта, для PyCompactUnicodeObject 72 байта и для PyLongObject 32 байта.

zz Аллокатор pymalloc выделяет блоки памяти размером не более 256 Кбайт. Все, что больше, передается для распределения системе.

zz pymalloc использует GIL вместо системной проверки безопасности потока.

Чтобы вам было проще понять этот процесс, представьте стадион. Для управления потоками людей была реализована система, разбивающая стадион на сектора от A до E, при этом сектора разбиты на ряды. В каждом секторе имеется 40 мест:

A

В рядах с 1 по 10 располагаются более просторные премиальные места, по 80 мест в каждом ряду. В рядах с 31 по 40 находятся места эконом-класса, по 150 мест в каждом ряду.

Книги для программистов: https://t.me/booksforits

170    Управление памятью

Алгоритм выделения памяти Python обладает сходными характеристиками:

zz На стадионе зрители имеют места, а алгоритм pymalloc имеет блоки памяти.

zz На стадионе места могут быть премиальными, стандартными и дешевыми; блоки памяти принадлежат к одному из диапазонов фиксированного размера. Вам не удастся принести на стадион свою табуретку!

zz Все места одного размера объединяются в ряды, а блоки одного размера — в пулы.

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

Такая стратегия обладает рядом достоинств:

1.Алгоритм обладает большей производительностью для основного сценария использования CPython: небольшие объекты с коротким сроком жизни.

2.Алгоритм использует GIL вместо системного обнаружения блокировок потоков.

3.Алгоритм использует перераспределение памяти (mmap()) вместо выделения памяти из кучи.

Исходные файлы

Ниже перечислены исходные файлы, относящиеся к аллокатору памяти.

Книги для программистов: https://t.me/booksforits

Аллокаторы памяти CPython    171

Важные термины

Ниже перечислены некоторые ключевые термины, встречающиеся в этой главе:

zz Запрашиваемая память сопоставляется с размером блока. zz Блоки одного размера входят в один пул памяти.

zz Пулы группируются в арены.

Блоки, пулы и арены

Наибольшая группа ячеек памяти называется ареной (arena). CPython создает арены размером 256 Кбайт, чтобы они совпадали по размеру с системной страницей. Граница системной страницы — непрерывный участок памяти фиксированной длины.

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

Арены

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

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

1 http://man7.org/linux/man-pages/man2/mmap.2.html.

Книги для программистов: https://t.me/booksforits

172    Управление памятью

Арена имеет структуру данных arenaobject:

ПРИМЕЧАНИЕ

Арены объединяются в двусвязный список внутри структуры данных арены при помощи указателейnextarena (следующая арена) иprevarena (предыдущая арена).

Если память для арены не выделена, то используется поле nextarena. Оно связывает все несвязанные арены водносвязный глобальный список unused_arena_objects.

Когда арена связывается сареной,для которой выделена память хотя бы с одним доступным пулом,оба указателя,nextarena иprevarena,исполь­ зуются в двусвязном списке usable_arenas.Этот список поддерживается по возрастанию значений nfreepools.

Пулы

Внутри арены создаются пулы, состоящие из блоков размером до 512 байт. В 32-разрядных системах шаг увеличения размера блока составляет 8 байт, поэтому определены 64 класса размера:

Книги для программистов: https://t.me/booksforits

В 64-разрядных системах шаг составляет 16 байт, поэтому определены 32 класса размера:

Все пулы имеют размер 4096 байт (4 Кбайт), так что арена всегда содержит 64 пула:

Книги для программистов: https://t.me/booksforits

174    Управление памятью

Пулы выделяются в памяти по требованию. Если для запрашиваемого индекса класса размера доступные пулы отсутствуют, предоставляется новый. У арен имеется верхний предел для индексирования количества введенных в действие пулов.

Пулы имеют три состояния:

1.Заполненный: все доступные блоки в пуле уже выделены.

2.Используемый: пул выделен, некоторые блоки заняты, но в пуле все еще осталось место.

3.Пустой: пул выделен, но блоки еще не заняты.

Внутри арены верхний предел устанавливается на последний выделенный пул:

Пулы имеют структуру данных poolp, которая является статическим распределением структуры pool_header. Тип pool_header содержит следующие свойства:

Книги для программистов: https://t.me/booksforits

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

Таблицы пулов

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

Таблица пулов сегментируется по индексу класса размера (i). Для индекса i usedpools[i + i] указывает на начало списка всех частично используемых пулов с таким же индексом класса размера.

Основные характеристики таблицы пулов:

zz Когда пул заполняется, он отсоединяется от своего списка usedpools[]. zz Если в заполненном пуле освобождается блок, то он возвращается

всостояние «используемый». Вновь освобожденный пул вставляется

вначало соответствующего списка usedpools[], так что следующее выделение памяти для его класса размера использует освобожденный блок.

zz При переходе в состояние «пустой» пул отсоединяется от списка usedpools[] и добавляется в начало односвязного списка freepools своей арены.

Блоки

Внутри пула память делится на блоки. Блоки обладают следующими характеристиками:

zz Внутри пула выделяются и освобождаются блоки фиксированного размера.

Книги для программистов: https://t.me/booksforits

176    Управление памятью

zz Доступные блоки внутри пула объединяются в односвязный список freeblock.

zz Когда блок освобождается, он вставляется в начало списка freeblock.

zz Когда пул инициализируется, только первые два блока связываются в списке freeblock.

zz Пока пул в состоянии «используемый», в нем есть хотя бы один доступный для выделения блок.

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

API выделения блоков

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

Objects obmalloc.c, строка 1590

static inline void*

pymalloc_alloc(void *ctx, size_t nbytes)

{

...

В запросе nbytes = 30 размер должен быть не равен нулю и не превышать значение SMALL_REQUEST_THRESHOLD, равное 512:

if (UNLIKELY(nbytes == 0)) { return NULL;

}

if (UNLIKELY(nbytes > SMALL_REQUEST_THRESHOLD)) { return NULL;

}

Книги для программистов: https://t.me/booksforits

Аллокаторы памяти CPython    177

В 64-разрядных системах при вычислении индекса класса размера будет получен результат 1. Это соответствует второму индексу класса размера (17–32 байта).

Следовательно, целевым пулом будет usedpools[1 + 1] (usedpools[2]):

uint size = (uint)(nbytes - 1) >> ALIGNMENT_SHIFT; poolp pool = usedpools[size + size];

block *bp;

Затем проверяется наличие доступного используемого ('used') пула для индекса класса размера. Если список freeblock находится в конце пула, значит, в пуле еще остаются чистые блоки.

Функция pymalloc_pool_extend() вызывается для расширения списка freeblock:

if (LIKELY(pool != pool->nextpool)) { /*

*Для этого класса размера имеется используемый пул.

*Получить первый блок его свободного списка

*/ ++pool->ref.count;

bp = pool->freeblock; assert(bp != NULL);

if (UNLIKELY((pool->freeblock = *(block **)bp) == NULL)) {

// Достигнут конец свободного списка. Попробовать расширить его pymalloc_pool_extend(pool, size);

}

}

Если доступные пулы отсутствуют, то создается новый пул и возвращается первый блок. allocate_from_new_pool() автоматически добавляет новый пул в список usedpools:

else {

/* Нет пула нужного класса размера. * Использовать свободный пул

*/

bp = allocate_from_new_pool(size);

}

return (void *)bp;

}

Наконец, возвращается адрес нового блока.

Книги для программистов: https://t.me/booksforits