Современные CPU ненавидят непредсказуемые условные переходы. Если данные случайные, branch predictor постоянно ошибается, и процессор сбрасывает pipeline снова и снова.

Пример из статьи: фильтруем массив, оставляя элементы меньше 500.

Классический подход с if:

if (numbers[i] < 500) {
    small_numbers[j] = numbers[i];
    j += 1;
}

Результат на Apple M1: 0,329 сек за 1000 итераций.

Branchless версия — без ветвления, unconditional store + conditional increment:

small_numbers[j] = numbers[i];
j += (numbers[i] < 500);

Результат: 0.036 сек. Разница в 9 раз.

На ассемблере вместо условного b.gt (branch if greater) используется cinc на ARM или setle на x86 — инкрементируем индекс, только если условие выполнено. Никаких прыжков, pipeline работает на полную.

Почему компилятор не делает это сам? Он не знает природу данных. Если почти все элементы проходят фильтр, branch predictor почти всегда прав, и if версия быстрее. А unconditional write может быть небезопасен — например, если за границей буфера лежит чужая память.

Интересный нюанс: branch predictor имеет ограниченную «память». На массиве из 10K элементов gap исчезает, потому что CPU запоминает паттерн. На 100K — predictior переполняется, и branchless выигрывает снова.

Quicksort, кстати, идеально ложится на branchless: партиционирование вокруг pivot — это ровно та задача, где ветвление убивает производительность.

Полная статья: https://easylang.online/blog/branchless

@prog_stuff