#prog #article (от самого Кармака, кстати)

In-Depth: Static Code Analysis

> It is impossible to do a true control test in software development, but I feel the success that we have had with code analysis has been clear enough that I will say plainly it is irresponsible to not use it.

#prog #article

От того же автора: Finding a CPU Design Bug in the Xbox 360, или как инструкция, которая никогда не выполняется, может привести к крашам.

#prog #rust #моё

TL;DR: OccupiedEntry::get, OccupiedEntry::into_mut.

Хочу рассказать про один нюанс насчёт этого API, с которым периодически сталкиваются новички. Метод entry возвращает Entry, который буквально либо занятое место, либо свободное:

enum Entry<'a, K: 'a, V: 'a> {
Occupied(OccupiedEntry<'a, K, V>),
Vacant(VacantEntry<'a, K, V>),
}

Пусть наш гипотетический новичок хочет таким образом получить доступ к значению из мапы:

let val = match map.entry(key) {
Entry::Occupied(e) => ???,
Entry::Vacant(_) => todo!(), // пока нас это не интересует
};

Что же вписать вместо ???. На это месте наш новичок бежит спрашивать в @rust_beginners_ru открывает доку по entry, доходит до документации по OccupiedEntry, начинает листать список методов и находит OccupiedEntry::get. "О, это оно!" — восклицает новичок и пишет:

let val = match map.entry(key) {
Entry::Occupied(e) => e.get(), // <---- тут
Entry::Vacant(_) => todo!(),
};

, после чего пишет код дальше, запускает и...

error[E0597]: `e` does not live long enough
 --> src/lib.rs:5:31
  |
4 |     let val = match map.entry(0) {
  |         --- borrow later stored here
5 |         Entry::Occupied(e) => e.get(),
  |                               ^^^^^^-
  |                               |     |
  |                               |     `e` dropped here while still borrowed
  |                               borrowed value does not live long enough

Ах, да, тот самый borrow checker. "Но это же абсолютно нормальный код!" — восклицает новичок — "Что этому тупому компилятору не нравится?!". После забрасывает раст, забрасывает программирование, уходит из универа и пишет статью о том, как статически типизированные языки страдают от сложности.

Тем не менее, компилятор тут абсолютно прав. Посмотрим еще раз на сигнатуру OccupiedEntry::get:

fn get(&self) -> &V

Или, если мы вспомним правила lifetime elision и выпишем времена жизни явно:

fn get<'entry>(&'entry self) -> &'entry V

Теперь ещё раз внимательно посмотрим на код:

let val = match map.entry(key) {
Entry::Occupied(e) => e.get(), // <---- тут
Entry::Vacant(_) => todo!(),
};

Что тут происходит? e — это значение типа OccupiedEntry. Не ссылки на неё! Метод .get() возвращает ссылку на значение, но для этого он берёт ссылку на e. Однако после вызова этого метода e дропается в конце ветки match — своей лексической области видимости — и таким образом инвалидирует ссылку, возвращённую .get(). Не удивительно, что компилятор жалуется — в противном случае код давал бы повисшую ссылку!

Возникает вопрос: зачем так сделано? Разве нельзя было бы возвращать ссылку, которая бы не заимствовала бы саму OccupiedEntry? Но тут возникает вопрос, какое время жизни должна иметь возвращаемая ссылка. Ясное дело, ссылка не может взяться из воздуха, так что произвольным оно быть не может, равно как и 'static. Тогда какое?

Посмотрим на определение OccupiedEntry ещё раз:

struct OccupiedEntry<'a, K: 'a, V: 'a> {
/* fields omitted */
}

Откуда берётся 'a? Оно берётся из объемлющей Entry, а оно, в свою очередь, из метода HashMap::entry:

fn entry(&mut self, key: K) -> Entry<'_, K, V>

Или же, если расписать времена жизни явно:

fn entry<'map>(&'map mut self, key: K) -> Entry<'map, K, V>

То есть OccupiedEntry параметризованно временем жизни ссылки на мапу. Вопрос: что мешает сделать такой метод?

impl<'map, K: 'map, V: 'map> OccupiedEntry<'map, K, V> {
fn get_as_in_map(&self) -> &'map V { ... }
}

Мешает то, что такой метод не мог бы быть безопасным. Рассмотрим такой код в предположении, что такой метод уже написан:

let val = match map.entry(key) {
Entry::Occupied(e) => {
// ссылка на значение
let val = e.get_as_in_map();

// убираем значение из мапы
e.remove();

val // и куда теперь указывает ссылка?
}
Entry::Vacant(_) => todo!(),
};

Окей, такого метода быть не может. Но неужели мы никак не можем таки получить ссылку на значение с тем же временем жизни, что и ссылка на мапу? На самом деле можем, и этот метод — into_mut:

impl<'map, K: 'map, V: 'map> OccupiedEntry<'map, K, V> {
fn into_mut(self) -> &'map mut V { ... }
}

Обратите внимание, этот метод принимает self по значению, то есть после его вызова мы уже не можем использовать запись, а значит, и как-то инвалидировать возвращённую ссылку. Возвращаясь к коду нашего новичка, мы можем посоветовать вместо ??? вписать e.into_mut():

let val = match map.entry(key) {
Entry::Occupied(e) => e.into_mut(),
Entry::Vacant(_) => todo!(),
};

И напоследок ещё пару вопросов.

Первый: можно ли обойтись одним .into_mut(), без .get() и .get_mut()? Нет, поскольку эти методы дают возможность получить доступ к значению и после этого всё же вызвать методы на записи. В качестве примера приведу функцию, которая будет из мапы, хранящей по ключам векторы, доставать из этого вектора последний элемент и удалять этот вектор из мапы, если после этого он стал пустым:

fn pop_and_remove_empty(
key: i32,
map: &mut HashMap<i32, Vec<Record>>
) -> Option<Record> {
match map.entry(key) {
Entry::Occupied(mut e) => {
let val = e.get_mut().pop();
if e.get().is_empty() {
e.remove();
}
val
}
Entry::Vacant(_) => None,
}
}

Второй вопрос: обязательно ли было применять .into_mut()? Строго говорят, нет, поскольку можно было бы написать и без него, воспользовавшись трюком, про который рассказывал Вафель на RustCon2021:

let delayed_entry;
let val = match map.entry(key) {
Entry::Occupied(e) => {
delayed_entry = e;
delayed_entry.get()
}
Entry::Vacant(_) => todo!(),
};

В данном случае проблем с повисшими ссылками нету, поскольку delayed_entry объявлена за пределами match и потому живёт дольше привязанных внутри значений.

#music

Задорный чиптюновый трек. И у меня стойкое впечатление, что где-то его уже слышал — не напрямую, так его вариацию.

youtube.com/watch?v=eICgxtddfx0

А если набрать, скажем, std.rs/HashSet::get_or_insert_with, то документация откроется сразу на странице поиска с указанной строкой в качестве запроса.

А ещё можно использовать n.std.rs, чтобы искать по документации по nightly (thanks @caralice)

С днём рождения меня

Возможно, слишком специфический #meme, но он уж больно хорош

Должен признаться в кое-чём весьма личном и важном.

Я — цис.

В СМЫСЛЕ УЖЕ АПРЕЛЬ

#prog

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

#prog #rust #article #abnormalprogramming

Self Modifying Code, или "Алексей Кладов ненавидит макросы, часть N + 1"

#prog #performancetrap #go #article

Generics can make your Go code slower (перевод)

(thanks @go_perf)

Отвечая на закономерный вопрос "Какого фига": это — закономерный результат стратегии имплементации обобщённых функций. Вместо того, чтобы делать по реализации обобщённой функции на каждый тип, компилятор Go делает по реализации на каждую GC shape. Это "форма с точки зрения сборщика мусора" определяется одинаковой у каждой пары типов, если: у них одинаковый underlying type (в смысле встроенного в Go формы strong typedef); или если они оба являются указателями. Любыми.

Разумеется, в обобщённые функции надо всё-таки как-то прокидывать методы от конкретных типов. И делается это при помощи словаря с типами, который является генерируемым компилятором статическим значением и который прокидывается неявным аргументом в каждую обобщённую функцию (это похоже на то, во что компилируются классы типов в Haskell во время компиляции в GHC Core). Так как у обобщённой функции может быть больше одного тИпового параметра, этот словарь передаётся по указателю.

Что же происходит при вызове метода из ограничения на обобщённый тип? Сначала из словаря по указателю загружается описание нужного типа. Затем из этого описания по статически известному смещению загружается адрес функции. Только после этого происходит собственно вызов. Для сравнения, интерфейсы в том же Go реализованы через толстые указатели, поэтому там только два шага: считать адрес функции из таблицы и вызвать её.

В общем, для дженериков получается куча лишних шагов. И хотя сам по себе косвенный вызов — не такой уж большой оверхед, само наличие косвенного вызова предотвращает возможности инлайнинга и последующих оптимизаций. Отсюда и выходит фиговая производительность. Особенно в статье автор отмечает: "This is possibly the most salient point of this analysis: passing interfaces to a generic function in Go is never a good idea". Почему? Да потому что интерфейсы в Go уже подразумевают косвенность, и при передаче в обобщённую функцию эта косвенность только добавляется.

И вот сейчас мне хотелось бы похвалить Rust. Он не только предоставляет выбор между статическим и динамическим полиморфизмом — он ещё и позволяет написать статическую версию и получить автоматом версию с динамическим полиморфизмом в подарок абсолютно бесплатно: достаточно привести явно тип аргумента к (указателю) на dyn Trait. Всё это — без дупликации кода со стороны программиста.

что общего у следующих игр?

1. игр на досках в 8 или 10 рядов (как индийские игры аштапада и дасапада)
2. игр на вымышленных досках (как шахматы с завязанными глазами)
3. игр, в которых нужно кидать кубик
4. игр с мячом
5. игр с ветряными мельницами сделанных из пальмовых листьев
6. игр, в которых нужно угадывать мысли друзей
7. игр, имитирующих деформации
8. игр, в которых нужно пахать игрушечным плугом

эти и некоторые другие игры можно найти в статье википедии «‎List of games that Buddha would not play»

Патриотизм — это, на самом деле, так тупо

#prog #amazingopensource #regex #rust

Язык, который компилируется в регулярные выражения.

(thanks @sergeysova)