При работе с современными 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 очень хорошо подходит для программирования без ветвлений, так как основная задача алгоритма заключается в разбиении данных перемещением всех элементов меньше опорного в одну сторону.
Комментарии (86)
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 действие. К тому же я не могу представить, зачем нам результат без количества. Что-то очень специфичное.
Deosis
13.05.2026 09:35Для этого в алгоритме есть переменная smlen. Никто не должен читать данные начиная с этого индекса.
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 может отсечь потенциальные побочные эффекты, из за которых приходится генерировать странный код.
AndreyDmitriev
13.05.2026 09:35векторный код рассосётся
Не, вроде не рассосётся, я вернул счётчик наружу, код замедлился, но векторизация осталась, вот коммент ниже со скриншотом.
domix32
13.05.2026 09:35Менял на годболте из начального комментария. Вынос переменной smlen удаляет любые векторные вызовы. Если скопипастить код из статьи, то векторные операции появляются только на инициализации массивов, но не в обработке.
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 именно так и делает, когда решает, что может поменять направление счётчика.
VADemon
13.05.2026 09:35Сегодня цена ошибки предсказания ветвления — пара тактов
Citation needed для временной эпохи наставшей после класса уязвимостей Spectre.
а лишний доступ в память (даже в кэш второго уровня, даже на чтение)
Здесь вы путаетесь, в тексте, даже цитате, стоит: "в этой версии добавляется безусловное сохранение". Безусловное сохранение - это не чтение (благодаря write-back cache). Во-вторых, здесь безусловно используется L1D cache, даже с того же самого lane. Где такой оппортунизм станет дорогим - на много-много ядер и дорогой синхронизацией кэша из-за постоянной модификации памяти. Решение? Устранить конкуренцию между потоками.
event1
13.05.2026 09:35Citation needed для временной эпохи наставшей после класса уязвимостей Spectre.
Предсказание ветвления заключается в том, что процессор пытается угадать с какого места в памяти заполнять конвейер после того, как туда попала команда ветвления (спекулятивное заполнение). Потому что точный адрес ветвления выяснится в блоке исполнения ближе к концу конвейера. Соответственно, цена ошибки — время затраченное на заполнение конвейера командами с неправильного адреса. Очевидно, такая цена не может быть выше длины конвейера (в тактах). В зависимости от архитектуры она будет болтаться где-то возле половины длины. Скажем, тактов 10-15
Здесь вы путаетесь, в тексте, даже цитате, стоит: "в этой версии добавляется безусловное сохранение". Безусловное сохранение - это не чтение (благодаря write-back cache)
Производительность приложения предложенного в статье интересна исключительно с академической точки зрения. Автор демонстрирует некий принцип. Теоретически верный сам по себе. Но, при современном уровне развития вычислительной техники (скорость процессора на порядок выше скорости памяти) намного важнее, как программа обращается с памятью. Лишнее обращение может запросто перекрыть все выгоды от оптимизированных ветвлений
VADemon
13.05.2026 09:35Про misprediction понял, где ошибся, пока читал текст.
The average misprediction penalty was measured to approximately 18 clock cycles for Zen 1-3. The misprediction penalty varies from 15 - 18 in Zen 4 and 15 - 25 in Zen 5.
https://agner.org/optimize/microarchitecture.pdf стр 35
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); }MountainGoat
13.05.2026 09:35Ещё поэкспериментировал. Абсолютный чемпион с отрывом
fn sum_black_cats_for2(cats: &[Cat]) -> u64 { let mut total = 0; for cat in cats { total += cat.weight * cat.is_black as u64; } total }Что и следовало ожидать. Просто в реальном коде так красиво редко свернётся.
IF-ы не бесплатны. Сильно не бесплатны. Арифметика намного дешевле. Не надо добавлять if-ы, чтобы избежать немного арифметики. Вот главное, что нужно
vvdev
13.05.2026 09:35Не надо добавлять if-ы, чтобы избежать немного арифметики. Вот главное, что нужно
Даже не вспоминаем о возможном "лишнем" обращении к незакешированной памяти для обеспечения чистой арифметики, с этим и так понятно.
Но вот у меня есть живой пример, в котором с помощью ИФа можно ИНОГДА избавиться от простого int64 idiv над операндами, гарантированно лежащими в регистре и кеш-линии. И оно того стоит - любые бенчмарки и реальность это подтверждают.
Так что не всякая арифметика одинаково полезна.
Medeyko
13.05.2026 09:35Не очень понятно, что именно умножается в данном варианте. (Cat::weight у Вас объявлена как f32. На u64 она не умножается.) Похоже, Вы не всё описали, что сделали. От этого быстродействие может изменяться.
А так, ещё можно вместо умножения попробовать делать - (отрицание) и & (побитовое И).
vvdev
13.05.2026 09:35Умножается оно здесь на 1 (удовлетворяет условию) или на 0 (не удовлетворяет), таким образом получаем сумму весов котов, удовлетворяющих условию.
А так, ещё можно вместо умножения попробовать делать - (отрицание) и & (побитовое И).
Можно, и даже побитовое NOT. Всё это можно сделать без ветвлений, парой-тройкой арифметических/битовых операций. Иногда ОЧЕНЬ ускоряет, иногда - нет.
Тут ещё стоит не забывать про буферы декодера и блока обработки циклов (как его там) - там сдвиг команд на пару байтов туда-сюда может СИЛЬНО влиять на производительность.
Medeyko
13.05.2026 09:35Нет, Вы не поняли мой вопрос. Rust не даст умножить f32 на u64. Соответственно, MountainGoat что-то сделал с Cat::weight - то ли сделал его u64, то ли ещё чего-то...
А когда я говорил "можно попробовать делать" - я это так ненавязчиво намекал, чтобы MountainGoat попробовал сделать и поэкспериментировать, хех!
А про буферы - ну, да, действительно, ещё куча разных мелочей, влияющих на быстродействие...
vvdev
13.05.2026 09:35Что, не приведёт имплицитно инт в флоту?
Я не специалист, на с# приводит и результат ожидаемо лучший....побитовые операции с флотом тоже вполне себе существуют.
Medeyko
13.05.2026 09:35Нет, Rust не любит имплицитные операции из соображений уменьшения возможностей (вероятности) выстрелов в собственную ногу. Там выбор дизайна в большинстве мест тяготеет к тому, чтобы пишущий и читающий код программист хорошо осознавал, что происходит.
Если хочется f32, так и надо прямо писать as f32, а не as u64.
(Извините, не уловил, что автором реплики был MountainGoat, а не Вы - поправил свою реплику.)
MountainGoat
13.05.2026 09:35Раст принципиально ничего не приводит. Даже f32 к f64. Только литералы подбирает по типу, и то 10.0 в u64 класть низя.
MountainGoat
13.05.2026 09:35Да я просто во всей программе тип несколько раз поменял и забыл, какой оставил. Было интересно, соотношение скоростей поменяется при смене типа или нет. Ответ: поменяется. При переходе с 32 на 64 бит разница в скорости между разными методами уменьшилась вдвое. При переходе с f на u ничего не изменилось.
Побитовые операции ничего не дадут потому, что компилятор и так их вставляет, где может. То же самое касается и векторизации вручную. Это очень вымороченный случай, когда руками что-то можно так сделать, что компилятор не сможет.
degor
13.05.2026 09:35Это вы заблуждаетесь. Компилятор VS2026 создает одинаковый код за одним исключением: во втором варианте он все суммирует в один регистр, а потом копирует его значение в регистр результата.
То есть вторая функция медленнеe на одно копирование из регистра в регистр (это сарказм, если чо). В разы, да.
AndreyDmitriev
13.05.2026 09:35Чё-то мне VS2026 не стала выдавать одинаковый код, судя по шестикратной разнице. Но интеловсим компилятором он сильно эффективнее получился, а дальше я глубоко не ковырялся.
sci_nov
13.05.2026 09:35Для этого этот цикл надо хотя бы на 4 линии заunrollить. Я предпочитаю пользоваться оператором ? при этом.
Porohovnik
13.05.2026 09:35А здесь говорится ровно о противоположном, и разбирается до боли похожий пример:
AndreyDmitriev
13.05.2026 09:35Если вы возьмёте нормальный современный оптимизирующий компилятор, скажем Intel OneAPI (да, я в курсе, что вы на Apple M1, но тем не менее), то будете приятно удивлены, потому что вот это:
Превратится вот в это:
Это под профилировщиком VTune запущено. И нет никаких бранчей и SIMD на месте.
Разница между if и bl есть, но не драматическая. Кодом bl утомлять не буду, его там больше. Зато разница между Intel и Visual Studio впечатляющая:
100000 итераций (for (int i = 0; i < 100000; i++) ret = small_**();) Интел: Time if: 0.195534 Time bl: 0.124896 Студия Time if: 35.107267 Time bl: 5.962277Синтетические примеры хороши для понимания, но в реальной жизни они могут быть чуть другие. А так интеловский компилятор в общем неплохо справляется, вот, к примеру, тернарный оператор он сам на cmove заменяет, надо просто в ассемблер поглядывать и ему иногда немножко помогать, зато это даёт возможность не отказываясь от удобного представления искодников с "if" получать тем не менее "branchless" машинный код.
unreal_undead2
13.05.2026 09:35А флаги какие (и нет ли изменений в исходнике, номера строчек смущают)? У меня на godbolt отказался:
Begin optimization report for: small_if()
LOOP BEGIN at <source> (26, 5)
remark #15344: Loop was not vectorized: vector dependence prevents vectorization
remark #15346: vector dependence: assumed FLOW dependence between [ <source> (29, 19) ] and [ <source> (28, 13) ]
remark #15346: vector dependence: assumed FLOW dependence between [ <source> (29, 19) ] and [ <source> (29, 19) ]
remark #25438: Loop unrolled without remainder by 8
LOOP END
При выносе в независимую функцию без использования глобальных переменных векторизует, ссылку кидал выше.
AndreyDmitriev
13.05.2026 09:35Флаги по умолчанию, включена скорость и повальный AVX2 на Haswell (я упражняюсь на i7-4800MQ):
и вот
Но, кстати, когда я перебрасываю код в библиотечную функцию (я ещё и на Расте покрутил), то там не всё так шоколадно, хотя интел всё равно в лидерах.
А, и не то, чтобя я годболту не доверяю, но я привык верить исключительно собственным глазам, поэтому только декомпиляция/анализ листингов компиляции или анализ под отладчиком или профилировщиком именно у меня, там, где оно запускается. Все версии самые свежие 2026, что интел, что MSVC.
unreal_undead2
13.05.2026 09:35Кстати, меня в этом ассемблерном коде несколько смущает отсутствие записи в выходной массив.
AndreyDmitriev
13.05.2026 09:35Кстати, совершенно верное наблюдение, я просто навскидку скопипастив скомпилировал, было интересно именно наличие векторных инструкций, и да, есть подозрение, что эта часть вообще выкинута за ненадобностью, ну было поздно вечером уже.
degor
13.05.2026 09:35Студия Time if: 35.107267А по мнению VTune, куда здесь время уходит? Есть подозрение, что не на branch prediction.
AndreyDmitriev
13.05.2026 09:35Нет конечно, там рыхло всё, вот так выглядит:
А интеловский компилятор судя по всему запись в массив выкинул, а я, засыпая, не заметил. Там чисто на векторизации просто не вытянуть такую разницу.
LinkToOS
13.05.2026 09:35О таких вещах должен думать разработчик компилятора. Чтобы у миллиона программистов не болела голова. Нереально при создании программы анализировать каждый маленький участок кода, и предсказывать как он будет исполняться в железе. Такое нормально только если пишешь вирусы и софт для взлома, и нужно использовать особенности работы железа, которые можно использовать как уязвимость.
vvdev
13.05.2026 09:35smlen = 0;for(inti = 0; i < 1000; i++) {if(numbers[i] < 500) { small_numbers[smlen] = numbers[i]; smlen += 1; }}А о чём конкретно в случае изначального примера должен думать разработчик компилятора?
И что в нём такого, что его нужно прям анализировать и предсказывать [особенно Инженеру встраиваемых систем (младшему)]?
unreal_undead2
13.05.2026 09:35Как уже показали выше, компилятор вполне может векторизовать такой код, заменяя бранчи на другие инструкции, дающие такой же результат. То есть его разработчики подумали о том, как использовать подходящие инструкции процессора для некоторых характерных паттернов исходного кода. Другое дело, что это срабатывает не всегда - тогда см. ответ рядом про профилировку.
vvdev
13.05.2026 09:35Векторизировать условное поэлементное копирование?
Я не так просто поинтересовался об изначальном примере. Там компилятору вообще нечего решать, кроме как счётчик заменить на обратный (думаю, что многие компиляторы так и делают, JIT .NETa - точно) и, возможно, цикл развернуть - всё остальное до самого времени исполнения неясно.
То есть, здесь только разработчик может знать, что значения. к примеру, отсортированы - и тогда нужен ИФ с ранним выходом, или "почти отсортированы", и тогда код как в примере будет оптимальным, или вообще непредсказуемые, и тогда нужен оптимизированный вариант из примера.
Тут только JIT PGO мог бы по ходу дела переписывать асм, вопрос - не было бы это дороже, чем прогонять цикл как написано.А так-то да, "его разработчики подумали" о многом. иной раз читаешь релиз ноутс и диву даёшься. Но всего на их уровне не придумаешь.
unreal_undead2
13.05.2026 09:35Векторизировать условное поэлементное копирование?
Именно так. Загрузили вектор в регистр, одной инструкцией сравниваем значения с заранее подговленным вектором с размноженной константой, другой копируем подходящие в выходной массив (подряд).
только разработчик может знать, что значения. к примеру, отсортированы
Понятно, что про входные данные компилятор не знает.
vvdev
13.05.2026 09:35Именно так. Загрузили вектор в регистр, одной инструкцией сравниваем значения с заранее подговленным вектором с размноженной константой, другой копируем подходящие в выходной массив (подряд).
Можно по-подробнее, псевдокод?
unreal_undead2
13.05.2026 09:35Уже кидал ссылку на годболт, вот основные инструкции
vmovdqu ymm1, ymmword ptr [rdi + 4*r9] vpcmpgtd k1, ymm0, ymm1 // ymm0 - размноженная константа vpcompressd ymmword ptr [rsi + 4*rdx] {k1}, ymm1vvdev
13.05.2026 09:35vpcompressdДа, пропустил, спасибо за науку.
Жаль, что нарочно на такое .NET JIT (пока) не спровоцировать, мне бы пригодилось кое-где.
unreal_undead2
13.05.2026 09:35Только небольшой нюанс - на клиентских процессорах (десктопы, ноутбуки) её либо нет либо выигрыша в производительности не даст.
AndreyDmitriev
13.05.2026 09:35но
vpcompressd— это вроде AVX512, если я туда, куда надо смотрю. Но и на чистом AVX2 можно тоже сделать, что б восемь значений за итерацию, там через свою LUT можно выкрутиться, вроде.unreal_undead2
13.05.2026 09:35Да, меня в основном серверные процессоры интересуют, там либо AVX512, либо SVE на ARM с похожей инструкцией COMPACT.
Medeyko
13.05.2026 09:35Вопрос же не в этом! Вопрос в том, что здесь очень значительная зависимость от неизвестных данных.
Ну, а так, естественно, вдумчиво оптимизировать нужно с профайлером и, соответственно, горячие пути.
Но и это будет всё больше автоматизироваться с применением нейросетей, я уверен. Типа AlphaDev, но в более общем виде.
unreal_undead2
13.05.2026 09:35Не факт, что пишущий подобный код программист сам знает что-то о данных (скажем, если это библиотечная функция, вызываемая из тысяч мест). Если профилировка показала, что больше всего времени приходится на конкретный вызов и по коду верхнего уровня можно делать какие-то предположения - можно и написать кастомную версию.
unreal_undead2
13.05.2026 09:35Нереально при создании программы анализировать каждый маленький участок кода, и предсказывать как он будет исполняться в железе.
Не надо ничего предсказывать. После того, как написан работающий вариант программы, запускаем профилировщик, смотрим, какие проблемы со стороны железа испытывают наиболее часто исполняемые участки и думаем, что с ними делать.
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 соизволит.
navferty
Для C# набросал бенчмарк, вот результаты
Результаты
Код методов на C#
Так что да, тернарный оператор
var isSmall = num < 500 ? 1 : 0;действительно не будет использовать прыжки, вот asm код:Sixshaman
roudakov
Любопытно. Но работать будет только на Си? А на более сложных условиях эффект будет?
spirit1984
Вообще был один интересный вопрос на Stackoverflow - почему обработка с if отсортированного массива куда быстрей? И шикарный ответ.
Вкратце - если последовательность данных упорядочена, то предиктор процессора работает как по маслу в таких случаях. Фактически if убирают за вас.
Можно возразить "Так а если у меня неотсортированная последовательность?". Однако если мы говорим не про лабораторный эксперимент с использованием ГСЧ, как правило, эти последовательности не берутся из воздуха. Они хранятся в какой-нибудь базе и уже упорядочены.
vvdev
Далеко не всегда хранятся, далеко не всегда в базе, и даже если и упорядочены - далеко не всегда по тому критерию(ям), по которому(ым) у нас условие(я).