При работе с современными 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 очень хорошо подходит для программирования без ветвлений, так как основная задача алгоритма заключается в разбиении данных перемещением всех элементов меньше опорного в одну сторону.