#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)

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

assert!(() == {});
assert!((42) == {42});

#prog #rust #моё

Тем временем в комментариях вспомнили weird-exprs.rs — "Just a grab bag of stuff that you wouldn't want to actually write.". Если быть точнее, то функцию special_characters. Выглядит она так:

fn special_characters() {
let val = !((|(..):(_,_),__@_|__)((&*"\\",'🤔')/**/,{})=={&[..=..][..];})//
;
assert!(!val);
}

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

let val = !((|(..):(_,_),__@_|__)((&*"\\",'🤔'),{})=={&[..=..][..];});

Справа отрицание некоего выражения. Вынесем его в отдельную переменную и заодно уберём наружные скобки:

let tmp = (|(..):(_,_),__@_|__)((&*"\\",'🤔'),{})=={&[..=..][..];};
let val = !tmp;

Хм, определение tmp всё ещё выглядит сложноватым... Может, вызвать rustfmt?

let tmp = (|(..): (_, _), __ @ _| __)((&*"\\", '🤔'), {}) == {
&[..= ..][..];
};

Сильно проще не сделало, но зато теперь видно, что корень дерева выражений — это операция равенства. Посмотрим, что тут справа:

{
&[..= ..][..];
}

Хм, что тут у нас? У нас тут массив размера 1, в котором лежит выражение ..= .. (первый рендж, кстати, биндится первым и потому выражение в целом имеет тип RangeToInclusive<RangeFull>), который индексируется RangeFull, что работает за счёт deref coercion к соответствующему типу слайса, на полученный слайс берётся ссылка...

Но всё это можно было бы и не рассматривать, поскольку строчка оканчивается точкой с запятой, а потому выражение, каким бы оно ни было, отбрасывается, и в целом получается statement. А блок, который оканчивается statement-ом, как известно, возвращает в Rust ().

Итак, с правой часть равенства разобрались. А что же с левой?

(|(..): (_, _), __ @ _| __)((&*"\\", '🤔'), {})

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

|(..): (_, _), __ @ _| __

Между чёрточками тут два аргумента, разделённых запятой. И тут на полной используется тот факт, что на месте аргументов можно использовать не только идентификаторы, но и произвольные (но которые тайпчекаются, разумеется) паттерны. Вот первый аргумент:

(..): (_, _)

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

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

struct ManyFields(i32, String, char, u8, i32);

fn foo(mf: ManyFields) {
    let ManyFields(..) = mf;
}

Можно даже сматчить только поля из части кортежа:

fn ends(mf: &ManyFields) -> (i32, i32) {
match mf {
&ManyFields(start, .., end) => (start, end),
}
}

Впрочем, я отвлёкся.

Второй аргумент — это __ @ _. Как всегда в @-биндингах (ладно, ладно, at-биндингах), справа от @ находится паттерн — в данном случае _, который матчится абсолютно со всем — а слева от @ находится имя, которое привязывается к этому значению, __. Безусловно, идентификатор выглядит странно, но это валидное имя в Rust.

Ещё раз взглянем на замыкание целиком:

|(..): (_, _), __ @ _| __

Тело замыкания состоит из единственного идентификатора __. Иными словами, замыкание просто возвращает свой второй аргумент. С тем же успехом его можно было бы написать так:

|_, second| second

(или, если быть точнее и сохранить тот факт, что первый аргумент является парой, |_: (_, _), second| second).

Окей, с замыканием мы разобрались. Но чтобы понять, что же оно в итоге возвращает, нам нужно посмотреть на то, с какими аргументами оно вызывается:

(замыкание...)((&*"\\", '🤔'), {})

Первый аргумент — это пара (как и ожидается) из &str и char. Фрагмент &*"\\" валиден за счёт того, что строковой литерал имеет тип &'static str и, соответственно, его можно разыменовать (и взять ссылку от результата). Кстати, тут используется синтаксис для escaping-а, поэтому содержимое строки — это единственный символ \. А вот второй аргумент — это пустой блок. В Rust он вычисляется в (). С учётом того, что замыкание просто возвращает свой второй аргумент, получаем, что часть слева от оператора равенства просто возвращает ().

Теперь сложим вместе всё изложенное выше. Переменной val присваивается отрицание от сравнивания () и (). Так как unit всегда равен самому себе, в val записывается значение false. Строчкой ниже в функции вызывается assert!(!val), который ожидаемо проходит.

Как видите, тут нет абсолютно ничего сложного. 👌

#prog #rust #itsec

blog.rust-lang.org/2022/01/20/cve-2022-21658.html

> Rust 1.0.0 through Rust 1.58.0 is affected by this vulnerability.

Oof

#prog #rust

Вафель двигает Rust вперёд ✊🎉

#prog #meme

Сделал мем по мотивам https://t.iss.one/oleg_log/5319

#prog #rust

Does the Bronze Garbage Collector Make Rust Easier to Use? A Controlled Experiment

Разумеется, я не мог пройти мимо статьи с подобным еретическим громким заявлением. Авторы разработали сборщик мусора, решив при помощи stack maps от LLVM проблемы идентификации корней. Как сказано в абстракте:

> We found that for a task that required managing complex aliasing, Bronze users were more likely to complete the task in the time available, and those who did so required only about a third as much time (4 hours vs. 12 hours). We found no significant difference in total time, even though Bronze users re-did the task without Bronze afterward.

Однако меня заинтересовал сам сборщик мусора. В тексте я натолкнулся на упоминание того, что в эксперименте использовалась версия, которая фактически сборку мусора не проводила. Меня это насторожило. Я пошёл смотреть исходники и увидел issue (со ссылкой на URLO) о том, что bronze позволяет иметь две мутабельные ссылки на одно и то же значение одновременно. Что вообще-то UB. Таким образом, авторы фактически проверяли не "Rust со сборщиком мусора", а "Rust с выключенным borrow checker", что фактически ставит под сомнение результаты эксперимента. Авторы при этом ничего страшного в этом не видят. Более того, в треде отметили, что авторы скопировали часть кода из rust-gc от Manish Earth, при том,что bronze имел лицензию BSD, а rust-gc — Mozilla Public License 2.0, копилефтную лицензию.

Короче, дурная история

#prog #article

The Discovery of Apache ZooKeeper’s Poison Packet — статья от 2015 года об экзотическом баге, который связал воедино баги в ZooKeeper и ядре Linux. Да, серьёзно.

(thanks @oleg_log)

Какой же всё-таки у Instagram отвратительный интерфейс