#prog #rust #meme

Вафель начинает стрим по реализации QOI

Только 7-летней!

#design #web #game

20 игр, чтобы видеть детали, чувствовать нюансы и уловить смысл дизайна

(Flexbox Froggy прикольная)

Как бы #prog #meme, а как бы и нет

#prog #rust #моё

Не могу пройти мимо и удержаться от похвал Rust. Однако перед этим всё же проведу небольшой эксперимент по поводу производительности алгоритмов в стандартной библиотеке Rust. Проверять будем при помощи такого кода:

use rand::prelude::*;

fn measure(size: usize) -> usize {
    use std::cmp::Ordering::*;

    let mut comp_count = 0;
    let gas = size + 1;
    let mut n_solid = 0;

    let mut indices = (0..size).collect::<Vec<_>>();
    let mut values = vec![gas; size];
    indices.shuffle(&mut thread_rng());

    // indices.select_nth_unstable_by(size - 2, |&x, &y| {
    indices.sort_unstable_by(|&x, &y| {
        comp_count += 1;
        match (values[x] == gas, values[y] == gas) {
            (true, true) => {
                values[x] = n_solid;
                n_solid += 1;
                Less
            }
            (true, false) => Greater,
            (false, true) => Less,
            (false, false) => values[x].cmp(&values[y]),
        }
    });

    comp_count
}

fn main() {
    let sizes = std::iter::successors(Some(100), |&i| Some(i * 2)).take_while(|&i| i <= 6400);
    for size in sizes {
        let n_comp = measure(size);
        println!("{size}\t{n_comp}");
    }
}

Как видите, это тот самый худший случай для быстрой сортировки. Однако pattern-defeating quicksort — текущая реализация сортировки в Rust std — достаточно хороша. Как же она себя ведёт?

Внизу размер массива, слева — число сравнений.

🟠 Rust
🔵 std::sort (LLVM)
🟣 std::sort (GCC)

Как видите, производительность самих сортировок отличается незначительно, и они явно имеют одну асимптотику.

Но что насчёт nth_element/select_nth_unstable?

Внизу размер массива, слева — число сравнений.

🟠 Rust
🔵 std::sort (LLVM)
⚫️ std::sort (GCC)

А вот тут ситуация уже похуже. Квадратичная асимптотика в полный рост, и quickselect из Rust std явно уязвим к эксплоиту. При всём этом версия на Rust делает примерно в 2.5 раз меньше операций сравнений, чем версия для LLVM. Не знаю, почему так, но рискну предположить, что более богатый — трёхвариантный — компаратор даёт больше информации и потому требует меньше вызовов.

Теперь можно и разбирать некоторые ошибки, найденные Даней, а также недостатки API у C++ std.

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

Теперь что касается ловушек, уникальных для C++. Безусловно, к реализациям Ord предъявляются требования, удостоверяющие полный порядок, но это не то требование, которое можно проверить компилятором (во всяком случае, компилятором Rust). Таким образом, реализация безопасной сортировки в Rust std не может полагаться на то, что эти требования все выполняются, а потому сегфолт исключается (если он вдруг произойдёт при использовании компаратора с safe кодом, это будет считаться багом в стандартной библиотеке). Пункт с неправильным типом также исключён: подобный код в Rust вызовет ошибку компиляции. Ну а пример с сортировкой чисел с плавающей точек не просто не вызывает UB — он не компилируется, поскольку из-за NaN-ов f32 и f64 реализуют PartialOrd, но не Ord, который требуют функции сортировки.

Отдельно хочется отметить примеры, в которых отношение порядка нарушается. Вот тут Rust помогает тем, что в стандартной библиотеке есть варианты функций с суффиксом _by_key, которые вместо функции для сравнения двух элементов принимают функцию для извлечения некоторого ключа из элемента. Этот ключ должен реализовывать Ord, и именно результат сравнения ключей используется для определения отношения порядка между элементами. Это деление позволяет снизить вероятность ошибки (и объём кода) за счёт разделения логики выделения значимых для порядка элементов и собственно сравнения.

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

iovisor/bpftrace:
|(path, _)| (path != "unified", path)
(Пояснение: кортежи сравниваются покомпонентно, true считается больше false, так что unified пути упорядочиваются перед прочими. И да, конкретно тут, вероятно, на Rust не сойдутся типчики — я уже рассказывал, почему)

android/platform/system/unwinding
|&(reg, ..)| (reg != CFA_REG, reg)

ROCmSoftwarePlatform/rocPSARSE
|idx| col_entry[idx]

Ещё стоит отметить подводный камень насчёт вызовов nth_element подряд. Не то чтобы подобный баг нельзя допустить в Rust, но сделать это несколько сложнее из-за более богатого API. Там, где std::nth_element возвращает void, select_nth_unstable возвращает тройку из: мутабельной ссылки на слайс слева от выбранного элемента, мутабельной ссылки на сам выбранный элемент и мутабельной ссылки на слайс справа от выбранного элемента. В итоге выбор двух средних элементов может выглядеть как-то так:

let mut cmp = ...;
let half = arr.len() / 2;
let (_, &mut mid_lo, right) = arr.select_nth_unstable_by(half - 1, &mut cmp);
let (_, &mut mid_hi, _) = right.select_nth_unstable_by(0, &mut cmp);
// или, если нам нужен только сам элемент, но не нужно переставлять значения:
// let &mid_hi = right.iter().min_by(&mut cmp).unwrap();

Что касается "sorting more than needed", то тут ловушки в Rust нету... Поскольку в Rust std нет partial_sort 😅. С другой стороны, паттерн "отсортировать только префикс вектора и его и оставить" на Rust вполне выразим, и достаточно просто:

let mut cmp = ...;
let (prefix, _, _) = vec.select_nth_unstable_by(n - 1, &mut cmp);
prefix.sort_unstable_by(cmp);
vec.truncate(n);

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

Я одному знакомому челу кидал картинки с анимешными девушками c плюшевыми акулами. Чел, отзовись, пожалуйста, не могу тебя найти -_-
Ты растер, одно время вроде был в джерке и даже был на растомитапе Тапка, и ник у тебя был вроде из двух букв.

UPD: Нашёлся.