Раздел 32 · Системное программирование: Zig, ассемблер, Verilog

Массивы, структуры и выравнивание на машинном уровне

senior~120 мин

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

Массивы, структуры и выравнивание на машинном уровне

В прошлых уроках компилятор превращал арифметику и вызовы в инструкции. Сегодня та же оптика наводится на данные: как A[i][j] становится сложением и умножением адресов, почему r.weight это mov с одним числом-смещением, и откуда в структуре из семи полезных байт берётся двадцать четыре. Раскладку в памяти ты уже видел, когда мы только знакомились со структурами; теперь посмотрим на неё глазами процессора и научимся читать её обратно, по ассемблеру восстанавливая устройство типа.

Цели урока

Выводить адрес элемента массива формулой base + i * sizeof(T) и узнавать её в масштабном множителе инструкции.
Разбирать доступ к двумерному массиву A[i][j] и видеть, где компилятор ставит shl, где lea, а где imul на ширину строки.
Понимать, во что превращается массив с длиной, известной только в рантайме, и почему тут появляется настоящее умножение.
Читать доступ к полю структуры как mov со смещением и восстанавливать смещения полей по ассемблеру, как в реверс-упражнениях книги.
Считать padding и хвостовое выравнивание руками, проверять себя через @offsetOf и @sizeOf, ужимать структуру перестановкой полей.
Видеть, что объединение это несколько имён на одну память: все поля читаются с нулевого смещения.
Уложить cons-ячейку интерпретатора так, чтобы младшие биты выровненного указателя несли тег, и уронить размер значения с шестнадцати байт до восьми.

Идея: доступ это арифметика над адресом

Массив в машине это просто последовательность одинаковых значений подряд. У него нет ни длины рядом, ни заголовка: только адрес начала и уговор, сколько байт занимает один элемент. Отсюда вся арифметика доступа. Если массив начинается по адресу base, а элемент занимает s байт, то элемент с номером i лежит по адресу base + i * s. Это и есть адресная арифметика, о которой книга говорит всю главу 3.8.

В уроке про указатели и срезы ты уже видел, что срез Zig носит длину с собой, а голый [*]T нет. На машинном уровне носителя длины не существует вовсе: и срез, и указатель дают один и тот же адрес, и доступ по индексу это одна инструкция. Разница только в том, вставит ли компилятор проверку границы, и об этом мы говорили в том же уроке. Здесь нас интересует сама формула адреса, поэтому листинги снимаем в ReleaseFast, где проверок нет, а в конце вернёмся к тому, что добавляет ReleaseSafe.

Все листинги ниже сняты кросс-компиляцией под Linux x86-64 и разобраны через objdump -d, поэтому синтаксис AT&T, как в книге: сначала источник, потом приёмник, память записана как disp(base,index,scale).

Одномерный массив: один множитель в адресе

Начнём с самого простого доступа: взять i-й элемент массива i32.

// arr_access.zig
export fn get_i32(a: [*]const i32, i: usize) i32 {
    return a[i];
}

Экспортируем функцию с C-совместимой сигнатурой, чтобы оптимизатор не встроил её в вызывающего, и снимаем машинный код:

$ zig build-obj arr_access.zig -O ReleaseFast -target x86_64-linux -femit-bin=arr.o
$ objdump -d arr.o

get_i32:
    movl    (%rdi,%rsi,4), %eax
    ret

Одна инструкция несёт всю формулу. По соглашению о вызовах %rdi это первый аргумент a, то есть base, а %rsi это i. Запись (%rdi,%rsi,4) называется масштабированной адресацией и означает %rdi + %rsi * 4. Четвёрка это @sizeOf(i32), тот самый s из формулы. Процессор умеет умножать индекс на 1, 2, 4 или 8 прямо внутри вычисления адреса, бесплатно, поэтому для массива элементов такого размера отдельного умножения не нужно. movl тянет четыре байта по этому адресу в %eax, младшую половину %rax, и это возвращаемое значение.

Запомни этот множитель: он ещё много раз мелькнёт как ,4) или ,8) в конце адреса. Каждый раз это sizeof элемента, вшитый в инструкцию.

Двумерный массив: строки идут подряд

Row-major раскладка двумерного массива это просто строки, положенные одна за другой. Для [3][4]i32 сначала лежат четыре элемента строки 0, потом четыре строки 1, потом строки 2. Чтобы попасть в A[i][j], надо пропустить i целых строк по 4 элемента и ещё j элементов: адрес это base + (i * 4 + j) * 4.

export fn get_2d(a: *const [3][4]i32, i: usize, j: usize) i32 {
    return a[i][j];
}

get_2d:
    shlq    $0x4, %rsi           # rsi = i << 4 = i * 16, шаг одной строки
    addq    %rdi, %rsi           # rsi = base + i * 16
    movl    (%rsi,%rdx,4), %eax  # eax = *(rsi + j * 4)
    ret

Разбери три инструкции. Одна строка это 4 элемента по 4 байта, всего 16 байт, поэтому i * 16 это шаг строки. Шестнадцать это степень двойки, и компилятор считает i * 16 сдвигом влево на 4: shlq $0x4, %rsi. Потом addq прибавляет базу, и в %rsi оказывается адрес начала строки i. Последняя инструкция это уже знакомый доступ внутри строки: %rsi + j * 4. Внешний индекс лёг в отдельную арифметику, внутренний уехал в масштабный множитель.

Обрати внимание: настоящего умножения тут нет, потому что и размер элемента, и ширина строки это степени двойки. Так будет не всегда.

Когда появляется imul

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

const Cell = extern struct { a: u32, b: u32, c: u32 };
export fn get_cell_a(m: [*]const [7]Cell, i: usize, j: usize) u32 {
    return m[i][j].a;
}

get_cell_a:
    imulq   $0x54, %rsi, %rax    # rax = i * 84, шаг строки из 7 ячеек по 12 байт
    addq    %rdi, %rax           # rax = base + i * 84
    leaq    (%rdx,%rdx,2), %rcx  # rcx = j * 3
    movl    (%rax,%rcx,4), %eax  # eax = *(rax + (j * 3) * 4) = *(rax + j * 12)
    ret

Теперь шаг строки это 7 * 12 = 84 байта, число 0x54, и оно не степень двойки, поэтому компилятор ставит настоящее imulq $0x54, %rsi, %rax. А вот внутренний индекс интереснее. Ячейка занимает 12 байт, поле a лежит в начале ячейки со смещением 0, и адрес j-й ячейки это base_row + j * 12. Двенадцать это не масштаб (масштаб бывает только 1, 2, 4, 8), поэтому компилятор разбивает: сначала leaq (%rdx,%rdx,2), %rcx считает j + j * 2 = j * 3, а потом масштаб 4 в movl домножает до j * 12. Инструкция lea тут работает не как доступ к памяти, а как умножение на 3, о чём был отдельный урок про арифметику и lea.

Из одного этого листинга видно, как компилятор дробит любой множитель: степени двойки уходят в shl и в масштаб адреса, остаток собирается из lea и, если совсем не повезло, из imul.

Массив переменной длины

В C двумерный массив с шириной строки, известной только в рантайме, называется массивом переменной длины. В Zig своего синтаксиса для него нет, но та же ситуация возникает сразу, как только ширину строки приносит переменная, а не константа типа. Тогда её значение неизвестно на этапе компиляции, и компилятору некуда деть умножение.

export fn get_dyn(base: [*]const i32, width: usize, i: usize, j: usize) i32 {
    return base[i * width + j];
}

get_dyn:
    imulq   %rdx, %rsi           # rsi = i * width
    leaq    (%rdi,%rsi,4), %rax  # rax = base + (i * width) * 4
    movl    (%rax,%rcx,4), %eax  # eax = *(rax + j * 4)
    ret

Здесь %rsi это i, %rdx это width, %rcx это j. Первая инструкция это imulq %rdx, %rsi: переменная ширина не даёт свернуть умножение в сдвиг, потому что width это регистр, а не число. Дальше lea прибавляет базу с масштабом 4, а movl добавляет j * 4. Формула ровно та же, base + (i * width + j) * 4, но цена другая: одно настоящее умножение на каждый доступ. Именно поэтому в горячем коде ширину строки стараются сделать константой или обходить массив построчно, двигая указатель на width за раз, а не пересчитывая адрес с нуля.

Когда ширина известна, компилятор сам разворачивает обход. Сумма одной строки [3][4]i32 вообще не содержит цикла:

export fn row_sum(a: *const [3][4]i32, i: usize) i64 {
    var total: i64 = 0;
    for (a[i]) |v| total += v;
    return total;
}

row_sum:
    shlq    $0x4, %rsi           # смещение строки i
    movslq  (%rdi,%rsi), %rax    # элемент 0 строки, знаковое расширение до 64 бит
    movslq  0x4(%rdi,%rsi), %rcx # элемент 1
    addq    %rax, %rcx
    movslq  0x8(%rdi,%rsi), %rdx # элемент 2
    movslq  0xc(%rdi,%rsi), %rax # элемент 3
    addq    %rdx, %rax
    addq    %rcx, %rax
    ret

Четыре элемента, четыре загрузки по смещениям 0, 4, 8 и 0xc от начала строки, три сложения, и никакого цикла: компилятор знал длину строки на этапе компиляции и развернул обход целиком. movslq это загрузка i32 со знаковым расширением до 64 бит, потому что аккумулятор объявлен как i64.

Что добавляет ReleaseSafe

Всё это был ReleaseFast, где проверок границ нет. В ReleaseSafe та же get_2d обрастает двумя сравнениями перед арифметикой, по одному на каждый индекс:

get_2d:
    cmpq    $0x2, %rsi           # i > 2 (последняя строка [3][4]) ?
    ja      .Loob_i              # да: выход за границу по i, паника
    cmpq    $0x4, %rdx           # j >= 4 ?
    jae     .Loob_j              # да: выход за границу по j, паника
    shlq    $0x4, %rsi           # дальше ровно тот же адрес, что в ReleaseFast
    addq    %rsi, %rdi
    movl    (%rdi,%rdx,4), %eax
    ret
.Loob_i:
    movq    %rsi, %rdi
    movl    $0x3, %esi
    callq   outOfBounds          # паника: индекс i, длина 3
.Loob_j:
    movl    $0x4, %esi
    movq    %rdx, %rdi
    callq   outOfBounds          # паника: индекс j, длина 4

Проверка i записана как cmpq $0x2 и ja: сравнение беззнаковое, поэтому и настоящий выход i >= 3, и отрицательный i, который в usize выглядит огромным числом, ловятся одним переходом. Сама адресная арифметика после проверок не изменилась ни на инструкцию: безопасность стоит двух cmp и двух непройденных переходов, а не переписанной формулы. Мы подробно разбирали цену этих проверок и то, как оптимизатор выносит их из циклов, в уроке про указатели и срезы; здесь важно только, что смещение элемента одно и то же в обоих режимах.

Структура: смещение вместо индекса

У структуры поля не одинаковые, поэтому вместо i * size компилятор знает точный байт каждого поля заранее. Это число называется смещением поля и вшивается прямо в инструкцию. Возьмём запись, поля которой нарочно разной ширины.

const Record = extern struct {
    id: u32, // смещение 0
    tag: u8, // смещение 4
    weight: f64, // смещение 8
    next: ?*Record, // смещение 16
};

export fn bump_id(r: *Record) void {
    r.id += 1;
}
export fn read_tag(r: *const Record) u8 {
    return r.tag;
}
export fn read_weight(r: *const Record) f64 {
    return r.weight;
}
export fn list_len(head: ?*const Record) usize {
    var n: usize = 0;
    var cur = head;
    while (cur) |node| : (cur = node.next) n += 1;
    return n;
}

bump_id:
    addl    $0x1, (%rdi)         # id по смещению 0

read_tag:
    movzbl  0x4(%rdi), %eax      # tag по смещению 4, байт с нулевым расширением

read_weight:
    movsd   0x8(%rdi), %xmm0     # weight по смещению 8, f64 в регистр xmm

list_len:
    ...
    movq    0x10(%rdi), %rdi     # next по смещению 16 (0x10)
    ...

Каждое поле это одно число в скобках. Поле id в начале, смещение 0, поэтому скобки пустые: (%rdi). Поле tag на смещении 4, и movzbl тянет один байт, дополняя нулями до 32 бит. Поле weight на смещении 8, тип f64, поэтому загрузка идёт инструкцией movsd в регистр %xmm0, где живут числа с плавающей точкой. Поле next на смещении 16, 0x10 в шестнадцатеричной записи, и list_len идёт по списку, каждый раз читая указатель на следующий узел именно с этого смещения.

Смещения 0, 4, 8, 16 это не произвольные числа. Поле u8 встало бы и на 4, и на 5, но следующее за ним f64 требует адреса, кратного 8, поэтому после tag три байта пропущены, и weight начинается на 8. Правила этого пропуска мы разбирали в уроке про структуры и раскладку; сейчас важно, что компилятор один раз посчитал смещение и вшил его в каждую инструкцию доступа.

Реверс: восстанови структуру по ассемблеру

Вот приём из реверс-упражнений книги (3.44 и 3.45): по ассемблеру доступа восстановить устройство типа. Тебе дали четыре функции, каждая читает или пишет одно поле некой структуры S. Про саму S известно только, что в ней есть поля u32, u8, f64 и указатель, а в каком порядке, ты не знаешь.

touch_a:
    movsd   0x8(%rdi), %xmm0     # читает f64 с смещения 8
touch_b:
    addl    $0x1, (%rdi)         # пишет u32 на смещение 0
touch_c:
    movzbl  0x4(%rdi), %eax      # читает u8 с смещения 4
touch_d:
    movq    0x10(%rdi), %rax     # читает 8-байтовый указатель со смещения 16

Читаем смещения из скобок и типы из мнемоник. movsd ... %xmm0 это f64, и оно на 8. addl пишет 4 байта на 0, это u32. movzbl тянет один байт с 4, это u8. movq ... %rax берёт 8 байт с 16, это указатель. Складываем в таблицу:

смещение	инструкция	тип	поле
0	`addl (%rdi)`	u32	b
4	`movzbl 0x4(%rdi)`	u8	c
8	`movsd 0x8(%rdi)`	f64	a
16	`movq 0x10(%rdi)`	указатель	d

Между смещением 4 и 8 лежат три байта, которые ни одна функция не трогает: это padding, вставленный ради выравнивания f64. Между 8 и 16 всё занято восемью байтами weight. Значит структура это extern struct { b: u32, c: u8, a: f64, d: *T }, размер как минимум 24 байта. Это ровно Record из предыдущего раздела, восстановленная по одним лишь инструкциям доступа. Проверить себя можно, дописав @offsetOf(S, "a") и сравнив с числом из скобок: так книга и предлагает закрывать реверс-упражнения.

Выравнивание, padding и перестановка полей

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

поле выравнивается по своему размеру: u32 на адрес, кратный 4, f64 и указатель на кратный 8;
структура выравнивается по максимуму среди полей, и её размер кратен этому максимуму (хвостовой padding);
padding появляется там, где следующее поле требует большего выравнивания, чем текущий адрес.

Из этих правил следует практический вывод: порядок полей меняет размер. Разложи маленькие поля вокруг большого, и между ними вырастут дыры; собери поля от большого к маленькому, и дыры почти исчезнут. Виджет ниже показывает это на ленте памяти. Перетаскивай поля мышью или двигай стрелками, переключай режим между struct, extern struct и packed struct, следи за строкой «padding» и за строкой «переставить»: она говорит, сколько байт вернёт оптимальный порядок в режиме extern. Нажми «переставить оптимально» и увидишь, что делает компилятор в режиме auto сам.

Возьми набор u8, u64, u16, u8, u32 из первого примера виджета. В порядке объявления extern struct раскладывает его в 24 байта: после первого u8 семь байт дыры до u64, потом ещё дыра после u16 и u8. Полезной нагрузки в нём 16 байт, треть размера это пустота. Переставь поля по убыванию выравнивания, u64, u32, u16, u8, u8, и размер падает до 16 байт без единой дыры. Восемь сэкономленных байт на каждой записи это ощутимо, когда таких записей миллион. Проверить числа можно на реальном компиляторе:

const std = @import("std");

const Bad = extern struct { a: u8, b: u64, c: u16, d: u8, e: u32 };
const Good = extern struct { b: u64, e: u32, c: u16, a: u8, d: u8 };

test "перестановка ужимает структуру" {
    try std.testing.expectEqual(@as(usize, 24), @sizeOf(Bad));
    try std.testing.expectEqual(@as(usize, 16), @sizeOf(Good));
    // auto выбирает тот же минимум сам:
    const Auto = struct { a: u8, b: u64, c: u16, d: u8, e: u32 };
    try std.testing.expectEqual(@as(usize, 16), @sizeOf(Auto));
}

$ zig test padding.zig
1/1 padding.test.перестановка ужимает структуру...OK
All 1 tests passed.

Отсюда правило раздела: в режиме auto компилятор Zig и так укладывает поля по убыванию выравнивания, поэтому размер минимальный, но порядок в памяти не совпадает с порядком объявления. Как только ты берёшь extern struct ради C ABI или ради стабильной раскладки на диске, порядок фиксируется, и следить за padding приходится самому. extern struct при этом ещё и лучший инструмент самопроверки: раскладка предсказуемая, а @offsetOf даёт точное смещение каждого поля, с которым удобно сверять и ручные расчёты, и восстановленную по ассемблеру таблицу.

Объединение: несколько имён на одну память

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

const Reg = extern union {
    word: u32,
    half: u16,
    bytes: [4]u8,
};

export fn read_word(r: *const Reg) u32 {
    return r.word;
}
export fn read_half(r: *const Reg) u16 {
    return r.half;
}
export fn read_byte0(r: *const Reg) u8 {
    return r.bytes[0];
}

read_word:
    movl    (%rdi), %eax         # 4 байта со смещения 0
read_half:
    movzwl  (%rdi), %eax         # 2 байта со смещения 0
read_byte0:
    movzbl  (%rdi), %eax         # 1 байт со смещения 0

Все три чтения идут по одному адресу (%rdi), смещение 0. Разница только в ширине: movl берёт четыре байта, movzwl два, movzbl один, и все с начала объединения. Именно это и значит «поля делят память»: у объединения нет смещений, каждое поле начинается с нуля, а размер равен самому большому полю. Проверим на числах:

const std = @import("std");

const Reg = extern union {
    word: u32,
    half: u16,
    bytes: [4]u8,
};

test "поля union начинаются с нулевого байта" {
    var r: Reg = .{ .word = 0x11223344 };
    try std.testing.expectEqual(@as(u8, 0x44), r.bytes[0]); // младший байт, little-endian
    try std.testing.expectEqual(@as(u16, 0x3344), r.half);
    r.bytes[3] = 0xFF;
    try std.testing.expectEqual(@as(u32, 0xFF223344), r.word);
    try std.testing.expectEqual(@as(usize, 4), @sizeOf(Reg));
}

$ zig test union_access.zig
1/1 union_access.test.поля union начинаются с нулевого байта...OK
All 1 tests passed.

Записав word, мы прочитали те же байты как bytes[0] и как half, а изменив старший байт через bytes[3], увидели новое значение word. Одна память, разные имена. Порядок байт тут little-endian, о чём подробно был урок про биты и endianness: младший байт 0x44 лежит первым, поэтому bytes[0] это 0x44, а не 0x11. На этом свойстве, тег в младших битах указателя, построен следующий раздел.

Шаг проекта: zl укладывает значение в одно слово

В прошлом уроке значение zl стало extern struct из двух слов: байт вида, семь байт выравнивания и восемь байт нагрузки. Раскладка обещана, граница C пройдена, но цена видна в каждом листинге: значение едет парой регистров, ячейка из двух значений занимает 32 байта, и половина из них это вид и дыры после него. Этот раздел урока показал, откуда берутся такие дыры. Теперь уберём их совсем.

Идея в выравнивании. Если каждая ячейка лежит по адресу, кратному 16, то четыре младших бита её адреса всегда нули. Четыре бита, которые ничего не сообщают, можно отдать под вид значения. Такое слово называется тегированным указателем: адрес с пометкой в младших битах. Всё, что не адрес (число, номер символа, номер примитива), сдвигается влево и метится в тех же битах.

Раскладка слова

Вид	Слово	Почему так
`nil`	ноль	нулевой указатель; проверка на пустой список это сравнение с нулём
число	`n << 3`, младшие биты `001`	единица в младшем бите бывает только у чисел, разрядность `i61`
пара	адрес ячейки, младшие биты `0000`	тег нулевой, адрес готов к чтению без единой инструкции
замыкание	адрес, младшие биты `0100`	тег снимается маской
символ	`номер << 4`, младшие биты `1000`	номер сдвинут за весь тег
примитив	`номер << 4`, младшие биты `1100`	то же

Два решения стоит проговорить. Первое: у пары нулевой тег. Самые частые операции лиспа это car и cdr, и с нулевым тегом значение пары и есть адрес: car это чтение по смещению 0, cdr по смещению 8, снимать нечего. Платят за это остальные виды, но реже. Второе: бит 1 (0b0010) не занят ни одним видом. У числа биты 1 и 2 нулевые из-за сдвига на три, у адреса нулевые все четыре, у номеров тоже. Этот бит пригодится сборщику мусора: пометку живой ячейки он поставит прямо в её слово car, не заводя отдельной памяти.

Почему число сдвинуто на три, а не на четыре? Для числа хватает одного бита метки, а сдвиг на три оставляет биты 1 и 2 нулевыми, то есть бит 1 свободен и у чисел. Так разрядность теряет три бита, а не четыре: i61 вместо i60. Та же договорённость про nil, числа и пары встретится в уроке про JIT, где машинный код читает значения сам.

Выравнивание на 16 вместо 8

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

pub const Cell = extern struct {
    car: Value align(16),
    cdr: Value,
};

Выравнивание структуры это максимум выравниваний её полей, поэтому align(16) у первого поля делает выровненной всю ячейку. Размер остаётся 16 байт без единой дыры: второе поле и так лежит по смещению 8. Арена и любой аллокатор Zig выдают память под Cell с выравниванием @alignOf(Cell), так что каждая новая ячейка сама попадает на адрес, кратный 16. Замыкание на этом шаге ещё отдельная структура из трёх значений, и его адрес тоже несёт тег, поэтому ему тот же align(16): 24 байта полей, и хвостовой padding добивает структуру до 32.

Так выглядят размеры до шага и после:

Тип	Шаг 14	Шаг 15
`@sizeOf(Value)`	16	8
`@sizeOf(Cell)`	32	16
`@sizeOf(Closure)`	48	32

value.zig целиком

Меняется только этот файл. Методы сохранили подписи, и ни eval.zig, ни bytecode.zig, ни примитивы этого не заметили: представление сменилось уже второй раз, а остальной код по-прежнему ходит к значению только через методы.

//! Значения zl и куча cons-ячеек.
//!
//! Значение это одно машинное слово, тегированный указатель. Ячейка выровнена
//! на 16 байт, поэтому четыре младших бита её адреса всегда нулевые, и в них
//! помещается вид значения. То, что не адрес (число, номер символа или
//! примитива), сдвигается влево и получает свой тег в освободившихся битах:
//!
//!   0                          nil, нулевой указатель
//!   n << 3 | 0b001             число; единица в младшем бите только у чисел
//!   адрес ячейки | 0b0000      пара: тег нулевой, адрес готов к чтению
//!   адрес замыкания | 0b0100   замыкание
//!   номер << 4 | 0b1000        символ
//!   номер << 4 | 0b1100        примитив
//!
//! Бит 1 (0b0010) не занят ни одним видом и в значении всегда ноль. Он
//! пригодится сборщику мусора.
//!
//! Представление сменилось уже второй раз, а остальной код этого не заметил:
//! он обращается к значению только через методы этого файла и ни разу не
//! разбирает его сам. Перечень `Tag` от представления не зависит.

const std = @import("std");

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

pub const SymbolId = symbols.SymbolId;

/// Номер примитива в таблице встроенных функций.
pub const PrimIndex = u32;

/// Что лежит в значении. Этот перечень стабилен: представление меняется, он нет.
pub const Tag = enum(u8) { nil, fixnum, symbol, cons, closure, primitive };

/// Пара. Весь лисп это связанные пары: список `(1 2)` это пара, у которой
/// в `car` единица, а в `cdr` пара с двойкой и nil.
///
/// Два слова по 8 байт выровнялись бы на 8, и под тег осталось бы три бита.
/// `align(16)` у первого поля поднимает выравнивание всей ячейки до 16, и
/// бит становится четыре. Размер при этом не меняется: 16 байт без дыр.
/// `extern` обещает порядок полей: `car` по смещению 0, `cdr` по смещению 8.
pub const Cell = extern struct {
    car: Value align(16),
    cdr: Value,
};

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

/// Значение в одно слово. `extern struct` с единственным полем лежит в памяти
/// ровно как `u64` и едет через границу C в одном регистре, а отдельный тип
/// не даёт перепутать значение с обычным числом.
pub const Value = extern struct {
    bits: u64,

    pub const nil: Value = .{ .bits = 0 };

    /// Младший бит числа. У адреса ячейки и у номеров он всегда ноль.
    const fixnum_bit: u64 = 0b0001;
    /// Число сдвинуто за тег `001`: три младших бита.
    const fixnum_shift = 3;
    /// Всё, что под тегом. У адреса выровненной ячейки эти биты нулевые.
    const tag_mask: u64 = 0b1111;
    /// Вид всего, что не число, в битах 2 и 3.
    const kind_mask: u64 = 0b1100;
    const cons_kind: u64 = 0b0000;
    const closure_kind: u64 = 0b0100;
    const symbol_kind: u64 = 0b1000;
    const primitive_kind: u64 = 0b1100;
    /// Номер символа или примитива сдвинут за все четыре бита тега.
    const index_shift = 4;

    pub fn tag(self: Value) Tag {
        if (self.bits == 0) return .nil;
        if (self.bits & fixnum_bit != 0) return .fixnum;
        return switch (self.bits & kind_mask) {
            cons_kind => .cons,
            closure_kind => .closure,
            symbol_kind => .symbol,
            else => .primitive,
        };
    }

    /// В слово помещается `i61`: три бита ушли под тег. Выход за этот диапазон
    /// в Debug и ReleaseSafe ловит `@intCast`, так же как переполнение `i64`
    /// в самой арифметике.
    pub fn fromFixnum(n: i64) Value {
        const small: i61 = @intCast(n);
        const word: u64 = @bitCast(@as(i64, small));
        return .{ .bits = (word << fixnum_shift) | fixnum_bit };
    }

    pub fn fromSymbol(id: SymbolId) Value {
        return .{ .bits = (@as(u64, id) << index_shift) | symbol_kind };
    }

    /// Тег пары нулевой, поэтому адрес ячейки и есть значение.
    pub fn fromCell(cell: *Cell) Value {
        return .{ .bits = @intFromPtr(cell) };
    }

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

    pub fn fromPrimitive(index: PrimIndex) Value {
        return .{ .bits = (@as(u64, index) << index_shift) | primitive_kind };
    }

    /// Пустой список это нулевое слово: проверка одним сравнением с нулём.
    pub fn isNil(self: Value) bool {
        return self.bits == 0;
    }

    /// Пара это ненулевое слово, у которого все четыре бита тега нулевые.
    pub fn isCons(self: Value) bool {
        return self.bits != 0 and self.bits & tag_mask == cons_kind;
    }

    /// Атом это всё, что не пара. nil тоже атом, как у Маккарти.
    pub fn isAtom(self: Value) bool {
        return !self.isCons();
    }

    /// Сдвиг вправо знаковый, поэтому отрицательные числа переживают дорогу
    /// туда и обратно.
    pub fn asFixnum(self: Value) i64 {
        std.debug.assert(self.tag() == .fixnum);
        return @as(i64, @bitCast(self.bits)) >> fixnum_shift;
    }

    pub fn asSymbol(self: Value) SymbolId {
        std.debug.assert(self.tag() == .symbol);
        return @intCast(self.bits >> index_shift);
    }

    /// Снимать нечего: тег пары нулевой. `@ptrFromInt` в Debug и ReleaseSafe
    /// проверяет, что адрес не ноль и кратен 16, как обещает тип `*Cell`.
    pub fn asCell(self: Value) *Cell {
        std.debug.assert(self.tag() == .cons);
        return @ptrFromInt(self.bits);
    }

    /// Тег замыкания снимается одной маской.
    pub fn asClosure(self: Value) *Closure {
        std.debug.assert(self.tag() == .closure);
        return @ptrFromInt(self.bits & ~tag_mask);
    }

    pub fn asPrimitive(self: Value) PrimIndex {
        std.debug.assert(self.tag() == .primitive);
        return @intCast(self.bits >> index_shift);
    }

    /// Всё, что можно поставить в голову формы.
    pub fn isCallable(self: Value) bool {
        return switch (self.tag()) {
            .closure, .primitive => true,
            else => false,
        };
    }

    /// Тождество в смысле `eq`: числа и символы сравниваются по значению,
    /// пары и замыкания по адресу. В одном слове это одно сравнение: у каждого
    /// вида своё слово на каждое значение.
    pub fn eql(a: Value, b: Value) bool {
        return a.bits == b.bits;
    }
};

/// `car` и `cdr` возвращают null на атоме: решение, что с этим делать,
/// принимает вызывающий (интерпретатор превращает null в ошибку).
pub fn car(v: Value) ?Value {
    if (!v.isCons()) return null;
    return v.asCell().car;
}

pub fn cdr(v: Value) ?Value {
    if (!v.isCons()) return null;
    return v.asCell().cdr;
}

/// Длина правильного списка. Для точечной пары возвращает null.
pub fn listLen(v: Value) ?usize {
    var n: usize = 0;
    var rest = v;
    while (!rest.isNil()) {
        if (!rest.isCons()) return null;
        n += 1;
        rest = rest.asCell().cdr;
    }
    return n;
}

/// Куча значений. Ячейки живут на арене: интерпретатор их не освобождает
/// поштучно, вся память уходит одним движением в конце. Сборщик мусора
/// появится сильно позже, когда куча станет своей.
pub const Heap = struct {
    arena: std.heap.ArenaAllocator,
    /// Сколько ячеек выделено за жизнь кучи. Пригодится, когда будем мерить цену.
    cells_allocated: usize = 0,
    closures_allocated: usize = 0,

    pub fn init(gpa: std.mem.Allocator) Heap {
        return .{ .arena = .init(gpa) };
    }

    pub fn deinit(self: *Heap) void {
        self.arena.deinit();
        self.* = undefined;
    }

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

    pub fn closure(self: *Heap, params: Value, body: Value, env: Value) std.mem.Allocator.Error!Value {
        const cl = try self.arena.allocator().create(Closure);
        cl.* = .{ .params = params, .body = body, .env = env };
        self.closures_allocated += 1;
        return .fromClosure(cl);
    }

    /// Собрать список из готового среза значений, справа налево.
    pub fn list(self: *Heap, items: []const Value) std.mem.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;
    }
};

test "размер значения на этом шаге" {
    // Одно слово: вид спрятан в младших битах.
    try std.testing.expectEqual(@as(usize, 8), @sizeOf(Value));
}

test "eq различает тождество пар и равенство чисел" {
    var heap: Heap = .init(std.testing.allocator);
    defer heap.deinit();

    const one = Value.fromFixnum(1);
    const also_one = Value.fromFixnum(1);
    const pair_a = try heap.cons(one, .nil);
    const pair_b = try heap.cons(one, .nil);

    try std.testing.expect(one.eql(also_one));
    try std.testing.expect(!pair_a.eql(pair_b));
    try std.testing.expect(pair_a.eql(pair_a));
    try std.testing.expect(Value.nil.eql(.nil));
}

test "список и его длина" {
    var heap: Heap = .init(std.testing.allocator);
    defer heap.deinit();

    const items = [_]Value{ .fromFixnum(1), .fromFixnum(2), .fromFixnum(3) };
    const built = try heap.list(&items);

    try std.testing.expectEqual(@as(?usize, 3), listLen(built));
    try std.testing.expectEqual(@as(i64, 1), car(built).?.asFixnum());

    const dotted = try heap.cons(.fromFixnum(1), .fromFixnum(2));
    try std.testing.expectEqual(@as(?usize, null), listLen(dotted));
    try std.testing.expectEqual(@as(?Value, null), car(.fromFixnum(7)));
}

Пройдись по методам с раскладкой в голове. fromCell вообще ничего не делает: адрес и есть значение. isNil это сравнение слова с нулём, isCons это «не ноль и четыре младших бита нулевые». asClosure снимает тег одной маской & ~0b1111. У номеров тег снимается сдвигом вправо на четыре, у числа знаковым сдвигом на три: знаковым, чтобы минус три после дороги туда и обратно остался минус тремя.

@intFromPtr превращает указатель в число, @ptrFromInt делает обратное. У обратного превращения в Debug и ReleaseSafe две проверки: адрес не ноль (тип *Cell не допускает null) и адрес кратен @alignOf(Cell), то есть 16. К этому мы ещё вернёмся. fromFixnum проверяет своё: @intCast к i61 в безопасных режимах ловит число, которому не хватило разрядности, так же, как сложение i64 ловит переполнение. Методы as* проверяют вид через std.debug.assert, и эта проверка тоже доживает до ReleaseSafe.

Отдельный тип Value вместо голого u64 оставлен нарочно. extern struct с одним полем лежит в памяти ровно как u64 и едет через границу C в одном регистре, но спутать значение с обычным числом теперь не выйдет: fromFixnum(5) и 5 это разные типы.

В primitives.zig меняется только комментарий у Native, потому что регистров стало меньше:

/// Тот же примитив по соглашению C. Машина едет в `%rdi`, список аргументов
/// в `%rsi` (значение это одно слово), результат возвращается в `%rax`.
/// Ошибки Zig через эту границу не проходят, поэтому ошибка остаётся
/// в машине, а наружу уходит nil.
pub const Native = *const fn (vm: *Vm, args: Value) callconv(.c) Value;

Что стало с ассемблером

Снимем вход car так же, как в прошлом уроке, и поставим рядом с его двухсловной версией:

$ zig build asm -Dtarget=x86_64-linux -Doptimize=ReleaseFast
$ nm zig-out/bin/zl-llvm | grep primitives.native | sort -k3 | head -3
0000000001074270 t primitives.native__struct_27624.entry
0000000001074220 t primitives.native__struct_27633.entry
0000000001074190 t primitives.native__struct_27641.entry
$ objdump -d --no-show-raw-insn \
    --disassemble-symbols=primitives.native__struct_27624.entry zig-out/bin/zl-llvm

<primitives.native__struct_27624.entry>:
    pushq   %rbp
    movq    %rsp, %rbp
    testq   %rsi, %rsi                # args это nil?
    sete    %cl
    testb   $0xf, %sil                # тег args не 0000, то есть не пара?
    setne   %dl
    movw    $0x20, %ax                # код ошибки ArityMismatch наготове
    orb     %cl, %dl
    jne     <...+0x3e>                # args не пара: ArityMismatch
    cmpq    $0x0, 0x8(%rsi)           # cdr списка аргументов: nil?
    jne     <...+0x3e>                # аргумент не один
    movq    (%rsi), %rcx              # car списка, сам аргумент: одно чтение
    testq   %rcx, %rcx                # та же проверка «это пара?»
    sete    %dl
    testb   $0xf, %cl
    setne   %sil
    movw    $0x1f, %ax                # теперь наготове NotAPair
    orb     %dl, %sil
    jne     <...+0x3e>
    movq    (%rcx), %rax              # его car: ответ уже в rax
    popq    %rbp
    retq
    movw    %ax, 0xbc(%rdi)           # vm.failure = код ошибки
    xorl    %eax, %eax                # вернуть nil: ноль в rax
    popq    %rbp
    retq

Сравни с листингом прошлого урока. Список аргументов приехал одним регистром %rsi, а не парой %sil и %rdx. Проверка «это пара» стала двумя тестами над самим словом (не ноль, младшие четыре бита нули) вместо сравнения отдельного байта вида, который для аргумента приходилось читать из памяти. cdr списка читается по 0x8(%rsi), car по (%rsi): смещения 0 и 8 вместо 0 и 16, потому что ячейка вдвое меньше. Ответ уходит одним %rax, путь ошибки обнуляет один регистр вместо двух. И ни одной инструкции на снятие тега пары: её тег нулевой.

Теги, которые снимать приходится, видны в apply. Оптимизатор встроил её в eval.eval; вот место, где решается, кого звать:

    testq   %r12, %r12                # r12 = callee; nil нельзя применить
    je      <NotApplicable>
    movl    %r12d, %eax
    andl    $0xd, %eax                # биты 0, 2 и 3: число? какой вид?
    cmpq    $0x4, %rax                # 0100: замыкание
    je      <замыкание>
    cmpl    $0xc, %eax                # 1100: примитив
    jne     <NotApplicable>
    shrq    $0x4, %r12                # снять тег примитива: номер
    movq    %rbx, %rdi                # vm в rdi
    callq   *0x1013d28(,%r12,8)       # natives[номер]
    ...
<замыкание>:
    andq    $-0x10, %r12              # снять тег замыкания: адрес структуры
    movq    (%r12), %r15              # cl.params по смещению 0
    movq    0x10(%r12), %rdi          # cl.env по смещению 16

Маска 0xd это 1101: компилятор проверяет бит числа и оба бита вида одной инструкцией and, а свободный бит 1 в ней не участвует. Тег примитива снимается сдвигом shrq $0x4, и номер тут же становится индексом в таблице natives. Тег замыкания снимается andq $-0x10: минус шестнадцать в дополнительном коде это все единицы, кроме четырёх младших битов, то есть та самая маска ~0b1111.

Сколько это даёт на живой программе, видно по памяти. На шаге 14 и на шаге 15 куча это арена, которая ничего не освобождает, поэтому весь fib.zl оседает в памяти процесса:

$ /usr/bin/time -l zl programs/fib.zl            # шаг 14
6765
             7815168  maximum resident set size
$ /usr/bin/time -l zl programs/fib.zl            # шаг 15
6765
             4980736  maximum resident set size

Замер на Apple M4 Max, сборка ReleaseFast. Минус 2,8 МБ: это шестнадцать сэкономленных байт на каждой из ста семидесяти с лишним тысяч ячеек, которые программа успевает построить.

Что ловит ReleaseSafe

Главная опасность тегированных указателей это забыть снять тег. Возьмём значение с тегом замыкания и прочитаем его как адрес ячейки:

// untag.zig
const std = @import("std");

const Cell = extern struct { car: u64 align(16), cdr: u64 };
const closure_kind: u64 = 0b0100;

/// Ошибка, ради которой всё затевалось: взять адрес из значения с тегом
/// замыкания и забыть снять тег.
fn headOf(bits: u64) *Cell {
    return @ptrFromInt(bits);
}

pub fn main() void {
    var cells: [2]Cell = @splat(.{ .car = 7, .cdr = 0 });
    var value: u64 = @intFromPtr(&cells[0]) | closure_kind;
    _ = &value;
    std.debug.print("car = {d}\n", .{headOf(value).car});
}

$ zig build-exe -O ReleaseSafe untag.zig && ./untag
thread 64903751 panic: incorrect alignment
untag.zig:9:12: 0x100f8c8f7 in headOf (untag)
    return @ptrFromInt(bits);
           ^
$ zig build-exe -O ReleaseFast untag.zig && ./untag
car = 0

В ReleaseSafe @ptrFromInt сверяет адрес с выравниванием типа *Cell, видит в младших битах 0100 и останавливает программу на той самой строке. В ReleaseFast проверки нет, чтение идёт со сдвигом на четыре байта, захватывает старшую половину car и младшую cdr, и программа тихо печатает ноль вместо семёрки. Так выглядит проверка в машинном коде (функции с export, снятые под x86_64-linux):

// headof.zig
const Cell = extern struct { car: u64 align(16), cdr: u64 };

export fn head_car(bits: u64) u64 {
    const head: *Cell = @ptrFromInt(bits);
    return head.car;
}

export fn closure_car(bits: u64) u64 {
    const head: *Cell = @ptrFromInt(bits & ~@as(u64, 0b1111));
    return head.car;
}

$ zig build-obj headof.zig -O ReleaseSafe -target x86_64-linux
$ objdump -d headof.o

head_car:                             # ReleaseSafe
    testq   %rdi, %rdi                # адрес ноль?
    je      <паника>
    testb   $0xf, %dil                # младшие четыре бита не нули?
    jne     <паника>
    movq    (%rdi), %rax
    ret

closure_car:                          # ReleaseSafe
    andq    $-0x10, %rdi              # снять тег; заодно флаг «вышел ноль»
    je      <паника>
    movq    (%rdi), %rax
    ret

В head_car проверка выравнивания стоит две инструкции. В closure_car её нет вовсе: после маски младшие биты нулевые по построению, и компилятор это знает. Остаётся проверка на ноль, и она бесплатна, потому что andq сам выставляет флаг нуля. В ReleaseFast от обеих функций остаются andq и movq.

Тот же приём с другой стороны это @alignCast. Он нужен, когда указатель пришёл с меньшим выравниванием, чем требует тип, например из буфера байт: так память видит пул, которому её выдали срезом []u8.

// align_cast.zig
const std = @import("std");

const Cell = extern struct { car: u64 align(16), cdr: u64 };

/// Ячейка из сырого буфера байт: так её получает пул, которому память
/// выдали как `[]u8`. Смещение приходит в рантайме.
fn cellAt(bytes: []u8, offset: usize) *Cell {
    return @ptrCast(@alignCast(bytes[offset..].ptr));
}

pub fn main(init: std.process.Init) !void {
    var buf: [64]u8 align(16) = @splat(0);
    const args = try init.minimal.args.toSlice(init.arena.allocator());
    const offset = try std.fmt.parseInt(usize, args[1], 10);
    const cell = cellAt(&buf, offset);
    std.debug.print("ячейка по смещению {d}: car = {d}\n", .{ offset, cell.car });
}

$ zig build-exe -O ReleaseSafe align_cast.zig
$ ./align_cast 16
ячейка по смещению 16: car = 0
$ ./align_cast 8
thread 64903908 panic: incorrect alignment
$ zig build-exe -O ReleaseFast align_cast.zig && ./align_cast 8
ячейка по смещению 8: car = 0

@alignCast это обещание компилятору: «я знаю, что этот адрес кратен 16». В Debug и ReleaseSafe обещание проверяется в рантайме, в ReleaseFast принимается на веру. Смещение 8 обещание нарушает. На x86-64 и на Apple M4 обычное чтение по невыровненному адресу всё равно сработает, поэтому ReleaseFast напечатал ответ. Но у нас выравнивание это не вопрос скорости, а часть кодировки: ячейка по адресу, кратному 8, но не 16, имеет единицу в бите 3, и её значение читалось бы как символ. Поэтому вся проверка выравнивания в zl стоит на @ptrFromInt в asCell и asClosure, и тесты мы гоняем в Debug.

Тесты шага

В build.zig номер шага: const steps = [_][]const u8{ "05", "06", "13", "14", "15" };. Тест размер значения на этом шаге в value.zig теперь ждёт 8.

//! Шаг 15: значение это тегированный указатель в одно слово. Проверяем
//! размеры и выравнивание, раскладку битов каждого вида и то, что вид
//! переживает дорогу туда и обратно на краях своего диапазона.

const std = @import("std");

const zl = @import("zl");

const eval = zl.eval;
const primitives = zl.primitives;
const reader = zl.reader;
const Cell = zl.value.Cell;
const Value = zl.Value;
const Vm = zl.Vm;

const testing = std.testing;

test "значение в одно слово, ячейка в два" {
    try testing.expectEqual(@as(usize, 8), @sizeOf(Value));
    try testing.expectEqual(@as(usize, 16), @sizeOf(Cell));
    try testing.expectEqual(@as(usize, 16), @alignOf(Cell));
    try testing.expectEqual(@as(usize, 8), @offsetOf(Cell, "cdr"));
}

test "раскладка битов: nil ноль, число с единицей внизу, пара это адрес" {
    var vm: Vm = try .init(testing.allocator);
    defer vm.deinit();

    try testing.expectEqual(@as(u64, 0), Value.nil.bits);
    try testing.expectEqual(@as(u64, 5 << 3 | 1), Value.fromFixnum(5).bits);
    try testing.expectEqual(@as(u64, 0xffff_ffff_ffff_fff9), Value.fromFixnum(-1).bits);

    const pair = try vm.heap.cons(.fromFixnum(1), .nil);
    try testing.expectEqual(@intFromPtr(pair.asCell()), pair.bits);
    try testing.expectEqual(@as(u64, 0), pair.bits & 0b1111);

    const sym = try vm.symbolValue("hello");
    try testing.expectEqual(@as(u64, 0b1000), sym.bits & 0b1111);
    const prim = Value.fromPrimitive(primitives.indexOf("cons"));
    try testing.expectEqual(@as(u64, 2 << 4 | 0b1100), prim.bits);

    const cl = try eval.evalSource(&vm, "(lambda (x) x)");
    try testing.expectEqual(@as(u64, 0b0100), cl.bits & 0b1111);
}

test "car и cdr это чтение слова по смещению 0 и 8, без снятия тега" {
    var vm: Vm = try .init(testing.allocator);
    defer vm.deinit();

    const pair = try reader.readOne(&vm, "(7 . 9)");
    const words: *const [2]u64 = @ptrFromInt(pair.bits);
    try testing.expectEqual(Value.fromFixnum(7).bits, words[0]);
    try testing.expectEqual(Value.fromFixnum(9).bits, words[1]);
}

test "бит 1 свободен у значения любого вида" {
    var vm: Vm = try .init(testing.allocator);
    defer vm.deinit();

    const values = [_]Value{
        .nil,
        .fromFixnum(-3),
        .fromFixnum(std.math.maxInt(i61)),
        try vm.symbolValue("x"),
        try reader.readOne(&vm, "(1 2)"),
        try eval.evalSource(&vm, "(lambda () nil)"),
        .fromPrimitive(primitives.indexOf("print")),
    };
    for (values) |v| try testing.expectEqual(@as(u64, 0), v.bits & 0b10);
}

test "края диапазонов переживают дорогу туда и обратно" {
    const numbers = [_]i64{ 0, 1, -1, std.math.maxInt(i61), std.math.minInt(i61) };
    for (numbers) |n| {
        const v = Value.fromFixnum(n);
        try testing.expectEqual(zl.value.Tag.fixnum, v.tag());
        try testing.expectEqual(n, v.asFixnum());
    }

    const id = std.math.maxInt(zl.value.SymbolId);
    try testing.expectEqual(id, Value.fromSymbol(id).asSymbol());
    try testing.expectEqual(zl.value.Tag.symbol, Value.fromSymbol(id).tag());
    try testing.expectEqual(zl.value.Tag.symbol, Value.fromSymbol(0).tag());
    try testing.expectEqual(zl.value.Tag.primitive, Value.fromPrimitive(0).tag());
}

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

Прогон

$ zig build test --summary all
Build Summary: 13/13 steps succeeded; 45/45 tests passed
test success
+- run test 7 pass (7 total) 322ms MaxRSS:2M      тесты внутри модулей
+- run test 12 pass (12 total) 665ms MaxRSS:3M    шаг 05
+- run test 10 pass (10 total) 1s MaxRSS:9M       шаг 06
+- run test 5 pass (5 total) 2s MaxRSS:23M        шаг 13
+- run test 6 pass (6 total) 1s MaxRSS:3M         шаг 14
+- run test 5 pass (5 total) 955ms MaxRSS:3M      шаг 15

Шаг 13 в прошлом уроке брал 29 МБ памяти, теперь 23: его тест на хвостовой вызов строит сотни тысяч ячеек, и каждая похудела вдвое. Под amd64 результат тот же:

$ docker run --rm --platform linux/amd64 -v "$PWD":/work -w /work \
    ghcr.io/bondiano/runner-zig:dev-amd64 \
    zig build test --summary all --cache-dir /work/.zc --global-cache-dir /work/.zg
Build Summary: 13/13 steps succeeded; 45/45 tests passed

Практика

Пора собрать формулы этого урока руками. В задаче три функции. Первые две работают с матрицей, уложенной в плоский срез построчно: matGet и matSet вычисляют индекс i * cols + j, ту самую адресную арифметику, что компилятор прячет в масштаб и imul. Третья, recordScore, читает поле f32 из массива структур, лежащего в сыром буфере байт: смещение записи это idx * stride, а поле внутри неё на + off. Тесты берут stride и off у @sizeOf и @offsetOf, поэтому твоя ручная арифметика обязана совпасть с настоящей раскладкой, ровно как в реверс-упражнениях выше.

Упражнения

CHK-1★

Напиши функцию доступа к элементу трёхмерного массива *const [2][3][4]i32 по индексам i, j, k, сними её ассемблер под ReleaseFast через objdump -d и найди в нём два умножения (или сдвига): одно на размер плоскости 3 * 4, другое на ширину строки 4. Выпиши формулу адреса.

CHK-2★★

Возьми функцию get_dyn из урока и напиши рядом вариант, который обходит всю строку i через указатель, сдвигаемый на width за итерацию, без пересчёта i * width внутри цикла. Сними ассемблер обоих и сравни, сколько инструкций imul осталось в каждом.

CHK-3★★

Дан ассемблер четырёх функций доступа к структуре: movzwl (%rdi), %eax, movzbl 0x2(%rdi), %eax, movl 0x4(%rdi), %eax, movsd 0x8(%rdi), %xmm0. Восстанови смещения и типы полей, посчитай, где лежит padding, и напиши extern struct в порядке объявления, для которой @offsetOf даст ровно эти числа. Проверь себя тестом.

CHK-4★★

Открой виджет и подбери набор из пяти полей разных типов так, чтобы extern struct в порядке объявления занимал ровно вдвое больше своего минимума. Запиши оба порядка как extern struct и подтверди размеры через @sizeOf.

CHK-5★★

Опиши extern union из полей value: u64, pair: extern struct { lo: u32, hi: u32 } и bytes: [8]u8. Через @sizeOf и запись с последующим чтением под другим именем покажи, что pair.hi это старшие четыре байта value, и объясни результат через endianness.

CHK-6★★

Сделай шаг zl у себя и сними ассемблер входа cdr (вторая строка таблицы примитивов). По какому смещению он читает ответ и сколько инструкций уходит на проверки вида? Поставь его рядом со входом car из урока и со входом car из прошлого урока, где значение было двумя словами, и посчитай, сколько обращений к памяти исчезло.

CHK-7★★★

Убери align(16) у поля car в Cell и прогони тесты в Debug. Какие тесты падают и с какими сообщениями? Объясни, почему арена теперь может выдать ячейку, адрес которой читается как символ, и почему это случается не с каждой ячейкой. Прогони то же в ReleaseFast и сравни, что изменилось в сообщениях.

CHK-8★★★

Перейди на числа n << 1 | 1 с разрядностью i63. Какие тесты шага упадут и почему? Какой бит пришлось бы тогда отдать сборщику мусора и как пришлось бы перекроить теги символа, замыкания и примитива, чтобы он остался свободным у всех видов?

Итоги

Массив в машине это адрес начала и размер элемента, больше ничего. Доступ по индексу это base + i * size, где size часто прячется в масштабном множителе адреса (base,index,4).
Масштаб бывает только 1, 2, 4 или 8. Для элементов такого размера умножения нет: оно уходит в сам адрес.
Двумерный массив row-major это строки подряд. A[i][j] это base + (i * cols + j) * size. Если ширина строки степень двойки, внешний индекс уходит в shl; если нет, появляется lea или настоящий imul.
Массив с шириной строки, известной только в рантайме, всегда стоит одного imul на доступ, потому что множитель это регистр, а не число.
Поле структуры это фиксированное смещение, вшитое в инструкцию: 0x8(%rdi). Тип поля виден по мнемонике: movzbl это байт, movsd это f64 в xmm, movq это восемь байт.
По ассемблеру доступа можно восстановить смещения и типы полей, а промежутки между ними это padding. Проверка себя через @offsetOf закрывает реверс.
Padding растёт из выравнивания: поле по своему размеру, структура по максимуму полей, хвост добит до этого максимума. Порядок полей меняет размер, перестановка по убыванию выравнивания даёт минимум.
В режиме auto Zig укладывает поля минимально сам; в extern struct порядок фиксирован ради C ABI, и следить за дырами приходится вручную.
Объединение кладёт все поля на смещение 0: любое чтение идёт по одному адресу, меняется только ширина mov. Размер равен самому большому полю.
Шаг zl: значение стало тегированным указателем в одно слово. Ячейка выровнена на 16, nil это ноль, число это n << 3 | 1, пара это голый адрес, бит 1 оставлен сборщику мусора. Значение ужалось с 16 байт до 8, ячейка с 32 до 16, а ReleaseSafe ловит забытый тег как incorrect alignment.

Дальше

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

домашка

Домашка

Опиши доступ к элементу трёхмерного массива A[i][j][k] формулой, сними ассемблер функции доступа под ReleaseFast и найди в нём два умножения.S
По ассемблеру четырёх функций доступа восстанови смещения и типы полей структуры, потом проверь себя через @offsetOf.S
Возьми структуру из своего кода, посчитай padding в extern struct, переставь поля в минимальный размер и сверь с auto.M