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