Branchless RUST и цена одной ветки

Знаете, какой самый неожиданный тормоз в коде? Не аллокации памяти и не сложные алгоритмы, а одна маленькая конструкция if. В реальном кейсе убрали один условный оператор — и ускорили фильтр почти в четыре раза.

Проблема: фильтр, который тормозил

Автор статьи, Serhii Potapov, известный как greyblake, столкнулся с задачей: отфильтровать миллион чисел с плавающей точкой, оставив только те, что больше порога. Идиоматичный код на Rust выглядел просто и аккуратно:

pub fn filter_iter(input: &[f64], threshold: f64) -> Vec<f64> {
input.iter()
.copied()
.filter(|&x| x > threshold)
.collect()
}

Но время выполнения оказалось странным: оно зависело не от объёма данных, а от того, сколько элементов в итоге оставалось после фильтрации.

Замеры: куда уходят миллисекунды

На миллионе случайных чисел от 0 до 100 автор менял порог так, чтобы оставалось 1%, 25%, 50%, 75% или 99% элементов. Результат оказался неожиданным: самый медленный сценарий был не там, где копировалось больше всего, а там, где оставлялась примерно половина значений.

Первая версия гипотезы была простой: виноваты перевыделения памяти, ведь collect() заранее не знает размер результата. Тогда автор попробовал предвыделить память вручную:

pub fn filter_prealloc(input: &[f64], threshold: f64) -> Vec<f64> {
let mut out = Vec::with_capacity(input.len());
for &x in input {
if x > threshold {
out.push(x);
}
}
out
}

Ускорение оказалось почти незаметным. Значит, проблема была не в аллокациях.

Причина: предсказатель переходов

Современный процессор работает не по одной инструкции за раз, а конвейером. Это эффективно, пока не встречается развилка вида: писать элемент или пропустить его. В этот момент процессор вынужден угадывать, какая ветка сработает, а угадывание делает branch predictor.

Если данные ведут себя предсказуемо, процессор почти не ошибается. Если же вход случайный, предсказатель начинает промахиваться, и цена ошибки оказывается высокой: конвейер сбрасывается, спекулятивное выполнение отменяется, и процессор тратит лишние такты на восстановление.

Именно поэтому сценарий с 50% оставшихся элементов оказался самым медленным: для случайных данных ветвление становится почти непредсказуемым, а значит, ошибается слишком часто.

ВЕТВЛЕНИЕ vs BRANCHLESS
────────────────────────
ДАННЫЕ ─▶ [Сравнить] ─▶ if/else ─▶ Записать?
                 │
                 ├─▶ Ответ зависит от данных
                 └─▶ Предсказатель может ошибиться

ДАННЫЕ ─▶ [Сравнить] ─▶ 0/1 ─▶ Добавить к счётчику
                 │
                 ├─▶ Нет развилки
                 └─▶ Предсказывать нечего

Подтверждение: сортировка решает проблему

Если причина в непредсказуемости данных, то что будет, если отсортировать входной массив? На тех же числах и том же пороге фильтр на отсортированных данных заработал заметно быстрее, чем на случайных.

На отсортированном массиве ветка долго идёт в одну сторону, затем долго в другую, и предсказатель быстро обучается. Но сортировка сама по себе дороже фильтрации, да и порядок элементов обычно важен, так что это не универсальное решение.

Решение: branchless-подход

Идея branchless-программирования — убрать непредсказуемый переход совсем и заменить его арифметикой. Вместо «писать или пропустить» мы всегда пишем элемент, а потом сдвигаем индекс только в том случае, если элемент подошёл под условие.

pub fn filter_branchless(input: &[f64], threshold: f64) -> Vec<f64> {
let mut out = vec![0.0; input.len()];
let mut n = 0;

for &x in input {
out[n] = x;
n += (x > threshold) as usize;
}

out.truncate(n);
out
}

Трюк здесь в том, что сравнение всё ещё выполняется, но его результат используется как число, а не как направление ветвления. Компилятор превращает это в простую инструкцию, которая выдаёт 0 или 1. Ветвление исчезает, а вместе с ним и проблема предсказания.

КАК МЕНЯЕТСЯ ЦИКЛ
──────────────────
if/else ─▶ Непредсказуемая ветка ─▶ Ошибка предсказания ─▶ Потеря тактов
   │
   └─▶ branchless ─▶ 0/1 ─▶ Сдвиг счётчика ─▶ Нет развилки

Результаты: красивая таблица

Branchless-версия дала почти плоское время выполнения: результат перестал зависеть от того, сколько элементов осталось после фильтрации. Худший случай ускорился примерно в четыре раза.

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

Стоит ли использовать?

Обычно — нет. Такой код сложнее читать и легче сломать. Но если профилировщик показывает горячий цикл, а внутри него сидит ветвление на непредсказуемых данных, branchless-подход может оказаться очень полезным.

Главный вывод простой: на производительность влияет не только алгоритмическая сложность, но и то, как код ложится на архитектуру процессора. Иногда одна ветка действительно стоит миллисекунд.

Ссылки

• Branchless Rust: оригинальная статья Сергея Потапова — исходный разбор кейса и бенчмарков
• Репозиторий с бенчмарками и кодом — исходники примеров и измерений
• Why is processing a sorted array faster than processing an unsorted array? — обсуждение причины ускорения на отсортированных данных
• Mispredicted branches can multiply your running times — Daniel Lemire — материал о цене неверных предсказаний ветвлений
• Branchless Programming in C++ — Fedor Pikus, CppCon 2021 — доклад о branchless-подходе и оптимизациях