В свежем Rust 1.58.0 наконец-то можно использовать переменные напрямую при форматировании строк:

let person = get_person();
// ...
println!("Hello, {person}!"); // captures the local `person`

Пока что это работает только с именами, а не произвольными выражениями, но всё равно приятно. Прощайте format!("{name}", name = name);!

Ещё из плющек:
— теперь *const T указатели можно дерефать в константных контекстах
— Теперь правила ансайзинга для дженерик структур немного проще[1]
— В copy{,_nonoverlapping} опять включили debug_assert'ы[2]
— реализация Clone для RSplit<T, P> больше не требует T: Clone
— Трейт Termiation теперь реализов для Result<Infallible, E>, позволяя писать fn main() -> Result<Infallible, ErrorType>, для програм которые не заканчиваются успешно через выход из main
— Стабилизировали File::options, замену FileOptions::new
— Стабилизировали {Option,Result}::unwrap_unchecked
— Стабилизировали многие методы Duration и MaybeUninit как const fn
— Компилятор теперь будет пытаться применять стабильные методы прежде, чем не стабильные. Это позволит избежать поломок при добавлении в std
методов, пересикающихся по именам с методами из сторонних трейтов.
— rustdoc теперь показывает методы из всех Deref реализаций, рекурсивно (а не только из первой)

[1]: Новые правила позволяют такое:
struct A<T, U: ?Sized + 'static>(T, B<T, U>);
struct B<T, U: ?Sized>(T, U);

fn main() {
let x: A<[u32; 1], [u32; 1]> = A([0; 1], B([0; 1], [0; 1]));
// This previously did not work as the last field of `A` also mentions `T`,
// as only `U` changes this is now allowed thanks to this feature.
let _y: &A<[u32; 1], [u32]> = &x;
}

TL;DR: если последнее поле это структура, которая ансайзиться, то теперь и наружняя структура тоже ансайзиться.

А полные новые правила такие:
— the tail field depends on at least one type or const parameter not used in any other field
— the target struct can be created from the source by replacing only the parameters only found in the last struct field
— the tail field implements Unsize from source to target

[2]: Ранее они были отключены из-за того, что их нельзя выполнить в const fn

Полный список изменений: RELEASES.md#version-1580-2022-01-13

#prog #rust

Хозяйке на заметку

Как известно, если у типа в Rust есть несколько методов от разных трейтов с одними и теми же именами, то попытка вызвать один из них при помощи синтаксиса метода будет прервана компилятором с жалобой на неоднозначность имён, вынуждая прибегнуть к развёрнутому синтаксису вызова (Trait::method(&value, arg1, arg2)). Менее известен тот факт, что методы самого типа (inherent methods) перекрывают одноимённые методы трейтов, так что если одному имени отвечают метод типа и сколько угодно методов трейтов, то предпочтение всегда отдаётся методу самого типа и не вызывает неоднозначностей. Этим можно воспользоваться, чтобы иметь возможность в необобщённом контексте вызывать методы трейта, не импортируя сам трейт:

trait Trait {
fn method(&mut self, arg: Arg);
}

struct Type {
...
}

impl Trait for Type {
fn method(&mut self, arg: Arg) {
...
}
}

impl Type {
fn method(&mut self, arg: Arg) {
Trait::method(self, arg)
}
}

// где-то в другом месте, где в текущем пространстве имён
// есть Type, но нету Trait:

let mut value = Type::make(...);
value.method(arg);

#prog #rust #моё

Допустим, нам нужно сделать на Rust бинарное дерево. Казалось бы, плёвое дело:

struct TreeNode<T> {
value: T,
left: Option<Box<Self>>,
right: Option<Box<Self>>,
}

struct Tree<T> {
root: Option<TreeNode<T>>,
}

Однако тут у нас по аллокации на каждый узел, от чего у нас страдает локальность данных и, как следствие, эффективность кеша (не говоря уже о стоимости аллокаций в рантайме). С другой стороны, у нас есть возможность делать дерево произвольной (насколько хватит оперативки, конечно же) высоты. А можем ли мы, отказавшись от произвольной высоты и задавая её предел наперёд, хранить вложенные узлы напрямую, а не через указатель? Как оказалось, да!

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

struct Z;
struct S<T>(T);

Теперь немного подумаем о том, как это отобразить на древовидную структуру. Каждый узел дерева высотой N + 1 включает в себя узлы высотой N. Узел же дерева с высотой 0 не должен включать в себя данные вообще. Этого можно добиться, сопоставив Z тип с полями ненаселённого типа.

Кажется, что это изложение довольно легко перекладывается на код: определяем трейт с ассоциированным типом, который уменьшает число на единицу, реализуем его для S<T> с типом T, а для Z с типом never Infallible, параметризуем узел высотой Height и параметризуем вложенные узлы <Height as Decrement>::Output... К сожалению, это не работает: если определить узел таки образом, rustc не понимает, что рекурсия рано или поздно кончается, и жалуется на бесконечную вложенность типа без индирекции. Кажется, нам нужен другой подход.

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

struct Node<T, Next> {
value: T,
left: Next,
right: Next,
}

Тут важно, что поля left и right имеют тип Next, а не Option<Next>, иначе мы не сможем сделать узел нулевой высоты ненаселённым типом. Собственно, вот как отображение выглядит для Z:

use std::convert::Infallible as Never;

trait Project<T> {
type Projected;
}

impl<T> Project<T> for Z {
type Projected = Node<T, Never>;
}

Итого узел нулевой высоты нельзя сконструировать, как мы и хотели. Лишь немногим сложнее выглядит отображение для S<N>:

impl<T, N> Project<T> for S<N>
where
N: Project<T>,
{
type Projected = Node<T, Option<N::Projected>>;
}

Так как мы не хотим оперировать узлами напрямую (хотя бы потому, что через них затруднительно наложить ограничение на высоту), сделаем обёртку — собственно параметризованное высотой дерево:

struct Tree<T, Height: Project<T>> {
repr: Height::Projected,
}

Теперь реализуем парочку вспомогательных методов и попробуем сделать дерево высоты 2 (=S<S<Z>>):

let tree: Tree<i32, S<S<Z>>> = Node {
value: 42,
left: None,
right: Some(Node {
value: 42,
left: None,
right: None
}),
}.into();

Что ж... Оно работает. И даже нормально печатается поле repr, если добавить #[derive(Debug)] на Node. Попробуем теперь поменять тип дерева на дерево с единичной высотой:

let tree: Tree<i32, S<Z>> = Node {
...

Компилятор ожидаемо жалуется:

error[E0271]: type mismatch resolving <Z as Project<i32>>::Projected == Node<{integer}, Option<_>>
   --> src/main.rs:181:7
    |
181 |     }.into();
    |       ^^^^ expected enum Option, found enum Infallible
    |
    = note: expected struct Node<{integer}, Option<_>>
               found struct Node<i32, Infallible>

Не слишком внятно, но цели статически ограничить высоту дерева мы успешно достигли.

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

Оставайтесь на связи. 🤙

> Антон делает то, что я люблю в программировании больше всего — совершенно беcсмысленный, возведённый в абсолют бред, на который потрачено больше времени, чем стоило бы<...>

Ах, Вафель, ты был абсолютно прав.

Кстати, к него на канале уже 400 человечков! 👀🎉

#prog #rust #article

Why is my Rust build so slow? — офигенная статья от Амоса про ускорение компиляции большого проекта на Rust

#prog #performancetrap #rust #article

How a Single Line of Code Made a 24-core Server Slower Than a Laptop

TL;DR: Arc::clone на машине с кучей ядер

#prog #rust #article

Writing Non-Trivial Macros in Rust — полезная статья о том, как поэтапно писать на Rust (относительно) сложные декларативные макросы. Ссылается на The Little Book of Rust Macros, которая сама по себе достойна прочтения.

#prog #rust #моё

В крейте pulldown-cmark есть структура Options, в которой хранятся опции для конфигурирования поведения парсера. Эта структура перемещается внутрь парсера при создании и в процессе парсинга флаги оттуда только считываются, но никогда не меняется. Звучит, как идеальный кандидат для вынесения на уровень типов.

Я решил провести эксперимент: поменять определение Options с этого:

bitflags::bitflags! {
pub struct Options: u32 {
const ENABLE_TABLES = 1 << 1;
const ENABLE_FOOTNOTES = 1 << 2;
const ENABLE_STRIKETHROUGH = 1 << 3;
const ENABLE_TASKLISTS = 1 << 4;
const ENABLE_SMART_PUNCTUATION = 1 << 5;
const ENABLE_HEADING_ATTRIBUTES = 1 << 6;
}
}

на это:

pub struct Options<
const ENABLE_TABLES: bool,
const ENABLE_FOOTNOTES: bool,
const ENABLE_STRIKETHROUGH: bool,
const ENABLE_TASKLISTS: bool,
const ENABLE_SMART_PUNCTUATION: bool,
const ENABLE_HEADING_ATTRIBUTES: bool,
>(());

Там, где в коде был вызов, скажем, options.contains(Options::ENABLE_TABLES), в моём варианте стал вызов options.enable_tables() — метод, который просто возвращает значение параметра ENABLE_TABLES. Имея на руках доказуемо константные значения, компилятор может убрать из кода if-ы и вместе с ними лишний код, что должно снизить объём генерируемого кода для каждого варианта парсинга и повысить производительность за счёт отсутствия ветвлений.

Я запустил бенчмарки (кстати, разрабы молодцы, они используют criterion), ожидая увидеть увеличение ПЕРФОРМАНСА. И я действительно его увидел... На бенчмарках, число которых можно было пересчитать по пальцам одной руки. Во всех остальных бенмарках производительность либо не поменялась, либо — что было куда чаще — статистически значимо ухудшилась. 😒

То ли я неверно бенчмаркаю (что вполне может быть, ибо на фоне у меня таки висел VS Code), то ли я чего-то не знаю об оптимизирующих компиляторах. Короче, я разочарован, опечален и сконфужен.

Антон:
— Rust — простой язык, чего вы?

Тоже Антон:
<List as AsStrList<{ n_digits(<N as NumericValue>::VALUE) }>>::LIST

Обновил прошивку своего чипа

#prog #meme

#prog #go #article

How does Go calculate len()..?

Статья о том, как встроенная функция Go len, применимая к пяти семействам типов (слайс, массив, строка, мапа, канал), преобразуется в конкретные операции для каждого типа — от парсинга до кодгена

F::<()> { ptr: &(), __: <_>::default() }

Just normal code written by normal rust programmers

А потом ты узнаешь, что это всё вафель и добавил

#prog

В кодогенераторе cranelift (который, помимо всего прочего, планируют использовать как бекенд rustc для отладочных билдов) для аллокации регистров используется библиотека regalloc2. В репозитории есть занятный документ — обзор дизайна regalloc2, включающий в себя ожидания от входных данных, высокоуровневую структуру алгоритма, разбор используемых структур данных и различные заметки по поводу производительности (под которые отведён отдельный раздел, но по факту есть и в других местах).

Некоторые интересные цитаты:

* A performance note: merging is extremely performance-sensitive, and it turns out that a mergesort-like merge of the liverange vectors is too expensive, partly because it requires allocating a separate result vector (in-place merge in mergesort is infamously complex). Instead, we simply append one vector onto the end of the other and invoke Rust's builtin sort.

* For each of the preferred and non-preferred register sequences, we probe in an offset manner: we start at some index partway through the sequence, determined by some heuristic number that is random and well-distributed. <...> We then march through the sequence and wrap around, stopping before we hit our starting point again.

The purpose of this offset is to distribute the contention and speed up the allocation process. In the common case where there are enough registers to hold values without spilling (for small functions), we are more likely to choose a free register right away if we throw the dart at random than if we start every probe at register 0, in order. This has a large allocation performance impact in practice.

* We got substantial performance speedups from using vectors rather than linked lists everywhere. This is well-known, but nevertheless, it took some thought to work out how to avoid the need for any splicing, and it turns out that even when our design is slightly less efficient asymptotically (e.g., apend-and-re-sort rather than linear-time merge of two sorted liverange lists when merging bundles), it is faster.

* We use a "chunked sparse bitvec" to store liveness information, which is just a set of VReg indices. The design is fairly simple: the toplevel is a HashMap from "chunk" to a u64, and each u64 represents 64 contiguous indices. <...> We tried a number of other designs as well. Initially we used a simple dense bitvec, but this was prohibitively expensive: O(n^2) space when the real need is closer to O(n) (i.e., a classic sparse matrix). We also tried a hybrid scheme that kept a vector of indices when small and used either a bitvec or a hashset when large. This did not perform as well because (i) it was less memory-efficient (the chunking helps with this) and (ii) insertions are more expensive when they always require a full hashset/hashmap insert.

#science #article

Прекрасная интерактивная статья, рассказывающая о том, как работает GPS, с поэтапным учётом всё новых и новых обстоятельств.

(thanks @jemalloc)