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

в 5:55, , рубрики: Алгоритмы, ветвления, оптимизация кода, Программирование, Спортивное программирование, эксперимент, метки:

Я бы хотел предложить сообществу поучаствовать в пробном эксперименте. Суть его состоит в том, чтобы прогнать на своём компьютере программу, написанную на 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

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

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

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

Итак, давайте вместе выясним, что в каких случаях лучше и на каком процессоре.

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

  1. Hacker's Delight
  2. Bit Twiddling Hacks
  3. Optimized abs function
  4. Функция sign(x) — определение знака переменной
  5. Функция abs(x) — абсолютное значение числа
  6. Функции min(a,b) и max(a,b) для чисел со знаком
  7. Функции min(a,b) и max(a,b) для чисел без знака

Благодарности

Благодарю meduzik и ivas, за то, что напомнили мне про хаотичную подачу данных, о которой я случайно забыл.

Автор: Zealint

Источник

Поделиться новостью

* - обязательные к заполнению поля