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

🟠 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: Нашёлся.

#prog #elm #article

Elm is wrong

Шесть лет спустя (статья от 2016 года) вроде бы всё ещё справедливо.

Представьте, как надо сомневаться в собственной ориентации, чтоб запустить целое шоу

Нашёл

#prog #rust #моё

Если вы хоть когда-то писали на Rust код, который имеет дело с окрестностями на квадратной сетке, то вы знали, как с этим неудобно работать. Индексы в Rust беззнаковые — просто прибавить 1 и -1 нельзя (впрочем, можно на nightly), проверить на отрицательный индекс после вычитания нельзя, так что логика по обработке нижних и верхних границ разная. Вдобавок, нужный код для соседних мест приходится писать по четыре раза, смешивая сугубо техническую логику обхода соседей и бизнес-логику.

Разве не было бы удобно, если бы мы просто могли получить список валидных индексов для соседей и уже итерироваться по нему? Конечно, можно. Вот только возникает вопрос, в чём именно возвращать индексы. В зависимости от размеров сетки, количество валидных соседей (неймановских) может быть любое от нуля до четырёх включительно. Казалось бы, напрашивается использовать вектор, но выделять память в куче для 8 usize — это как-то перебор, особенно с учётом того, что код для получения соседей наверняка будет в горячем цикле, где память выделять нежелательно. Можно, конечно, завести какой-нибудь small vec, который при малых размерах хранит на стеке вместо кучи, но... Оно нам точно надо? Можно ещё сделать мини-вектор на четыре элемента максимум из enum, но это такая куча бойлерплейта...

Несколько малоизвестно, что похожий вопрос дизайна API решён в std. У char есть метод encode_utf8, который принимает мутабельную ссылку на слайс байт, использует этот буфер, чтобы перевести char в закодированную в UTF-8 строку, и возвращает ссылку на строковой слайс. Да, переинтепретированные байтики из аргумента:

fn encode_utf8(self, dst: &mut [u8]) -> &mut str

Мы можем использовать похожий подход: принимать на вход ссылку слайс из пар индексов, заполнять нужную часть и возвращать ссылку на заполненную часть. На самом деле лучше даже принимать ссылку не на слайс, а на массив из четырёх элементов — нам точно этого хватит.

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

Что ж, начнём писать код. Но для начала сделаем структуру для хранения размеров поля — это поможет сделать метод, благодаря которому будет сложнее перепутать пару индексов и пару размеров:

#[derive(Clone, Copy)]
struct Bounds {
rows: usize,
cols: usize,
}

Ну и начнём писать сам метод:

type Pos = (usize, usize);

impl Bounds {
fn around(
self,
buf: &mut [Pos; 4],
(row, col): Pos
) -> &[Pos] {
let mut i = 0;
...
}
}

Немного остановимся и подумаем, как будет выглядеть операция добавления индексов. Кажется, как-то так:

buf[i] = (new_row, new_col);
i += 1;

И так — для каждого из четырёх соседей... Нельзя ли покороче? Можно. Запишем замыкание:

let mut put = |r, c| {
buf[i] = (r, c);
i += 1;
}

Здесь принципиально то, что: а) замыкание не move, ибо нам buf и i ещё понадобятся, чтобы вернуть результат; б) замыкание должно быть мутабельным, чтобы позволить менять захваченные переменные. Что ж, приведу готовый метод целиком:

impl Bounds {
fn around(
self,
buf: &mut [Pos; 4],
(row, col): Pos
) -> &[Pos] {
let mut i = 0;
let mut put = |r, c| {
buf[i] = (r, c);
i += 1;
};
if let Some(row) = row.checked_sub(1) {
put(row, col);
}
if let Some(col) = col.checked_sub(1) {
put(row, col);
}
if col + 1 < self.cols {
put(row, col + 1);
}
if row + 1 < self.rows {
put(row + 1, col);
}
&buf[..i]
}
}

Аналогичный метод можно написать для окрестности Мура. И, кстати, такой код без non-lexical lifetimes не скомпилировался бы.

Вызывающий код будет выглядеть примерно так:

const BUF: [Pos; 4] = [(0, 0); 4];

// ⬇️ без этого компилятор будет выдавать предупреждение,
// поскольку берётся ссылка на временное значение,
// заданное константой, а не саму константу
#[allow(const_item_mutation)]
for i in 0..rows {
    for j in 0..cols {
        for &(row, col) in bounds.around(&mut BUF, (i, j)) {
            ...
        }
    }
}

У читателя может возникнуть резонный вопрос: а действительно ли сгенерированный код эффективный, нет ли там лишних паник? Проверка показывает, что при уровне оптимизации -O2 никаких паник в методе не остаётся. Оно и не удивительно: i не может стать больше четырёх, а у наc массив на четыре элемента как раз. Сила dataflow-анализа!

Как всегда, весь код в гисте.

Меня нарисовали. Приятно

#music

heavenpierceher.bandcamp.com/track/the-cyber-grind

(youtube.com/watch?v=e9EqU9y69vU)

Музыка, под которую хочется убивать.

(в чатике уже обсудили)

Допустим, вы запускаете в Linux процесс под рутом, которому нужно что-то прочитать или подключиться/забиндиться на сокет, а потом дропнуть привилегии до условного <nobody>/<nogroup>.

Почему-то интернет забит абсолютно неправильными примерами, как это делать. А потом опять "хакеры слили базы" и "виноваты рукожопые админы".

Итак, для смены пользователя текущего процесса мы вызываем libc::setuid(%uid_nobody%) (os.setuid в этом вашем питоне, nix::unistd::setuid в этом вашем расте и т.д.). Вызываем, понятно после смены группы, потому что если мы станем не рутом, то уже группу себе не сменим.

Так что сначала мы меняем группу. Как? Ну очевидно же что libc::setgid, как в миллионе каких-то примеров из гугла.

А вот и нихера.

libc::setgid не устанавливает процессу единую группу, а переключает её. В случае работы под рутом, вы можете выбрать любую группу, и она будет _добавлена_ в список групп процесса и выставлена по-умолчанию. Тоесть, если процесс был запущен как root:root, а вы вызвали libc::setgid(%gid_nogroup%), то процесс будет иметь обе группы - и nogroup (по-умолчанию) и root, а значит иметь право читать/писать всё в системе, куда имеет доступ группа root.

Как правильно?

Перед libc::setgid нужно обязательно вызвать libc::setgroups([%gid_nobody%]). Этот вызов выбрасывает у процесса все группы, кроме %gid_nobody% (добавляет её, если нет), но при этом процесс всё еще работает с gid=root(0). Далее, делаем libc::setgid. Потом libc::setuid. И всё работает как надо.

Тест для примера (пускать под рутом)

так права на группу остаются

echo "hello" > test.txt;chmod 640 test.txt
echo "import os; os.setgid(65534); os.setuid(65534);print(open('test.txt').read())"|python3

а так всё в порядке, доступа нет

echo "hello" > test.txt;chmod 640 test.txt
echo "import os;os.setgroups([65534]);os.setgid(65534);os.setuid(65534);print(open('test.txt').read())"|python3

PermissionError: [Errno 13]