Мощь и сложность Comptime и Inline в Zig

Эд Ю (@edyu на Github и @edyu в Twitter)

23 августа 2023 г.

Введение

Zig — это современный язык системного программирования, и хотя он претендует на звание лучшего языка C, многие люди, которые изначально не нуждались в системном программировании, были привлечены к нему из-за простота синтаксиса по сравнению с такими альтернативами, как C++ или Rust.

Однако из-за мощи языка некоторые синтаксисы не очевидны для тех, кто впервые знакомится с языком. На самом деле я был одним из таких людей.

Сегодня мы рассмотрим уникальный аспект метапрограммирования в Zig в его ключевых словах comptime и inline. Я всегда знал, что comptime особенный в Zig, но никогда не использовал его широко до недавнего времени, когда реализовал стирающее кодирование. Хотя в новой реализации удалена большая часть comptime, использованного в проекте, я считаю, что это поясняет мой путь обучения в comptime (и inline) при реализации первоначальной, в основном comptime версии этого проекта, потому что это позволило мне, безусловно, получить лучший результат. понять как силу, так и ограничение comptime.

WTF - это Comptime

Если вы начнете изучать Zig, вы обязательно встретите ключевые слова comptime и заметите, что они разбросаны во многих местах.

Например, в подписи к ArrayList вы заметите, что она написана как pub fn ArrayList(comptime T: type) type. Вы знаете, что когда вы создаете ArrayList, вам необходимо передать такой тип, как var list = std.ArrayList(u8).init(allocator);.

Скорее всего, вы учтете, что когда вы объявляете тип как параметр функции, вам нужно объявить этот тип как comptime. И для многих случаев использования это все, что вам нужно знать о comptime и идти своим путем.

Лорис Кро написал Что такое Comptime Зига? в 2019 году, и вы можете сначала прочитать его.

Итак, что же такое comptime? Если мы посмотрим на это буквально, часть comp в comptime означает компиляция, поэтому comptime на самом деле означает время компиляции. Ключевое слово comptime — это метка, которую можно применить к переменной, чтобы указать, что переменную можно изменить только в течение comptime, чтобы после компиляции программы и во время время выполнения (при запуске программы) эта переменная по сути const.

Это было слишком громко, так зачем вам создавать переменную comptime? Это позволит вам создавать макросы), потому что макросы — это время компиляции. И обратите внимание, что одной из причин, по которой Андрей изначально создал Zig, является удаление макросов из C, поэтому comptime является ответом на C. вариант использования макроса. Я знаю, что предыдущие предложения несколько противоречивы, поэтому на самом деле я имею в виду, что comptime был изобретен для того, чтобы разрешить варианты использования макросов с использованием вместо него comptime.

Теперь вопрос: что такое макрос? Один из способов подумать об этом состоит в том, что макросы — это замены, которые происходят во время во время компиляции как часть препроцессора. Препроцессор — это шаг перед обычной компиляцией (хотя обычно это происходит как часть компиляции).

Например, в C вы часто используете макросы для определения констант, например:

// a constant
#define MY_CONST 5

И после того, как вы определите константу, вы сможете использовать ее в любом месте вашего кода. Препроцессор заменит везде, где используется макрос, определенным значением (в данном случае 5).

printf("The constant is %d", MY_CONST);

В Zig вы можете просто сказать:

const MY_CONST = 5;

std.debug.print("The constant is {d}", .{MY_CONST});

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

// square a number
// you need the () around x because you might call square(4 + 2)
#define square(x) ((x) * (x))
// find the minimum of 2 numbers
#define min(a, b) (((a) < (b)) ? (a) : (b))

WTF это встроенный

Так чем же могут быть полезны эти макросы C? Почему мы не можем просто определить их как обычные функции?

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

В этом случае Zig ввел ключевое слово inline, чтобы вы могли делать следующее:

// note that this will overflow
// but I left it in this form intentionally
// to mimic the simplicity of the C macro
pub inline fn square(x: i32) i32 {
    return x * x;
}

pub inline fn min(a: i32, b: i32) i32 {
    return if (a < b) a else b;
}

test "square" {
    try std.testing.expectEqual(9, square(3));
    try std.testing.expectEqual(25, square(3 + 2));
}

test "min" {
    try std.testing.expectEqual(min(2, 3), 2);
    try std.testing.expectEqual(min(3, 3), 3);
    try std.testing.expectEqual(min(-1, -3), -3);
}

Как вы можете видеть, используя inline, Zig эффективно встраивает (заменяет) вызовы функций в код, не неся накладные расходы, связанные с вызовом функции.

WTF - это Comptime_Int

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

pub fn squareComptime(comptime x: comptime_int) comptime_int {
    return x * x;
}

pub inline fn minComptime(comptime a: comptime_int, comptime b: comptime_int) comptime_int {
    return if (a < b) a else b;
}

test "squareComptime" {
    try std.testing.expectEqual(9, squareComptime(3));
    try std.testing.expectEqual(25, squareComptime(3 + 2));
}

test "minComptime" {
    try std.testing.expectEqual(minComptime(0, 0), 0);
    try std.testing.expectEqual(minComptime(30000000, 30000000000), 30000000);
    try std.testing.expectEqual(minComptime(-10, -3), -10);
}

Обратите внимание, что я отметил squareComptime как обычную функцию, а minComptime обозначил как функцию inline. Другими словами, inline и comptime не являются эксклюзивными друг для друга. Вам не обязательно иметь оба, даже если оба используются во время во время компиляции.

Почему бы не Comptime все

Когда я впервые начал использовать comptime, я осознал две проблемы:

  1. comptime каким-то образом загрязняет код, которого касается. Я имею в виду, что как только вы что-то comptime, все, что оно использует, также должно быть comptime. Позже я покажу более сложный пример.
  2. Другая проблема заключается в том, что как только вам понадобится начать использовать значение время выполнения, например передать аргумент командной строки, вы столкнетесь с ошибками при компиляции кода.

Позвольте мне проиллюстрировать здесь проблему 2. Скажем, я хочу передавать числа во время выполнения, передавая число в командной строке (та же проблема с файлом или с пользовательским вводом), вам будет сложно вызвать squareComptime и minComptime версии.

Мой друг [InKryption] лаконично выразил это в цитате: «comptime существует в своего рода чистой сфере, где ввод-вывод не существует».

Если вы попытаетесь передать в функцию аргумент командной строки:

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();
    const args = try std.process.argsAlloc(allocator);
    defer std.process.argsFree(allocator, args);
    var x = try std.fmt.parseInt(i32, args[1], 10);
    var y = squareComptime(x);
    std.debug.print("square = {d}\n", .{y});
}

И затем запустите программу:

> zig run main.zig -- 1337

Вы столкнетесь со следующей ошибкой:

error: unable to resolve comptime value
var y = squareComptime(x);

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

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

test "comptime" {
    comptime var y = squareComptime(1337);
    // you can now pass y to anything that requires comptime
    comptime var z = minComptime(y, 7331);
    try std.testing.expectEqual(z, 1337);
}

Единственный способ исправить проблему 2 — сделать ваши функции отличными от comptime.

// while we are at it, might as well fix the overflow problem
pub inline fn squareNoOverflow(x: i32) u64 {
    return @intCast(std.math.mulWide(i32, x, x));
}

pub fn main() !void {
    var gpa = std.heap.GeneralPurposeAllocator(.{}){};
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();
    const args = try std.process.argsAlloc(allocator);
    defer std.process.argsFree(allocator, args);
    var x = try std.fmt.parseInt(i32, args[1], 10);
    var y = squareNoOverflow(x);
    std.debug.print("square = {d}\n", .{y});
}

Теперь запустите его с аргументом командной строки:

> zig run main.zig -- 1337
square = 1787569

Развертывание циклов с помощью Inline

Я уже упоминал об одном распространенном использовании inline, добавляя к объявлению функции ключевое слово inline для встраивания функции из соображений эффективности. Еще более распространенное использование, чем встраивание функции с помощью inline, заключается в развертывании цикла путем добавления к циклу for префикса inline.

Например, мне нужно вычислить факториал числа. Мы знаем, что факториал числа n записывается как n! и означает n * (n - 1) * (n - 2)...1. Другими словами, 2! — это 2 * 1 = 2, 3! — это 3 * 2 * 1 = 6, 4! — это 4 * 3 * 2 * 1 = 24 и так далее. В особых случаях 1! и 0! они оба равны 1.

Хотя факториал часто записывается как рекурсивная функция, достаточно просто и эффективно использовать цикл for.

Давайте напишем версию comptime:

pub fn factorial(comptime n: u8) comptime_int {
    var r = 1; // no need to write it as comptime var r = 1
    for (1..(n + 1)) |i| {
        r *= i;
    }
    return r;
}

Когда вы добавляете к циклу for префикс inline, вы фактически разворачиваете цикл, так что каждая итерация цикла выполняется последовательно без ветвления. Обычно это делается также из соображений эффективности.

Когда вы inline цикл, он по-прежнему может выполнять работу, но ветвление цикла и переменные итерации теперь равны comptime.

pub fn factorial(comptime n: u8) comptime_int {
    var r = 1; // no need to write it as comptime var r = 1
    inline for (1..(n + 1)) |i| {
        r *= i;
    }
    return r;
}

WTF — это функция типа

Настоящая сила comptime заключается в так называемой функции типа. Ранее, когда я показывал подпись ArrayList, на самом деле это функция типа. Функция типа — это просто функция, возвращающая тип.

Давайте еще раз посмотрим на ArrayList функцию типа:

pub fn ArrayList(comptime T: type) type {
    return ArrayListAligned(T, null);
}

Как видите, поскольку функция типа возвращает тип, имя функции по соглашению обычно пишется с заглавной буквы, как если бы это был тип. По сути, вы можете использовать функцию типа везде, где обычно требуется тип, например, в аннотации типа, аргументах функции и даже возвращаемых типах. Однако обратите внимание, что имя функции типа само по себе не является типом, поскольку это функция, и вам нужно фактически предоставить ей необходимые параметры. Например, ArrayList не является типом, а ArrayList(u8) является типом, поскольку ArrayList функция типа требует тип в качестве параметра, указанного как comptime T: type.

Например, скажем, мне нужно реализовать функцию, которая позволит мне вычислить комбинаторику m choose n. Из школьного курса математики вы знаете, что (m choose n) равно m! / (n! * (m-n)!). Другими словами, если у вас есть 3 предмета и вы хотите получить все комбинации из 2 предметов из этих 3 раз, вы можете использовать такую ​​функцию, чтобы подсчитать, сколько уникальных комбинаций вы получите. Итак, для (3 choose 2) у вас есть 3! / (2! * 1!) = (6 / 2) = 3.

Для выполнения математических вычислений вы можете использовать следующую функцию:

pub fn numChosen(comptime m: u8, comptime n: u8) comptime_int {
    return factorial(m) / (factorial(n) * factorial(m - n));
}

Если вы хотите получить все реальные перестановки такой комбинаторики, вам нужно каким-то образом сгруппировать перестановки вместе, а для (3 choose 2) или 6 перестановок вам нужно иметь группу из 6 элементов, где каждый элемент представляет собой комбинацию из 2 индексы. Например, предположим, что у вас есть (0, 1, 2) на входе, и вы хотите получить массив [6][2]u8, который представляет собой массив из 6 элементов, где каждый элемент представляет собой массив из 2 u8s.

Причина, по которой мы используем массив вместо ArrayList, состоит в том, чтобы не только иметь возможность находить перестановки в comptime, но и нам не нужно иметь дело с распределителями.

Чтобы это работало, нам нужна функция типа, которая упростила бы тип возвращаемого значения нашей функции.

pub fn ChosenType(comptime m: u8, comptime n: u8) type {
    comptime var t = numChosen(m, n);
    return [t][n]u8;
}

Как видите, эта функция вызывает ранее определенную numChosen для расчета количества элементов в возвращаемом типе массива. Тип возвращаемого значения функции типа — это тип.

Теперь перейдем к окончательной реализации функции choose, которая возвращает все перестановки.

pub fn choose(comptime l: []const u8, comptime k: u8) ChosenType(l.len, k) {
    std.debug.assert(l.len >= k);
    std.debug.assert(k > 0);
    var ret: ChosenType(l.len, k) = std.mem.zeroes(ChosenType(l.len, k));
    if (k == 1) {
        inline for (0..l.len) |i| {
            ret[i] = [k]u8{l[i]};
        }
        return ret;
    }
    comptime var c = choose(l[1..], k - 1);
    comptime var i = 0;
    inline for (0..(l.len - 1)) |m| {
        inline for (0..c.len) |n| {
            if (l[m] < c[n][0]) {
                ret[i][0] = l[m];
                inline for (0..c[n].len) |j| {
                    ret[i][j + 1] = c[n][j];
                }
                i += 1;
            }
        }
    }
    return ret;
}

Порядок зависимости аргументов Comptime и тип возвращаемого значения

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

Однако существует порядок зависимости переменных comptime. Я имею в виду, что если у вас есть 2 параметра comptime, то последний параметр может зависеть от более раннего параметра comptime. Это справедливо независимо от количества параметров в функции, а тип возвращаемого значения функции может зависеть от значений comptime переменных, определенных в параметрах функции.

В функции choose тип возвращаемого значения ChosenType(m, n) зависит от обоих двух параметров в аргументах функции. В этой конкретной функции это фактически зависит от длины первого фрагмента comptime и числа, переданного в качестве второго аргумента.

Более сложный пример — это мой код, где, хотя мне и не нужно было передавать параметр comptime z, мне пришлось это сделать, потому что мне нужен этот параметр, чтобы определить, на какую матрицу можно разрешить умножение, и матрицу результата. Другими словами, когда вы умножаете матрицу m x n (собственная) на матрицу n x z (другое), вы знаете, что типом должна быть матрица m x z (тип возвращаемого значения). Однако, поскольку я не могу указать параметр (другой) матрицы, не зная обоих значений n и z из какого-либо другого параметра, за исключением случаев, когда он уже передан в качестве аргумента, мне приходится принять дополнительный параметр z.

pub fn multiply(self: *Self, comptime z: comptime_int, other: BinaryFieldMatrix(n, z, b)) !BinaryFieldMatrix(m, z, b)

В этом конкретном объявлении функции BinaryFieldMatrix также является функцией типа.

На самом деле это одно из проявлений проблемы 1, о которой я упоминал ранее в разделе WTF — это Comptime_Int.

Первоначально я сделал Matrix функцией типа, которая принимает значения comptime, и это сделало BinaryFiniteField и BinaryFieldMatrix функцией типа, что, в свою очередь, сделало мою ErasureCoder также функцией типа , и все зависело от значений comptime для инициализации, что отлично сработало, когда я тестировал код.

Однако, когда я начал выполнять код, указав аргументы командной строки, я понял, что не могу передать какие-либо аргументы командной строки для создания ErasureCoder, поскольку аргументы командной строки не могут быть принудительно преобразованы в comptime, даже если я добавляю к имени переменной comptime.

Теперь я хочу закончить фразой: «Великая сила предполагает большую ответственность». Пользуйся своим comptime с умом, друг мой!

Бонус

Ключевое слово comptime фактически можно поставить перед любым выражением, например циклом, блоком или даже функцией.

Когда вы это сделаете, вы фактически создадите это выражение comptime.

Например, когда вы вызываете функцию факториала, вы можете добавить comptime к вызову функции, и тогда функция будет запущена во время компиляции, и для вычисления факториала не потребуется никаких ресурсов времени выполнения. Поэтому не имеет значения, 5! или 10! во время выполнения, на самом деле это просто константа, рассчитанная во время во время компиляции.

pub fn main() !void {
    const z = comptime factorial(50);
    std.debug.print("10! = {d}\n", .{z});
}
> zig run main.zig
10! = 3628800

Конец

Вы можете прочитать блог Лориса Кро Что такое Comptime Зига?.

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

Особая благодарность InKryption за помощь в вопросах comptime!

Проект стирающего кодирования, о котором я упоминал ранее, здесь.