#prog #rust #rustlib

griddle — библиотека, которая реализует hash map с амортизированной по операциям вставки расширением размера. Может быть полезна для случаев, когда важна маленькая tail latency. Реализована не с нуля, а с помощью "сырого" API hashbrown.

На графике бенчмарк операций вставки для HashMap из std и griddle::HashMap.

#prog #rust #rustlib #article

Designing A Fast Concurrent Hash Table

Статья о дизайне papaya, многопоточной в основном lock-free хэш-мапы с упором на пропускную способность на операциях чтения из мапы и предсказуемые задержки (без пиков). Также пока что является, кажется, единственной подобной структурой данных, которую можно использовать из асинхронного кода.

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

Так как многопоточная мапа по определению не может иметь аналог entry API (по крайней мере, без кучи тонкостей из-за потенциальных гонок с другими потоками), papaya предоставляет операции по атомарной модификации отдельных записей, использующие переданные коллбеки для выполнения нужной операции. Для наиболее ходовых операций есть отдельные методы, а для тех, которые в эти методы не укладываются, есть операция compute. Коллбек, переданный в этот метод, должен возвращать значение типа Operation, описывающий требуемое действие:

enum Operation<V, T> {
Insert(V),
Remove,
Abort(T),
}

В конце автор сравнивает свою реализацию с другими подобными библиотеками для Rust и поясняет, почему может иметь смысл использовать их вместо papaya.

#prog #rust #rustlib

walkdir — кросс-платформерная библиотека для рекурсивного обхода директорий от Andrew Gallant aka Burntsushi.

use walkdir::WalkDir;

for entry in WalkDir::new("foo").min_depth(1).max_depth(3) {
    println!("{}", entry?.path().display());
}

Библиотека умеет обнаруживает циклы символьных ссылок и сообщать в этих случаях об ошибке.

Небольшое неудобство заключается в том, что .filter() на итераторе не будет предотвращать заход в пропущенные директории, для этого нужно на итераторе вызвать .filter_entry(). Пример из документации для пропуска скрытых файлов на *nix-системах:

use walkdir::{DirEntry, WalkDir};

fn is_hidden(entry: &DirEntry) -> bool {
    entry.file_name()
         .to_str()
         .map(|s| s.starts_with("."))
         .unwrap_or(false)
}

for entry in WalkDir::new("foo")
                     .into_iter()
                     .filter_entry(|e| !is_hidden(e)) {
    println!("{}", entry?.path().display());
}

#prog #rust #rustlib

#prog #rustlib

include-utils — библиотека для включения в исходники только части текста из указанного файла. Макрос include_md! также позволяет ссылаться на нужные части файла не через номера строк, а через указание секций, как это сделано в mdbook.

#prog #rust #rustlib

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

#prog #rustlib #article

parser combinators with nom 8 are here!

(восьмая мажорная версия — это прям дофига для Rust-библиотек)

Geoffroy Couprie рассказывает о новой архитектуре nom. В этой версии он позаимствовал из chumsky подход к архитектуре парсеров. Про этот подход ещё в 2022 году писал Niko Matsakis в статье Many modes: a GAT pattern, которая демонстрировала, как GAT могут пригодиться в реальных библиотеках, и таким образом обосновывала необходимость иметь GAT в языке.

В nom 8 парсером является то, что реализует трейт Parser. Вот как выглядит его определение за вычетом методов с реализацией по умолчанию:

trait Parser<Input> {
    type Output;
    type Error: ParseError<Input>;

    fn process<OM: OutputMode>(
        &mut self,
        input: Input,
    ) -> PResult<OM, Input, Self::Output, Self::Error>;
}

Параметр OM реализует трейт OutputMode, реализации которого являются фактически type-level конфигом парсера:

trait OutputMode {
    type Output: Mode;
    type Error: Mode;
    type Incomplete: IsStreaming;
}

Трейт Mode является ключом к новым возможностям. Реализации этого трейта позволяют абстрагироваться над "выходом парсера, имеющего отношение к T":

trait Mode {
    type Output<T>;
    // методы для комбинирования и преобразовывания Output
}

Для чего всё это нужно? Дело в том, что в nom есть комбинаторы, которые используют переданный аргументом парсер, но при этом не используют то, что этот парсер выдаёт в качестве результата. В качестве примера таких комбинаторов можно назвать preceded и delimited. Если конструирование значения является дорогим (скажем, это условный separated_list0, который собирает результаты разбора под-парсеров в вектор), то запускать парсер только ради того, чтобы отбросить его значение, будет довольно расточительно.

В самом nom определены два типа, которые реализовывают Mode: Emit и Check. Emit реализовывает Mode с type Output<T> = T, то есть парсер работает, как обычно. Check же реализовывает Mode с type Output<T> = (), то есть парсер работает, но отбрасывает результаты. Именно такое поведение годится для комбинаторов, которым не нужен результат под-парсера. Так как конечный парсер имеет методы, обобщённые по параметру OM, реализующему OutputMode, парсер не может сконструировать результат напрямую, а вынужден использовать для этого методы Mode, определённые на OM::Output. В случае Emit эти методы просто применяют переданные функции к аргументам, а для Check эти методы просто дропают переданные функции и возвращают ().

Так как ошибка парсера тоже может дорого конструироваться, тип OutputMode::Error по аналогичным причинам также реализует Mode. Это нужно, например, для opt, который делает парсер опциональным и по понятным причинам отбрасывает и разобранный результат, и ошибку.

Как вы могли заметить, у OutputMode также есть параметр Incomplete, реализующий трейт IsStreaming. Он отвечает за то, является ли недостаточный вход фатальной ошибкой или же одним из вариантов ошибки, от которой можно восстановиться. Раньше почти каждый базовый комбинатор nom существовал в двух версиях: streaming и complete. Это было нежелательно по нескольким причинам, главная из которых — разные сорта парсеров очень легко перепутать при написании своих парсеров и потом долго ловить непонятные ошибки. Ещё одним нежелательным следствием этого подхода стало, очевидно, дублирование кода. Разные версии этих парсеров по разному обрабатывали неполный вход, но за вычетом этого аспекта логика там была одинаковая.

Новый подход позволяет написать ветвление по OM::IsIstreaming::is_streaming() и обработать оба варианта в одной функции, естественным образом собирая разные варианты реагирования на ошибку неполного входа в одном месте. Так как в nom оба типа, реализующих IsStreaming — Streaming и Complete — в соответствующих методах просто возвращают true и false соответственно, компилятор может увидеть ветвление по константному значению и просто убрать одну из веток, избежав генерации ненужного кода.

#prog #rust #rustlib

eval-macro — макрос, позволяющий генерировать код с использованием обычного кода на Rust. Посмотрите пример по ссылке.

Реализовано довольно проклято:

The content inside eval! is pasted into the main function of a temporary Rust project created in $HOME/.cargo/eval-macro/<project-id>. This project is created, compiled, executed, and removed at build time, and its stdout becomes the generated Rust code

#prog #rust #rustlib

seq — a seq! macro to repeat a fragment of source code and substitute into each repetition a sequential numeric counter.

use seq_macro::seq;

fn main() {
    let tuple = (1000, 100, 10);
    let mut sum = 0;

    // Expands to:
    //
    //     sum += tuple.0;
    //     sum += tuple.1;
    //     sum += tuple.2;
    seq!(N in 0..=2 {
        sum += tuple.N;
    });

    assert_eq!(sum, 1110);
}

Написано, конечно же, Толяном.

#prog #rust #rustasync #rustlib

async-std официально deprecated. Взамен советуют использовать smol и смежные крейты.

ДАВНО ПОРА

#prog #rust #rustlib #article

Introducing facet: Reflection for Rust

Как сказано в facet.rs:

the last proc macro / the last derive you’ll ever need

Сердце библиотеки — трейт Facet и derive-макрос для него. В отличие от других крейтов, которые ползают по определениям типов, facet генерирует не код обхода значений, а константы, которые описывают формы значений и потому могут быть утилизированы разными библиотеками разными способами. Из примеров: (де)сериализация, отладочная печать, ассерты с диффами (которые не полагаются на пост-обработку Debug-выхлопа). В силу того, что код не генерируется, эти реализации могут использовать нерекурсивные алгоритмы и таким образом избежать переполнение стека и легко регулировать глубину вложенности.

В статье рассказывается, зачем это создано и какие ещё преимущества даёт.

#prog #rust #rustlib #article

I Wrote A String Type

Статья, рассказывающая о принципиальном устройстве byteyarn — оптимизированного типа для строк, который умещается в 16 байт, имеет small string optimisation и имеет нишу, позволяющую не увеличивать размер при оборачивании в Option

#prog #rust #rustlib #ml #abnormalprogramming

unwrap_or_ai

Tired of manually handling unwrap() results? Let AI do the heavy lifting!

#prog #rust #rustlib

TIL что в bindgen есть возможность прицепить коллбеки, которые будут вызываться для определений, обрабатываемых во время генерации биндингов, и что есть уже готовый CargoCallbacks, который печатает

cargo:rerun-if-changed...

для каждого обрабатываемого файла и каждой явно заданной переменной окружения.

#prog #rust #rustlib

brie-tree - SIMD-optimized B+ Tree implementation that uses integer keys

A fast B+ Tree implementation that uses integer keys.
The API is similar to the standard library's BTreeMap with some significant differences:

* Lookups and insertions are 2-4x faster than BTreeMap.
* BTree can optionally be used as a multi-map and hold duplicate keys.
* Keys must be integer types or convertible to integers via the BTreeKey trait.
* The maximum integer value is reserved for internal use and cannot be used by keys.
* Elements in the tree are ordered by the integer value of the key instead of the Ord implementation of the keys.
* Cursors can be used to seek back-and-forth in the tree while inserting or removing elements.
* Iterators only support forward iteration.