#prog #rust #моё

(этот текст является логическим продолжением моей статьи о compile time Fizzbuzz, так что если вы её ещё не читали — настоятельно рекомендую начать с неё)

Кое-что при реализации всего этого дела я упустил: конечным продуктом всех этих type-level-конструкций является гетерогенный список из enum, и код для вывода итоговой строки подгружает эти enum, бранчится по им и для каждого вызывает println!("{}", s.as_str()). В оптимизированном коде бранчи, разумеется, уходят — так как они известны статически — но даже так на каждый Str вызывается _print, которая в конечном счёте вызывает io::Write::write_fmt на LineWriter. Это, мягко говоря, неоптимально.

Как же можно было сделать лучше? Таки сделать ответ одной строкой, которая ляжет литералом в сегмент данных, и вызвать write_all на Stdout. Это всё ещё пойдёт через построчную буферизацию, но всё же не будет вызывать машинерию std::fmt, которая очень плохо вычищается оптимизатором. Можно было бы сделать ещё быстрее путём вызова системных функций вызова напрямую, но этот подход требует небезопасного и вдобавок платформо-зависимого кода, так что я решил не идти по этому пути.

Самое обидное, что получение ответа в виде одного слайса не просто возможно, а было возможно ещё на момент публикации статьи на актуальной тогда версии Rust 1.55.0! Но, впрочем, достаточно с введением, перейдём к делу.

Итак, получение байтиков. Как нам это сделать? Нужно взять массив байтов нужного размера и последовательно записать в него нужные значения. Размер искомого массива подсчитать, в принципе, возможно — мы знаем, сколько байт нужно на каждое число, сколько байт нужно на каждое слово — нужно только не забыть прибавить по месту на перевод строки на каждое значение в списке.

Подумаем немного о том, как именно мы будем заполнять этот массив. Заполнение его с начала кажется логичным, но по факту сопряжено с трудностями. Создание нужного значения как ассоциированной константы не представляется возможным, поскольку поток управления будет идти от голов Cons-ов к хвостам, но при индуктивных определениях констант поток данных идёт, наоборот, от конечного Nil вверх к обрамляющим Cons. Прибавим к этому тот факт, что прямое заполнение наверняка потребовало бы методов на трейтах (но это не точно), которые пока не поддерживаются в const fn, а также тот факт, что наиболее очевидный способ получения цифр числа выдаёт их в "обратном" порядке — от младших разрядов к старшим — и вам станет понятно, почему я решил заполнять итоговый массив от конца к началу.

Теперь немного подумаем об интерфейсе для этих операций. Наиболее удобно было бы отдавать в функции мутабельные ссылки на слайсы, но мутабельные ссылки в const fn, опять-таки, пока не разрешены. Посему придётся принимать массив аргументом и его же и возвращать — как следствие, везде придётся тягать через const generics его размер. Так как слайсы использовать не получится, нам также придётся как-то обозначать место, в которое надо писать. Впрочем, ввиду заполнения с конца доступное место для записи всегда будет начинаться с нулевого индекса, а потому для передачи места записи достаточно одного индекса.

Кажется очевидным, что это должен быть индекс места, куда нужно писать очередной байт. Но не всё так просто. Дело в том, что после записи очередного символа это индекс нужно декрементировать. А что будет при записи нулевого байта — первого по порядку в итоговой строке и последнего по порядку записи? Будет декрементация нулевого индекса — и так как индексы в Rust беззнаковые, а вычислитель константных выражений ловит underflow, после записи нулевого байта произойдёт ошибка вычисления константного выражения, которая зафейлит всю компиляцию.

Для решения этой проблемы есть несколько способов решения разной степени поганости:

* использовать знаковые индексы — но тогда придётся кастить их на каждой индексации.
* каким-то образом отделять последнюю итерацию цикла заполнения — неудобно и придётся прокидывать через все операции.
* вместо условного idx -= 1 писать idx = idx.saturating_sub(1) — громоздко и, вообще говоря, избыточно.

Все эти способы объединяет один недостаток: они толком не позволяют отловить ситуацию, когда мы по каким-то причинам ошиблись в подсчёте размера итогового буфера и предоставили его меньшего размера, чем надо. Так что я в итоге выбрал способ, отличный, от всех этих: прокидываемый индекс является индексом, на единицу бо‌льшим места, куда нужно писать очередной байт. Безусловно, это означает - 1 на всех операциях индексации, но нам не нужно делать последнюю итерацию особым случаем, мы получим ошибку при использовании слишком маленького буфера, а убедиться в том, что буфер не слишком большой, мы можем пост-фактум, проверив, что индекс места для записи равен нулю.

Итак, с этим определились. Теперь нам нужны операции для записи нужных значений в нужное место в переданном массиве байт. Так как нам нужно записывать перевод строки и после чисел, и после fizz/buzz, логично вынести операцию записи строки отдельно (а ещё это даст нам возможность забесплатно поменять используемый разделитель, просто поменяв определение именованной константы):

const fn write_str_at<const N: usize>(
s: &str,
mut bytes: [u8; N],
mut at: usize,
) -> ([u8; N], usize) {
let mut i = s.len();
let s = s.as_bytes();

while i > 0 {
bytes[at - 1] = s[i - 1];
at -= 1;
i -= 1;
}

(bytes, at)
}

Ничего сложного, просто побайтовое копирование строки в нужное место (с конца). Конечно, тот факт, что мы не можем использовать богатый инструментарий std в const fn, делает этот код менее красивым, чем он мог бы быть, но и без этого код довольно понятен. Отмечу, что мы можем передать строку длиннее переданного буфера, но в этом случае код завалится на декременте at и в const-контексте прервёт компиляцию.

С использованием этой вспомогательной функции запись строки с переводом строки становится совсем простой:

const DELIMITER: &str = "\n";

const fn write_str_with_delimiter_at<const N: usize>(
s: &str,
mut bytes: [u8; N],
mut at: usize,
) -> ([u8; N], usize) {
(bytes, at) = write_str_at(DELIMITER, bytes, at);
write_str_at(s, bytes, at)
}

Запись же числа концептуально схожа с записью строки, с той лишь разницей, что нужные значения мы вычисляем на лету вместо того, чтобы индексироваться в строку. Нужно только обработать специальный случай, когда переданное число равно нулю, потому что без этого мы вообще ничего для нуля писать не будем (на самом деле в этой программе этот путь исполнения никогда не затрагивается, потому что создаваемый нами fizzbuzz-список не содержит нуля, но... Давайте не будем писать код со слишком большими допущениями по умолчанию):

const fn write_num_with_delimiter_at<const N: usize>(
mut n: usize,
mut bytes: [u8; N],
mut at: usize,
) -> ([u8; N], usize) {
(bytes, at) = write_str_at(DELIMITER, bytes, at);

if n == 0 {
bytes[at - 1] = b'0';
at -= 1;
return (bytes, at);
}

while n != 0 {
bytes[at - 1] = (n % 10) as u8 + b'0';
at -= 1;
n /= 10;
}

(bytes, at)
}

(я не стал писать не-_delimiter вариант, потому что он и так использовался бы в одном месте)

Хорошо, нужные строительные блоки есть. Теперь нужно собрать их них что-то полезное. Для того, чтобы собрать массив байтиков для гетерогенного списка, нам нужно на шаге индукции получить заполненный массив для хвоста (вместе с местом, куда надо писать дальше) и дописать порцию, соответствующую голове. Базой индукции в этом случае (для Nil) будет чистый массив и at, равный его длине.

Но прежде, чем выписывать общую операцию, немного подумаем, как именно выразить запись очередного значения. Именно, в нашем type-level Fizzbuzz списке лежат элементы двух разных семейств: числа Пеано и Fizz/Buzz/FizzBuzz. Они будут обрабатываться по разному: для чисел Пеано мы записываем их численное представление, а для *zz-типов — фиксированную строку. Вроде всё норм, ничто не мешает нам написать blanket impl для чисел Пеано и по impl-у на каждый из *zz-типов, но... нам же ведь ещё нужно рассчитать размер итогового массива, верно? А там нам нужны будут размеры записываемых строк... Какое-то неприятное дублирование вылезает, а, как известно, в надёжных системах есть только один источник истины.

Что ж, объединим формы представления в единый тип и будем в дальнейшем оперировать его значением:

enum Repr {
Direct(&'static str),
Numeric(usize),
}

Ну и сделаем трейт для представления элементов списка в этом виде:

trait AsRepr {
const REPR: Repr;
}

Напишем реализации. Для чисел Пеано они будут опираться на NumericValue, ну а для *zz-типов это просто строки:

impl<T: NumericValue> AsRepr for T {
const REPR: Repr = Repr::Numeric(T::VALUE);
}

impl AsRepr for Fizz {
const REPR: Repr = Repr::Direct("fizz");
}


// то же самое для `Buzz` и `FizzBuzz` с нужными литералами

Заметим, что Repr даёт нам не только информацию о том, что нужно писать, но и информацию о том, сколько места для этого потребуется. И строки не дублируются. Успех!

(сказанное выше насчёт единого источника истины не относится к числам Пеано, поскольку за счёт NumericValue их числовое значение является их неотъемлемым свойством, а количества места для записи является производным от VALUE значением через n_digits)

Что ж, теперь мы можем написать трейт для представления в виде байтов — и так как мы не хотим затачиваться на конкретный размер, нам нужно обобщить его по размеру итогового буфера:

trait WriteBuf<const N: usize> {
const BUF: ([u8; N], usize);
}

База индукции — нетронутый массив:

impl<const N: usize> WriteBuf<{ N }> for Nil {
const BUF: ([u8; N], usize) = ([0; N], N);
}

(кстати, конкретное значение начального массива несущественно — всё равно оно потом перезаписывается целиком)

За счёт реализаций AsRepr реализация шага индукции очень проста и из всех нетривиальных операций требует лишь match по Repr:

impl<Head, Tail, const N: usize> WriteBuf<{ N }> for Cons<Head, Tail>
where
Head: AsRepr,
Tail: WriteBuf<{ N }>,
{
const BUF: ([u8; N], usize) = {
let (bytes, at) = Tail::BUF;
match Head::REPR {
Repr::Direct(s) =>
write_str_with_delimiter_at(s, bytes, at),
Repr::Numeric(n) =>
write_num_with_delimiter_at(n, bytes, at),
}
};
}

Прежде, чем воспользоваться полученным инструментом, нам нужно рассчитать требуемое место. Делегируем эту задачу ещё одному трейту:

trait WriteLen {
const LEN: usize;
}

База индукции — Nil — ничего не пишет:

impl WriteLen for Nil {
const LEN: usize = 0;
}

Для записи Cons нужно столько же, сколько под хвост, плюс под значение в голове, плюс разделитель:

impl<Head, Tail> WriteLen for Cons<Head, Tail>
where
Head: AsRepr,
Tail: WriteLen,
{
const LEN: usize = Tail::LEN
+ DELIMITER.len()
+ match Head::REPR {
Repr::Direct(s) => s.len(),
Repr::Numeric(n) => n_digits(n),
};
}

Осталось только объединить эти две вещи — и можно прям сразу в константу:

const FIZZ_BUZZ_BYTES: &[u8] = &{
let (precalculated, at) = {
const LIST_WRITE_LEN: usize = <List as WriteLen>::LEN;
<List as WriteBuf<LIST_WRITE_LEN>>::BUF
};

// проверим, что буфер перезаписан целиком
assert!(at == 0);

precalculated
};

Вывод результата элементарен — нам даже не нужно переводить в строку, потому что используемое API потребляет байты напрямую:

use std::io::Write;
std::io::stdout().write_all(FIZZ_BUZZ_BYTES).unwrap();

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

К изложенному выше можно присовокупить кое-что ещё. Внимательный читатель мог заметить, что, по большому счёту, весь итоговый результат требует подачи на вход лишь одного type-level числа, и его одного, в принципе, достаточно, чтобы получить и тип результата, и его значение. А значит, должно быть возможным написать const fn, принимающую на вход ти‌повый параметр и возвращающую итоговый массив.

Внимательный читатель прав... Принципиально. К сожалению, на текущий момент const generics в Rust весьма ограничены. Искомая функция требует написать возвращаемый тип, зависящий от константы, подсчитанной от переданного типа, что в настоящий момент невозможно на stable (это можно обойти при помощи generic-array, но давайте не будем о грустном не будем втягивать лишние зависимости). С другой стороны, в Rust есть нестабильная фича для того, чтобы включить const generics на полную: generic_const_exprs. И вот с её помощью нужную функцию написать вполне реально.

#![feature(generic_const_exprs)]
#![allow(incomplete_features))] // да, я в курсе, что она не готова

const fn to_buf<N>() -> ([u8; FizzBuzzList::<N>::LEN], usize)
where
N: RangeDownFrom,
MakeRangeDownFrom<N>: ReverseWith<Nil>,
RangeTo<N>: EnumerateFromWithCycle<Z, Three>,
EnumerateFromZeroWithCycle3<RangeTo<N>>: EnumerateFromWithCycle<Z, Five>,
FizzBuzzEnumerate<RangeTo<N>>: TailOf,
Tail<FizzBuzzEnumerate<RangeTo<N>>>: ToFizzBuzz,
FizzBuzzList<N>: WriteLen + WriteBuf<{ FizzBuzzList::<N>::LEN }>,
{
<FizzBuzzList::<N> as WriteBuf<{ FizzBuzzList::<N>::LEN }>>::BUF
}

Эту функцию я написал без ошибок с первого раза путём вдумчивого написания кода... Нет, конечно. Я поступил так, как поступил бы любой нормальный Rust-программист: написал функцию с телом и заголовком, а потом добавлял where clauses, о которых услужливо сообщал компилятор. Итоговый результат выглядит устрашающе, но, поверьте, без ти‌повых алиасов это выглядело ещё хуже.

К сожалению, для того, чтобы эта функция компилировалась, нам нужно подправить определение Three и Five — без них компилятор не поймёт, что EnumerateFromWithCycle<Z, Three> и EnumerateFromWithCycle<Z, S<S<S<Z>>>> — это одно и то же:

type Three = S<S<S<Z>>>;
type Five = S<S<S<S<S<Z>>>>>;

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

Что ж, весь код, как всегда, в гисте. Обратите внимание, в этот раз, помимо кода, там есть ещё и Cargo.toml. В него включены две фичи, которые можно легко менять через cargo run/cargo build. Фича use_nightly меняет определение FIZZ_BUZZ_BYTES на использующую ночную фичу функцию to_buf выше. Фича compare_with_previous_impl активирует предыдущую реализацию compile-time Fizzbuzz, а также ассерт, который проверяет, что результаты, полученные разными методами, одинаковы. Фичи можно активировать независимо друг от друга, но use_nightly, разумеется, требует +nigthly.

Кусочек ассемблерного листинга, подтверждающий сказанное выше

It is Wednesday, my dudes.

Последняя Wednesday этого месяца.

#meme про Chrome

А вот с лесбиянками подобное уже не прокатит

#meme про... Мемы?

._.

#quotes #трудовыебудни

#prog

Однако

(thanks @smertig)

Силовики — это массовка, помноженная на акселератов

#prog #rust #abnormalprogramming

Тем временем nnethercote занят по настоящему важными вещами.

(а вот и сами шахматы)

В СМЫСЛЕ УЖЕ СЕНТЯБРЬ

#prog #rust #article

How to speed up the Rust compiler in August 2023

Очередная пачка изменений для ускорения компилятора