При работе с современными CPU устранение ошибочного предсказания ветвления — ключевой способ повышения скорости программ. Один из самых эффективных способов снижения количества ошибочных предсказаний — полное устранение ветвлений.
Возьмём для примера простую задачу: итеративный обход массива и копирование всех чисел меньше 500 в новый массив. Прямолинейная реализация на C выглядит так:
smlen = 0; for (int i = 0; i < 1000; i++) { if (numbers[i] < 500) { small_numbers[smlen] = numbers[i]; smlen += 1; } }
Если числа распределены случайно, то результат условия if становится непредсказуемым для блока предсказания ветвления CPU. Из-за этого показатель ошибочного предсказания будет высоким, существенно препятствуя производительности, потому что процессору многократно приходится сбрасывать конвейер и начинать исполнение повторно.
Можно избежать этой проблемы при помощи решения без ветвления:
smlen = 0; for (int i = 0; i < 1000; i++) { small_numbers[smlen] = numbers[i]; smlen += (numbers[i] < 500); }
Хоть в этой версии добавляется безусловное сохранение (запись в память, даже если условие не выполняется), её затраты обычно гораздо меньше, чем огромная цена ошибочного предсказания ветвления.
Сравнение производительности
Чтобы получить существенные результаты, выполним по 1000 итераций обеих программ с использованием 100000 случайных чисел.
// SPDX-License-Identifier: MIT #include <stdio.h> #include <stdlib.h> #include <sys/time.h> #define SIZE 100000 int numbers[SIZE]; int small_numbers[SIZE]; int smlen; double ts(void) { static double t0; struct timeval tv; gettimeofday(&tv, NULL); double h = t0; t0 = tv.tv_sec + tv.tv_usec / 1000000.0; return t0 - h; } void init(void) { srand(1); for (int i = 0; i < SIZE; i++) numbers[i] = rand() % 1000; ts(); } void small_if(void) { smlen = 0; for (int i = 0; i < SIZE; i++) { if (numbers[i] < 500) { small_numbers[smlen] = numbers[i]; smlen += 1; } } } void small_bl(void) { smlen = 0; for (int i = 0; i < SIZE; i++) { small_numbers[smlen] = numbers[i]; smlen += (numbers[i] < 500); } } int main(void) { init(); for (int i = 0; i < 1000; i++) small_if(); printf("Time if: %.3f\n", ts()); init(); for (int i = 0; i < 1000; i++) small_bl(); printf("Time bl: %.3f\n", ts()); }
Результаты бенчмарка получены на Apple M1 с оптимизацией -O1. В этом бенчмарке -O3 не давал дополнительного повышения скорости, а лишь увеличивал объём генерируемого кода.
Time if: 0.345 Time bl: 0.036
Анализ ассемблерного кода
При помощи objdump -d --no-show-raw-insn мы можем увидеть разницу в обработке этих циклов CPU.
В случае версии с if компьютер генерирует условное ветвление b.gt.
ldr w13, [x10], #0x4 ; Загрузка numbers[i] cmp w13, #0x1f3 ; Сравнение с 499 (0x1f3) b.gt 0x100000678 ; Ветвление, если больше (узкое место) str w13, [x12, w8, sxtw #2] ; Сохранение значения в small_numbers[j] add w8, w8, #0x1 ; j += 1
В версии без ветвления компилятор использует функцию cinc (условный инкремент).
ldr w13, [x10], #0x4 ; Загрузка numbers[i] str w13, [x12, w8, uxtw #2] ; Безусловное сохранение в small_numbers[j] cmp w13, #0x1f4 ; Сравнение с 500 cinc w8, w8, lt ; Условный инкремент (без ветвления)
В этой версии не происходит ветвления на основании значения данных. Поток управления полностью линеен, что позволяет CPU использовать всю ширину конвейера.
Почему компилятор автоматически не оптимизирует случай с if?
Компилятор не знает природу ваших данных. Если бы меньше 500 была лишь крошечная доля чисел, то версия с ветвлением была бы быстрее, потому что блок предсказания почти всегда бы угадывал правильно.
Версия без ветвления каждый раз выполняет операцию записи (str). Компилятор не может безопасно предполагать, что ему допускается выполнять запись в память, если операция записи в память в изначальном коде должна была происходить только при определённом условии, например, чтобы избежать записи за пределами распределённого буфера.
На x86_64
Intel Xeon (E5-2680)
Time if: 0.576 Time bl: 0.110
В версии с if компилятор генерирует условное ветвление jg.
mov edx, DWORD PTR [rax] ; Загрузка numbers[i] cmp edx, 0x1f3 ; Сравнение значения с 499 (0x1f3) jg 1260 ; Ветвление, если больше movsxd rdi, ecx ; Тело 'if' mov DWORD PTR [r9+rdi*4],edx ; Сохранение значения в small_numbers[j] add ecx, 0x1 ; j += 1
В версии без ветвления компилятор использует команду setle.
mov ecx, DWORD PTR [rax] ; Загрузка numbers[i] movsxd rsi, edx ; Подготовка текущего индекса j mov DWORD PTR [rdi+rsi*4],ecx; Безусловное сохранение в small_numbers[j] cmp ecx, 0x1f3 ; Сравнение значения с 499 setle cl ; Если условие выполняется, то cl = 1, иначе 0 (без ветвления) movzx ecx, cl ; Добавление к cl нуля до ecx add edx, ecx ; j += (0 или 1)
Память предсказателя переходов
Снижение размера массива до 10000 элементов или меньшего количества уменьшает разрыв в производительности, потому что таблицы истории предсказателя переходов достаточно велики, чтобы отследить паттерн. При многократной обработке одного и того же массива CPU узнаёт результат каждого условия if, достигая почти идеальной точности предсказания. При увеличении размера до 100000 элементов его память переполняется.
Quicksort
Quicksort очень хорошо подходит для программирования без ветвлений, так как основная задача алгоритма заключается в разбиении данных перемещением всех элементов меньше опорного в одну сторону.
Комментарии (43)
Krinopotam
13.05.2026 09:35Суть примера понятна, спасибо! Но разве примеры с ветвлением и без ветвления всегда дадут одинаковый результат? В примере с ветвлением массив `
small_numbers` никогда не будет содержать числа, больше499, в вот пример без ветвления может, если последний элемент в исходном массиве будет больше499. А значит у них разная логика и их производительность нельзя сравнивать.
Gromilo
13.05.2026 09:35С одной стороны я согласен. С другой: а нам не без разницы что там лежит? Всё что за заполненным размером - мусор.
Krinopotam
13.05.2026 09:35Мой посыл был в том, что сравнивать производительность алгоритмов корректно только в случае равенства их результатов. Если после одного из алгоритмов нужно делать какие-то дополнительные вычисления, то их сравнение уже не корректно. Можете считать это занудством.
P.S. Просто отбросить хвост, считая его мусором, не получится. Нужно проверять, что лежит в последнем индексе массива, что уже усложнит читабельность кода.Gromilo
13.05.2026 09:35А что за вычисления?
Krinopotam
13.05.2026 09:35В итоговом массиве
small_numbersпоследним элементом может казаться число, больше 499, чего быть не должно. А может и не оказаться, если в исходном массиве значений последнее число меньше 500. А следовательно нужно проверить, что последний элемент не больше 499 и убрать его, если мы собираемся использовать массивsmall_numbersгде-то дальше. Или я ошибаюсь?Gromilo
13.05.2026 09:35Я исхожу из того, что у массива есть длина в отдельной переменной и мы никогда не обращаемся за пределы этой длины. Число большее 499 - это не последний элемент, а элемент за пределами массива.
Например, если мы нашли одно маленькое число, то оно будет лежать по индексу 0, а по индексу 1 может лежать что угодно.Пример на шарпах
![Во втором массиве отличается второй элемент, но это всё-равно, т.к. smlen==1 и мы нигде не должны обращаться к small_numbers[1]](https://habrastorage.org/getpro/habr/upload_files/594/158/e35/594158e3531ce03407b079c8b7bd1dc4.png "Во втором массиве отличается второй элемент, но это всё-равно, т.к. smlen==1 и мы нигде не должны обращаться к small_numbers[1]")
Во втором массиве отличается второй элемент, но это всё-равно, т.к. smlen==1 и мы нигде не должны обращаться к small_numbers[1] Krinopotam
13.05.2026 09:35Если в таком смысле, то все верно. Но в реальной практике эти алгоритмы ведь должны быть для каких-то целей и обычно внутри функций. И результаты их вычислений также нужны не просто так, а где-то должны использоваться, и скорее всего должны быть переданы в другую функцию, которая уже не ожидает значения больше 499. Вот и получается, что первый алгоритм в качестве результата может вернуть готовый чистый массив
small_numbers, в котором точно нет значений, больше 499. А branchless алгоритм должен либо подчистить массивsmall_numbers(для чего потребуется хоть и незначительная, но доп. логика), либо должен возвращать грязный массивsmall_numbersи индекс для "отсечения хвоста", и тогда доп. логику придется реализовывать позже.Gromilo
13.05.2026 09:35либо подчистить массив
small_numbers(для чего потребуется хоть и незначительная, но доп. логика)Согласен. Но это ни на что не влияет, т.к. 1 действие. К тому же я не могу представить, зачем нам результат без количества. Что-то очень специфичное.
event1
13.05.2026 09:35Если в конце добавить проверку последнего элемента и корректирующие действия, это изменит сложность на константу. При измерении вычислительной сложности константами обычно пренебрегают.
unreal_undead2
13.05.2026 09:35Интеловский компилятор, кстати, генерирует из прямолинейной реализации векторизованный код без ветвлений внутри цикла (используя VPCOMPRESS).
domix32
13.05.2026 09:35В статье счётчик и данные - глобальные переменные, у вас же счётчик существует только в области видимости функции, и данные передаются в аргументы. Если повторить окружение как в статье, то векторный код рассосётся и не появится даже для branchless версии. Забавно конечно, что автор вообще не думает за локальность данных, которая чаще будет давать больше профита, нежели branchless.
unreal_undead2
13.05.2026 09:35Да, похоже он тогда боится, что запись в small_numbers может перекрыться с smlen (хотя по идее это UB и изменение поведения в такой ситуации можно проигнорировать ради оптимизации). Но да, в любом случае использование локальных переменных и restrict может отсечь потенциальные побочные эффекты, из за которых приходится генерировать странный код.
Dark_Purple
13.05.2026 09:35Как минимум результат выполнения кода из примеров может быть разный. Преждевременная оптимизация или более понятный код - выбор очевиден.
domix32
13.05.2026 09:35устранение ошибочного предсказания ветвления — ключевой способ повышения скорости программ.
оно конечно повышает скорость программы, но вот к ключевым способам я бы это не отнёс. Применение кода без ветвлений - довольно нетривиальная задача и имеет довольно узкую область применимости. И упоминание quicksort особенно забавно, ибо branchless вариант нашёл не человек, а робот, что ещё раз подчёркивает нетривиальность этой методики в большинстве реального кода.
Большим профитом было бы показать, как локальность данных помогла бы в этой ситуации больше, нежели сэкономить на ветвлениях.
MaxMxMz
13.05.2026 09:35(numbers[i] < 500) Вот не могу вспомнить - стандарт языка нам точно и всегда гарантирует что результат операции 1, а не любое отличное от 0 ?domix32
13.05.2026 09:35Гарантировано как минимум в C99
6.3.1.2 Boolean type
1. When any scalar value is converted to _Bool, the result is 0 if the value compares equal to 0; otherwise, the result is 1.
в более ранних стандартах оператор сравнения выплевывал гарантированное значение 0 или 1.
event1
13.05.2026 09:35Хоть в этой версии добавляется безусловное сохранение (запись в память, даже если условие не выполняется), её затраты обычно гораздо меньше, чем огромная цена ошибочного предсказания ветвления.
Это было безусловно верно 40 лет назад. Сегодня цена ошибки предсказания ветвления — пара тактов, а лишний доступ в память (даже в кэш второго уровня, даже на чтение) — десятки и сотни тактов. Через это, подобные оптимизации имеют смысл только для очень маленьких и горячих циклов, либо из академического интереса.
Кстати, для пущего улучшения, можно циклы перевернуть, чтоб шли от тысячи к нулю. На RISC-платформах сэкономится регистр.
unreal_undead2
13.05.2026 09:35цена ошибки предсказания ветвления — пара тактов
Скорее десяток, можно глянуть скажем в исходниках компиляторов - хотя там некое "среднее по больнице", реальное влияние зависит от кода вокруг.
а лишний доступ в память (даже в кэш второго уровня, даже на чтение)
Примерно столько же (даже если важна именно latency доступа). В интеловском мануале цифры в районе 10-15.
event1
13.05.2026 09:35Скорее десяток
зависит от длины конвейера, но для современных х86 систем, вы пожалуй правы.
Примерно столько же (даже если важна именно latency доступа). В интеловском мануале цифры в районе 10-15.
Опять же зависит от архитектуры, но это если действительно повезло попасть в L2-кэш. А если нужных данных нет ни в одном кэше?
vvdev
13.05.2026 09:35справедливости ради в этом примере оба массива практически с гарантией окажутся в кешах.
unreal_undead2
13.05.2026 09:35Понятно, что latency доступа в DRAM будет заметно больше. Тут уже общее правило - перед тем, как оптимизировать, сначала определить узкое место в коде, потом - узкое место в железе, из за которого тормозит этот код, и потом целенаправленно бить в нужную точку.
vvdev
13.05.2026 09:35Кстати, для пущего улучшения, можно циклы перевернуть, чтоб шли от тысячи к нулю. На RISC-платформах сэкономится регистр
На х86/64 тоже, чего бы ему не сэкономить.
event1
13.05.2026 09:35там в коде ассемблера сравнение с константой. Не уверен, есть ли какая-то разница между сравнением с константой и сравнением с нулём.
vvdev
13.05.2026 09:35Есть. Даже c# код под Интел экономит регистр на обратных циклах.
Типа такого будет:
L0027 dec r8d L002a jns short L0020
supernastos2013
13.05.2026 09:35а обратный цикл -- не сломает кеш предсказуемость?
vvdev
13.05.2026 09:35Отличный вопрос, меня он тоже тревожит. По опыту - нет, хотя объяснить я себе этого не могу.
Но: с обратным циклом и пойнтер-арифметикой (ref var curr + MemoryMarshal + Unsafe.Add) можно и от регистра для exit condition избавиться, и доступ прямой последовательный сохранить. И JIT именно так и делает, когда решает, что может поменять направление счётчика.
RootTool
13.05.2026 09:35По своей природе очень похоже на написание кода для GPU, где обычно условия не приветствуются :)
Можно всю итерацию вычислять цвет пикселя, а затем в самом конце происходит умножение на ноль и все вычисления коту под хвост
Да, довольно таки ужасно, но зато без ветвлений + предсказуемо...
MountainGoat
13.05.2026 09:35с ифами много приколов связано. С тем, как процессор реагирует на ветвления.
Допустим, у нас есть структура
Кот {цвет, вес}.И надо посчитать суммарный вес всех чёрных котов.Казалось бы, надо так:
пусть сумма = 0; Для каждого кота в массиве: { если (кот.цвет == чёрный) { сумма += кот.вес; } }Но вот фигуёки. Если компилятор только за вас не перепишет. Потому что вот так будет в разы быстрее.
пусть сумма = 0; Для каждого кота в массиве: { пусть временная_сумма = сумма + кот.вес; если (кот.цвет == чёрный) { сумма = временная_сумма; } }Во первых, вычисление предсказуемо и процессор в очереди может его оптимизировать. Во вторых, это ещё и векторизуется проще.
MountainGoat
13.05.2026 09:35Хммм. Сейчас на LLMил пример, и что-то у меня улучшение не такое сильное, как в прошлый раз. 35 ms против 42. Но всё равно есть. Может, LLVM улучшили?
Короче, вот
коткод.Вот
use std::time::Instant; use rand::prelude::*; // The Cat struct with two fields. #[derive(Debug, Clone)] struct Cat { is_black: bool, weight: f32, } /// Sum the weights of black cats using a plain `for` loop. fn sum_black_cats_for(cats: &[Cat]) -> f32 { let mut total = 0.0; for cat in cats { if cat.is_black { total += cat.weight; } } total } /// Sum the weights with unconditional sum. fn sum_black_cats_for2(cats: &[Cat]) -> f32 { let mut total = 0.0; for cat in cats { let temp_total = total + cat.weight; if cat.is_black { total = temp_total; } } total } /// Sum the weights of black cats using iterator adapters. fn sum_black_cats_iter(cats: &[Cat]) -> f32 { cats.iter() .filter(|cat| cat.is_black) .map(|cat| cat.weight) .sum() } fn main() { let mut rng = rand::rng(); let n = 10_000_000; // Generate a vector of one million random cats. let cats: Vec<Cat> = (0..n) .map(|_| Cat { is_black: rng.random(), // 50% chance of being black weight: rng.random_range(3.0..10.0), // random weight between 0 and 100 }) .collect(); // ---- Time the for-loop version ---- let start = Instant::now(); let sum_for = sum_black_cats_for(&cats); let duration_for = start.elapsed(); println!("For-loop sum: {:.2}", sum_for); println!("For-loop time: {:?}", duration_for); // ---- Time the always sum version ---- let start = Instant::now(); let sum_for = sum_black_cats_for2(&cats); let duration_for = start.elapsed(); println!("Always sum sum: {:.2}", sum_for); println!("Always sum time: {:?}", duration_for); // ---- Time the iterator version ---- let start = Instant::now(); let sum_iter = sum_black_cats_iter(&cats); let duration_iter = start.elapsed(); println!("Iterator sum: {:.2}", sum_iter); println!("Iterator time: {:?}", duration_iter); }
degor
13.05.2026 09:35Это вы заблуждаетесь. Компилятор VS2026 создает одинаковый код за одним исключением: во втором варианте он все суммирует в один регистр, а потом копирует его значение в регистр результата.
То есть вторая функция медленнеe на одно копирование из регистра в регистр (это сарказм, если чо). В разы, да.
sci_nov
13.05.2026 09:35Для этого этот цикл надо хотя бы на 4 линии заunrollить. Я предпочитаю пользоваться оператором ? при этом.
roudakov
Выглядит как натягивание совы на глобус. Да, в ассемблере есть удобная инструкция
SETLEочень хорошо подходящая именно под этот случай. Ну а если надо не посчитать числа меньше 500, а просуммировать? А если что-то другое, для чего нет подходящей инструкции в ассемблере?SaihonFox
если надо просуммировать, то где то на хабре был пост о том, как компиляторы оптимизируют ваш код и там примерно такой алгоритм выходил: (n * (n + 1)) / 2. сумма от 1 до n включительно
roudakov
Не о том речь.
Весьма локальное решение представляют как панацею. Я не могу представить много вариантов, где подобный трюк будет полезен.
Как академическое исследование - любопытно, но не полно. Будет ли такой же эффект на других процессорах и процессорных архитектурах? А в случае байткода? А на интерпретируемых языках?
domix32
применение branchless в принципе довольно локальная история, да. иногда полезно, но обычно пайплайн ни разу не настолько линейный и скорость появляется при превращении в filter-map-reduce пайплайн - чисто за счёт cache locality.
Сам приём в среднем вроде не привязан к архитектуре процессоров, поэтому в теории может везде работать. В случае байткода - как повезёт. Java/С#/Swift наверняка запрятали это где-нибудь в JIT-оптимизациях, CPython или Lua - может быть, но с большим шансом только в каких-нибудь более мажорных версиях.
roudakov
А будет ли так же работать в Java и Swift? Там нет прямого приведения булево к целому. Толь через ?:
?: оптимизируется лучше чем if?
vvdev
Зависит от компилятора/JITа, но на уровне команд процессоров Интела, вполне может компилироваться как бранчлесс.
Однако тут есть нюанс: сначала оба операнда читаются из памяти, потом один из них выбирается. Если чтение не из кешей - то бранч может оказаться выгоднее.
domix32
Я не настолько силён в этих языках. Выбрал как представителей использующих виртуальные машины с собственными инструкциями. Робот уточняет
Swift - благодаря llvm бэкэнду снативится до setle.
Go - есть поддержка на уровне IR, и соотвественно нативно.
Wasm - поддерживает типизированные варианты инструкции, так что зависит от оптимизатора. Рантайм Node, deno, bun и браузеры вполне могут их использовать, если JIT соизволит.
C# - может соптимизировать нативно, в CIL нет прямой поддержки,
JVM - kotlin, java - не могёт.
OCaml, Haskell - оба имеют и на уровне байткода и при компиляции в натив.
Nim - зависит от бэкэнда для транспиляции - для си понятно дело заведётся, для JS - зависит от финального рантайма.
Lua и Luajit - оба имеют на уровне байткода
Cpython - не умеет, PyPi - если JIT соизволит.
Sixshaman
roudakov
Любопытно. Но работать будет только на Си? А на более сложных условиях эффект будет?
spirit1984
Вообще был один интересный вопрос на Stackoverflow - почему обработка с if отсортированного массива куда быстрей? И шикарный ответ.
Вкратце - если последовательность данных упорядочена, то предиктор процессора работает как по маслу в таких случаях. Фактически if убирают за вас.
Можно возразить "Так а если у меня неотсортированная последовательность?". Однако если мы говорим не про лабораторный эксперимент с использованием ГСЧ, как правило, эти последовательности не берутся из воздуха. Они хранятся в какой-нибудь базе и уже упорядочены.
vvdev
Далеко не всегда хранятся, далеко не всегда в базе, и даже если и упорядочены - далеко не всегда по тому критерию(ям), по которому(ым) у нас условие(я).