Rust: удаление if ускорило фильтрацию данных почти в 4 раза
Разработчик Сергей Потапов в блоге greyblake.com (пост от 2 августа 2026 года) разобрал случай из практики: понадобилось оптимизировать участок кода на Rust, который фильтрует массив чисел по порогу, операцию, которую движки баз данных выполняют постоянно. Для теста он взял массив из миллиона случайных чисел типа f64, равномерно распределённых в диапазоне 0,0, 100,0, и подобрал пять порогов так, чтобы фильтр оставлял 1%, 25%, 50%, 75% или 99% элементов.
Идиоматичная реализация на итераторах (input.iter().filter(|&x| x > threshold).collect()) дала неожиданный результат: медленнее всего фильтр работал именно при пороге, оставляющем около половины элементов, хотя копировал лишь половину данных. При пороге, оставляющем 99% элементов (почти вдвое больше данных на выходе), тот же фильтр оказался в 2,6 раза быстрее, чем при 50%. Первая гипотеза, накладные расходы на переаллокацию вектора внутри collect(), не подтвердилась: версия с предварительным выделением памяти (Vec::with_capacity) на пороге 50% показала 3,87 мс, лишь на 2% быстрее исходной.
Причина оказалась в предсказателе переходов процессора. Конвейер современного CPU начинает выполнять инструкции спекулятивно ещё до того, как известен результат сравнения x > threshold; при ошибке предсказания конвейер приходится сбрасывать и начинать заново, а это стоит порядка 15, 20 тактов против одного такта на само сравнение. При пороге 1% или 99% предсказатель почти всегда угадывает направление, потому что данные предсказуемы, и промахи редки. А при пороге 50% на перемешанных случайных данных угадывать нечего, предсказатель работает как подбрасывание монеты и ошибается примерно на каждом втором элементе. Для миллиона чисел это около полумиллиона сбросов конвейера, что на частоте 4 ГГц даёт примерно 2 мс чистых потерь, величина, которая и объясняет разрыв между строками 50% и 99% в таблице.
Автор проверил догадку экспериментом: та же функция, тот же порог, тот же миллион чисел, но предварительно отсортированные (сортировка, вне замеряемого участка). Результат, ускорение в 4,5 раза по сравнению с перемешанными данными: на отсортированном массиве предсказатель после одной ошибки безошибочно угадывает «пропустить» для всей первой половины и «оставить» для второй. Тот же эффект обсуждается в вопросе на Stack Overflow с 27 тысячами голосов, «Почему обработка отсортированного массива быстрее, чем неотсортированного». Сортировка, впрочем, не решение: она сама стоит дороже, чем фильтрация, да и исходный порядок элементов обычно всё равно нужен.
Настоящее решение, программирование без ветвлений (branchless): убрать непредсказуемый условный переход вовсе, чтобы предсказывать было нечего. В такой версии каждый элемент безусловно записывается в выходной массив по текущей позиции курсора n, а сам курсор продвигается на (x > threshold) as usize, на 1, если элемент подошёл под условие, и на 0, если нет; после прохода массив обрезается функцией truncate(n), отбрасывающей неиспользованный хвост. Сравнение по-прежнему выполняется, но его результат используется как число для сдвига курсора, а не как решение о переходе, на языке компиляторов это называется превращением управляющей зависимости в зависимость по данным. В сгенерированном ассемблере сравнение превращается в инструкцию seta, которая просто возвращает 0 или 1: переходить в буквальном смысле больше не на что. Автор оговаривается: проверка границ массива при записи в out[n] и условие самого цикла, тоже переходы, но они миллион раз подряд ведут себя одинаково, и предсказатель обрабатывает их бесплатно; убрать пришлось только непредсказуемый переход.
Результат: худший случай (50% отбора) ускорился почти в 4 раза, а время работы новой версии перестало зависеть от того, сколько элементов проходит фильтр, график стал плоским. Бесплатным ускорение не бывает: при пороге 1% исходная версия с if по-прежнему быстрее, потому что почти всегда правильно предсказанный переход обходится процессору практически бесплатно, а версия без ветвлений платит за запись всех элементов независимо от результата фильтра. Автор советует: в большинстве случаев переходить на такой код не стоит, он хуже читается и его легче сломать, а часть подобных оптимизаций компилятор и так делает сам. Приём себя оправдывает, только когда профилировщик прямо указал на горячий цикл с переходом по непредсказуемым данным.
Бенчмарки сделаны на библиотеке criterion, код и замеры выложены в открытом репозитории branchless-rust-benchmarks, результаты можно перепроверить самостоятельно. Процессор, на котором получены цифры, Intel i7-10875H; версия компилятора, флаги сборки и операционная система в посте не указаны. Сравнение ограничено тремя однопоточными скалярными реализациями на Rust, SIMD, автовекторизация, многопоточность и GPU не рассматриваются.
Ключевые факты
- Фильтрация массива из 1 млн чисел f64 на Rust медленнее всего работает при пороге, оставляющем около 50% элементов: на пороге 99% (почти вдвое больше данных на выходе) та же операция быстрее в 2,6 раза.
- Причина не в переаллокации памяти (предвыделение вектора ускоряет лишь на 2%), а в предсказателе переходов CPU: на случайных данных при 50%-й селективности он ошибается через раз, вызывая около полумиллиона сбросов конвейера (по 15, 20 тактов каждый).
- На отсортированных данных та же функция с тем же порогом ускоряется в 4,5 раза, предсказатель безошибочно угадывает переход после первой ошибки.
- Переписав фильтр без ветвлений (безусловная запись каждого элемента плюс сдвиг курсора на 0 или 1 вместо
if), автор ускорил худший случай почти в 4 раза и избавил время работы от зависимости от доли отбираемых элементов. - Приём не универсален: при пороге 1% исходный код с
ifбыстрее, потому что версия без ветвлений всегда пишет все элементы; переходить на неё стоит только когда профилировщик указал на горячий цикл с непредсказуемым переходом.
Почему это важно
Пост на измеримом примере с открытым для проверки кодом показывает эффект, о котором легко забыть: скорость программы на современном CPU зависит не только от количества операций, но и от того, насколько предсказуемо ветвится код. Фильтрация, базовая операция, которую движки баз данных и обработчики данных выполняют постоянно, поэтому цена ошибки предсказания перехода (15, 20 тактов против одного такта на само сравнение) касается куда более широкого круга задач, чем один синтетический бенчмарк. Материал наглядно показывает и то, что интуитивная оптимизация вроде предвыделения памяти иногда не решает проблему вовсе, настоящая причина требует понимания того, как устроен процессор внутри.
Кому это важно
В первую очередь, разработчикам на Rust и других системных языках, которые пишут код с реальными горячими участками: движки баз данных, обработку потоков данных, низкоуровневые библиотеки. Эффект не специфичен для Rust: предсказатель переходов есть в любом современном x86- или ARM-процессоре, так что приём применим и в C++, C, Go, в любом компилируемом языке. Полезен материал и тем, кто профилирует код и видит необъяснимые просадки производительности: паттерн «код неожиданно медленный именно при отборе около половины элементов» стоит в первую очередь проверять на предсказуемость данных, а не только на алгоритмическую сложность.
Как это применить
Схема приёма для Rust: вместо out.push(x) внутри if x > threshold, всегда писать out[n] = x в заранее выделенный массив нужного максимального размера, а курсор n продвигать на (x > threshold) as usize (0 или 1); в конце, out.truncate(n), чтобы отбросить неиспользованный хвост. Ключевое условие, не переписывать код без нужды, а сначала профилировщиком найти реально горячий цикл, в котором переход зависит от непредсказуемых (случайных, неотсортированных) данных: на предсказуемых данных (сильный перекос к 0% или 100% отбора) выигрывает обычный код с if. Перед внедрением стоит замерить оба варианта на своих данных, автор использовал для этого библиотеку criterion и выложил тестовый проект branchless-rust-benchmarks в открытом доступе, так что методику можно скопировать напрямую.
Можно ли доверять
Сам эффект, не открытие автора, а хорошо документированное свойство конвейерных процессоров: на него ссылается и вопрос на Stack Overflow с 27 тысячами голосов, и материалы для дальнейшего чтения, которые приводит автор, в частности, блог Дэниела Лемира, известного бенчмарками низкоуровневой производительности, и доклад Фёдора Пикуса на CppCon 2021. Для проверяемости своих цифр автор выложил код и бенчмарки в открытый репозиторий branchless-rust-benchmarks, а измерения сделаны стандартной для Rust библиотекой criterion, результаты можно перепроверить, а не просто принять на слово. При этом в тексте поста явно приведено только одно точное значение задержки (3,87 мс для предвыделенной версии на пороге 50%); остальные результаты даны как относительные множители со ссылкой на таблицы-скриншоты, не воспроизведённые в тексте. Не указаны версия компилятора, флаги сборки и операционная система, тестирование ограничено одним процессором (Intel i7-10875H) и тремя однопоточными скалярными реализациями без сравнения с SIMD или многопоточностью.
Риски и подводные камни
Автор прямо предупреждает: код без ветвлений читается хуже обычного и его легче сломать, а часть подобных оптимизаций компилятор и так делает сам, переписывать код без веских оснований не стоит. Ускорение не гарантировано: при сильно перекошенных данных (порог, оставляющий около 1% элементов) исходная версия с if остаётся быстрее, потому что вариант без ветвлений всегда пишет весь миллион элементов независимо от того, сколько из них реально подошло под условие. В показанном коде такая функция сразу выделяет буфер размером со весь вход (vec![0.0; input.len()]), а не по фактическому размеру результата, память резервируется по максимуму. Главное практическое ограничение: приём даёт эффект только на конкретном классе задач, горячий цикл с переходом по непредсказуемым данным; на предсказуемых данных или вне горячего пути в нём нет смысла.
«Переход, это дёшево. Неверно предсказанный переход, нет.»
— Сергей Потапов, автор поста