Аренная аллокация

Арена (также называемая регионом, пулом или bump-аллокатором) - это блок памяти, который раздаёт множество мелких аллокаций и освобождает их все разом. Вместо вызова malloc/free под каждый объект вы выделяете память под объекты в арене по мере их создания, используете их, пока жива арена, а по завершении сбрасываете весь регион одной операцией. Отдельные объекты сами по себе никогда не освобождаются.

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

Как устроена аллокация

Простейшая арена - это bump-аллокатор. Он хранит буфер и смещение. Выделение n байт возвращает текущее смещение и сдвигает его на n. Здесь нет списков свободных блоков (free list), классов размеров (size classes), объединения фрагментов (coalescing) - аллокация сводится к сложению указателя и проверке границ. Когда буфер заполняется, арена запрашивает следующий чанк (арены обычно делают в виде связного списка чанков, чтобы существующие ссылки оставались валидными; арена на базе Vec, выполняющая реаллокацию, сделала бы их невалидными). Освобождение означает удаление всех чанков или сброс смещения в ноль для повторного использования пространства.

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

Ссылки против индексов

Есть два распространённых способа ссылаться на данные в арене, и выбор между ними приводит к ощутимым последствиям.

Арены, раздающие ссылки, возвращают настоящий указатель (&T) внутрь региона. В Rust так устроен крейт typed_arena: arena.alloc(value) возвращает &mut T, а borrow checker привязывает время жизни этой ссылки к времени жизни самой арены, поэтому сохранить ссылку после уничтожения арены нельзя. Это эргономично: можно делать pattern matching прямо по ссылкам (чего Rust иначе не умеет делать через Box в рекурсивном enum'е), но каждая ссылка - это полноценный указатель (64 бита на большинстве платформ), и всё дерево ссылок делит одно общее время жизни арены, которое затем просачивается в сигнатуру каждой функции, работающей с ним.

Арены, раздающие индексы (семейство generational arena, например generational-arena или slotmap), хранят объекты в базовом Vec'е и возвращают целочисленный индекс вместо указателя. Для разыменования вы обращаетесь по индексу обратно в арену. Индексы могут быть 32- или даже 16-битными, поэтому они упаковываются плотнее указателей - что важно при наличии множества мелких узлов. Часть "generational" добавляет счётчик поколений к каждому слоту, что позволяет обнаружить устаревший индекс (указывающий на слот, который был использован повторно), а не молча прочитать чужой объект.

Почему индексы вместо указателей избавляют от борьбы с borrow checker'ом

Подход с индексами популярен в Rust именно потому, что он позволяет обойти borrow checker. Граф или двусвязная структура на базе ссылок &T заставляют доказывать компилятору, что каждая ссылка живёт дольше любого её использования и что правила алиасинга соблюдаются - что для циклических или самоссылающихся структур часто невозможно без unsafe, Rc<RefCell<T>> или Pin. Если же узлы живут в Vec<Node>, а рёбра представлены индексами usize, то ссылки, которые волнуют borrow checker, сводятся к короткоживущим &self.nodes[i], получаемым прямо в момент обращения. Сама структура графа не несёт никаких времён жизни. Тот же приём используется в safe-gc: пропустить каждое обращение через индексацию Heap, а не через сырой указатель, и целые классы ошибок use-after-free и некорректного алиасинга исчезают из пространства достижимых состояний. Плата за это в том, что устаревший или неверный индекс становится логической ошибкой, а не ошибкой компиляции - счётчики поколений как раз и нужны, чтобы превратить её в отслеживаемый сбой во время выполнения.

Интернирование

Арена отлично сочетается с интернированием: выделением памяти с дедупликацией. Перед сохранением значения вы вычисляете его хэш и проверяете, нет ли уже такого же в арене; если есть, возвращаете существующий дескриптор. В результате одинаковые значения делят одну аллокацию, а проверка на равенство сводится к сравнению дескрипторов вместо глубокого сравнения содержимого. rustc активно этим пользуется: он интернирует типы в арену, поэтому идентичные типы равны по указателю, что удешевляет и сравнение типов, и кэширование; он также интернирует HIR при понижении AST (AST lowering), раздавая дескрипторы HirId. Пример ниже с pretty printer'ом для Gleam использует облегчённый вариант: ключевые слова и разделители вроде String("fn") или запятой списка выделяются в арене один раз и используются везде по ссылке вместо повторного оборачивания в Box.

Время жизни и освобождение памяти

Определяющее ограничение: освободить один объект раньше остальных нельзя. Всё содержимое арены уничтожается одновременно. Для работы с выраженными фазами это преимущество - внутри фазы не бывает утечек и двойных освобождений (double-free), а очистка требует O(1) операций по чанкам вместо O(n) по объектам. Для долгоживущих структур с действительно независимыми временами жизни объектов это неподходящий инструмент: арена, которая только растёт, будет удерживать память до конца фазы, поэтому сервер, использующий арены на каждое соединение, обязан сбрасывать арену между запросами, иначе она ведёт себя как утечка памяти. Это дисциплина, противоположная пообъектным схемам вроде raii, где деструктор каждого объекта детерминированно выполняется при выходе из его собственной области видимости, а также схемам очистки вроде epoch-based-reclamation, созданным ровно для того, чтобы безопасно освобождать отдельные узлы в многопоточной среде.

Пример: pretty printer в Gleam

Конкретный пример - gleam-pretty-printer-arenas. Форматтер Gleam строит рекурсивное дерево Document, где вложенные варианты упаковывались в кучу через Box (Nest(Box<Self>)). Замена этих Box'ов на ссылки в арену (Nest(&'doc Self)) на базе typed_arena устранила большую часть поузловых аллокаций в куче и позволила кэшировать повторяющиеся документы один раз. Форматтер стал быстрее примерно на 24%, а пиковое потребление памяти упало примерно на 10%. Платой за это стала чисто механическая работа: каждой функции, создающей документы, пришлось принимать арену дополнительным аргументом и протаскивать её время жизни через сигнатуры.

В big-pineapple-dns-cache-layout применяется компактный вариант этой идеи: записи сериализуются в переиспользуемый scratch-буфер, а затем копируются в одну аллокацию точного размера под каждую запись кэша.

Арены встречаются повсюду в системном программировании и разработке языков по тем же причинам: bump-аллокация быстра, массовое освобождение тривиально, а язык с ручным управлением памятью (как в dayvster-manual-memory-management) получает большую часть преимуществ автоматического управления в плане безопасности внутри ограниченного региона. В многопоточном контексте совместное использование арены между потоками упирается в привычные ограничения rust-send-sync: однопоточная bump-арена по умолчанию не является ни Send, ни Sync, а безопасный доступ к ней требует либо синхронизации, либо раздельных арен на каждый поток.