Я бы хотел предложить сообществу поучаствовать в пробном эксперименте. Суть его состоит в том, чтобы прогнать на своём компьютере программу, написанную на C++, и поделиться результатом измерения времени, которое она выдаёт, сравнивая скорость работы функций sign(x), abs(x), min(a,b) и max(a,b) в исполнении с ветвлением и без него. В статье я объясню свою мотивацию, покажу сами функции, а в конце предложу условия участия в эксперименте и его (увы) ограничения.
Среди программистов, особенно тех, кто учился программировать где-то в конце 90-х, до сих пор живо стойкое убеждение, что алгоритм без ветвлений лучше, чем алгоритм с ветвлениями. Я нередко встречал чрезвычайную фанатичность в попытках реализовать ряд простых функций без ветвлений только из-за того, что программисту кажется, будто так будет эффективнее. Среди таких простых функций я особо выделил пока четыре: знак числа, абсолютное значение числа, минимум и максимум (в двух вариантах: для чисел со знаком и без знака). Если мой эксперимент окажется удачным, я возьмусь и за многие другие алгоритмы.
Нет, это неправда. Если быть более точным, то избавление от ветвлений может как дать прирост скорости, так и усугубить ситуацию в несколько раз. Всё зависит от конкретной машины, на которой данный код будет исполняться, и от компилятора. Приведу в качестве примера свой старый компьютер Core 2 Duo E8400 @3ГГц – на нём все предложенные функции работают быстрее в варианте с IF, когда данные подаются упорядоченно и ситуация может стать обратной при хаотичной подаче (подробности ниже). Компилятор у меня VC++ 2015, опция компиляции /Ox.
Давайте рассмотрим чуть подробнее те функции, что я предлагаю протестировать. Каждая из четырёх функций может быть написана полудюжиной вариантов, все из которых Вы можете изучить самостоятельно по ссылкам [1-7] в конце статьи. Все эти варианты я уже тестировал и выбрал для каждой функции два: классический и какой-либо без ветвлений (наилучший по моим измерениям). Если, опять же, мой эксперимент окажется удачным, я проведу похожее сравнение вообще всех известных мне вариантов [4-7].
Для начала я ввожу свои псевдонимы для типов данных и константу для сдвига:
Классический вариант реализуется несложной схемой из условий:
Наилучший вариант без ветвлений выглядит следующим образом:
Да, здесь используется знаковый сдвиг и то тот факт, что отрицательные числа кодируются дополнительным кодом. Поэтому здесь мы имеем важное ограничение нашего эксперимента: у Вас на машине должен быть знаковый сдвиг и дополнительный код.
На моём процессоре разница между этими двумя функциями весьма заметна. Я прогнал их на всех возможных числах из рабочего диапазона и первая сработала за 2,87 секунды, а вторая только за 3,97 при упорядоченной подаче чисел и 13,02 vs 1,26 при хаотичной.
Здесь ситуация несколько лучше. Первая функция с IF, может выглядеть, например, вот так:
А без ветвления самый лучший (на мой взгляд) вариант имеет вид:
Время работы первой 2,29, а второй — 2,33 при упорядоченной подаче и 12,01 vs 0,81 при хаотичной. Прошу обратить внимание: программист часто не знает, что компилятор может сам сделать код без ветвлений для abs, который будет по логике полностью совпадать со вторым вариантом [3]. Таким образом, если в программе есть IF, это не значит, что после компиляции ветвление останется. Мой компилятор генерирует код с ветвлением.
Кому-то может показаться, что классический вариант таких функции будет выглядеть вот так:
На самом деле (и для меня это совершенно непонятно) вот такой вариант в полтора раза быстрее:
Я обнаружил это, когда сравнивал разные варианты реализации, но конкретного ответа так и не нашёл. Когда смотрел ассемблерный листинг, то обнаружил, что разница только в порядке сравнения (a сравниваем с b, или наоборот). Подозреваю, что всё дело в микроархитектуре процессора. Аналогично, я замечал уже, что команда inc ecx работает значительно медленнее, чем lea eax, [eax+1], что тоже непонятно как можно объяснить, если не кривизной микроархитектуры.
Вариант без ветвлений для функций минимума и максимума в моём репертуаре только один (который корректно работает для всех возможных входных данных):
Здесь разница колоссальная. Первая серия функций работает около 3,5 секунд, вторая – около 9 на последовательных данных и 2 секунды vs 6 секунд на хаотичных. Разница почти втрое в обоих случаях.
Дело в том, что в архитектуре x86 существует команда cmovl, которая как раз позволяет компилятору создать в первом случае код без ветвлений. Таким образом, получается, что на языке Си у нас ветвление есть, а реально его нет. Программист, который любой ценой хочет избавиться от ветвлений, не всегда знает, что компилятор может сделать это лучше него, если посчитает нужным.
Классический вариант не меняется, кроме замены i32 на u32:
Вариант без ветвлений будет основан на другой страшной формуле:
Разница по скорости ещё больше: если первый вариант работает всё так же 3,5 секунд, то второй уже 9,5 на последовательных данных и примерно 2 секунды против 6 на хаотичных.
Я предлагаю читателям сами проверить на своих машинах то, каков будет результат сравнения. С этой целью была написана программа (GitHub) (с учётом замечаний meduzik и ivas, даю исправленную программу — тестируем обе. В одной данные подаются последовательно, во второй — хаотично). Её нужно скомпилировать и запустить. Работать она может долго, возможно, несколько минут, имейте терпение. Прошу обязательно отключить остальные ресурсоёмкие приложения на компьютере, когда запускаете эту программу.
Отработав, она выдаст в STDOUT таблицу (последовательная подача данных)
В первой колонке время работы функций с IF, а во второй – без ветвлений. В STDERR будет выведено число, не обращайте на него внимания, оно для правильного понимания компилятором циклов в программе.
Аналогичная таблица для хаотичной подачи:
Я прошу сделать следующее: вот эти таблички вместе с характеристиками своего процессора и названием компилятора (а также с опциями компиляции, если они имеют смысл) написать в качестве ответа к первому комментарию, который я сделаю. И других ответов именно к этому комментарию прошу не давать, чтобы не замусорить эксперимент.
Сразу хочу предупредить о возможных неудачах Вашего эксперимента, за которые я прошу меня простить, но я ничего не могу с этим поделать, как не старался.
Итак, давайте вместе выясним, что в каких случаях лучше и на каком процессоре.
Благодарю meduzik и ivas, за то, что напомнили мне про хаотичную подачу данных, о которой я случайно забыл.
Мотивация
Среди программистов, особенно тех, кто учился программировать где-то в конце 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, за то, что напомнили мне про хаотичную подачу данных, о которой я случайно забыл.
