Блог*

Теперь можно и разбирать некоторые ошибки, найденные Даней, а также недостатки 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]

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

Внизу размер массива, слева — число сравнений. 🟠 Rust 🔵 std::sort (LLVM) ⚫️ std::sort (GCC) Как видите, производительность самих сортировок отличается незначительно, и они явно имеют одну асимптотику. Но что насчёт nth_element/select_nth_unstable?

#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 — достаточно хороша. Как же она себя ведёт?

#politota rbc.ru/newspaper/2022/04/25/6262eed69a79472666361d78 Охота на мыслеведьм

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

#design #web #game 20 игр, чтобы видеть детали, чувствовать нюансы и уловить смысл дизайна (Flexbox Froggy прикольная)

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

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

куличи переоценены

#prog #rust #meme

Анекдот из жизни принесла. Две тётки ругаются в очереди к психиатру. Опуская предысторию, апогей конфликта: — Вот и правильно вас тут лечат, психованную! — Да я справку для работы пришла получать! Это тебя тут правильно лечат! — Да мне рецепт для лежачего нужен! Внезапно поднимается молчавший мужик: — Вот меня тут лечат. И если вы не замолчите, я вас обеих покусаю! У меня справка есть, мне можно!

За пенсию в 30 лет я бы голосовал

А всё же некоторая польза от [спецоперации] есть: по отношению к ней очень легко понять, кто нормальный человек, а кто — полоумный патриорк

Все же уже слышали про новый формат QOI (quite ok image format, qoiformat.org), который lossless сжимает картинки +- так же хорошо, как PNG, но при этом в 20-50 раз быстрее, а его спецификация умещается на одну страницу? Хотели бы кодинг стрим где я бы подумал вслух и написал бы реализацию энкодера/декодера? 👀

#prog #rust #meme