Свой аллокатор: malloclab на Zig

В прошлом уроке ты построил модель кучи: регион со своим sbrk, блоки с заголовком и граничным тегом, place, coalesce и три стратегии поиска по неявному списку. Это был аллокатор в смысле книги: функции malloc и free, которые работают с адресами. Сегодня он становится аллокатором в смысле Zig: значением типа std.mem.Allocator, на котором живут ArrayList, хеш-таблицы и всё остальное. Потом мы дважды поменяем способ поиска свободного блока, на явный список и на сегрегированные списки, не тронув ни строки в остальном коде. Снимем utilization и throughput на шести трассах, поставим рядом аллокаторы стандартной библиотеки и разберём, откуда берётся каждое странное число в таблице. А в конце переведём на этот аллокатор кучу нашего Лиспа zl.

Цели урока

• Знать контракт четырёх функций std.mem.Allocator.VTable в Zig 0.16: что обязан делать alloc, чем resize отличается от remap, что free получает вместо одного указателя и что стандартная библиотека делает сама, не доходя до vtable.
• Выделять память с выравниванием больше 16 байт так, чтобы free ничего не знал о выравнивании: через зазор, который становится обычным свободным блоком.
• Написать явный двусвязный список свободных блоков внутри их нагрузки и объяснить, почему минимальный блок из-за него равен 32 байтам.
• Разложить свободные блоки по классам размеров и объяснить, почему first fit внутри класса ведёт себя почти как best fit по всей куче.
• Проверять аллокатор в три слоя: проверяльщик кучи, стандартные испытания std.heap.testAllocator и трассы со сверкой содержимого.
• Читать таблицу utilization и throughput: отличать внутреннюю фрагментацию от внешней, видеть цену линейного поиска и цену системного вызова.
• Объяснить, чем промышленные аллокаторы jemalloc и mimalloc отличаются от лабораторного: арены и кэши на поток, классы размеров без заголовков, свободные списки на страницу.
• Поставить кучу zl на свой аллокатор: пул ячеек одним регионом, свободный список через cdr, статистика раздробленности.

Что такое malloclab

В курсе CS:APP лабораторная по аллокатору считается самой коварной. Задание короткое: напиши mm_init, mm_malloc, mm_free и mm_realloc. Драйвер проигрывает на них файлы трасс и ставит оценку по двум числам. Первое это utilization, пик суммы живых нагрузок, делённый на итоговый размер кучи. Второе это throughput, операций в секунду. Коварство в том, что эти числа тянут в разные стороны. Best fit бережёт память и обходит всю кучу на каждый запрос. Next fit почти не ищет и сорит дырами. Учебная версия из книги, неявный список с first fit, на этих трассах набирает чуть больше половины баллов, и раздел 9.9.13 заканчивается обещанием: с явным списком будет быстрее. Раздел 9.9.14 описывает сегрегированные списки уже без кода. Мы напишем и то, и другое.

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

Проект our-alloc из прошлого урока остаётся тем же. Сегодня в нём появятся четыре файла и дорастут три:

our-alloc/
  build.zig              + шаг 58, цель bench
  src/
    root.zig             + два индекса и два типа аллокатора
    allocator.zig        без правок: сегодня разбираем то, что отложили
    explicit.zig         новый: двусвязный список свободных блоков
    segregated.zig       новый: шестнадцать списков по классам размеров
    bench.zig            новый: замеры и json для графиков
  tests/
    step_58.zig          новый

heap.zig, implicit.zig, trace.zig и gen.zig не меняются ни на строку: ради этого код и был разрезан на кучу и индекс.

Интерфейс: четыре функции и один указатель

Во всех уроках раздела аллокатор приходил в функцию параметром: gpa.alloc(u8, n), list.append(gpa, x), gpa.free(slice). Пора посмотреть, что это за значение. std.mem.Allocator это структура из двух полей:

const std = @import("std");

pub const Shape = struct {
    /// Состояние конкретного аллокатора, тип стёрт.
    ptr: *anyopaque,
    /// Четыре функции, которые умеют с этим состоянием работать.
    vtable: *const std.mem.Allocator.VTable,
};

Это интерфейс в том же смысле, в каком std.Io.Writer интерфейс: указатель на данные и таблица функций, которые принимают этот указатель первым аргументом. Наследования в Zig нет, а vtable пишется руками. Всё, что ты привык вызывать (alloc, create, dupe, realloc, free, destroy), это обычные методы std.mem.Allocator, написанные один раз поверх четырёх функций таблицы. В Zig 0.16 таблица выглядит так:

const std = @import("std");
const Alignment = std.mem.Alignment;

pub const VTable = struct {
    alloc: *const fn (*anyopaque, len: usize, alignment: Alignment, ret_addr: usize) ?[*]u8,
    resize: *const fn (*anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ret_addr: usize) bool,
    remap: *const fn (*anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ret_addr: usize) ?[*]u8,
    free: *const fn (*anyopaque, memory: []u8, alignment: Alignment, ret_addr: usize) void,
};

Разберём, что обязана делать каждая.

alloc возвращает адрес len байт, выровненный на alignment, или null. Не ошибку, а именно null: в error.OutOfMemory его превращает обёртка. Выравнивание приходит не числом, а типом Alignment: это перечисление, в котором хранится двоичный логарифм, так что не степень двойки туда просто нельзя положить. Байты достаёт alignment.toByteUnits(). Запрос нулевой длины до тебя не дойдёт: gpa.alloc(u8, 0) стандартная библиотека обслуживает сама и возвращает пустой срез с ненулевым выровненным адресом.

resize пробует изменить размер блока, не двигая его. Ответ true означает: адрес тот же, а длина теперь new_len. Ответ false означает: на месте не получится, и это не ошибка, блок остался как был. Право отказать есть всегда, даже при уменьшении. Этой функцией пользуется, например, ArrayList, когда хочет дорасти, не копируя элементы.

remap делает то же, но ему разрешено блок переместить. Вернул адрес, старый или новый: блок теперь длины new_len, данные на месте. Вернул null: это значит “переезд у меня был бы обычным alloc, копированием и free, делай его сам, у тебя выйдет не хуже”. Зачем тогда функция нужна? Ради аллокаторов, у которых переезд дешевле копирования. page_allocator на Linux отвечает на remap системным вызовом mremap: ядро переставляет записи в таблице страниц, и гигабайтный буфер переезжает без единого скопированного байта. У нас такого фокуса нет, блок посреди кучи страницами не переставишь, так что наш remap это resize, который при отказе возвращает null.

free получает срез целиком, с длиной, и то же выравнивание, с которым блок выделялся. Вот главное отличие от free из C: там аллокатор обязан сам помнить размер каждого блока, и заголовок появился в том числе поэтому. В Zig размер помнит вызывающий, он у него в срезе. Аллокатор, которому этого достаточно (так устроены арены и аллокаторы с классами размеров), может вообще не хранить ничего рядом с блоком. Нам заголовок всё равно нужен: по нему работают обход кучи и слияние.

Последний параметр ret_addr это адрес возврата из того места, где программа попросила память. Он нужен отладочным аллокаторам, чтобы печатать, кто выделил утёкший блок. Мы его игнорируем.

Как из четырёх функций получается realloc? Вот его логика, записанная через публичные методы (настоящий код в std/mem/Allocator.zig работает с сырыми байтами, но шаги те же):

const std = @import("std");

pub fn reallocSketch(gpa: std.mem.Allocator, old: []u8, new_len: usize) ![]u8 {
    // 1. Вдруг аллокатор умеет сам: на месте или дешёвым переездом.
    if (gpa.remap(old, new_len)) |moved| return moved;
    // 2. Не умеет. Тогда новый блок, копия, старый блок на свободу.
    const fresh = try gpa.alloc(u8, new_len);
    const kept = @min(old.len, new_len);
    @memcpy(fresh[0..kept], old[0..kept]);
    gpa.free(old);
    return fresh;
}

test "realloc сохраняет начало блока" {
    const gpa = std.testing.allocator;
    var block = try gpa.alloc(u8, 4);
    @memcpy(block, "zig!");
    block = try reallocSketch(gpa, block, 4096);
    defer gpa.free(block);
    try std.testing.expectEqualStrings("zig!", block[0..4]);
}

Отсюда вывод для автора аллокатора: mm_realloc из лабораторной писать не нужно. Нужно научиться растить блок на месте, а всё остальное стандартная библиотека сделает сама.

allocator.zig: то, что отложили

Файл src/allocator.zig ты набрал целиком в прошлом уроке и прочитал в нём malloc, free и grow. Остались три куска: ветка over_aligned в mallocAligned, функция resizeInPlace и хвост с таблицей. Править ничего не нужно, нужно понять. Ниже эти куски выписаны из файла как есть, с теми же отступами.

Каркас и индекс

Напомню устройство. HeapAllocator это функция времени компиляции: принимает тип индекса и возвращает тип аллокатора. От индекса нужно пять функций, они перечислены в шапке файла: findFit, insert, remove, reset и check. Интерфейс для этого заводить не пришлось: параметр comptime Index: type проверяется утиной типизацией, и если у типа нет findFit, компилятор скажет об этом в месте вызова.

Обрати внимание на порядок в mallocAligned: сначала findFit, потом сразу index.remove(bp), и только потом блок меняется. И в coalesce соседи убираются из индекса до того, как их размеры сложены. Неявному списку это безразлично, у него remove почти пустой. А сегрегированный индекс ищет список по размеру блока: стоит поменять размер до remove, и он полезет не в тот список. Это правило одно на весь файл: индекс забывает блок, пока блок ещё выглядит так, каким индекс его запомнил.

Рост на месте

        /// Меняет размер блока, не двигая его. Уменьшение удаётся всегда,
        /// рост только за счёт свободного соседа справа или конца кучи.
        pub fn resizeInPlace(self: *Self, bp: usize, new_size: usize) bool {
            const asize = heap.adjust(new_size);

            if (heap.blockSize(bp) < asize) {
                var room = roomAt(bp);
                // Блок у самого конца кучи дорастает через sbrk.
                if (room < asize and bp + room == self.heap.end()) {
                    _ = self.extendTail(@max(asize - room, heap.min_block)) orelse return false;
                    room = roomAt(bp);
                }
                if (room < asize) return false;
                self.index.remove(heap.nextBlock(bp));
                heap.mark(bp, room, true);
            }

            // Лишний хвост возвращается в кучу.
            if (heap.place(bp, asize)) |rest| {
                self.index.insert(heap.coalesce(rest, &self.index));
            }
            return true;
        }

        /// Размер блока вместе со свободным соседом справа.
        fn roomAt(bp: usize) usize {
            const next = heap.nextBlock(bp);
            return heap.blockSize(bp) + if (heap.isAllocated(next)) 0 else heap.blockSize(next);
        }

resizeInPlace отвечает на вопрос resize: можно ли дать блоку new_size байт, не двигая его. Уменьшение удаётся всегда: place отрезает лишний хвост, хвост сливается с правым соседом, если тот свободен, и возвращается в индекс. Если отрезать нечего (остаток меньше минимального блока), place оставит блок как есть, и это тоже успех: нагрузка нужного размера в блок помещается.

С ростом интереснее. Комната для роста, roomAt, это сам блок плюс правый сосед, если он свободен. Хватает комнаты: забираем соседа из индекса, помечаем объединённый блок занятым, лишнее отрезаем. Не хватает, но блок стоит у самого конца кучи: тогда кучу можно просто продлить через sbrk ровно на недостающее, и свежий кусок станет тем самым свободным соседом. Этот случай кажется редким, а на деле он самый частый: буфер, который растёт в цикле, обычно и есть последний выделенный блок. В таблице замеров ты увидишь его след: 99.7 процента utilization на трассе realloc.

Влево блок не растёт никогда: данные пришлось бы двигать, а resize обещал адрес не менять.

Выравнивание больше 16

        /// Выделяет `size` байт по адресу, кратному `alignment`.
        ///
        /// Обычные 16 байт даёт сама раскладка. Для большего выравнивания
        /// блок берётся с запасом, а подходящий адрес ищется внутри него.
        /// Зазор перед этим адресом становится отдельным свободным блоком,
        /// так что возвращённый указатель это честный `bp` со своим
        /// заголовком, и `free` ничего не нужно знать о выравнивании.
        pub fn mallocAligned(self: *Self, size: usize, alignment: usize) ?usize {
            if (size == 0) return null;
            const asize = heap.adjust(size);
            const over_aligned = alignment > heap.alignment;
            // Зазор не бывает больше alignment + min_block - 16.
            const wanted = if (over_aligned) asize + alignment + heap.min_block else asize;

            var bp = self.index.findFit(&self.heap, wanted) orelse self.grow(wanted) orelse return null;
            self.index.remove(bp);

            if (over_aligned) {
                var aligned = std.mem.alignForward(usize, bp, alignment);
                // Зазор короче минимального блока блоком стать не может:
                // сдвигаемся на следующий подходящий адрес.
                if (aligned != bp and aligned - bp < heap.min_block) aligned += alignment;
                if (aligned != bp) {
                    const total = heap.blockSize(bp);
                    const gap = aligned - bp;
                    heap.mark(bp, gap, false);
                    heap.mark(aligned, total - gap, false);
                    // Слева от зазора занятый блок: свободные соседи слиты заранее.
                    self.index.insert(bp);
                    bp = aligned;
                }
            }

            if (heap.place(bp, asize)) |rest| self.index.insert(rest);
            return bp;
        }

Раскладка кучи сама даёт нагрузке выравнивание 16: заголовок занимает 8 байт и стоит по адресу вида 16k + 8. Для u64, указателей и даже u128 этого хватает. Но alignedAlloc вправе попросить 64 (линия кэша, урок про код, дружественный к кэшу), 4096 (страница) и больше, а стандартное испытание testAllocatorLargeAlignment просит половину страницы, на macOS arm64 это 8 КБ.

Классический трюк из C: выделить с запасом, вернуть выровненный адрес внутри блока, а настоящий адрес блока записать в слово перед ним, чтобы free его нашёл. Нам он не годится по двум причинам. Слово перед нагрузкой у нас уже занято заголовком. И free пришлось бы отличать обычные блоки от сдвинутых.

Мы поступим честнее. Блок берётся с запасом, внутри него ищется подходящий адрес, а зазор перед этим адресом становится отдельным свободным блоком. Пример на пустой куче, base это её начало, страница выровнена, так что base кратен любому разумному выравниванию:

запрос: 100 байт, выравнивание 64
asize  = 128                       блок под 100 байт: плюс 16 служебных, вверх до 16
wanted = 128 + 64 + 32 = 224       с запасом на зазор

findFit ничего не нашёл, grow дал блок: bp = base + 32, размер 4096
aligned = base + 64                первый адрес, кратный 64, не раньше bp
gap     = 32                       хватает на минимальный блок

до:     | hdr 4096 |                      свободный блок                     |
после:  | hdr 32 | зазор, свободен | hdr 128 | нагрузка по base + 64 | hdr 3936 | остаток |

После двух вызовов mark в куче стоят два правильных блока с заголовками и тегами. Зазор уходит в индекс как обычный свободный блок, выровненный блок занимается через обычный place. Возвращённый адрес это честный bp со своим заголовком на слово раньше, и free обрабатывает его как любой другой. О выравнивании не знает никто, кроме mallocAligned.

Тонкость одна. Зазор может получиться в 16 байт, а это меньше минимального блока: в 16 байт не влезут заголовок, тег и две ссылки списка. Тогда мы шагаем на следующий подходящий адрес, и зазор становится 16 + alignment. Отсюда и запас в wanted: худший зазор это alignment + 16, и после него в блоке размера asize + alignment + 32 остаётся не меньше asize + 16 байт, то есть выровненный блок помещается всегда. Слева от зазора всегда занятый блок: свободные соседи были слиты ещё при освобождении, так что сливать зазор ни с кем не нужно.

Хвост: четыре функции таблицы

        pub fn allocator(self: *Self) std.mem.Allocator {
            return .{ .ptr = self, .vtable = &vtable };
        }

        const vtable: std.mem.Allocator.VTable = .{
            .alloc = vtAlloc,
            .resize = vtResize,
            .remap = vtRemap,
            .free = vtFree,
        };

        fn vtAlloc(ctx: *anyopaque, len: usize, alignment: Alignment, _: usize) ?[*]u8 {
            const self: *Self = @ptrCast(@alignCast(ctx));
            const bp = self.mallocAligned(len, alignment.toByteUnits()) orelse return null;
            return @ptrFromInt(bp);
        }

        fn vtResize(ctx: *anyopaque, memory: []u8, _: Alignment, new_len: usize, _: usize) bool {
            const self: *Self = @ptrCast(@alignCast(ctx));
            return self.resizeInPlace(@intFromPtr(memory.ptr), new_len);
        }

        /// Перенос блока с копированием `std.mem.Allocator` сделает сам, когда
        /// получит `null`: вызовет `alloc`, скопирует байты и вызовет `free`.
        fn vtRemap(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ret_addr: usize) ?[*]u8 {
            return if (vtResize(ctx, memory, alignment, new_len, ret_addr)) memory.ptr else null;
        }

        fn vtFree(ctx: *anyopaque, memory: []u8, _: Alignment, _: usize) void {
            const self: *Self = @ptrCast(@alignCast(ctx));
            self.free(@intFromPtr(memory.ptr));
        }

Каждая функция таблицы начинается одной и той же строкой: const self: *Self = @ptrCast(@alignCast(ctx)). Тип состояния стёрт до *anyopaque, и вернуть его может только тот, кто знает, что там лежит. @alignCast здесь не украшение: у *anyopaque выравнивание 1, у *Self оно 8, и в безопасных режимах сборки Zig проверит адрес.

Дальше всё сводится к переводу между двумя мирами. Мир std.mem.Allocator говорит срезами и указателями, наш говорит адресами usize: @ptrFromInt(bp) в одну сторону, @intFromPtr(memory.ptr) в другую. vtFree не использует ни длину среза, ни выравнивание: размер блока написан в его заголовке. Таблица объявлена константой уровня структуры, на весь тип она одна, и allocator() отдаёт её адрес вместе с адресом экземпляра.

Из этого следует правило, на котором обжигаются все: аллокатор нельзя перемещать, пока жив хоть один std.mem.Allocator, полученный от него. Внутри лежит *Self. Верни HeapAllocator из функции по значению после вызова allocator(), и указатель повиснет.

На macOS. Весь код этого урока собирается и работает на macOS и на Linux без единого условия: регион кучи берётся у page_allocator, то есть через mmap на обеих системах, а своего sbrk мы у ядра не просим (на macOS он объявлен устаревшим и выдаёт всего 4 МБ, на Linux он общий на процесс и мешал бы системному malloc). Разница видна в двух местах. Страница на Apple Silicon 16 КБ, а не 4: поэтому testAllocatorLargeAlignment просит выравнивание 8 КБ, а page_allocator в замерах тратит по 16 КБ на каждую ячейку в 32 байта. И системный malloc, с которым мы сравниваемся через c_allocator, на macOS это libmalloc с зонами и магазинами на процессор, а на Linux с glibc это ptmalloc2 с аренами: числа в колонке c_allocator между системами не переносятся. Размер живого блока у системного аллокатора бенч спрашивает через malloc_size на macOS и через malloc_usable_size на Linux.

Явный список свободных блоков

У неявного списка один недостаток, зато фундаментальный: чтобы найти свободный блок, он идёт по всем блокам подряд, занятым тоже. Время malloc растёт вместе с числом живых объектов программы. Программа, которая держит сто тысяч мелких объектов и просит ещё один, платит за сто тысяч заголовков.

Идея раздела 9.9.13: связать свободные блоки в список и ходить только по ним. Где взять память под ссылки? Там же, где лежат сами блоки. Нагрузка свободного блока никому не нужна, и первые два её слова можно занять указателями prev и next:

занятый блок:    | hdr |            нагрузка              | ftr |
свободный блок:  | hdr | prev | next |      мусор         | ftr |
                       ^ bp

Вот откуда взялась константа min_block = 32 в heap.zig, которую в прошлом уроке пришлось принять на веру: заголовок, тег и две ссылки по 8 байт. Блок меньше не сможет стать свободным. За это платит utilization на мелких объектах: под один байт нагрузки уходит 32 байта кучи.

//! Явный список свободных блоков: двусвязный, новые блоки встают в голову
//! (LIFO). Ссылки лежат прямо в нагрузке свободного блока, она всё равно
//! никому не нужна: первое слово это `prev`, второе это `next`, ноль значит
//! «нет соседа». Отсюда и минимальный блок в 32 байта.
//!
//! Поиск теперь идёт только по свободным блокам, а не по всей куче, и
//! освобождение с граничными тегами остаётся за константу.

const std = @import("std");
const heap = @import("heap.zig");

fn prevOf(bp: usize) usize {
    return heap.get(bp);
}

fn nextOf(bp: usize) usize {
    return heap.get(bp + heap.word);
}

fn setPrev(bp: usize, value: usize) void {
    heap.put(bp, value);
}

fn setNext(bp: usize, value: usize) void {
    heap.put(bp + heap.word, value);
}

/// Двусвязный список свободных блоков. Сегрегированный аллокатор держит
/// массив таких же списков, по одному на класс размеров.
pub const List = struct {
    head: usize = 0,

    pub fn push(self: *List, bp: usize) void {
        setPrev(bp, 0);
        setNext(bp, self.head);
        if (self.head != 0) setPrev(self.head, bp);
        self.head = bp;
    }

    pub fn unlink(self: *List, bp: usize) void {
        const prev = prevOf(bp);
        const next = nextOf(bp);
        if (prev != 0) setNext(prev, next) else self.head = next;
        if (next != 0) setPrev(next, prev);
    }

    /// Первый блок списка не меньше `asize`.
    pub fn firstFit(self: *const List, asize: usize) ?usize {
        var bp = self.head;
        while (bp != 0) : (bp = nextOf(bp)) {
            if (heap.blockSize(bp) >= asize) return bp;
        }
        return null;
    }

    pub const CheckError = error{ AllocatedInList, BrokenLink, WrongClass };

    /// Обходит список, сверяет обратные ссылки и считает блоки. `min` и `max`
    /// задают допустимые размеры: явному списку подходит любой.
    pub fn check(self: *const List, min: usize, max: usize) CheckError!usize {
        var count: usize = 0;
        var prev: usize = 0;
        var bp = self.head;
        while (bp != 0) : (bp = nextOf(bp)) {
            if (heap.isAllocated(bp)) return error.AllocatedInList;
            if (prevOf(bp) != prev) return error.BrokenLink;
            const size = heap.blockSize(bp);
            if (size < min or size > max) return error.WrongClass;
            prev = bp;
            count += 1;
        }
        return count;
    }
};

pub const Index = struct {
    list: List = .{},

    pub fn reset(self: *Index) void {
        self.list = .{};
    }

    pub fn findFit(self: *Index, _: *const heap.Heap, asize: usize) ?usize {
        return self.list.firstFit(asize);
    }

    pub fn insert(self: *Index, bp: usize) void {
        self.list.push(bp);
    }

    pub fn remove(self: *Index, bp: usize) void {
        self.list.unlink(bp);
    }

    /// В списке должны быть все свободные блоки кучи и только они.
    pub fn check(self: *const Index, _: *const heap.Heap, stats: heap.Heap.Stats) !void {
        const listed = try self.list.check(heap.min_block, std.math.maxInt(usize));
        if (listed != stats.free_blocks) return error.FreeCountMismatch;
    }
};

Четыре маленькие функции в начале файла это вся структура данных: ссылки читаются и пишутся теми же heap.get и heap.put, что и теги. Ноль означает “соседа нет”: настоящий блок по нулевому адресу стоять не может.

push ставит блок в голову. Это политика LIFO: освобождённый последним блок найдётся первым. Вставка стоит четыре записи в память и не зависит от длины списка. Вместе с граничными тегами это даёт free за константу: слияние с соседями за константу, два unlink за константу, один push за константу.

unlink показывает, зачем список двусвязный. Блок выдёргивается из середины в двух случаях: его нашёл findFit или его поглощает сосед при слиянии. Во втором случае мы приходим к блоку не по списку, а по куче, через тег соседа, и предыдущего звена списка не знаем. С односвязным списком пришлось бы искать его от головы.

У LIFO есть альтернатива: держать список упорядоченным по адресам. Тогда first fit по списку выбирает те же блоки, что first fit по куче, и utilization возвращается к цифрам неявного списка. Цена: вставка перестаёт быть константой, при освобождении надо найти место в списке. В книге это описано одним абзацем, у нас это домашнее задание, а разницу в utilization ты увидишь в замерах уже сегодня: LIFO проигрывает её заметно.

Index в конце файла это переходник между списком и каркасом: пять функций, каждая в одну строку. Параметр heap в findFit списку не нужен, он знает свою голову сам.

Сегрегированные списки

Явный список сокращает обход со всех блоков до всех свободных. Но если куча раздроблена, свободных блоков тоже тысячи, и мелкие дыры в голове списка приходится перешагивать при каждом крупном запросе. Следующий шаг очевиден, когда он назван: не один список, а несколько, по классам размеров. Запрос на 100 байт даже не заглядывает в список блоков по 32.

В разделе 9.9.14 описаны три разновидности. Простое сегрегированное хранение: в каждом списке блоки строго одного размера, без разбиения и слияния, быстро и расточительно. Сегрегированные подгонки (segregated fits): в списке блоки диапазона размеров, найденный блок режется, остаток уходит в свой класс, при освобождении соседи сливаются. Так устроен malloc в glibc. И системы двойников, где размеры только степени двойки, а слияние возможно лишь с двойником по адресу. Мы пишем вторую разновидность: она берёт от нашего каркаса всё, что уже есть.

//! Сегрегированные списки: свободные блоки разложены по классам размеров,
//! на каждый класс свой двусвязный список из `explicit.zig`.
//!
//! Классы идут по степеням двойки: до 32 байт, до 64, до 128 и так далее,
//! последний класс забирает всё крупное. Поиск начинается с класса запроса
//! и поднимается выше, пока не найдёт блок. Внутри класса это first fit, но
//! так как размеры в классе отличаются не больше чем вдвое, по качеству он
//! близок к best fit по всей куче, а стоит как короткий список.

const std = @import("std");
const heap = @import("heap.zig");
const List = @import("explicit.zig").List;

pub const class_count = 16;

/// Номер класса для блока размера `size`: 32 это класс 0, 33..64 класс 1.
pub fn classOf(size: usize) usize {
    const log = std.math.log2_int_ceil(usize, @max(size, heap.min_block));
    return @min(log - std.math.log2_int(usize, heap.min_block), class_count - 1);
}

/// Наибольший размер блока в классе.
pub fn classMax(class: usize) usize {
    if (class == class_count - 1) return std.math.maxInt(usize);
    return heap.min_block << @intCast(class);
}

pub const Index = struct {
    lists: [class_count]List = @splat(.{}),

    pub fn reset(self: *Index) void {
        self.lists = @splat(.{});
    }

    pub fn findFit(self: *Index, _: *const heap.Heap, asize: usize) ?usize {
        for (self.lists[classOf(asize)..]) |*list| {
            if (list.firstFit(asize)) |bp| return bp;
        }
        return null;
    }

    pub fn insert(self: *Index, bp: usize) void {
        self.lists[classOf(heap.blockSize(bp))].push(bp);
    }

    /// Размер блока к этому моменту ещё не тронут, так что класс находится
    /// тем же вычислением, что и при вставке.
    pub fn remove(self: *Index, bp: usize) void {
        self.lists[classOf(heap.blockSize(bp))].unlink(bp);
    }

    /// Каждый свободный блок кучи лежит ровно в одном списке, и этот список
    /// соответствует его размеру.
    pub fn check(self: *const Index, _: *const heap.Heap, stats: heap.Heap.Stats) !void {
        var listed: usize = 0;
        for (&self.lists, 0..) |*list, class| {
            const min = if (class == 0) heap.min_block else classMax(class - 1) + 1;
            listed += try list.check(min, classMax(class));
        }
        if (listed != stats.free_blocks) return error.FreeCountMismatch;
    }
};

Шестьдесят строк, и половина из них комментарии. Весь файл стоит на List из explicit.zig: шестнадцать голов вместо одной.

classOf считает номер класса без циклов и таблиц: округлённый вверх двоичный логарифм размера минус логарифм минимального блока. Блок в 32 байта это класс 0, от 33 до 64 класс 1, 4096 это класс 7. Последний, пятнадцатый, забирает всё от мегабайта и выше. Логарифм в железе это одна команда подсчёта ведущих нулей, lzcnt на x86-64 и clz на arm64, так что выбор списка стоит дешевле одного промаха кэша.

findFit начинает с класса запроса и поднимается выше. Срез self.lists[classOf(asize)..] и цикл по нему: вот и весь поиск. Внутри класса это first fit, и здесь прячется главная мысль раздела. Размеры в одном классе отличаются не больше чем вдвое. Значит, первый подходящий блок из класса запроса проигрывает лучшему возможному не больше половины своего размера, а обычно гораздо меньше. First fit по сегрегированным спискам приближает best fit по всей куче, только стоит как проход по короткому списку. В замерах это видно напрямую: utilization сегрегированной версии на mixed 91.2 процента против 92.0 у настоящего best fit и 70.9 у одного списка LIFO.

Почему поиск не останавливается на классе запроса? Потому что блок из того же класса может оказаться меньше нужного (в классе от 65 до 128 лежит блок на 80, а нужен на 112), а в следующем классе подойдёт любой. Поэтому firstFit внутри первого списка честно проверяет размер, а начиная со второго срабатывает на первом же блоке.

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

Три версии в одном модуле

Корень модуля дорастает до финального вида: два новых индекса и два новых типа. Три версии аллокатора это три строки:

//! Корень модуля alloc: malloclab на Zig.

const allocator = @import("allocator.zig");

pub const heap = @import("heap.zig");
pub const implicit = @import("implicit.zig");
pub const explicit = @import("explicit.zig");
pub const segregated = @import("segregated.zig");
pub const trace = @import("trace.zig");

pub const HeapAllocator = allocator.HeapAllocator;

/// Три версии аллокатора: общий каркас, разный индекс свободных блоков.
pub const ImplicitAllocator = HeapAllocator(implicit.Index);
pub const ExplicitAllocator = HeapAllocator(explicit.Index);
pub const SegregatedAllocator = HeapAllocator(segregated.Index);

test {
    _ = heap;
    _ = implicit;
    _ = explicit;
    _ = segregated;
    _ = trace;
}

build.zig вырос: в списке шагов появился "58", добавилась цель bench. Бенч всегда собирается в ReleaseFast, какой бы режим ты ни попросил для остального: в Debug каждое обращение к срезу проверяет границы, и замер показал бы цену проверок, а не аллокатора. И только бенч линкуется с libc: она нужна ради c_allocator, остальной проект от неё свободен.

//! Сборка our-alloc.
//!
//! `zig build test` гоняет тесты всех шагов, `zig build test -Dstep=58` один
//! шаг, `zig build gen` переписывает трассы, `zig build bench` снимает
//! utilization и throughput. Бенч всегда собирается в ReleaseFast: в Debug
//! меряются проверки безопасности, а не аллокатор.

const std = @import("std");

/// Шаги проекта по номерам уроков.
const steps = [_][]const u8{ "57", "58" };

pub fn build(b: *std.Build) void {
    const target = b.standardTargetOptions(.{});
    const optimize = b.standardOptimizeOption(.{});
    const only_step = b.option([]const u8, "step", "Прогнать тесты одного шага, например -Dstep=57");

    const alloc = b.addModule("alloc", .{
        .root_source_file = b.path("src/root.zig"),
        .target = target,
        .optimize = optimize,
    });

    const gen = b.addExecutable(.{
        .name = "gen",
        .root_module = b.createModule(.{
            .root_source_file = b.path("src/gen.zig"),
            .target = target,
            .optimize = optimize,
        }),
    });
    const gen_cmd = b.addRunArtifact(gen);
    gen_cmd.setCwd(b.path("."));
    gen_cmd.has_side_effects = true;
    b.step("gen", "Переписать трассы в traces/").dependOn(&gen_cmd.step);

    const bench = b.addExecutable(.{
        .name = "bench",
        .root_module = b.createModule(.{
            .root_source_file = b.path("src/bench.zig"),
            .target = target,
            .optimize = .ReleaseFast,
            // libc нужна ради c_allocator: сравниваем и с системным malloc.
            .link_libc = true,
            .imports = &.{.{ .name = "alloc", .module = b.createModule(.{
                .root_source_file = b.path("src/root.zig"),
                .target = target,
                .optimize = .ReleaseFast,
            }) }},
        }),
    });
    b.installArtifact(bench);

    const bench_cmd = b.addRunArtifact(bench);
    bench_cmd.step.dependOn(b.getInstallStep());
    bench_cmd.setCwd(b.path("."));
    bench_cmd.has_side_effects = true;
    if (b.args) |args| bench_cmd.addArgs(args);
    b.step("bench", "Снять замеры: zig build bench -- --json bench").dependOn(&bench_cmd.step);

    const test_step = b.step("test", "Прогнать тесты всех шагов");

    // Тесты самого модуля лежат рядом с кодом.
    const module_tests = b.addTest(.{ .root_module = alloc });
    test_step.dependOn(&b.addRunArtifact(module_tests).step);

    inline for (steps) |step_name| {
        const path = "tests/step_" ++ step_name ++ ".zig";
        if (only_step == null or std.mem.eql(u8, only_step.?, step_name)) {
            const tests = b.addTest(.{
                .root_module = b.createModule(.{
                    .root_source_file = b.path(path),
                    .target = target,
                    .optimize = optimize,
                    .imports = &.{.{ .name = "alloc", .module = alloc }},
                }),
            });
            const run_tests = b.addRunArtifact(tests);
            // Тесты читают трассы из `traces/`: рабочий каталог это корень проекта.
            run_tests.setCwd(b.path("."));
            test_step.dependOn(&run_tests.step);
        }
    }
}

Проверки в три слоя

Ошибка в аллокаторе проявляется не там, где сделана. Забыл обновить тег при слиянии, а упадёт через две тысячи операций посторонний ArrayList, в который кто-то записал чужой заголовок. Отладчик покажет место падения, а не место ошибки. Поэтому в лабораторной главным инструментом считается не отладчик, а проверяльщик кучи: функция, которая обходит всё и проверяет то, что обязано быть правдой всегда. Вызываешь её после каждой операции, и ошибка ловится на той операции, которая её внесла.

Слой первый: проверяльщик

Нижнюю половину ты написал в прошлом уроке, это Heap.check в heap.zig: пролог на месте, каждый блок выровнен и не меньше минимального, заголовок равен тегу, двух свободных блоков подряд нет, обход заканчивается эпилогом ровно на границе sbrk. Он возвращает Stats со счётчиком свободных блоков.

Сегодня к нему добавилась верхняя половина, по функции check в каждом индексе. Каркас зовёт их по очереди: сначала куча, потом индекс, и индексу передаётся статистика кучи. Что проверяет список:

• в списке нет занятых блоков (AllocatedInList);
• обратная ссылка каждого звена показывает на предыдущее (BrokenLink);
• размер блока подходит списку, в котором он лежит (WrongClass);
• блоков в списках ровно столько, сколько свободных блоков насчитал обход кучи (FreeCountMismatch).

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

У неявного списка check пустой: у него нет своей структуры, сверять нечего.

Слой второй: испытания стандартной библиотеки

В std.heap лежат четыре функции, которыми стандартная библиотека проверяет собственные аллокаторы. Они публичные, и любой std.mem.Allocator можно отдать им на растерзание:

• testAllocator: сто мелких объектов через create, realloc среза со ста элементов до двадцати тысяч (данные должны пережить переезд), цепочка resize вниз, запросы нулевой длины и типов нулевого размера;
• testAllocatorAligned: выделение с каждым выравниванием от 1 до 64 и уменьшение на месте;
• testAllocatorLargeAlignment: выравнивание в половину страницы, рост и уменьшение через realloc с сохранением выравнивания;
• testAllocatorAlignedShrink: блок в две страницы с лишним уменьшается вдвое через realloc, и байты в его начале обязаны уцелеть.

Внутри каждая оборачивает твой аллокатор в std.mem.validationWrap. Эта обёртка проверяет контракт с обеих сторон: что alloc вернул адрес с обещанным выравниванием и что в resize, remap и free приходят законные длины. Бесплатный тест на четыреста строк, написанный людьми, которые знают контракт лучше всех.

Слой третий: трассы

Формат трасс и проигрыватель src/trace.zig у тебя есть с прошлого урока, но тогда тесты играли трассы сами, через голые malloc и free, а функции apply и run лежали без дела: им нужен std.mem.Allocator. Теперь он есть. Проигрыватель работает с любым аллокатором, и это решение окупится дважды: одна и та же трасса проверяет наши три версии и меряет аллокаторы стандартной библиотеки, без единой строки особого кода.

Главное в apply это параметр verify. С ним каждый блок после выделения заливается байтом, вычисленным из его номера, а перед освобождением и после realloc заливка сверяется. Проверяльщик кучи видит структуру, но не видит данные: если два блока перекрылись, теги могут быть в полном порядке. Заливка ловит именно это: сосед записал свой байт в чужую нагрузку, и apply вернёт error.Corrupted на той операции, которая это обнаружила. Параметр объявлен comptime, поэтому в бенче, где он false, от проверок не остаётся ни одной инструкции.

payloadAfter и peakPayload считают числитель utilization. Он зависит только от трассы, не от аллокатора: это сумма запрошенных размеров по живым блокам, и нас интересует её пик.

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

# short1: разбиение и все четыре случая слияния
a 0 24
a 1 100
a 2 24
a 3 500
a 4 24
f 1
f 3
f 2
a 5 600
f 0
f 4
f 5

Пять блоков подряд, потом освобождаются второй и четвёртый (оба соседа заняты, дважды), потом третий между ними: свободны оба соседа, три блока сливаются в один. Запрос на 600 байт проверяет, что слияние правда случилось: в слитый блок он помещается, а без слияния куче пришлось бы расти. Чем заканчивается трасса, какие случаи слияния срабатывают на последних трёх строках и сколько свободных блоков остаётся после каждой, проследи сам: это первое упражнение урока.

Тесты шага

//! Шаг 58: три версии аллокатора за интерфейсом `std.mem.Allocator`.
//!
//! Явный и сегрегированный списки проверяются отдельно, потом все версии
//! проходят одни и те же испытания: стандартные проверки из `std.heap`,
//! контейнеры стандартной библиотеки, трассы со сверкой содержимого и
//! пороги utilization.

const std = @import("std");
const alloc = @import("alloc");

const testing = std.testing;
const heap = alloc.heap;
const trace = alloc.trace;

const reserve = 256 << 20;

fn makeImplicit(fit: alloc.implicit.Fit) !alloc.ImplicitAllocator {
    return alloc.ImplicitAllocator.init(reserve, .{ .fit = fit });
}

/// Запускает `body(allocator, ctx)` на каждой версии: три стратегии неявного
/// списка, явный список и сегрегированные.
fn forEachVersion(ctx: anytype, comptime body: anytype) !void {
    inline for (.{ alloc.implicit.Fit.first, alloc.implicit.Fit.next, alloc.implicit.Fit.best }) |fit| {
        var a = try makeImplicit(fit);
        defer a.deinit();
        try body(&a, ctx);
    }
    {
        var a = try alloc.ExplicitAllocator.init(reserve, .{});
        defer a.deinit();
        try body(&a, ctx);
    }
    {
        var a = try alloc.SegregatedAllocator.init(reserve, .{});
        defer a.deinit();
        try body(&a, ctx);
    }
}

// ---------------------------------------------------------------------------
// Списки
// ---------------------------------------------------------------------------

test "List: LIFO, unlink из головы, середины и хвоста" {
    var h = try heap.Heap.init(1 << 20);
    defer h.deinit();
    var bp = h.extend(4 * 64).?;
    var blocks: [4]usize = undefined;
    for (&blocks) |*slot| {
        slot.* = bp;
        bp = heap.place(bp, 64) orelse break;
    }
    for (blocks) |block| heap.mark(block, 64, false);

    var list: alloc.explicit.List = .{};
    for (blocks) |block| list.push(block);
    try testing.expectEqual(blocks[3], list.head);
    try testing.expectEqual(@as(usize, 4), try list.check(heap.min_block, 1 << 20));

    list.unlink(blocks[1]); // середина
    list.unlink(blocks[3]); // голова
    list.unlink(blocks[0]); // хвост
    try testing.expectEqual(blocks[2], list.head);
    try testing.expectEqual(@as(usize, 1), try list.check(heap.min_block, 1 << 20));
    try testing.expectEqual(@as(?usize, blocks[2]), list.firstFit(64));
    try testing.expectEqual(@as(?usize, null), list.firstFit(80));
}

test "classOf: степени двойки, последний класс забирает крупное" {
    const seg = alloc.segregated;
    try testing.expectEqual(@as(usize, 0), seg.classOf(32));
    try testing.expectEqual(@as(usize, 1), seg.classOf(48));
    try testing.expectEqual(@as(usize, 1), seg.classOf(64));
    try testing.expectEqual(@as(usize, 2), seg.classOf(80));
    try testing.expectEqual(@as(usize, 7), seg.classOf(4096));
    try testing.expectEqual(@as(usize, seg.class_count - 1), seg.classOf(1 << 30));
    try testing.expectEqual(@as(usize, 64), seg.classMax(1));
}

test "проверяльщик ловит занятый блок в списке и потерянный свободный" {
    var a = try alloc.ExplicitAllocator.init(reserve, .{});
    defer a.deinit();
    const bp = a.malloc(100).?;
    const guard = a.malloc(100).?;
    _ = guard;
    a.free(bp);
    _ = try a.check();

    // блок в списке, а в заголовке он занят
    heap.mark(bp, heap.blockSize(bp), true);
    try testing.expectError(error.AllocatedInList, a.check());
    heap.mark(bp, heap.blockSize(bp), false);

    // блок свободен, а в списке его нет
    a.index.remove(bp);
    try testing.expectError(error.FreeCountMismatch, a.check());
}

test "сегрегированный индекс кладёт блок в список своего класса" {
    var a = try alloc.SegregatedAllocator.init(reserve, .{});
    defer a.deinit();
    const small = a.malloc(40).?; // блок 64, класс 1
    const guard = a.malloc(40).?;
    _ = guard;
    a.free(small);
    try testing.expectEqual(small, a.index.lists[1].head);
    _ = try a.check();

    // подсовываем блок не в тот класс
    a.index.lists[1].unlink(small);
    a.index.lists[5].push(small);
    try testing.expectError(error.WrongClass, a.check());
}

// ---------------------------------------------------------------------------
// std.mem.Allocator
// ---------------------------------------------------------------------------

test "стандартные проверки std.heap на всех версиях" {
    try forEachVersion({}, struct {
        fn body(a: anytype, _: void) !void {
            try std.heap.testAllocator(a.allocator());
            _ = try a.check();
            try std.heap.testAllocatorAligned(a.allocator());
            _ = try a.check();
            try std.heap.testAllocatorLargeAlignment(a.allocator());
            _ = try a.check();
            try std.heap.testAllocatorAlignedShrink(a.allocator());

            const stats = try a.check();
            try testing.expectEqual(@as(usize, 0), stats.allocated_bytes);
        }
    }.body);
}

test "выравнивание больше 16: адрес кратен, куча цела, free без подсказок" {
    try forEachVersion({}, struct {
        fn body(a: anytype, _: void) !void {
            const gpa = a.allocator();
            inline for (.{ 32, 64, 256, 4096, 1 << 16 }) |alignment| {
                var kept: [8][]align(alignment) u8 = undefined;
                for (&kept, 0..) |*slot, i| {
                    slot.* = try gpa.alignedAlloc(u8, .fromByteUnits(alignment), 10 + i * 37);
                    try testing.expectEqual(@as(usize, 0), @intFromPtr(slot.ptr) % alignment);
                    @memset(slot.*, @intCast(i));
                    _ = try a.check();
                }
                for (kept, 0..) |slot, i| {
                    try testing.expect(std.mem.allEqual(u8, slot, @intCast(i)));
                    gpa.free(slot);
                }
            }
            const stats = try a.check();
            try testing.expectEqual(@as(usize, 0), stats.allocated_bytes);
            try testing.expect(stats.free_blocks <= 1);
        }
    }.body);
}

test "resize и remap: рост на месте в конце кучи и в свободного соседа" {
    try forEachVersion({}, struct {
        fn body(a: anytype, _: void) !void {
            const gpa = a.allocator();
            var first = try gpa.alloc(u8, 100);
            var second = try gpa.alloc(u8, 100);
            @memset(first, 1);
            @memset(second, 2);

            // справа занятый сосед: на месте не вырасти
            try testing.expect(!gpa.resize(first, 5000));
            try testing.expectEqual(@as(?[]u8, null), gpa.remap(first, 5000));

            // последний блок кучи дорастает через sbrk
            try testing.expect(gpa.resize(second, 100_000));
            second = second.ptr[0..100_000];
            try testing.expect(std.mem.allEqual(u8, second[0..100], 2));

            // уменьшение всегда на месте, хвост возвращается в кучу
            const shrunk = gpa.remap(second, 50).?;
            try testing.expectEqual(second.ptr, shrunk.ptr);
            _ = try a.check();

            // realloc с переездом сохраняет содержимое
            const third = try gpa.alloc(u8, 100);
            first = try gpa.realloc(first, 5000);
            try testing.expect(std.mem.allEqual(u8, first[0..100], 1));

            gpa.free(first);
            gpa.free(shrunk);
            gpa.free(third);
            const stats = try a.check();
            try testing.expectEqual(@as(usize, 0), stats.allocated_bytes);
        }
    }.body);
}

test "ArrayList и StringHashMap живут на нашем аллокаторе" {
    try forEachVersion({}, struct {
        fn body(a: anytype, _: void) !void {
            const gpa = a.allocator();

            var list: std.ArrayList(u64) = .empty;
            defer list.deinit(gpa);
            for (0..10_000) |i| try list.append(gpa, i * i);
            for (list.items, 0..) |item, i| try testing.expectEqual(@as(u64, i * i), item);

            var map: std.StringHashMap(usize) = .init(gpa);
            defer {
                var keys = map.keyIterator();
                while (keys.next()) |key| gpa.free(key.*);
                map.deinit();
            }
            for (0..2000) |i| {
                const key = try std.fmt.allocPrint(gpa, "ключ-{d}", .{i});
                try map.put(key, i);
            }
            var buf: [32]u8 = undefined;
            for (0..2000) |i| {
                const key = try std.fmt.bufPrint(&buf, "ключ-{d}", .{i});
                try testing.expectEqual(@as(?usize, i), map.get(key));
            }
            _ = try a.check();
        }
    }.body);
}

test "OutOfMemory, когда регион исчерпан" {
    var a = try alloc.SegregatedAllocator.init(1 << 16, .{});
    defer a.deinit();
    try testing.expectError(error.OutOfMemory, a.allocator().alloc(u8, 1 << 20));
    const ok = try a.allocator().alloc(u8, 1000);
    a.allocator().free(ok);
    _ = try a.check();
}

// ---------------------------------------------------------------------------
// Трассы
// ---------------------------------------------------------------------------

const max_trace_bytes = 1 << 20;

fn readOps(name: []const u8) ![]trace.Op {
    var dir = try std.Io.Dir.cwd().openDir(testing.io, "traces", .{});
    defer dir.close(testing.io);
    const text = try dir.readFileAlloc(testing.io, name, testing.allocator, .limited(max_trace_bytes));
    defer testing.allocator.free(text);
    return trace.parse(testing.allocator, text);
}

/// Проигрывает трассу со сверкой содержимого и проверяльщиком каждые
/// `check_every` операций. Возвращает utilization в процентах.
fn play(a: anytype, ops: []const trace.Op, check_every: usize) !usize {
    const slots = try testing.allocator.alloc([]u8, trace.slotCount(ops));
    defer testing.allocator.free(slots);
    @memset(slots, &.{});

    for (ops, 0..) |op, i| {
        try trace.apply(a.allocator(), op, slots, true);
        if (i % check_every == 0) _ = try a.check();
    }
    const stats = try a.check();
    try testing.expectEqual(@as(usize, 0), stats.allocated_bytes);
    try testing.expect(stats.free_blocks <= 1);
    return try trace.peakPayload(testing.allocator, ops) * 100 / a.heap.size();
}

test "короткие трассы: проверяльщик после каждой операции" {
    inline for (.{ "short1.trace", "short2.trace" }) |name| {
        const ops = try readOps(name);
        defer testing.allocator.free(ops);
        try forEachVersion(ops, struct {
            fn body(a: anytype, trace_ops: []const trace.Op) !void {
                _ = try play(a, trace_ops, 1);
            }
        }.body);
    }
}

const Floor = struct { name: []const u8, explicit: usize, segregated: usize };

/// Нижние границы utilization в процентах, с запасом в несколько пунктов от
/// снятых чисел. Пороги неявного списка проверяет шаг 57.
const floors = [_]Floor{
    .{ .name = "mixed.trace", .explicit = 66, .segregated = 87 },
    .{ .name = "binary.trace", .explicit = 50, .segregated = 50 },
    .{ .name = "coalescing.trace", .explicit = 95, .segregated = 95 },
    .{ .name = "realloc.trace", .explicit = 90, .segregated = 89 },
    .{ .name = "random.trace", .explicit = 81, .segregated = 85 },
    .{ .name = "cells.trace", .explicit = 76, .segregated = 76 },
};

fn expectFloor(name: []const u8, version: []const u8, util: usize, min: usize) !void {
    if (util >= min) return;
    std.debug.print("{s}, {s}: utilization {d}% ниже порога {d}%\n", .{ name, version, util, min });
    return error.UtilizationTooLow;
}

test "длинные трассы: корректность и порог utilization" {
    for (floors) |floor| {
        const ops = try readOps(floor.name);
        defer testing.allocator.free(ops);
        {
            var a = try alloc.ExplicitAllocator.init(reserve, .{});
            defer a.deinit();
            try expectFloor(floor.name, "explicit", try play(&a, ops, 97), floor.explicit);
        }
        {
            var a = try alloc.SegregatedAllocator.init(reserve, .{});
            defer a.deinit();
            try expectFloor(floor.name, "segregated", try play(&a, ops, 97), floor.segregated);
        }
    }
}

test "неявный список проходит длинную трассу и через vtable" {
    const ops = try readOps("mixed.trace");
    defer testing.allocator.free(ops);
    var a = try makeImplicit(.first);
    defer a.deinit();
    _ = try play(&a, ops, 97);
}

test "reset возвращает пустую кучу на тех же страницах" {
    const ops = try readOps("random.trace");
    defer testing.allocator.free(ops);
    var a = try alloc.SegregatedAllocator.init(reserve, .{});
    defer a.deinit();

    const first = try play(&a, ops, 997);
    a.reset();
    try testing.expectEqual(@as(usize, 32), a.heap.size());
    try testing.expectEqual(first, try play(&a, ops, 997));
}

Вспомогательная forEachVersion гоняет одно и то же тело на всех пяти вариантах: три стратегии неявного списка, явный список, сегрегированные. Замыкание в Zig в тест не передашь, поэтому тело это функция безымянной структуры, а контекст идёт явным параметром. Тело получает a: anytype: типы у версий разные, и inline for с anytype разворачивают тест в пять копий на этапе компиляции.

На что смотреть в тестах:

• Тест про проверяльщик портит кучу нарочно, двумя способами, и требует, чтобы check назвал каждую порчу её именем. Проверяльщик, который никогда не падал, ничего не доказывает: может, он ничего и не проверяет.
• Тест про resize и remap фиксирует все четыре исхода из разбора выше: отказ при занятом соседе, рост последнего блока через sbrk, уменьшение на месте и realloc с переездом, который делает сама стандартная библиотека.
• В тесте про ArrayList и StringHashMap две тысячи ключей выделяются через allocPrint и освобождаются по одному. Это лучшая имитация настоящей программы, какая помещается в двадцать строк.
• play зовёт проверяльщик не на каждой операции, а каждые 97: проверяльщик обходит всю кучу, и на длинной трассе с проверкой после каждой операции тест шёл бы минуты. Шаг взят простым числом, чтобы не попадать в ритм трассы. На коротких трассах шаг равен единице.
• В конце каждой трассы куча обязана оказаться пустой, а свободных блоков должно быть не больше одного: всё слилось обратно.
• Пороги в floors стоят на несколько пунктов ниже снятых чисел. Это регрессионный тест на utilization: сломаешь разбиение или слияние, и тест скажет об этом раньше бенча.

Прогон шага на Apple M4 Max (macOS 26.6, Zig 0.16.0, сборка Debug; время на твоей машине будет другим, у меня она была загружена соседними задачами):

$ zig build test -Dstep=58 --summary all
Build Summary: 5/5 steps succeeded; 16/16 tests passed
test success
+- run test 3 pass (3 total) 613ms MaxRSS:2M
|  +- compile test Debug native success 10s MaxRSS:272M
+- run test 13 pass (13 total) 22s MaxRSS:272M
   +- compile test Debug native success 11s MaxRSS:296M

Три теста это тесты самого модуля (два в trace.zig и сборный в root.zig), тринадцать это шаг. Двадцать две секунды уходят почти целиком на длинные трассы неявного списка с проверяльщиком в сборке Debug. Без -Dstep=58 к ним добавятся восемнадцать тестов прошлого урока, и все они обязаны остаться зелёными.

Трассы для замеров

Шесть длинных трасс лежат в traces/ с прошлого урока, их написал zig build gen. Зёрна генератора фиксированы, файлы у тебя совпадают с моими байт в байт, поэтому и числа utilization совпадут до десятой доли процента. Каждая трасса придумана под один вопрос.

трасса	операций	что в ней	какой вопрос задаёт
mixed	6606	мелкие, средние и редкие крупные объекты вперемешку	как ведёт себя стратегия на обычной программе
binary	6000	64 и 448 через один, потом 512 в дыры от 448	что бывает, когда дыры чуть меньше запросов
coalescing	3600	два блока по 4095, потом один на 8190	работает ли слияние
realloc	4499	растущий буфер и мелкие блоки между шагами	умеет ли блок расти на месте
random	5144	размеры от 1 до 32768, выделение и освобождение пополам	худший случай без всякой структуры
cells	18300	ячейки по 32 байта, короткие строки, потом векторы	куча интерпретатора вроде zl

Все трассы заканчиваются освобождением всего живого. Это нужно не нам, а чужим аллокаторам в бенче: DebugAllocator при разрушении ругается на утечки.

Бенчмарк

//! Бенчмарк аллокаторов: `zig build bench`.
//!
//! На каждой трассе меряются две величины из malloclab:
//!
//! * utilization: пик живой нагрузки, делённый на размер кучи. У наших версий
//!   размер кучи это граница `sbrk`. Для `page_allocator` знаменатель
//!   считается точно: каждый запрос округляется до страницы. Для
//!   `c_allocator` берётся сумма `malloc_size` по живым блокам, это оценка
//!   сверху: служебные структуры системного malloc в неё не входят. У
//!   `DebugAllocator` и `smp_allocator` размер кучи снаружи не виден.
//! * throughput: операций в секунду. Трасса проигрывается сериями, берётся
//!   медиана серий. Наши версии между проходами сбрасываются через `reset`,
//!   страницы региона остаются за процессом, как в драйвере malloclab.
//!
//! С аргументом `--json <каталог>` пишутся `results.json` и
//! `allocator-bench-data.json` для виджета урока 58. `--runs N` задаёт число
//! серий (по умолчанию 9).

const std = @import("std");
const alloc = @import("alloc");

const trace = alloc.trace;

const hardware = "Apple M4 Max (aarch64, macOS 26.6), Zig 0.16.0, ReleaseFast";
const date = "2026-09-21";

const reserve = 512 << 20;
/// Серия длится не меньше этого времени: короткую трассу повторяем.
const min_series_ns: f64 = 30e6;
/// Сколько точек динамики оставить на трассу для графика.
const max_points = 200;

const trace_names = [_][]const u8{ "mixed", "binary", "coalescing", "realloc", "random", "cells" };

const Contender = enum {
    implicit_first,
    implicit_next,
    implicit_best,
    explicit,
    segregated,
    page_allocator,
    c_allocator,
    debug_allocator,
    smp_allocator,

    fn id(self: Contender) []const u8 {
        return switch (self) {
            .implicit_first => "implicit-first",
            .implicit_next => "implicit-next",
            .implicit_best => "implicit-best",
            .explicit => "explicit",
            .segregated => "segregated",
            .page_allocator => "page_allocator",
            .c_allocator => "c_allocator",
            .debug_allocator => "DebugAllocator",
            .smp_allocator => "smp_allocator",
        };
    }

    fn label(self: Contender) []const u8 {
        return switch (self) {
            .implicit_first => "неявный список, first fit",
            .implicit_next => "неявный список, next fit",
            .implicit_best => "неявный список, best fit",
            .explicit => "явный список, LIFO",
            .segregated => "сегрегированные списки",
            .page_allocator => "std.heap.page_allocator",
            .c_allocator => "std.heap.c_allocator",
            .debug_allocator => "std.heap.DebugAllocator",
            .smp_allocator => "std.heap.smp_allocator",
        };
    }

    fn isOurs(self: Contender) bool {
        return @intFromEnum(self) <= @intFromEnum(Contender.segregated);
    }
};

const contenders = std.enums.values(Contender);

const Cell = struct {
    /// Доля от 0 до 1, `null`, если размер кучи снаружи не виден.
    util: ?f64 = null,
    ops_per_sec: f64 = 0,
    /// Размер кучи в точках прореженной динамики, только у наших версий.
    heap_series: []usize = &.{},
};

const TraceResult = struct {
    name: []const u8,
    title: []const u8,
    ops: usize,
    peak_payload: usize,
    /// Номера операций, на которых снята динамика, и живая нагрузка в них.
    points: []usize,
    payload_series: []usize,
    cells: [contenders.len]Cell,
};

fn nowNs(io: std.Io, started: std.Io.Timestamp) f64 {
    return @floatFromInt(started.durationTo(std.Io.Timestamp.now(io, .awake)).nanoseconds);
}

/// Один проход трассы на аллокаторе версии `A`; куча перед проходом пустая.
fn Ours(comptime A: type) type {
    return struct {
        a: A,

        fn pass(self: *@This(), ops: []const trace.Op, slots: [][]u8) !void {
            self.a.reset();
            try trace.run(self.a.allocator(), ops, slots, false);
        }

        /// Проход с записью размера кучи в отмеченных точках.
        fn sample(self: *@This(), ops: []const trace.Op, slots: [][]u8, points: []const usize, out: []usize) !void {
            self.a.reset();
            @memset(slots, &.{});
            var next: usize = 0;
            for (ops, 0..) |op, i| {
                try trace.apply(self.a.allocator(), op, slots, false);
                if (next < points.len and points[next] == i) {
                    out[next] = self.a.heap.size();
                    next += 1;
                }
            }
        }
    };
}

/// Проход на аллокаторе стандартной библиотеки. `DebugAllocator` создаётся на
/// каждый проход заново: иначе он копит служебные таблицы между проходами.
fn passStd(who: Contender, ops: []const trace.Op, slots: [][]u8) !void {
    switch (who) {
        .page_allocator => try trace.run(std.heap.page_allocator, ops, slots, false),
        .c_allocator => try trace.run(std.heap.c_allocator, ops, slots, false),
        .smp_allocator => try trace.run(std.heap.smp_allocator, ops, slots, false),
        .debug_allocator => {
            var debug: std.heap.DebugAllocator(.{}) = .init;
            defer _ = debug.deinit();
            try trace.run(debug.allocator(), ops, slots, false);
        },
        else => unreachable,
    }
}

/// Медиана скорости по сериям. `pass` это замыкание на один проход трассы.
fn throughput(io: std.Io, runs: usize, ops_len: usize, ctx: anytype, comptime pass: anytype) !f64 {
    // Разогрев и калибровка: сколько проходов укладывается в серию.
    const warm = std.Io.Timestamp.now(io, .awake);
    try pass(ctx);
    const one = @max(nowNs(io, warm), 1);
    const reps: usize = @max(1, @as(usize, @intFromFloat(min_series_ns / one)));

    var samples: [64]f64 = undefined;
    const count = @min(runs, samples.len);
    for (samples[0..count]) |*sample| {
        const started = std.Io.Timestamp.now(io, .awake);
        for (0..reps) |_| try pass(ctx);
        const ns = nowNs(io, started);
        sample.* = @as(f64, @floatFromInt(ops_len * reps)) / ns * 1e9;
    }
    std.mem.sort(f64, samples[0..count], {}, std.sort.asc(f64));
    return samples[count / 2];
}

/// Пик суммы по живым блокам, где размер блока даёт `rounded`.
fn peakFootprint(gpa: std.mem.Allocator, ops: []const trace.Op, comptime rounded: fn (u32) usize) !usize {
    const sizes = try gpa.alloc(usize, trace.slotCount(ops));
    defer gpa.free(sizes);
    @memset(sizes, 0);
    var live: usize = 0;
    var peak: usize = 0;
    for (ops) |op| {
        const size = if (op.kind == .free) 0 else rounded(op.size);
        live = live - sizes[op.id] + size;
        sizes[op.id] = size;
        peak = @max(peak, live);
    }
    return peak;
}

fn pageRounded(size: u32) usize {
    return std.mem.alignForward(usize, size, std.heap.pageSize());
}

/// То же для системного malloc: размеры спрашиваем у него самого.
fn peakUsableC(gpa: std.mem.Allocator, ops: []const trace.Op) !?usize {
    const usable = if (@TypeOf(std.c.malloc_size) != void)
        std.c.malloc_size
    else if (@TypeOf(std.c.malloc_usable_size) != void)
        std.c.malloc_usable_size
    else
        return null;

    const slots = try gpa.alloc([]u8, trace.slotCount(ops));
    defer gpa.free(slots);
    @memset(slots, &.{});
    const sizes = try gpa.alloc(usize, slots.len);
    defer gpa.free(sizes);
    @memset(sizes, 0);

    var live: usize = 0;
    var peak: usize = 0;
    for (ops) |op| {
        try trace.apply(std.heap.c_allocator, op, slots, false);
        const size = if (op.kind == .free) 0 else usable(slots[op.id].ptr);
        live = live - sizes[op.id] + size;
        sizes[op.id] = size;
        peak = @max(peak, live);
    }
    return peak;
}

fn measureOurs(
    comptime A: type,
    index: anytype,
    gpa: std.mem.Allocator,
    io: std.Io,
    runs: usize,
    result: *const TraceResult,
    ops: []const trace.Op,
    slots: [][]u8,
) !Cell {
    var ours: Ours(A) = .{ .a = try A.init(reserve, index) };
    defer ours.a.deinit();

    const Ctx = struct { ours: *Ours(A), ops: []const trace.Op, slots: [][]u8 };
    const speed = try throughput(io, runs, ops.len, Ctx{ .ours = &ours, .ops = ops, .slots = slots }, struct {
        fn pass(ctx: Ctx) !void {
            try ctx.ours.pass(ctx.ops, ctx.slots);
        }
    }.pass);

    const series = try gpa.alloc(usize, result.points.len);
    try ours.sample(ops, slots, result.points, series);
    return .{
        .util = @as(f64, @floatFromInt(result.peak_payload)) / @as(f64, @floatFromInt(ours.a.heap.size())),
        .ops_per_sec = speed,
        .heap_series = series,
    };
}

fn measureStd(gpa: std.mem.Allocator, io: std.Io, runs: usize, who: Contender, result: *const TraceResult, ops: []const trace.Op, slots: [][]u8) !Cell {
    const Ctx = struct { who: Contender, ops: []const trace.Op, slots: [][]u8 };
    const speed = try throughput(io, runs, ops.len, Ctx{ .who = who, .ops = ops, .slots = slots }, struct {
        fn pass(ctx: Ctx) !void {
            try passStd(ctx.who, ctx.ops, ctx.slots);
        }
    }.pass);

    const footprint: ?usize = switch (who) {
        .page_allocator => try peakFootprint(gpa, ops, pageRounded),
        .c_allocator => try peakUsableC(gpa, ops),
        else => null,
    };
    return .{
        .util = if (footprint) |bytes| @as(f64, @floatFromInt(result.peak_payload)) / @as(f64, @floatFromInt(bytes)) else null,
        .ops_per_sec = speed,
    };
}

fn measureTrace(gpa: std.mem.Allocator, io: std.Io, runs: usize, name: []const u8) !TraceResult {
    var dir = try std.Io.Dir.cwd().openDir(io, "traces", .{});
    defer dir.close(io);
    const file_name = try std.fmt.allocPrint(gpa, "{s}.trace", .{name});
    const text = try dir.readFileAlloc(io, file_name, gpa, .limited(1 << 22));
    const ops = try trace.parse(gpa, text);
    const slots = try gpa.alloc([]u8, trace.slotCount(ops));

    // Первая строка трассы это её описание.
    const first_line = text[0 .. std.mem.indexOfScalar(u8, text, '\n') orelse text.len];
    const colon = std.mem.indexOf(u8, first_line, ": ") orelse 0;

    // Точки динамики: каждая stride-я операция и обязательно последняя.
    const stride = std.math.divCeil(usize, ops.len, max_points) catch unreachable;
    var points: std.ArrayList(usize) = .empty;
    var payload: std.ArrayList(usize) = .empty;
    const sizes = try gpa.alloc(u32, slots.len);
    @memset(sizes, 0);
    var live: usize = 0;
    var peak: usize = 0;
    for (ops, 0..) |op, i| {
        live = trace.payloadAfter(op, sizes, live);
        peak = @max(peak, live);
        if (i % stride == 0 or i + 1 == ops.len) {
            try points.append(gpa, i);
            try payload.append(gpa, live);
        }
    }

    var result: TraceResult = .{
        .name = name,
        .title = first_line[colon + 2 ..],
        .ops = ops.len,
        .peak_payload = peak,
        .points = points.items,
        .payload_series = payload.items,
        .cells = undefined,
    };
    for (contenders, 0..) |who, i| {
        result.cells[i] = switch (who) {
            .implicit_first => try measureOurs(alloc.ImplicitAllocator, alloc.implicit.Index{ .fit = .first }, gpa, io, runs, &result, ops, slots),
            .implicit_next => try measureOurs(alloc.ImplicitAllocator, alloc.implicit.Index{ .fit = .next }, gpa, io, runs, &result, ops, slots),
            .implicit_best => try measureOurs(alloc.ImplicitAllocator, alloc.implicit.Index{ .fit = .best }, gpa, io, runs, &result, ops, slots),
            .explicit => try measureOurs(alloc.ExplicitAllocator, alloc.explicit.Index{}, gpa, io, runs, &result, ops, slots),
            .segregated => try measureOurs(alloc.SegregatedAllocator, alloc.segregated.Index{}, gpa, io, runs, &result, ops, slots),
            else => try measureStd(gpa, io, runs, who, &result, ops, slots),
        };
    }
    return result;
}

pub fn main(init: std.process.Init) !void {
    const gpa = init.arena.allocator();
    const io = init.io;
    const args = try init.minimal.args.toSlice(gpa);

    var json_dir: ?[]const u8 = null;
    var runs: usize = 9;
    var index: usize = 1;
    while (index + 1 < args.len) : (index += 2) {
        if (std.mem.eql(u8, args[index], "--json")) {
            json_dir = args[index + 1];
        } else if (std.mem.eql(u8, args[index], "--runs")) {
            runs = try std.fmt.parseInt(usize, args[index + 1], 10);
        }
    }

    var buf: [4096]u8 = undefined;
    var writer = std.Io.File.stdout().writer(io, &buf);
    const out = &writer.interface;

    var results: [trace_names.len]TraceResult = undefined;
    for (trace_names, 0..) |name, i| {
        results[i] = try measureTrace(gpa, io, runs, name);
        const r = &results[i];
        try out.print("\n{s}: {d} операций, пик нагрузки {d} байт\n", .{ r.name, r.ops, r.peak_payload });
        // Ширину {s:<16} Zig считает в байтах, поэтому кириллица выровнена руками.
        try out.writeAll("  версия             util           оп/с\n");
        for (contenders, 0..) |who, c| {
            const cell = r.cells[c];
            try out.print("  {s:<16} ", .{who.id()});
            if (cell.util) |util| try out.print("{d:>5.1}%", .{util * 100}) else try out.writeAll("   нет");
            try out.print(" {d:>14.0}\n", .{cell.ops_per_sec});
        }
        try out.flush();
    }

    if (json_dir) |dir_path| {
        var dir = try std.Io.Dir.cwd().openDir(io, dir_path, .{});
        defer dir.close(io);
        try dir.writeFile(io, .{ .sub_path = "results.json", .data = try renderJson(gpa, &results, false) });
        try dir.writeFile(io, .{ .sub_path = "allocator-bench-data.json", .data = try renderJson(gpa, &results, true) });
        try out.print("\njson записан в {s}\n", .{dir_path});
        try out.flush();
    }
}

fn writeArray(w: *std.Io.Writer, values: []const usize) !void {
    try w.writeAll("[");
    for (values, 0..) |value, i| {
        if (i > 0) try w.writeAll(", ");
        try w.print("{d}", .{value});
    }
    try w.writeAll("]");
}

/// Сводка без динамики идёт в `results.json`, с динамикой в файл для виджета.
fn renderJson(gpa: std.mem.Allocator, results: []const TraceResult, with_series: bool) ![]const u8 {
    var text: std.Io.Writer.Allocating = .init(gpa);
    const w = &text.writer;

    try w.print("{{\n  \"hardware\": \"{s}\",\n  \"date\": \"{s}\",\n", .{ hardware, date });
    try w.writeAll("  \"allocators\": [\n");
    for (contenders, 0..) |who, i| {
        try w.print("    {{ \"id\": \"{s}\", \"label\": \"{s}\", \"ours\": {} }}{s}\n", .{
            who.id(), who.label(), who.isOurs(), if (i + 1 < contenders.len) "," else "",
        });
    }
    try w.writeAll("  ],\n  \"traces\": [\n");
    for (results, 0..) |r, ri| {
        try w.print("    {{\n      \"id\": \"{s}\",\n      \"title\": \"{s}\",\n", .{ r.name, r.title });
        try w.print("      \"ops\": {d},\n      \"peakPayload\": {d},\n", .{ r.ops, r.peak_payload });
        if (with_series) {
            try w.writeAll("      \"points\": ");
            try writeArray(w, r.points);
            try w.writeAll(",\n      \"payload\": ");
            try writeArray(w, r.payload_series);
            try w.writeAll(",\n");
        }
        try w.writeAll("      \"results\": [\n");
        for (contenders, 0..) |who, c| {
            const cell = r.cells[c];
            try w.print("        {{ \"id\": \"{s}\", \"util\": ", .{who.id()});
            if (cell.util) |util| try w.print("{d:.4}", .{util}) else try w.writeAll("null");
            try w.print(", \"opsPerSec\": {d:.0}", .{cell.ops_per_sec});
            if (with_series and cell.heap_series.len > 0) {
                try w.writeAll(", \"heap\": ");
                try writeArray(w, cell.heap_series);
            }
            try w.print(" }}{s}\n", .{if (c + 1 < contenders.len) "," else ""});
        }
        try w.print("      ]\n    }}{s}\n", .{if (ri + 1 < results.len) "," else ""});
    }
    try w.writeAll("  ]\n}\n");
    return text.written();
}

Файл длинный, но устроен просто: девять участников, шесть трасс, для каждой пары два числа.

Throughput меряет функция throughput, и в ней собраны все правила из урока про замеры. Первый проход не считается: он разогревает кэши и заодно калибрует, сколько проходов укладывается в серию длиной 30 миллисекунд, потому что один проход короткой трассы длится микросекунды и часы на нём шумят. Серий девять, в ответ идёт медиана, а не среднее: один выброс от соседнего процесса медиану не двигает. Часы .awake, монотонные. Наши версии между проходами сбрасываются через reset: куча возвращается в исходное состояние, а страницы региона остаются за процессом, так что ни mmap, ни сбои страниц в замер не попадают. Так же поступает драйвер лабораторной.

Utilization у наших версий считается честно: пик нагрузки, делённый на границу sbrk после трассы. У чужих аллокаторов размер кучи снаружи не виден, и бенч выкручивается. Для page_allocator знаменатель считается точно, без запуска: каждый запрос округляется до страницы. Для c_allocator берётся сумма malloc_size по живым блокам, это оценка сверху: служебные структуры системного malloc в неё не входят, и 100 процентов в таблице означают только, что запрошенный размер совпал с классом размера. Для DebugAllocator и smp_allocator честного способа нет, и в таблице стоит слово “нет”.

Обрати внимание на приём в peakUsableC: @TypeOf(std.c.malloc_size) != void. Функции, которых нет на целевой системе, в std.c объявлены как void, и проверка типа на этапе компиляции выбирает malloc_size на macOS и malloc_usable_size на Linux без единого if по имени системы.

С ключом --json <каталог> бенч пишет два файла: сводку и файл с динамикой размера кучи, по которому рисует виджет ниже.

$ zig build bench
...
binary: 6000 операций, пик нагрузки 576000 байт
  версия             util           оп/с
  implicit-first    53.7%          70605
  implicit-next     53.7%         920376
  implicit-best     53.7%         106833
  explicit          53.7%        5443452
  segregated        53.7%       25889685
  page_allocator     1.8%        1747439
  c_allocator      100.0%       14634076
  DebugAllocator      нет       58644632
  smp_allocator       нет       78411713

Это один сырой прогон на машине, где в тот момент собиралось ещё несколько проектов, и скорости в нём в два с лишним раза ниже, чем в таблице ниже. Запомни этот пример: числа throughput, снятые один раз, не значат ничего.

Числа

Железо: Apple M4 Max (aarch64, macOS 26.6), Zig 0.16.0, ReleaseFast, 21 сентября 2026 года. Скорость это медиана трёх прогонов бенча по девять серий в каждом. Оговорка обязательная: тихой машины у меня не было, средняя загрузка держалась около шести, и разброс скорости между прогонами доходил до 84 процентов. Порядкам величин в таблице скорости верить можно, второй значащей цифре нельзя. Utilization детерминирован: он зависит только от трассы и алгоритма, и у тебя выйдут те же цифры.

Utilization, проценты:

версия	mixed	binary	coalescing	realloc	random	cells
неявный, first fit	89.2	53.7	99.2	99.7	91.1	80.8
неявный, next fit	73.1	53.7	99.2	98.7	85.5	80.8
неявный, best fit	92.0	53.7	99.2	93.1	92.4	80.8
явный список, LIFO	70.9	53.7	99.2	94.8	85.2	80.8
сегрегированные	91.2	53.7	99.2	93.4	89.3	80.8
page_allocator	4.6	1.8	25.0	84.0	66.7	0.6
c_allocator, оценка сверху	92.3	100.0	100.0	97.9	92.3	93.9

Throughput, миллионы операций в секунду:

версия	mixed	binary	coalescing	realloc	random	cells
неявный, first fit	5.6	0.22	380	261	22	0.32
неявный, next fit	72	1.9	336	255	81	8.1
неявный, best fit	3.6	0.22	381	241	8.1	0.32
явный список, LIFO	159	12	317	216	171	28
сегрегированные	155	107	167	170	125	144
page_allocator	3.4	3.8	3.4	5.4	3.4	3.6
c_allocator	72	85	84	106	49	93
DebugAllocator	20	108	1.4	29	1.9	129
smp_allocator	162	163	209	39	153	94

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

Провал на три порядка

Начнём с самого громкого числа. На binary неявный список с first fit делает 0.22 миллиона операций в секунду, сегрегированные списки 107 миллионов. Разница почти в пятьсот раз, на cells в четыреста пятьдесят.

Причина в том, что считает неявный список. К концу первой фазы binary в куче две тысячи живых блоков. Каждый malloc на 512 байт начинает с первого блока и идёт по всем заголовкам подряд: занятый, дыра на 464 (мала), занятый, дыра (мала), и так до конца кучи, где наконец находится место. Две тысячи шагов на запрос, каждый шаг это чтение заголовка из нового места памяти, то есть ещё и промах кэша. Best fit на этой трассе равен first fit по скорости: он обходит всю кучу всегда, а first fit вынужден.

На coalescing и realloc те же версии делают сотни миллионов операций в секунду. Там в куче два или три блока, и линейный поиск по трём блокам быстрее любой умной структуры. Неявный список не медленный. Он линейный по числу живых блоков, и вся его скорость зависит от того, сколько их.

Next fit на binary в девять раз быстрее first fit: бегунок стоит в конце кучи, где и появляется свободное место, и не перечитывает начало. Но он всё ещё ходит по занятым блокам, когда место у бегунка кончается.

Явный список лечит болезнь наполовину: 12 миллионов на binary, 28 на cells. По занятым блокам он не ходит, но свободных на binary тысяча, и все они малы для запроса: дыры на 464 стоят в списке стеной, и каждый malloc на 512 перешагивает через все. Сегрегированные списки лечат целиком: дыры на 464 лежат в классе от 257 до 512, а запрос на блок 528 начинает поиск с класса от 513 до 1024 и в тот список не заглядывает вовсе.

Цена этого видна на тихих трассах. На coalescing сегрегированная версия вдвое медленнее остальных, 167 против 380: вычисление класса, шестнадцать голов вместо одной, разные линии кэша. Когда блоков три, простота выигрывает. Промышленный аллокатор выбирают не по лучшему случаю, а по отсутствию плохих, и по этой мерке сегрегированные списки единственная версия без провалов: от 107 до 170 на всех шести трассах.

53.7 у всех: внешняя фрагментация

На binary utilization одинаков у всех пяти версий, до десятой. Посчитаем его руками. Блок под 64 байта занимает 80, под 448 занимает 464, под 512 занимает 528. После первой фазы куча это тысяча пар: 80 000 и 464 000 байт. Крупные блоки освобождаются, остаётся тысяча дыр по 464 байта, разделённых живыми блоками по 80. Слиться им не с кем. Приходит тысяча запросов на блок 528, ни в одну дыру он не лезет, и куча вырастает ещё на 528 000. Итог: 1 072 000 байт кучи при пике нагрузки 64 000 + 512 000 = 576 000. Делим: 53.7 процента.

Это внешняя фрагментация в чистом виде: 464 000 свободных байт, и ни один запрос ими воспользоваться не может. Стратегия поиска здесь бессильна, потому что искать нечего: подходящего блока в куче нет. Помочь могли бы только два средства, и оба нам недоступны. Первое: передвинуть живые блоки и сомкнуть дыры, но в C и Zig адрес блока известен программе, и двигать его нельзя. Второе: угадать будущее и селить блоки по 64 отдельно от блоков по 448. Вот это промышленные аллокаторы как раз делают, и ниже мы к этому вернёмся: у них на binary дыр такого вида не возникает вообще.

80.8 у всех: внутренняя фрагментация

На cells версии снова сходятся до десятой, но причина другая. Ячейка в 32 байта занимает блок в 48: заголовок и тег забирают треть. Если бы трасса состояла из одних ячеек, utilization упёрлась бы в 66.7 процента. До 80.8 её поднимают векторы во второй фазе: у блока в 2 КБ те же 16 служебных байт это меньше процента.

Это внутренняя фрагментация, и она от стратегии тоже не зависит: служебные байты одинаковы у всех версий. В книге описана оптимизация, которая срезает её часть: граничный тег нужен только свободным блокам (по нему сосед справа узнаёт, можно ли сливаться влево), а занятому достаточно одного бита в заголовке следующего блока. Сделай её в домашнем задании, но сначала посчитай на бумаге: блоку под 24 байта она сэкономит 16 байт из 48, а блоку под 32 не сэкономит ничего, потому что 32 + 8 при выравнивании 16 это всё те же 48. Объектам одного размера, которых миллионы, по-настоящему помогает другое: пул без заголовков вообще. Именно так мы сегодня устроим кучу zl.

Почему LIFO теряет память

На mixed явный список набирает 70.9 процента против 89.2 у first fit по куче, хотя внутри списка это тот же first fit. Разница в порядке. Неявный список перебирает блоки по адресам и селит новые объекты в начало кучи, плотно; хвост кучи остаётся свободным одним куском, и крупный запрос находит его целым. LIFO первым предлагает блок, освобождённый только что, где бы он ни лежал. Мелкий запрос откусывает от свежей крупной дыры, остаток снова встаёт в голову, следующий мелкий запрос откусывает от него. Крупные блоки перемалываются в мелочь раньше, чем понадобятся целыми, и когда приходит крупный запрос, куча растёт.

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

Сегрегированные списки возвращают 91.2, и дело не в порядке внутри списка (там тот же LIFO), а в том, что мелкий запрос идёт в список мелких блоков и крупные не трогает. Best fit, 92.0, это верхняя планка для нашей раскладки на этой трассе: лучше него сегрегация быть не обязана, она его приближает.

На realloc порядок обратный: first fit 99.7, best fit 93.1. Буфер растёт в конце кучи, а мелкие блоки между шагами first fit селит в начало, в дыру от предыдущего мелкого блока, и буферу никто не мешает дорастать через sbrk. Best fit и сегрегированные списки находят мелкому блоку место получше где придётся, иногда прямо за буфером, и тогда буферу приходится переезжать, оставляя за собой дыру.

Рядом с аллокаторами стандартной библиотеки

page_allocator это прямой mmap на каждый запрос и munmap на каждое освобождение. Отсюда ровные 3 до 5 миллионов операций в секунду на любой трассе: это цена системного вызова на этой машине, примерно 300 наносекунд, и от размера запроса она не зависит. Отсюда же 0.6 процента на cells: страница в 16 КБ на ячейку в 32 байта. Это не недостаток, а назначение: page_allocator задуман как поставщик больших регионов для других аллокаторов. Наш Region берёт у него память ровно один раз.

c_allocator это системный malloc, на macOS libmalloc. Он ровный, от 49 до 106, без провалов и без рекордов: внутри классы размеров и кэши на процессор. Колонка utilization у него завышена по построению, сравнивать её с нашей нельзя.

DebugAllocator ведёт себя странно, пока не знаешь устройства: 129 на cells и 1.4 на coalescing. Мелкие запросы он раскладывает по корзинам с классами размеров, а всё крупнее корзины отправляет прямо в page_allocator. Блоки по 4095 и 8190 это системный вызов на каждый, отсюда скорость page_allocator, делённая ещё пополам на собственный учёт. Медленным его считают из-за сборки Debug, где он на каждое выделение снимает трассу стека; в ReleaseFast трасс нет. Его сила не в скорости: он ловит двойное освобождение, утечки и никогда не выдаёт один адрес дважды, чтобы висячий указатель упал, а не тихо прочитал чужие данные.

smp_allocator это быстрый аллокатор общего назначения из стандартной библиотеки, рассчитанный на потоки: у каждого потока свои свободные списки по классам размеров со степенями двойки, память нарезается из кусков по 64 КБ, а всё крупнее куска уходит в mmap напрямую. На пяти трассах он держится рядом с нашей сегрегированной версией, от 94 до 209. Провал на realloc, 39, того же рода, что у DebugAllocator: буфер быстро перерастает 64 КБ, и каждый его рост становится системным вызовом.

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

• у нас один поток, и ни одной атомарной операции или замка на пути выделения;
• мы никогда не возвращаем память системе: граница sbrk только растёт, и программа, которая на секунду заняла гигабайт, держит его до выхода;
• у нас нет защиты от двойного освобождения, от освобождения чужого адреса, от переполнения соседнего блока: заголовки лежат прямо рядом с данными, и запись на один байт за границу портит кучу;
• мы мерили на трассах, которые сами и придумали.

Как устроены jemalloc и mimalloc

Лабораторный аллокатор и промышленный различаются не качеством кода, а вопросом, на который отвечают. Наш вопрос: как найти свободный блок. Их вопрос: как сделать, чтобы тридцать два потока выделяли память одновременно и не ждали друг друга, а память возвращалась системе. Ответы у двух самых известных открытых аллокаторов разные, и оба стоит знать. Рассказываю по первоисточникам, они в ресурсах урока: доклад Джейсона Эванса о jemalloc с BSDCan 2006 и технический отчёт Microsoft Research о mimalloc 2019 года.

Общее: классы размеров без заголовков

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

Следствий три. Внутренняя фрагментация от заголовков исчезает, остаётся только округление до класса; классов много (у jemalloc по четыре на каждое удвоение размера), и округление теряет в худшем случае около 20 процентов, в среднем заметно меньше. Наша трасса binary перестаёт быть ловушкой: объекты по 64 и по 448 живут в разных кусках, дыры от 448 идеально подходят следующим 448, а запросам на 512 отведено своё место. И запись за границу объекта портит соседний объект, но не структуры аллокатора: метаданные лежат отдельно.

Слияния соседних блоков в таком устройстве нет вовсе. Кусок либо занят своим классом, либо опустел целиком и возвращается в общий котёл. Платят за это другой фрагментацией: программа, которая выделила миллион объектов по 48 байт и освободила все, кроме каждого сотого, держит все куски занятыми.

jemalloc: арены и кэш потока

jemalloc родился как malloc для FreeBSD, потом стал аллокатором Firefox и серверов Facebook. Главная идея доклада 2006 года это арены: вместо одной кучи с одним замком несколько независимых куч, по умолчанию вчетверо больше числа процессоров. Поток при первом выделении приписывается к арене по кругу и дальше ходит только в неё. Два потока сталкиваются, только если попали в одну арену, а при таком запасе это редкость.

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

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

mimalloc: свободный список на каждую страницу

mimalloc написан в Microsoft Research для сред исполнения языков Koka и Lean, где программы выделяют очень много очень мелких объектов. Его идея вынесена в заголовок отчёта: шардирование свободных списков. Вместо одного списка на класс размера, как у нас, свой список у каждой страницы mimalloc (так он называет кусок в 64 КБ, отданный одному классу).

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

Куча у каждого потока своя, и выделение идёт без замков вообще. Трудный случай это освобождение чужим потоком: объект выделил один поток, а освобождает другой. Для него у каждой страницы заведён отдельный список, куда чужие потоки добавляют объекты одной атомарной операцией сравнения с обменом. Хозяин страницы забирает этот список целиком, тоже одной операцией, когда его собственный список опустел. Итого у страницы три списка: откуда выделяем, куда освобождаем сами, куда освобождают чужие. Быстрый путь malloc в отчёте это считанные инструкции с одной проверкой.

Что из этого забрать себе. Классы размеров у нас уже есть, но мы по ним раскладываем свободные блоки, а они раскладывают память заранее. Свободный список через нагрузку есть и у нас, и у mimalloc. Арен, кэшей потока и атомарных списков у нас нет, и появятся они не раньше блока про потоки. Зато теперь, когда в профиле серверной программы ты увидишь je_malloc или mi_malloc, ты знаешь, что внутри.

Шаг проекта: куча zl на своём аллокаторе

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

Таблица замеров подсказывает, что делать. Для ячеек общий аллокатор плох при любой стратегии: на трассе 16 служебных байт на 32 полезных, а у ячейки zl в 16 байт служебных столько же, сколько полезных; вдобавок поиск, разбиение и слияние там, где все блоки одинаковы и резать нечего. Объектам одного размера нужен пул: один регион, нарезанный на равные ячейки, и свободный список через сами ячейки. Это простое сегрегированное хранение из раздела 9.9.14, доведённое до предела: класс размера один. Ровно этот приём применяют к мелким объектам jemalloc и mimalloc.

А вот сам регион пула, битовые карты, имена символов и таблица глобальных имён имеют разные размеры, и они идут через std.mem.Allocator. Сюда и встаёт аллокатор, который ты сегодня написал. Строк и векторов в нашем диалекте нет; появись они завтра, они пошли бы той же дорогой, мимо пула, в сегрегированные списки.

Зависимости между проектами при этом нет. zl знает только интерфейс: Vm.initWith(gpa, options). Какой аллокатор стоит за gpa, ему безразлично, и это лучшая иллюстрация того, зачем нужна таблица из четырёх функций.

heap.zig: пул ячеек

Новый файл. Раньше Heap жил в value.zig и был обёрткой над ареной; теперь это отдельный модуль.

//! Куча zl: пул cons-ячеек одним регионом.
//!
//! До этого шага ячейки жили на арене и не освобождались никогда. Теперь
//! куча своя. Весь пул это один непрерывный массив ячеек, взятый у внешнего
//! аллокатора одним запросом. Свободные ячейки связаны в список, и отдельной
//! памяти под него не нужно: свободной ячейке её `cdr` ни к чему, поэтому в
//! нём лежит ссылка на следующую свободную. Выделение это снять голову списка,
//! освобождение это надеть голову обратно, то и другое за O(1).
//!
//! Внешний аллокатор это параметр `std.mem.Allocator`. Сюда встаёт аллокатор
//! из malloclab: через него приходят регион пула, битовые карты, имена
//! символов и таблица глобальных имён, то есть всё, у чего размер переменный.
//! Ячейкам общий аллокатор не нужен: они одного размера, и пул обслуживает их
//! быстрее и без заголовков.
//!
//! Замыкание тоже сложено из ячеек: `(параметры . (тело . окружение))`. Так
//! в куче остаётся один вид объектов, и сборщику мусора не придётся знать
//! ни про какие другие.

const std = @import("std");

const value = @import("value.zig");

pub const Cell = value.Cell;
const Value = value.Value;

const Allocator = std.mem.Allocator;
const BitSet = std.DynamicBitSetUnmanaged;

pub const Options = struct {
    /// Сколько ячеек в пуле. Ячейка это 16 байт, так что по умолчанию 8 МБ.
    /// Меньше нельзя: мусор пока никто не собирает, `fib.zl` за один прогон
    /// съедает больше ста тысяч ячеек, а хвостовой цикл из тестов байткода
    /// почти полмиллиона.
    cells: usize = 1 << 19,
};

/// Снимок состояния пула.
pub const Stats = struct {
    capacity: usize,
    used: usize,
    free: usize,
    /// Наибольшее число одновременно занятых ячеек за жизнь кучи.
    peak: usize,
    /// Сколько непрерывных свободных участков в регионе.
    free_runs: usize,
    /// Длина самого длинного из них, в ячейках.
    largest_free_run: usize,

    /// Доля свободной памяти, которая лежит вне самого длинного участка.
    /// Ноль означает, что всё свободное место это один кусок. Выделению
    /// ячеек раздробленность не мешает, они все одного размера, зато от неё
    /// зависит, лягут ли соседние ячейки нового списка в одну линию кэша.
    pub fn fragmentation(self: Stats) f64 {
        if (self.free == 0) return 0;
        const largest: f64 = @floatFromInt(self.largest_free_run);
        const free: f64 = @floatFromInt(self.free);
        return 1.0 - largest / free;
    }
};

pub const Heap = struct {
    backing: Allocator,
    /// Регион пула: все ячейки кучи, занятые и свободные вперемешку.
    cells: []Cell,
    /// Голова свободного списка. Следующая свободная лежит в `cdr` головы.
    free_list: ?*Cell = null,
    /// Бит на ячейку: занята ли она. Свободный список отвечает на вопрос
    /// "какую ячейку отдать", а карта на вопрос "занята ли вот эта".
    live: BitSet,

    used: usize = 0,
    peak: usize = 0,
    /// Сколько пар и замыканий выделено за жизнь кучи.
    cells_allocated: usize = 0,
    closures_allocated: usize = 0,

    pub fn init(backing: Allocator, options: Options) Allocator.Error!Heap {
        const cells = try backing.alloc(Cell, options.cells);
        errdefer backing.free(cells);
        var live: BitSet = try .initEmpty(backing, options.cells);
        errdefer live.deinit(backing);

        var self: Heap = .{ .backing = backing, .cells = cells, .live = live };
        self.threadFreeList();
        return self;
    }

    pub fn deinit(self: *Heap) void {
        self.live.deinit(self.backing);
        self.backing.free(self.cells);
        self.* = undefined;
    }

    /// Продеть свободный список через все незанятые ячейки, от старших адресов
    /// к младшим: тогда голова списка это первая свободная ячейка региона,
    /// и подряд выделенные ячейки лежат в памяти подряд.
    pub fn threadFreeList(self: *Heap) void {
        self.free_list = null;
        var i = self.cells.len;
        while (i > 0) {
            i -= 1;
            if (!self.live.isSet(i)) self.pushFree(&self.cells[i]);
        }
    }

    fn pushFree(self: *Heap, cell: *Cell) void {
        cell.* = .{
            .car = .nil,
            .cdr = if (self.free_list) |next| .fromCell(next) else .nil,
        };
        self.free_list = cell;
    }

    /// Снять ячейку с головы свободного списка.
    fn take(self: *Heap) Allocator.Error!*Cell {
        const cell = self.free_list orelse return error.OutOfMemory;
        self.free_list = if (cell.cdr.isCons()) cell.cdr.asCell() else null;
        self.live.set(self.indexOf(cell));
        self.used += 1;
        self.peak = @max(self.peak, self.used);
        return cell;
    }

    /// Вернуть ячейку в пул. Вызывающий отвечает за то, что на неё никто
    /// больше не ссылается.
    pub fn release(self: *Heap, cell: *Cell) void {
        const index = self.indexOf(cell);
        std.debug.assert(self.live.isSet(index));
        self.live.unset(index);
        self.used -= 1;
        self.pushFree(cell);
    }

    /// Номер ячейки в регионе.
    pub fn indexOf(self: *const Heap, cell: *const Cell) usize {
        return (@intFromPtr(cell) - @intFromPtr(self.cells.ptr)) / @sizeOf(Cell);
    }

    /// Ячейка пула, внутрь которой показывает адрес, или null, если адрес
    /// лежит вне региона.
    pub fn cellAt(self: *Heap, addr: usize) ?*Cell {
        const base = @intFromPtr(self.cells.ptr);
        if (addr < base or addr >= base + self.cells.len * @sizeOf(Cell)) return null;
        return &self.cells[(addr - base) / @sizeOf(Cell)];
    }

    pub fn cons(self: *Heap, a: Value, d: Value) Allocator.Error!Value {
        const cell = try self.take();
        cell.* = .{ .car = a, .cdr = d };
        self.cells_allocated += 1;
        return .fromCell(cell);
    }

    /// Замыкание это две ячейки: `(параметры . (тело . окружение))`.
    pub fn closure(self: *Heap, params: Value, body: Value, env: Value) Allocator.Error!Value {
        const rest = try self.cons(body, env);
        const head = try self.cons(params, rest);
        self.closures_allocated += 1;
        return .fromClosure(head.asCell());
    }

    /// Собрать список из готового среза значений, справа налево.
    pub fn list(self: *Heap, items: []const Value) Allocator.Error!Value {
        var acc: Value = .nil;
        var i = items.len;
        while (i > 0) {
            i -= 1;
            acc = try self.cons(items[i], acc);
        }
        return acc;
    }

    pub fn stats(self: *const Heap) Stats {
        var runs: usize = 0;
        var largest: usize = 0;
        var run: usize = 0;
        for (0..self.cells.len) |i| {
            if (self.live.isSet(i)) {
                run = 0;
                continue;
            }
            if (run == 0) runs += 1;
            run += 1;
            largest = @max(largest, run);
        }
        return .{
            .capacity = self.cells.len,
            .used = self.used,
            .free = self.cells.len - self.used,
            .peak = self.peak,
            .free_runs = runs,
            .largest_free_run = largest,
        };
    }
};

const testing = std.testing;

test "свежий пул это один свободный участок, и ячейки выдаются подряд" {
    var heap: Heap = try .init(testing.allocator, .{ .cells = 8 });
    defer heap.deinit();

    const a = try heap.cons(.fromFixnum(1), .nil);
    const b = try heap.cons(.fromFixnum(2), .nil);
    try testing.expectEqual(@as(usize, 0), heap.indexOf(a.asCell()));
    try testing.expectEqual(@as(usize, 1), heap.indexOf(b.asCell()));

    const s = heap.stats();
    try testing.expectEqual(@as(usize, 2), s.used);
    try testing.expectEqual(@as(usize, 1), s.free_runs);
    try testing.expectEqual(@as(usize, 6), s.largest_free_run);
    try testing.expectEqual(@as(f64, 0), s.fragmentation());
}

test "освобождённая ячейка возвращается первой" {
    var heap: Heap = try .init(testing.allocator, .{ .cells = 4 });
    defer heap.deinit();

    const a = try heap.cons(.fromFixnum(1), .nil);
    _ = try heap.cons(.fromFixnum(2), .nil);
    heap.release(a.asCell());
    const c = try heap.cons(.fromFixnum(3), .nil);
    try testing.expectEqual(a.asCell(), c.asCell());
}

Сравни с explicit.zig: идея та же, свободный блок хранит ссылку списка в собственной пустующей нагрузке. Только всё проще. Список односвязный: ячейку никогда не выдёргивают из середины, потому что слияния нет, сливать ячейки одного размера незачем. Поиска нет: любая свободная ячейка подходит любому запросу, берём голову. Заголовков нет: размер ячейки знает тип. take и pushFree это по три записи в память.

Свободная ячейка выглядит как обычная пара: в car лежит nil, в cdr значение с тегом пары, которое показывает на следующую свободную. Отдельного представления для ссылки списка заводить не пришлось. У последней ячейки в cdr тоже nil, и проверка cell.cdr.isCons() в take отличает конец списка.

threadFreeList продевает список от старших адресов к младшим, и голова списка оказывается ячейкой с номером 0. Порядок выбран ради локальности: ячейки, выделенные подряд, лежат в памяти подряд, и список из десяти элементов, построенный одним вызовом list, занимает 160 байт подряд, две с половиной линии кэша, а не десять случайных.

Зачем рядом со списком битовая карта live? Список отвечает на вопрос “какую ячейку отдать”, карта на вопрос “занята ли вот эта”. Сегодня карта нужна для assert в release (двойное освобождение ловится сразу) и для статистики. В следующем уроке без неё будет нельзя: сборщик мусора обязан отличать занятую ячейку от свободной, глядя только на адрес.

Замыкание теперь сложено из двух ячеек: (параметры . (тело . окружение)). Раньше это была отдельная структура из трёх полей, и в куче жили объекты двух видов. С одним видом объектов пул один, и сборщику в следующем уроке не придётся знать ни про что, кроме пар.

Раздробленность: что меряем и зачем

Внешней фрагментации в смысле malloc у пула нет: не бывает запроса, которому не подошла бы свободная ячейка. Но порядок свободных ячеек всё равно важен. Когда свободное место это один сплошной участок, новый список ляжет в память подряд. Когда оно рассыпано по одной ячейке между живыми, соседние звенья нового списка окажутся в разных концах пула, и каждый шаг по cdr станет промахом кэша. Это та самая причина, по которой mimalloc дробит свободные списки по страницам.

Stats.fragmentation меряет это одним числом: доля свободных ячеек, которые лежат вне самого длинного свободного участка. Ноль означает, что всё свободное место это один кусок. Пример из тестов: заняты все восемь ячеек, освободили нулевую, вторую, четвёртую и шестую. Свободных четыре, участков четыре, самый длинный из одной ячейки: раздробленность 1 - 1/4 = 0.75. Освободили ещё первую: участки 0..2, 4 и 6, самый длинный из трёх, свободных пять, раздробленность 1 - 3/5 = 0.4.

value.zig: замыкание как вид на две ячейки

В value.zig три правки. Heap отсюда уехал. Значение с тегом замыкания теперь показывает на голову двух ячеек, а не на отдельную структуру. И сама структура Closure больше не объект кучи, а вид, который собирается на лету, поэтому align(16) ей больше не нужен: её адрес никуда не попадает.

/// Замыкание: список параметров, тело и захваченное окружение.
///
/// В куче это не отдельный объект, а две ячейки `(параметры . (тело .
/// окружение))`, и значение с тегом замыкания показывает на первую из них.
/// Эта структура только вид на них: её собирает `asClosure`.
pub const Closure = struct {
    params: Value,
    body: Value,
    env: Value,
};

    pub fn fromClosure(head: *Cell) Value {
        return .{ .bits = @intFromPtr(head) | closure_kind };
    }

    pub fn asClosure(self: Value) Closure {
        std.debug.assert(self.tag() == .closure);
        const head: *Cell = @ptrFromInt(self.bits & ~tag_mask);
        const rest = head.cdr.asCell();
        return .{ .params = head.car, .body = rest.car, .env = rest.cdr };
    }

    /// Ячейка кучи, на которую показывает значение: пара или голова замыкания.
    /// У атомов ячейки нет.
    pub fn heapCell(self: Value) ?*Cell {
        return switch (self.tag()) {
            .cons, .closure => @ptrFromInt(self.bits & ~tag_mask),
            else => null,
        };
    }

asClosure возвращает Closure по значению: тег снимается той же маской, что и раньше, а три поля читаются из двух ячеек. Код интерпретатора этого не заметил, callee.asClosure().body пишется так же, как раньше. Вот для чего в шапке value.zig с первого дня записано правило: остальной код обращается к значению только через методы и ни разу не разбирает тегированный указатель напрямую. Представление поменялось, а eval.zig остался нетронутым. Новый метод heapCell отвечает, на какую ячейку кучи показывает значение, пара это или замыкание; у атомов ячейки нет. Теги двух видов разные, а ячейка одна и та же, поэтому маска снимает тег в обоих случаях.

vm.zig: аллокатор и настройки снаружи

У машины появился второй конструктор. Старый init зовёт его с настройками по умолчанию:

    pub fn init(gpa: std.mem.Allocator) std.mem.Allocator.Error!Vm {
        return initWith(gpa, .{});
    }

    /// То же с настройками кучи. Аллокатор один на всё: из него приходят
    /// регион пула, имена символов и таблица глобальных имён.
    pub fn initWith(gpa: std.mem.Allocator, options: heap_mod.Options) std.mem.Allocator.Error!Vm {
        var vm: Vm = .{
            .gpa = gpa,
            .heap = try .init(gpa, options),
            .syms = .init(gpa),
            .sym = undefined,
        };
        errdefer vm.deinitPartial();

Дальше функция идёт как прежде: знакомые символы, константы nil и t, примитивы. Аллокатор один на всё: из него приходят регион пула, битовая карта, имена символов и таблица глобальных имён. В src/root.zig добавляется строка pub const heap = @import("heap.zig");, в build.zig номер шага: const steps = [_][]const u8{ "05", "06", "13", "14", "15", "19", "56", "58" };.

main.zig: ключи --cells и --stats

//! Программа `zl`.
//!
//!   zl                          диалог
//!   zl <file.zl>                исполнить файл и напечатать значение последней формы
//!   zl --cells 256 <file.zl>    то же в пуле на 256 ячеек
//!   zl --stats <file.zl>        после ответа напечатать статистику кучи
//!   zl --exec loop <file.zl>    исполнитель: tree (по умолчанию), loop или labeled

const std = @import("std");

const bytecode = @import("bytecode.zig");
const eval = @import("eval.zig");
const zl_heap = @import("heap.zig");
const printer = @import("printer.zig");
const repl = @import("repl.zig");
const Value = @import("value.zig").Value;
const Vm = @import("vm.zig").Vm;

/// Кто исполняет программу: обход дерева или байткод под одним из диспетчеров.
const Executor = enum { tree, loop, labeled };

/// Больше файла с программой на zl нам не нужно.
const max_source_bytes = 1 << 20;

pub fn main(init: std.process.Init) !void {
    var debug_allocator: std.heap.DebugAllocator(.{}) = .init;
    defer _ = debug_allocator.deinit();
    const gpa = debug_allocator.allocator();

    const args = try init.minimal.args.toSlice(init.arena.allocator());

    // writerStreaming, а не writer: позиционный писатель начинает с нулевого
    // смещения и затирает файл при перенаправлении `zl prog.zl > out.txt`.
    var out_buf: [4096]u8 = undefined;
    var stdout = std.Io.File.stdout().writerStreaming(init.io, &out_buf);
    const out = &stdout.interface;

    // Ключи идут перед именем файла, в любом порядке.
    var cells: usize = (zl_heap.Options{}).cells;
    var want_stats = false;
    var executor: Executor = .tree;
    var rest = args[1..];
    while (rest.len > 0 and std.mem.startsWith(u8, rest[0], "--")) {
        if (std.mem.eql(u8, rest[0], "--stats")) {
            want_stats = true;
            rest = rest[1..];
        } else if (std.mem.eql(u8, rest[0], "--cells") and rest.len > 1) {
            cells = std.fmt.parseInt(usize, rest[1], 10) catch {
                try out.print("--cells ждёт число, а получил {s}\n", .{rest[1]});
                try out.flush();
                return error.BadArgument;
            };
            rest = rest[2..];
        } else if (std.mem.eql(u8, rest[0], "--exec") and rest.len > 1) {
            executor = std.meta.stringToEnum(Executor, rest[1]) orelse {
                try out.print("--exec ждёт tree, loop или labeled, а получил {s}\n", .{rest[1]});
                try out.flush();
                return error.BadArgument;
            };
            rest = rest[2..];
        } else {
            try out.print("неизвестный ключ {s}\n", .{rest[0]});
            try out.flush();
            return error.BadArgument;
        }
    }

    var vm: Vm = try .initWith(gpa, .{ .cells = cells });
    defer vm.deinit();
    vm.out = out;

    if (rest.len == 0) {
        var in_buf: [4096]u8 = undefined;
        var stdin = std.Io.File.stdin().readerStreaming(init.io, &in_buf);
        try repl.run(&vm, &stdin.interface, out);
        return;
    }

    const path = rest[0];
    const source = std.Io.Dir.cwd().readFileAlloc(init.io, path, gpa, .limited(max_source_bytes)) catch |err| {
        try out.print("не читается {s}: {t}\n", .{ path, err });
        try out.flush();
        return err;
    };
    defer gpa.free(source);

    var machine: bytecode.Machine = .init(&vm);
    defer machine.deinit();

    const result = run(&machine, source, executor) catch |err| {
        try out.print("ошибка: {t}\n", .{err});
        try out.flush();
        return err;
    };

    try printer.write(out, &vm, result);
    try out.writeByte('\n');
    if (want_stats) try printStats(out, &vm);
    try out.flush();
}

fn run(machine: *bytecode.Machine, source: []const u8, executor: Executor) !Value {
    return switch (executor) {
        .tree => eval.evalSource(machine.vm, source),
        .loop => machine.runSource(source, .loop),
        .labeled => machine.runSource(source, .labeled),
    };
}

fn printStats(out: *std.Io.Writer, vm: *const Vm) !void {
    const s = vm.heap.stats();
    try out.print(
        \\пул: {d} ячеек, {d} КБ
        \\занято: {d}, свободно: {d}, пик: {d}
        \\выделено за прогон: {d}
        \\свободных участков: {d}, самый длинный: {d}, раздробленность: {d:.2}
        \\
    , .{
        s.capacity,        s.capacity * @sizeOf(zl_heap.Cell) / 1024,
        s.used,            s.free,
        s.peak,            vm.heap.cells_allocated,
        s.free_runs,       s.largest_free_run,
        s.fragmentation(),
    });
}

Ключи разбираются руками, в том же цикле по срезу аргументов, где с урока про циклы и switch живёт --exec: их три, и библиотека тут не нужна. Значение по умолчанию для --cells берётся из самой структуры настроек, (zl_heap.Options{}).cells, чтобы число не было написано в двух местах. По умолчанию пул на 524 288 ячеек, 8 МБ. Меньше нельзя, пока мусор никто не собирает: fib.zl съедает сто семьдесят пять тысяч ячеек, а тест хвостового вызова из урока про циклы почти полмиллиона.

Прогоны на Apple M4 Max, macOS 26.6:

$ zl --stats programs/fib.zl
6765
пул: 524288 ячеек, 8192 КБ
занято: 175159, свободно: 349129, пик: 175159
выделено за прогон: 175159
свободных участков: 1, самый длинный: 349129, раздробленность: 0.00

$ zl --cells 65536 programs/fib.zl
ошибка: OutOfMemory
error: OutOfMemory

$ zl --stats programs/list-sum.zl
500500
пул: 524288 ячеек, 8192 КБ
занято: 22075, свободно: 502213, пик: 22075
выделено за прогон: 22075
свободных участков: 1, самый длинный: 502213, раздробленность: 0.00

$ zl --cells 1024 --stats programs/eval.zl
(a c d)
пул: 1024 ячеек, 16 КБ
занято: 760, свободно: 264, пик: 760
выделено за прогон: 760
свободных участков: 1, самый длинный: 264, раздробленность: 0.00

Посмотри на первую пару прогонов внимательно. fib.zl считает двадцатое число Фибоначчи. Живых ячеек в каждый момент у него несколько сотен: глубина рекурсии двадцать, на каждом уровне кадр окружения и список аргументов. А занято в конце 175 159, пик равен занятому, и строка “выделено за прогон” равна занятому: ни одна ячейка не вернулась. Программе, которой хватило бы нескольких килобайт, мало мегабайта. Вторая строка error: OutOfMemory это сам Zig: main вернул ошибку, и стартовый код печатает её имя. Раздробленность при этом образцовая, 0.00, и понятно почему: release никто не зовёт, свободное место это нетронутый хвост пула.

Куча у нас теперь своя, а освобождать некому. В C это была бы обязанность программиста. В Лиспе программист про память не знает ничего, и ячейки за него должен возвращать интерпретатор. Это тема следующего урока.

Свой аллокатор вместо DebugAllocator

В main.zig за gpa стоит DebugAllocator: он ловит утечки, и для программы в разработке это правильный выбор. Чтобы поставить на его место аллокатор из our-alloc, хватит трёх строк. Скопируй каталог our-alloc/src в zl/src/alloc (или подключи модулем в build.zig, если предпочитаешь порядок) и замени начало main:

const alloc = @import("alloc/root.zig");

pub fn main(init: std.process.Init) !void {
    var own: alloc.SegregatedAllocator = try .init(64 << 20, .{});
    defer own.deinit();
    const gpa = own.allocator();
    // дальше без изменений

Я это проделал и дописал после printStats строку со статистикой самого аллокатора из own.check():

$ zl --stats programs/fib.zl
6765
пул: 524288 ячеек, 8192 КБ
...
аллокатор: куча 8458320 байт, блоков 29, свободных 3

$ zl --cells 4096 --stats programs/append.zl
(a b c d e)
пул: 4096 ячеек, 64 КБ
...
аллокатор: куча 73776 байт, блоков 37, свободных 5

Три десятка блоков на всю программу. Один огромный, это регион пула: 524 288 ячеек по 16 байт дают ровно 8 388 608 байт, и от кучи аллокатора в 8 458 320 это 99.2 процента. Остальное это битовая карта, имена символов, таблица глобальных имён и временные срезы читателя. Сравни с трассой cells, где те же ячейки шли через общий аллокатор по одной: 80.8 процента, тысячи блоков и 0.32 миллиона операций в секунду у неявного списка. Пул поверх общего аллокатора берёт лучшее от обоих: общий аллокатор занят тем, что умеет, объектами разного размера, а однородную мелочь обслуживает структура, у которой на выделение уходит три записи в память.

Все 94 теста zl на таком main проходят (на arm64 десять из них про машинный код x86-64 пропускают себя сами), но в самих тестах на месте gpa стоят std.testing.allocator, считающая обёртка и буфер фиксированного размера: тесты не должны зависеть от соседнего проекта.

Тесты шага

//! Шаг 58: куча zl это пул ячеек поверх произвольного аллокатора.
//!
//! Проверяем три вещи. Пул устроен так, как обещано: один регион, свободный
//! список продет через `cdr`, статистика сходится. Аллокатор под пулом любой:
//! подставляем считающую обёртку и буфер фиксированного размера и смотрим,
//! что куча ходит к нему редко и по делу. И интерпретатор с читателем живут
//! на пуле: каждая ячейка программы лежит внутри региона.

const std = @import("std");

const zl = @import("zl");

const eval = zl.eval;
const printer = zl.printer;
const programs = zl.programs;
const Heap = zl.heap.Heap;
const Value = zl.Value;
const Vm = zl.Vm;

const testing = std.testing;

/// Аллокатор-счётчик: пропускает запросы дальше и считает их. На его месте
/// в уроке стоит аллокатор из malloclab, стык тот же самый.
const Counting = struct {
    child: std.mem.Allocator,
    allocs: usize = 0,
    frees: usize = 0,
    bytes: usize = 0,

    fn allocator(self: *Counting) std.mem.Allocator {
        return .{ .ptr = self, .vtable = &.{
            .alloc = alloc,
            .resize = resize,
            .remap = remap,
            .free = free,
        } };
    }

    fn alloc(ctx: *anyopaque, len: usize, alignment: std.mem.Alignment, ra: usize) ?[*]u8 {
        const self: *Counting = @ptrCast(@alignCast(ctx));
        self.allocs += 1;
        self.bytes += len;
        return self.child.rawAlloc(len, alignment, ra);
    }

    fn resize(ctx: *anyopaque, memory: []u8, alignment: std.mem.Alignment, new_len: usize, ra: usize) bool {
        const self: *Counting = @ptrCast(@alignCast(ctx));
        return self.child.rawResize(memory, alignment, new_len, ra);
    }

    fn remap(ctx: *anyopaque, memory: []u8, alignment: std.mem.Alignment, new_len: usize, ra: usize) ?[*]u8 {
        const self: *Counting = @ptrCast(@alignCast(ctx));
        return self.child.rawRemap(memory, alignment, new_len, ra);
    }

    fn free(ctx: *anyopaque, memory: []u8, alignment: std.mem.Alignment, ra: usize) void {
        const self: *Counting = @ptrCast(@alignCast(ctx));
        self.frees += 1;
        self.child.rawFree(memory, alignment, ra);
    }
};

test "ячейка это два значения, шестнадцать байт" {
    try testing.expectEqual(@as(usize, 16), @sizeOf(zl.value.Cell));
}

test "свободный список продет через cdr от первой ячейки к последней" {
    var heap: Heap = try .init(testing.allocator, .{ .cells = 4 });
    defer heap.deinit();

    var cell = heap.free_list;
    var index: usize = 0;
    while (cell) |c| : (index += 1) {
        try testing.expectEqual(index, heap.indexOf(c));
        cell = if (c.cdr.isCons()) c.cdr.asCell() else null;
    }
    try testing.expectEqual(@as(usize, 4), index);
}

test "пул кончается ошибкой, а освобождённая ячейка снова в деле" {
    var heap: Heap = try .init(testing.allocator, .{ .cells = 3 });
    defer heap.deinit();

    const a = try heap.cons(.fromFixnum(1), .nil);
    _ = try heap.cons(.fromFixnum(2), .nil);
    _ = try heap.cons(.fromFixnum(3), .nil);
    try testing.expectError(error.OutOfMemory, heap.cons(.fromFixnum(4), .nil));

    heap.release(a.asCell());
    const again = try heap.cons(.fromFixnum(5), .nil);
    try testing.expectEqual(a.asCell(), again.asCell());
    try testing.expectEqual(@as(usize, 3), heap.stats().peak);
}

test "статистика: занято, свободно, пик и раздробленность" {
    var heap: Heap = try .init(testing.allocator, .{ .cells = 8 });
    defer heap.deinit();

    var cells: [8]Value = undefined;
    for (&cells, 0..) |*slot, i| slot.* = try heap.cons(.fromFixnum(@intCast(i)), .nil);
    try testing.expectEqual(@as(usize, 0), heap.stats().free);
    try testing.expectEqual(@as(f64, 0), heap.stats().fragmentation());

    // Освобождаем через одну: четыре свободных участка по одной ячейке.
    for ([_]usize{ 0, 2, 4, 6 }) |i| heap.release(cells[i].asCell());
    var s = heap.stats();
    try testing.expectEqual(@as(usize, 4), s.used);
    try testing.expectEqual(@as(usize, 4), s.free);
    try testing.expectEqual(@as(usize, 8), s.peak);
    try testing.expectEqual(@as(usize, 4), s.free_runs);
    try testing.expectEqual(@as(usize, 1), s.largest_free_run);
    try testing.expectEqual(@as(f64, 0.75), s.fragmentation());

    // Сосед освободился, два участка слились в один из трёх ячеек.
    heap.release(cells[1].asCell());
    s = heap.stats();
    try testing.expectEqual(@as(usize, 3), s.free_runs);
    try testing.expectEqual(@as(usize, 3), s.largest_free_run);
    try testing.expectEqual(@as(f64, 0.4), s.fragmentation());
}

test "замыкание это две ячейки пула" {
    var heap: Heap = try .init(testing.allocator, .{ .cells = 8 });
    defer heap.deinit();

    const cl = try heap.closure(.fromFixnum(1), .fromFixnum(2), .fromFixnum(3));
    try testing.expectEqual(@as(usize, 2), heap.stats().used);
    try testing.expectEqual(@as(usize, 1), heap.closures_allocated);

    const view = cl.asClosure();
    try testing.expectEqual(@as(i64, 1), view.params.asFixnum());
    try testing.expectEqual(@as(i64, 2), view.body.asFixnum());
    try testing.expectEqual(@as(i64, 3), view.env.asFixnum());
    try testing.expect(heap.cellAt(@intFromPtr(cl.heapCell().?)) != null);
}

test "вычисление ячеек у внешнего аллокатора не просит" {
    var counting: Counting = .{ .child = testing.allocator };
    var vm: Vm = try .initWith(counting.allocator(), .{ .cells = 4096 });
    defer vm.deinit();

    // Регион пула пришёл одним запросом и занимает ровно cells * 16 байт.
    try testing.expect(counting.bytes >= 4096 * @sizeOf(zl.value.Cell));

    _ = try eval.evalSource(&vm, "(define len (lambda (xs) (cond (xs (+ 1 (len (cdr xs)))) (t 0))))");
    // Читатель ходит к внешнему аллокатору за временным срезом элементов
    // списка, поэтому форму читаем заранее и меряем только вычисление.
    const form = try zl.reader.readOne(&vm, "(len '(a b c d e f g h))");
    const before = counting.allocs;
    const cells_before = vm.heap.cells_allocated;
    const v = try eval.eval(&vm, form, .nil);
    try testing.expectEqual(@as(i64, 8), v.asFixnum());

    // Десятки ячеек из пула и ни одного запроса к внешнему аллокатору.
    try testing.expect(vm.heap.cells_allocated - cells_before > 40);
    try testing.expectEqual(before, counting.allocs);
}

test "куча и машина целиком помещаются в буфер фиксированного размера" {
    // Один мегабайт на всё: пул, битовая карта, символы и глобальные имена.
    const memory = try testing.allocator.alloc(u8, 1 << 20);
    defer testing.allocator.free(memory);
    var fixed: std.heap.FixedBufferAllocator = .init(memory);

    var vm: Vm = try .initWith(fixed.allocator(), .{ .cells = 8192 });
    defer vm.deinit();

    const v = try eval.evalSource(&vm, programs.get("append.zl").?.source);
    var out: std.Io.Writer.Allocating = .init(testing.allocator);
    defer out.deinit();
    try printer.write(&out.writer, &vm, v);
    try testing.expectEqualStrings("(a b c d e)", out.written());
}

test "каждая пара программы лежит внутри региона пула" {
    var vm: Vm = try .initWith(testing.allocator, .{ .cells = 4096 });
    defer vm.deinit();

    const v = try eval.evalSource(&vm, "(cons 1 (cons 2 (lambda (x) x)))");
    var rest = v;
    while (rest.heapCell()) |cell| {
        try testing.expect(vm.heap.cellAt(@intFromPtr(cell)) == cell);
        rest = cell.cdr;
    }
}

test "после программы статистика показывает пик и занятое" {
    var vm: Vm = try .initWith(testing.allocator, .{ .cells = 1 << 14 });
    defer vm.deinit();

    _ = try eval.evalSource(&vm, programs.get("assoc.zl").?.source);
    const s = vm.heap.stats();
    try testing.expectEqual(s.capacity, s.used + s.free);
    try testing.expect(s.used > 0);
    // Мусор пока никто не собирает, поэтому занятое только растёт.
    try testing.expectEqual(s.used, s.peak);
    try testing.expectEqual(@as(usize, 1), s.free_runs);
}

Counting это второй за урок написанный руками std.mem.Allocator, и он показывает другой способ применить таблицу: не реализовать аллокатор, а обернуть чужой. Каждая функция считает и пропускает запрос дальше через rawAlloc, rawResize, rawRemap, rawFree: это те самые четыре функции таблицы, вызванные без обёрток. Так устроены и validationWrap из испытаний стандартной библиотеки, и std.testing.FailingAllocator, которым проверяют обработку OutOfMemory.

Самый содержательный тест называется “вычисление ячеек у внешнего аллокатора не просит”. Форма читается заранее, потому что читатель ходит к gpa за временным срезом элементов списка. Потом eval выделяет больше сорока ячеек, а счётчик запросов к внешнему аллокатору не сдвигается ни на единицу. Это и есть смысл пула, записанный как проверка.

Тест с FixedBufferAllocator показывает, что zl целиком, с пулом на 8192 ячейки, картой, символами и глобальными именами, помещается в один мегабайт, выделенный заранее. На микроконтроллере без кучи такой интерпретатор работал бы без единой правки.

$ zig build test -Dstep=58 --summary all
Build Summary: 5/5 steps succeeded; 35/35 tests passed
test success
+- run test 26 pass (26 total) 622ms MaxRSS:11M
+- run test 9 pass (9 total) 329ms MaxRSS:4M

Двадцать шесть это тесты модуля, включая два новых в heap.zig, девять это шаг. Полный прогон zig build test на macOS arm64 даёт 84 пройденных из 94: десять тестов прыгают в машинный код x86-64 и на другой архитектуре пропускают себя сами, как и раньше.

Практика

Две задачи, обе на чистых функциях: в песочнице нет ни mmap, ни файлов с трассами, поэтому куча в них лежит в обычном буфере.

В первой куча задана срезом 64-битных слов, и нужно написать coalesce для всех четырёх случаев. Размеры там в словах, а не в байтах, в остальном это функция из heap.zig, только без индекса. Тесты заливают нагрузку мусором, похожим на теги, и обходят кучу после каждого слияния.

Вторая задача это лабораторная в миниатюре: std.mem.Allocator с неявным списком поверх буфера в мегабайт. Расти буферу некуда, поэтому init сразу размечает его как один свободный блок между прологом и эпилогом. Хвост с таблицей из четырёх функций в заготовке готов, твои три метода: init, malloc и free. Скрытые тесты обходят кучу своим проверяльщиком, гоняют на аллокаторе ArrayList и проигрывают встроенную трассу на шесть тысяч операций со сверкой содержимого. В конце считается utilization: пик нагрузки, делённый на самый дальний байт буфера, до которого дотянулся занятый блок. Порог 80 процентов, решение из урока даёт 86. Без разбиения или без слияния до порога не дотянуть.

Упражнения

Итоги

• std.mem.Allocator это указатель на состояние и таблица из четырёх функций. alloc возвращает адрес или null. resize меняет длину на месте и вправе отказать. remap вправе переместить, а null от него означает “скопируй сам”. free получает срез с длиной и то же выравнивание, с которым блок выделялся.
• realloc, create, dupe и остальное написаны в стандартной библиотеке поверх этих четырёх. Автору аллокатора достаточно уметь растить блок на месте: в свободного соседа справа или, если блок последний, через sbrk.
• Выравнивание больше 16 делается через зазор: блок берётся с запасом, а память перед выровненным адресом становится отдельным свободным блоком. Возвращённый адрес остаётся обычным bp со своим заголовком, и free об этом ничего не знает.
• Явный список хранит ссылки prev и next в нагрузке свободного блока, отсюда минимальный блок в 32 байта. Поиск идёт только по свободным блокам, free с граничными тегами и вставкой в голову стоит константу. Двусвязность нужна, потому что при слиянии к блоку приходят не по списку, а по куче.
• Сегрегированные списки раскладывают свободные блоки по классам размеров. First fit внутри класса приближает best fit по всей куче, потому что размеры в классе отличаются не больше чем вдвое.
• Индекс забывает блок до того, как блок изменился: сегрегированный индекс находит список по размеру блока.
• Аллокатор проверяют в три слоя: проверяльщик кучи и списков после операций, испытания std.heap.testAllocator с обёрткой validationWrap, трассы с заливкой каждого блока своим байтом. Проверяльщик нужно проверять самому, портя кучу нарочно.
• Неявный список не медленный, а линейный по числу живых блоков: сотни миллионов операций в секунду на куче из трёх блоков и 0.2 миллиона на куче из двух тысяч. Сегрегированные списки единственная версия без провалов.
• 53.7 процента на binary у всех версий это внешняя фрагментация: дыры по 464 байта не вмещают блок на 528, и стратегия поиска тут бессильна. 80.8 на cells это внутренняя: 16 служебных байт на 32 полезных.
• LIFO и next fit теряют utilization, потому что предпочитают недавно освобождённую память и перемалывают крупные блоки в мелочь. Порядок по адресам и сегрегация по размерам это лечат.
• page_allocator стоит системного вызова на операцию и страницы на объект. DebugAllocator и smp_allocator быстры на мелочи и проваливаются там, где объект перерастает их корзины и уходит в mmap.
• Обогнать системный malloc на своих трассах не значит написать аллокатор лучше: у нас нет потоков, возврата памяти системе и защиты от ошибок программы.
• jemalloc и mimalloc отказались от заголовков: память режется на выровненные куски одного класса размера, и размер объекта следует из адреса. jemalloc масштабируется аренами и кэшем потока, mimalloc кучей на поток и свободным списком на каждую страницу с отдельным атомарным списком для чужих освобождений.
• Объектам одного размера нужен пул. Куча zl теперь один регион от внешнего аллокатора, свободный список продет через cdr, и вычисление не делает ни одного запроса к внешнему аллокатору.
• Своя куча без сборщика мусора только растёт: fib.zl выделяет 175 159 ячеек при нескольких сотнях живых.

Дальше

Куча у zl теперь своя, быстрая и с честной статистикой, и статистика эта неутешительна: всё, что выделено, остаётся занятым навсегда. В C за возврат памяти отвечает программист, и ты сегодня видел, сколько дисциплины это требует даже внутри одного аллокатора. В Лиспе программист о памяти не знает, и отвечать приходится среде исполнения. В следующем уроке мы научим zl находить мусор самому: определим достижимость, напишем Mark&Sweep поверх сегодняшнего пула, причём битовая карта live окажется ровно тем, что сборщику нужно, и разберёмся, как искать корни на машинном стеке в языке, где указатель неотличим от числа. fib.zl после этого уложится в 256 ячеек. А вторую половину урока посвятим тому, что бывает, когда за память отвечает человек: десять классических ошибок, каждая воспроизведена на C и потом на Zig в трёх режимах сборки.