Я бы хотел предложить сообществу поучаствовать в пробном эксперименте. Суть его состоит в том, чтобы прогнать на своём компьютере программу, написанную на 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 при упорядоченной подаче чисел и 13,02 vs 1,26 при хаотичной.
Абсолютное значение – 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 при упорядоченной подаче и 12,01 vs 0,81 при хаотичной. Прошу обратить внимание: программист часто не знает, что компилятор может сам сделать код без ветвлений для 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 на последовательных данных и 2 секунды vs 6 секунд на хаотичных. Разница почти втрое в обоих случаях.
Дело в том, что в архитектуре 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 на последовательных данных и примерно 2 секунды против 6 на хаотичных.
Суть и правила эксперимента
Я предлагаю читателям сами проверить на своих машинах то, каков будет результат сравнения. С этой целью была написана программа (GitHub) (с учётом замечаний meduzik и ivas, даю исправленную программу — тестируем обе. В одной данные подаются последовательно, во второй — хаотично). Её нужно скомпилировать и запустить. Работать она может долго, возможно, несколько минут, имейте терпение. Прошу обязательно отключить остальные ресурсоёмкие приложения на компьютере, когда запускаете эту программу.
Отработав, она выдаст в 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 будет выведено число, не обращайте на него внимания, оно для правильного понимания компилятором циклов в программе.
Аналогичная таблица для хаотичной подачи:
sign: 13.02 vs 1.26 abs: 12.01 vs 0.81 mini: 1.89 vs 5.97 maxi: 1.93 vs 6.31 minu: 1.89 vs 6.44 maxu: 1.92 vs 6.70
Я прошу сделать следующее: вот эти таблички вместе с характеристиками своего процессора и названием компилятора (а также с опциями компиляции, если они имеют смысл) написать в качестве ответа к первому комментарию, который я сделаю. И других ответов именно к этому комментарию прошу не давать, чтобы не замусорить эксперимент.
Сразу хочу предупредить о возможных неудачах Вашего эксперимента, за которые я прошу меня простить, но я ничего не могу с этим поделать, как не старался.
- Программа не скомпилируется. Это возможно, так как не все компиляторы понимают std::chrono. Ещё, возможно, я где-то вышел за пределы Стандарта языка С++. Гарантирую только, что код компилируется в Visual C++ 2015 и GCC 4.8.1 (из MinGW) в OS Windows 7 (64). Компилировал я именно 32-битовый код. Я пытался спросить у грамотных людей на SO, как сделать программу лучше, но пока не получил ответа.
- У Вас на машине нет знакового сдвига или отрицательные числа имеют представление не в дополнительном коде — тогда все функции будут работать неправильно.
- Программа будет работать не так, как должна. Это возможно. Я впервые использую chrono и мог ошибиться. До этого всегда измерял время через утилиту runexe, а в этой программе мне нужен универсальный способ, который работал бы у большинства пользователей.
Итак, давайте вместе выясним, что в каких случаях лучше и на каком процессоре.
Список источников
- Hacker's Delight
- Bit Twiddling Hacks
- Optimized abs function
- Функция sign(x) — определение знака переменной
- Функция abs(x) — абсолютное значение числа
- Функции min(a,b) и max(a,b) для чисел со знаком
- Функции min(a,b) и max(a,b) для чисел без знака
Благодарности
Благодарю meduzik и ivas, за то, что напомнили мне про хаотичную подачу данных, о которой я случайно забыл.
Автор: Zealint
