Я бы хотел предложить сообществу поучаствовать в пробном эксперименте. Суть его состоит в том, чтобы прогнать на своём компьютере программу, написанную на C++, и поделиться результатом измерения времени, которое она выдаёт, сравнивая скорость работы функций sign(x), abs(x), min(a,b) и max(a,b) в исполнении с ветвлением и без него. В статье я объясню свою мотивацию, покажу сами функции, а в конце предложу условия участия в эксперименте и его (увы) ограничения.

Мотивация

Среди программистов, особенно тех, кто учился программировать где-то в конце 90-х, до сих пор живо стойкое убеждение, что алгоритм без ветвлений лучше, чем алгоритм с ветвлениями. Я нередко встречал чрезвычайную фанатичность в попытках реализовать ряд простых функций без ветвлений только из-за того, что программисту кажется, будто так будет эффективнее. Среди таких простых функций я особо выделил пока четыре: знак числа, абсолютное значение числа, минимум и максимум (в двух вариантах: для чисел со знаком и без знака). Если мой эксперимент окажется удачным, я возьмусь и за многие другие алгоритмы.

Правда, что без IF быстрее?

Нет, это неправда. Если быть более точным, то избавление от ветвлений может как дать прирост скорости, так и усугубить ситуацию в несколько раз. Всё зависит от конкретной машины, на которой данный код будет исполняться, и от компилятора. Приведу в качестве примера свой старый компьютер Core 2 Duo E8400 @3ГГц – на нём все предложенные функции работают быстрее в варианте с IF. Компилятор у меня VC++ 2015, опция компиляции /Ox.

Давайте рассмотрим чуть подробнее те функции, что я предлагаю протестировать. Каждая из четырёх функций может быть написана полудюжиной вариантов, все из которых Вы можете изучить самостоятельно по ссылкам [1-7] в конце статьи. Все эти варианты я уже тестировал и выбрал для каждой функции два: классический и какой-либо без ветвлений (наилучший по моим измерениям). Если, опять же, мой эксперимент окажется удачным, я проведу похожее сравнение вообще всех известных мне вариантов [4-7].

Для начала я ввожу свои псевдонимы для типов данных и константу для сдвига:

typedef int32_t   i32; typedef uint32_t  u32; typedef int8_t    sign_t; const u32 SHIFT = 31;

Знак числа – sign

Классический вариант реализуется несложной схемой из условий:

sign_t sign0 (i32 a) {   if (a>0)  return +1;   if (a<0)  return -1;   return 0; }

Наилучший вариант без ветвлений выглядит следующим образом:

sign_t sign1 (i32 a) {   return (a >> SHIFT) | ((u32)(-a) >> SHIFT); }

Да, здесь используется знаковый сдвиг и то тот факт, что отрицательные числа кодируются дополнительным кодом. Поэтому здесь мы имеем важное ограничение нашего эксперимента: у Вас на машине должен быть знаковый сдвиг и дополнительный код.

На моём процессоре разница между этими двумя функциями весьма заметна. Я прогнал их на всех возможных числах из рабочего диапазона и первая сработала за 2,87 секунды, а вторая только за 3,97.

Абсолютное значение – abs

Здесь ситуация несколько лучше. Первая функция с IF, может выглядеть, например, вот так:

u32 abs0 (i32 a) {   if (a<0)  return -a;   return a; }

А без ветвления самый лучший (на мой взгляд) вариант имеет вид:

u32 abs1 (i32 a) {  const i32 b = a >> SHIFT;   return (a+b) ^ b; }

Время работы первой 2,29, а второй — 2,33. Можем считать эти скорости одинаковыми. Прошу обратить внимание: программист часто не знает, что компилятор может сам сделать код без ветвлений для abs, который будет по логике полностью совпадать со вторым вариантом [3]. Таким образом, если в программе есть IF, это не значит, что после компиляции ветвление останется.

Минимум и максимум со знаком — mini и maxi

Кому-то может показаться, что классический вариант таких функции будет выглядеть вот так:

i32 mini0 (i32 a, i32 b) {   return a<b ? a:b; } i32 maxi0 (i32 a, i32 b) {   return a>b ? a:b; }

На самом деле (и для меня это совершенно непонятно) вот такой вариант в полтора раза быстрее:

i32 mini0 (i32 a, i32 b) {   return a>b ? b:a; } i32 maxi0 (i32 a, i32 b) {   return a<b ? b:a; }

Я обнаружил это, когда сравнивал разные варианты реализации, но конкретного ответа так и не нашёл. Когда смотрел ассемблерный листинг, то обнаружил, что разница только в порядке сравнения (a сравниваем с b, или наоборот). Подозреваю, что всё дело в микроархитектуре процессора. Аналогично, я замечал уже, что команда inc ecx работает значительно медленнее, чем lea eax, [eax+1], что тоже непонятно как можно объяснить, если не кривизной микроархитектуры.

Вариант без ветвлений для функций минимума и максимума в моём репертуаре только один (который корректно работает для всех возможных входных данных):

i32 mini1 (i32 a, i32 b) {   i32 d = a-b;   return a - (d&(~(d^((a^b)&(d^a))) >> SHIFT)); } i32 maxi1 (i32 a, i32 b) {   i32 d = a-b;   return b + (d&(~(d^((a^b)&(d^a))) >> SHIFT)); }

Здесь разница колоссальная. Первая серия функций работает около 3,5 секунд, вторая – около 9.

Дело в том, что в архитектуре x86 существует команда cmovl, которая как раз позволяет компилятору создать в первом случае код без ветвлений. Таким образом, получается, что на языке Си у нас ветвление есть, а реально его нет. Программист, который любой ценой хочет избавиться от ветвлений, не всегда знает, что компилятор может сделать это лучше него, если посчитает нужным.

Минимум и максимум без знака — minu и maxu

Классический вариант не меняется, кроме замены i32 на u32:

u32 minu0 (u32 a, u32 b) {   return a>b ? b:a; } u32 maxu0 (u32 a, u32 b) {   return a<b ? b:a; }

Вариант без ветвлений будет основан на другой страшной формуле:

u32 minu1 (u32 a, u32 b) {   u32 d = a-b;   return a - (d&~(int((~a&b)|(~(a^b)&d)) >> SHIFT)); } u32 maxu1 (u32 a, u32 b) {   u32 d = a-b;   return b + (d&~(int((~a&b)|(~(a^b)&d)) >> SHIFT)); }

Разница по скорости ещё больше: если первый вариант работает всё так же 3,5 секунд, то второй уже 9,5.

Суть и правила эксперимента

Я предлагаю читателям сами проверить на своих машинах то, каков будет результат сравнения. С этой целью была написана программа (GitHub). Её нужно скомпилировать и запустить. Работать она может долго, возможно, несколько минут, имейте терпение. Прошу обязательно отключить остальные ресурсоёмкие приложения на компьютере, когда запускаете эту программу.

Отработав, она выдаст в STDOUT таблицу

 sign: 2.87 vs 3.97  abs: 2.29 vs 2.33 mini: 3.46 vs 8.93 maxi: 3.45 vs 9.10 minu: 3.45 vs 9.46 maxu: 3.45 vs 9.81

В первой колонке время работы функций с IF, а во второй – без ветвлений. В STDERR будет выведено число, не обращайте на него внимания, оно для правильного понимания компилятором циклов в программе.

Я прошу сделать следующее: вот эту табличку вместе с характеристиками своего процессора и названием компилятора (а также с опциями компиляции, если они имеют смысл) написать в качестве ответа к первому комментарию, который я сделаю. И других ответов именно к этому комментарию прошу не давать, чтобы не замусорить эксперимент.

Сразу хочу предупредить о возможных неудачах Вашего эксперимента, за которые я прошу меня простить, но я ничего не могу с этим поделать, как не старался.

Программа не скомпилируется. Это возможно, так как не все компиляторы понимают std::chrono. Ещё, возможно, я где-то вышел за пределы Стандарта языка С++. Гарантирую только, что код компилируется в Visual C++ 2015 и GCC 4.8.1 (из MinGW) в OS Windows 7 (64). Компилировал я именно 32-битовый код. Я пытался спросить у грамотных людей на SO, как сделать программу лучше, но пока не получил ответа.
У Вас на машине нет знакового сдвига или отрицательные числа имеют представление не в дополнительном коде — тогда все функции будут работать неправильно.
Программа будет работать не так, как должна. Это возможно. Я впервые использую chrono и мог ошибиться. До этого всегда измерял время через утилиту runexe, а в этой программе мне нужен универсальный способ, который работал бы у большинства пользователей.

Итак, давайте вместе выясним, существует ли хоть один случай, в котором вариант без ветвлений будет заметно лучше варианта с IF.

Список источников

ссылка на оригинал статьи https://habrahabr.ru/post/281629/

Так ли нужно избавляться от ветвлений? — На примере sign, abs, min и max