Блог*

#meme про Chrome

It is Wednesday, my dudes. Последняя Wednesday этого месяца.

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

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.

Но прежде, чем выписывать общую операцию, немного подумаем, как именно выразить запись очередного значения. Именно, в нашем 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 потребляет байты напрямую:

Все эти способы объединяет один недостаток: они толком не позволяют отловить ситуацию, когда мы по каким-то причинам ошиблись в подсчёте размера итогового буфера и предоставили его меньшего размера, чем надо. Так что я в итоге выбрал способ, отличный, от всех этих: прокидываемый индекс является индексом, на единицу бо́льшим места, куда нужно писать очередной байт. Безусловно, это означает - 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, равный его длине.

#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) — громоздко и, вообще говоря, избыточно.

Наиболее пострадавшие от пожаров лесные массивы засадят цифровыми деревьями Текст: Виталий Манн

Какая же жиза.

Погладил лысого

💅

Name squatting is a huge problem on crates.io Now also malicious intent was detected in some of the crates with popular names like postgress - https://blog.phylum.io/rust-malware-staged-on-crates-io/

#prog #article Как делается OpenSource: личный опыт От автора sane-airscan и ipp-usb.

Эм...

При устройстве на работу: - Условия мне нравятся, и индустрия у вас интересная, но скажите, какой у вас технологический стек? - Мы используем Rust и Tokio на бэкенде @ Rust и Tokio на бэкенде

Так, всё стало ещё страннее. Я тут обратил внимание, что вообще-то выделял память с выравниванием 1 🤦‍♂️ Начал выделять с выравниванием на страницу и результаты стали совсем странными. Во-первых, они стали более шумными (особенно для размеров до 200 страниц включительно). Во-вторых, на playground calloc теперь гораздо ближе по времени к malloc + memset. Иногда время может отличаться в два раза, причём в обе стороны (!). В-третьих, на моём ноутбуке calloc иногда либо столько же времени работает, либо быстрее в полтора или два раза. Я в ещё большем недоумении.