Вы устали писать турборыбу, когда collect не может вывести тип? Вам надоело явно задавать тип переменных? Не беда!

Представляю вашему вниманию: @-паттерны! С @-паттернами, вы можете задать тип переменной не задавая его! Попробуйте уже сейчас:

let v @ Vec { .. } = (1..10).collect();

[play] [via: users.rust-lang.org]

В старых версиях раста для работы с коллизиями в хэшмапах использовалось линейное зондирование (???, linear probing), а сиды переиспользовались. ~5 лет назад было обнаружено что это приводит к (неожиданно) квадратичному поведению.

Вот отличный writeup на эту тему: Accidentally Quadratic: Rust hash iteration+reinsertion

Эта проблема была позже разрешена тем, что хэшмапы по умолчанию используют случайный сид для хэшера, что делает порядки элементов в разных хэшмапах независимыми.

Так-же hashbrown, библиотека которую использует std, после редизайна использует ~квадратичное зондирование, что тоже помогает с этим.

Если интересно как редизайнули hashbrown (SwissTable), то можно прочитать вот тут: https://gankra.github.io/blah/hashbrown-tldr/

Цитируя авторку статьи:
> it was such an improvement that it reduced compile times for basically every rust program by ~10% (rustc is just several HashMaps in a trenchcoat)

Вчера я провёл стрим, где начал писать двухсторонюю хэшмапу. Т.е. если в обычной HashMap отношение K -> V, то в BiHashMap отношение K <-> K'.
‍
Всё пошло не так, как бы хотелось (я это ожидал и поэтому не публиковал тут ссылку на стрим), но в итоге я смог написать BiHashMap с парой самых базовых методов вроде insert и lget.

Вот тут можно посмотреть запись с вырезанными попытками починить стрим.

Я вроде смог настроить obs так, чтобы стрим больше не лагал, так что завтра продолжу писать BiHashMap, там ещё много чего надо сделать:
— Перейти с StaticRc на что-то другое (на стриме объясню почему)
— Дописать остальные методы, только с new, insert и lget в этом всём нет смысла
— Написать итераторы
— etc

Завтра, вс, 2022-02-13, ~16:00 @ twitch.tv/wafflelapkin

Уже минут через 10 начнём :)

ииии, я начинаю :)

Upd: стрим закончился

Антон сделал мемы по мотивам стрима:

TL;DR того, что случилось за 3 часа стрима:
— Кратко рассказал о том, что было на предыдущем стриме
— Написал небольшой типчик Mrc<_>, который по сути немного-более-безопасный указатель
— Переписал крейт с использования StaticRc, на Mrc
— Попытался написать {l,r}get_mut, понял что для BiHashMap такие методы не имеют смысла, разочаровался в жизни и впал в уныние
— Написал метод lreplace
— Неудачно попытался добавить проверки корнер кейсов в insert
— Долго пытался исправить проверки и избавиться от UB
— Придумал как правильно и просто написать проверки корнер кейсов в insert (оказалось почти совсем просто)

Итоговая реализация insert греет мне душу :)

CppCon 2019: Andrei Alexandrescu “Speed Is Found In The Minds of People"

Интересный доклад от Александреску, о сортировках и оптимизация.

как же хочется FulfillmentError

В std добавили (PR смерджен 2 часа назад, будет в следующем найтли) pin! макрос!

tl;dr он позволяет делать так:
let foo: Pin<&mut PhantomPinned> = pin!(PhantomPinned);
stuff(foo);

Он работает аналогично tokio::pin! или futures::pin_mut! — припинивает значение к стеку, не давая ему больше двигаться. Но, в отличии от этих макросов является выражением. pin! из tokio и futures работают примерно так, tokio::pin!(stuff); разворячивается в

let mut stuff = stuff; // (1)
let stuff = unsafe {   // (2)
    Pin::new_unchecked(&mut stuff); // (3)
}

1. Проверяет что код владеет значением
2. Переменная "затеняется" в следствии чего к оригинальной переменной больше нет доступа и двигать оригинальное значение нельзя
3. Поскольку двигать значение будет нельзя, то можно спокойно создавать Pin

Этот хак работает, но он не очень удобен, т.к. pin!() получается отдельным стейтментом, а не выражением.

pin! из std использует другой хак, а конкретно правила по которым работают tmp-значения при создании структур через литерал. std::pin! разворачивается в

Pin::<&mut _> { pointer: &mut { stuff } }

Но как так? Ведь это же просто создания структуры Pin, как этот код может гарантировать, что stuff не будет двигаться в памяти, менять адрес, инвалидировать ссылки на себя? Давайте разберём по порядку.

1. { stuff } — это block expression, последнее выражение в блоке "возвращается" из него. это проверка на то, что код владеет stuff аналогичная пункту (1) из tokio/futures pin!. Это же и создаёт анонимную tmp-переменную которая гарантирует (своей анонимностью) что значение не будет двигаться.
2. ::<&mut _> говорит что Pin будет параметризован ссылкой на что-то, это не особо важно, но в макросах полезно быть как можно более точными, чтобы потом что-нибудь внезапно не сломалось
3. Pin { pointer: &mut ... } это самая интересная часть, которую не могли повторить макросы из futures/tokio, сейчас объясню почему

Когда вызываются функции, tmp переменные привязываются к вызову, т.е. f(&{ a }) превращается в
{
let tmp = a;
f(&tmp)
} // tmp умирает здесь
Соответственно таким образом нельзя вызвать функции, которые возвращают эту ссылку и потом эту ссылку использовать — tmp на который тут ссылаются к тому моменту уже умрёт.

Соответственно tokio/futures не могли у себя сделать Pin::<&mut _>::new_unchecked(&mut { stuff }) — let a = pin!(stuff) бы просто не работало т.к. пыталось бы вернуть ссылку на tmp, который уже умер.

Но при создании структур правила другие, Struct { field: &{ a } } превращается в
let tmp = a;
Struct { field: &tmp }
в таком случае tmp может жить гораздо дольше!

Поэтому то, что стандартная библиотека имеет доступ к приватному полю (как этот доступ работает в макросах это отдельная история) позволяет ей реализовать более удобное API, позволяющее делать вещи вроде

let stuff = pin!(expr);

Которое потом разворачивается в что-то на подобии

let mut tmp = expr;
let stuff = Pin { pointer: &mut tmp };

(и все счастливы)

P.S. особо любознательным советую прочитать вот этот огромный комментарий из реализации макроса

А вы тоже сидите грустные и уставшие, а потом такие
YOU'RE DEAD, ALREADY, DEAD, DEAD, ALREADY-READY
DEAD, ALREADY, DEAD, DEAD, ALREADY-READY
DEAD, ALREADY, DEAD, DEAD, ALREADY-READY
DEAD, ALREADY, deeeeaaaad

и сразу всё нипочём и сразу прыгать хочется?

cursed-fact-of-the-day: бинарный поиск по массиву из 2^20 элементов примерно на 20% медленнее, чем бинарный поиск по массиву из 2^20 + 123 элементов.

Причина: https://en.algorithmica.org/hpc/cpu-cache/associativity/

Источник: twitter@sergey_slotin