Наконец-то дошли руки пройти Serena, которую я запускал в последний раз... 6 лет назад.

И знаете что?

Я обескуражен. Весьма.

Ворую чужие #prog #meme-ы

#prog #rust #моё

Тут Даня рассказывает о том, как можно уменьшить время на критические секции с мапой в многопоточном контексте, расчитывая хэш для поиска ключа заранее. Бенчмарк, который он сделал, показывает, что CPU time от подобных манипуляций остаётся практически то же, а вот wall time становится меньше, что в итоге уменьшает задержку (в смысле latency). Советую почитать, пост неплохой.

Но я несколько отвлёкся. В том же посте Даниил сокрушается, что подобная операция (поиск при помощи хэша) есть в коллекциях Abseil, но не в различных стандартных библиотеках языков, в том числе C++ и Rust. И вот тут Даня не совсем прав.

У HashMap из стандартной библиотеки Rust есть методы raw_entry{, mut}, которые предоставляют API для низкоуровневого манипулирования мапой, в том числе и поиск при помощи предвычисленного хэша. Единственная проблема заключаются в том, что эти методы... Ещё не стабилизированы. И, насколько я могу понять по обсуждениям в tracking issue, сейчас там обсуждается вопрос, должно ли это API вообще существовать в том виде, в котором оно есть сейчас. С другой стороны, HashMap из стандартной библиотеки сейчас не более, чем обёртка над hashbrown::HashMap, у которой эти методы есть, так что мы можем построить поверх неё аналог LockedHashMap из оригинального поста, а заодно осветить парочку моментов из стандартной библиотеки Rust, которые незаслуженно обделяют вниманием.

Для начала запишем определение:

use hashbrown::HashMap;

use std::{borrow::Borrow, hash::{BuildHasher, Hash, Hasher}, sync::{Mutex, MutexGuard, PoisonError}};

struct LockedHashMap<K, V, S> {
inner: Mutex<HashMap<K, V, S>>,
}

Расписывать конструкторы я не буду, они тривиальны. Методы LockedHashMap будут начинать свою работу со взятия блокировки на inner, но... Метод .lock() возвращает Result. Что с этим делать? И почему мы импортируем PoisonError?

Для начала разберёмся, почему Mutex::lock в принципе возвращает Result. Дело в том, что обычно программисты, пишущие код с блокировками, не пытаются расчитать поведение кода в том случае, если код запаникует, пока блокировка удерживается. С safe Rust это не может привести к проблемам с памятью, но прерывание обычного потока управления может оставить значение, защищаемое блокировкой, в логически неконсистентном состоянии. Если программист рассчитывает на то, что какие-то инварианты могут поддерживаться, но при этом временно их нарушает во время блокировок, то паника во время удерживания блокировки может эти логические инварианты сломать.

Дизайнеры стандартной библиотеки Rust решили, что это достаточно распространённая и при этом неочевидная ошибка, чтобы ограждать от неё в стандартной библиотеке. В итоге мьютекс из стандартной библиотеки может находиться не только в состоянии "разблокирован" или "заблокирован", но и в состоянии "отравлен". Когда MutexGuard (то, что реально возвращается в Ok-варианте из Mutex::lock) дропается, он не только разблокировывает связанный мьютекс, но и проверяет, паникует ли текущий поток. Если это так, то он помечает мьютекс как отравленный. Вызов Mutex::lock проверяет, является ли мьютекс отравленным, и если это так, то возвращает Err(PoisonError). Так как самое ленивое, что может сделать программист с результатом вызова .lock() — это вызвать .unwrap(), то в случае, если один из потоков, работающий с мьютексом, запаниковал — и, возможно, оставил защищённый мьютексом объект в логически неконсистентном состоянии — остальные потоки, использующие этот же мьютекс, также паникуют и, таким образом, не имеют возможности наблюдать состояние со сломанными инвариантами.

Такое дизайн-решение, вообще говоря, не бесспорное — и, скажем, в parking-lot метод lock не возвращает Result. Но что делать, если мы таки заботимся о соблюдении инвариантов? Так как отравление мьютекса — это защита от логических ошибок, а не от проблем с memory safety, lock на отравленном мьютексе таки захватывает его, и при помощи PoisonError::into_inner внутренний MutexGuard всё же можно достать. В общем, для упрощения остальных методов выделим LockedHashMap::lock_poisonless:

fn lock_poisonless(&self) -> MutexGuard<'_, HashMap<K, V, S>> {
self.inner.lock().unwrap_or_else(PoisonError::into_inner)
}

Теперь немного подумаем о том, что должен возвращать метод find_with_hash. Обычный HashMap::get возвращает ссылку на значение, но нам это не очень хорошо подходит, поскольку, пока ссылка жива, мы должны удерживать и блокировку, что прямо противоречит нашей цели: сокращение длительности критических секций. Я решил, что в данной ситуации будет разумно это значение клонировать. Итого метод выглядит так:

fn find_with_hash<Q>(&self, hash: u64, key: &Q) -> Option<V>
where
    Q: ?Sized + Eq,
    K: Borrow<Q> + Hash + Eq,
    V: Clone,
{
    self.lock_poisonless()
        .raw_entry()
        .from_key_hashed_nocheck(hash, key) // смотри-ка, хэш не считается!
        .map(|(_k, v)| v.clone())
}

insert пишется без проблем:

fn insert(&self, key: K, value: V) -> Option<V>
where
    K: Hash + Eq,
    S: BuildHasher,
{
    self.lock_poisonless().insert(key, value)
}

Кстати, тут также можно было бы ускорить поиск при помощи предрасчитанного хэша, но Даниил решил почему-то этого не делать. Гм... А давайте сделаем и версию с готовым хэшем:

fn insert_with_hash(&self, hash: u64, key: K, value: V) -> Option<V>
where
K: Hash + Eq,
S: BuildHasher,
{
use hashbrown::hash_map::RawEntryMut::*;

match self
.lock_poisonless()
.raw_entry_mut()
.from_key_hashed_nocheck(hash, &key)
{
Vacant(e) => {
e.insert(key, value);
None
}
Occupied(mut e) => Some(std::mem::replace(e.get_mut(), value)),
}
}

Так, требуемый функционал реализован. А теперь поговорим немного о том, как же эти самые хеши считать. В C++ задача хэширования возложена на специализации структуры std::hash. Для тех типов, которые умеют хэшироваться, соответствующая специализация имеет реализацию operator(), которая позволяет вызвать std::hash как функцию. К чему это я? В С++ хэш стандартной библиотеки имеет по одной конкретной хэш-функции на тип. В Rust же ситуация... Несколько сложнее.

В стандартной библиотеке есть трейт std::hash::Hash (и derive-макрос для него), который определяет единственный (необходимый) метод hash. Так что же, хэш однозначно определяется типом? Не совсем. Метод hash — обобщённый, и принимает аргументами &self и мутабельную ссылку на значение, реализующее трейт std::hash::Hasher. Этот трейт, в свою очередь, предоставляет набор методов навроде write_u32 для хэширования примитивов и write для хэширования слайса байт, а также метод finish, который возвращает значение типа u64 — вычисленный хэш. Таким образом, хэширование типа выражено в терминах методов Hasher — и в этом смысле хэш-функция зависит от типа, ибо это внутри реализации Hash решается, в каком порядке поля будут хэшированы — но конкретная реализация хэш-функции зависит от типа, реализующего Hasher. На практике это означает, что вместо того, чтобы довольствоваться некоторой стандартной хэш-функцией по умолчанию (которой для примитивных численных типов, согласно стандарту C++, вполне может быть функция идентичности), программист может выбрать хэш-функцию, которая наилучшим образом подходит для имеющихся данных — и при этом избежать выписывания этой хэш-функции для всех необходимых типов вручную (привет, 0xd34df00d).

Однако в случае хэш-мапы возникает новая задача: для подсчёта хэша нового элемента нам нужен новый, свежий хэшер. Но откуда его взять? Эта задача в стандартной библиотеке Rust делегирована третьему трейту: std::hash::BuildHasher. Его единственный метод build_hasher должен возвращать значение типа BuildHasher::Hasher, причём эти значения должны вести себя одинаково. Фактически, это фабрика хэшеров. Как и HashMap из стандартной библиотеки, так и hashbrown::HashMap параметризованы тремя типами, и этот третий тип — тот самый тип, реализующий BuildHasher. Так как значение этого типа у каждого экземпляра хэш-мапы может быть своим — и его даже можно предоставить явно при помощи with_hasher/with_capacity_and_hasher — это означает, что фактически конкретный экземпляр каждой хэш-мапы потенциально использует свою хэш-функцию (и, кстати, стандартная библиотека для фабрики хэшеров по умолчанию — std::collections::hash_map::RandomState — именно так в конструкторе и делает, что весьма огорчает некоторых пёселей). Таким образом, чтобы подсчитать хэш ключа так же, как это делает сама мапа, нам нужно получить доступ к build hasher внутри самой мапы — и, к счастью, такой геттер есть. Его можно написать и для LockedHashMap, имея при этом в виду те же соображения, что и для типа значения для find_with_hash:

fn hasher(&self) -> S
where
S: Clone,
{
self.lock_poisonless().hasher().clone()
}

Имея на руках значение типа, реализующего BuildHasher, уже несложно подсчитать хэш произвольного значения:

fn hash_single<T: Hash, S: BuildHasher>(build_hasher: &S, val: &T) -> u64 {
let mut hasher = build_hasher.build_hasher();
val.hash(&mut hasher);
hasher.finish()
}

(или же использовать BuildHasher::hash_one, когда его, чёрт побери стабилизируют) и скормить его мапе. В итоге код выглядит как-то так:

let hasher = locked_map.hasher();
// ...
let hash = hash_single(&hasher, &key);
let value = locked_map.find_with_hash(hash, &key);
if let Some(value) = value {
    // ...
}

Вот, собственно, и всё. Кода на этот раз совсем немного, но если вдруг кому-то понадобится — вот гист.

#wafflecontext #трудовыебудни

#prog #meme

Внезапно, годнота на Профункторе

#rust

Статья с впечатлениями от использования Rust в проде в течение больше, чем двух лет.

"All things considered, Rust is very mature and most of its pain points would exist in one shape or another in other mainstream languages. Rust makes reuse trivial and lets us deal safely with large code bases under active development without sacrificing performance.

Using Rust is for us no longer an experiment or a bet. It is the proven technology we are building on, <...>"

В СМЫСЛЕ УЖЕ ОКТЯБРЬ

#game

У вас нету причины не пройти Pyre.

И нет, не пытайтесь о ней что-то прочитать, к этой игре лучше подходить, ничего о ней не зная.

Всё так и было

А тихой сапой подкралась очередная круглая цифра — тысяча подписчиков. Казалось бы, вполне ожидаемое событие, учитывая, что в последние месяцы это число медленно, но верно росло — но меня оно всё равно застигло врасплох. Думаю, за это стоит поблагодарить несколько каналов, которые недавно прямо упоминали Блог*: @oleg_log (Олег, разблокируй уже в чате, пожалуйста), @lilfunctor (который недавно тоже перевалил за тысячу участников, в связи с чем искренне поздравляю Михаила) и @nosingularity. Спасибо, мужики.

Что же это значит для меня? Ну, во-первых, что я, оказывается, умею писать интересно — в смысле достаточно интересно, чтобы заинтересовать большее количество людей, чем с которым я могу познакомиться лично. Во-вторых — то, что число подписчиков — не особо осмысленная величина, но всё же приятно греет душу. В-третьих... Что большое количество подписчиков не обязательно означает большое количество финансовой отдачи 😅.

Впрочем, я веду блог не ради денег — иначе бы я уже давно бросил это дело. Как бы то ни было — спасибо, спасибо вам всем, в том числе и за временами плодотворные дискуссии в Чат*е. Вперёд, к новым вершинам — и к новым тысячам!

И традиционно попрошу новоприбывших ответить в опросе