Аллокаторы в СPython: PyArena

Один из самых простых аллокаторов в питоне. Исходники.

По сути данный аллокатор является небольшой оберткой поверх PyMem_Malloc, но с интересной особенностью. Если PyMem_Malloc имеет PyMem_Free для освобождения памяти каждого конкретного объекта, то PyArena имеет только _PyArena_Free(PyArena *arena) для освобождения сразу всей арены со всеми объектами, которые являются ее частью.

Смотрим:

struct _arena {
    /* Pointer to the first block allocated for the arena, never NULL.
       It is used only to find the first block when the arena is
       being freed. */
    block *a_head;

    /* Pointer to the block currently used for allocation.  Its
       ab_next field should be NULL.  If it is not-null after a
       call to block_alloc(), it means a new block has been allocated
       and a_cur should be reset to point it. */
    block *a_cur;

    /* A Python list object containing references to all the PyObject
       pointers associated with this arena.  They will be DECREFed
       when the arena is freed. */
    PyObject *a_objects;
};

Как мы видим, арена содержит два указателя на блоки. А вот и они:

typedef struct _block {
    /* Total number of bytes owned by this block available to pass out.
        Read-only after initialization.  The first such byte starts at
        ab_mem */
    size_t ab_size;

    /* Total number of bytes already passed out.  The next byte available
        to pass out starts at ab_mem + ab_offset */
    size_t ab_offset;

    /* An arena maintains a singly-linked, NULL-terminated list of
        all blocks owned by the arena.  These are linked via the
        ab_next member */
    struct _block *ab_next;

    /* Pointer to the first allocatable byte owned by this block.  Read-
        only after initialization */
    void *ab_mem;
} block;

И очищаем сразу все внутри арены:

void _PyArena_Free(PyArena *arena)
{
    assert(arena);
    // ...
    block_free(arena->a_head);
    Py_DECREF(arena->a_objects);
    PyMem_Free(arena);
}

Обратите внимание, что у PyArena есть block'и и есть список обычных PyObject *. Что достигается за счет следующих АПИ:
- _PyArena_New – создает новую арену и выделяет память под нее. Создает пустой список под будущие объекты
- _PyArena_Free – очищает память существующей арены. Удаляет все блоки из памяти, декрефит объекты в списке, их собирает reference-counter
- _PyArena_Malloc – создает новый block нужного размера и сохраняет указатель на него в single-linked list
- _PyArena_AddObject – добавляет PyObject * в список отслеживаемых объектов и гарантирует, что он будет жить столько, сколько живет сама арена

Использование

Где нужна арена? На самом деле – много где. Сам подход с ареной – можно сравнить с lifetime из Rust. Все объекты внутри арены живут до одного общего конца.

Используется там, где объекты логически имеют общий lifetime. Например, при парсинге кода в AST. Ведь все дерево объектов в AST – имеет общий лайфтайм. Так намного проще обрабатывать ошибки, если произошло что-то плохое, мы просто убиваем всю арену. И нам не надо чистить все объекты в памяти ручками.

Крайне удобная штука.

Большая статья по теме: https://rfleury.com/p/untangling-lifetimes-the-arena-allocator

Выводы

Вот и single-linked list с алгособесов пригодился! 🌚️️️️