Насколько эффективен оператор if по сравнению с тестом, который не использует if? (C ++)

Question

Мне нужна программа, чтобы получить меньшее из двух чисел, и мне интересно, если использовать стандартное «если х меньше, чем у»

int a, b, low;
if (a < b) low = a;
else low = b;

более или менее эффективно, чем это:

int a, b, low;
low = b + ((a - b) & ((a - b) >> 31));

(или вариант размещения int delta = a - b сверху и перестановки экземпляров a - b с этим).

Мне просто интересно, какой из них был бы более эффективным (или если разница слишком мала, чтобы быть релевантной), и эффективность операторов if-else по сравнению с альтернативами в целом.

Answer 1

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

Одним из преимуществ исключения оператора if является то, что вы избегаете штрафов за предсказание ветвлений.

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

a = random() % 10
if (a < 5)
  print "Less"
else
  print "Greater"

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

Одним из способов избежать такого рода штрафов является использование троичного (?:) оператора. В простых случаях компилятор будет генерировать инструкции условного перемещения, а не ветви.

So

int a, b, low;
if (a < b) low = a;
else low = b;

становится

int a, b, low;
low = (a < b) ? a : b

и во втором случае инструкция ветвления не требуется. Кроме того, он намного понятнее и удобочитаемее, чем ваша реализация с переворотом.

Конечно, это микрооптимизация, которая вряд ли окажет значительное влияние на ваш код.

Answer 2

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

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

Answer 3

Компиляция на gcc 4.3.4, amd64 (core 2 duo), Linux:

int foo1(int a, int b)
{
    int low;
    if (a < b) low = a;
    else low = b;
    return low;
}

int foo2(int a, int b)
{
    int low;
    low = b + ((a - b) & ((a - b) >> 31));
    return low;
}

Я получаю:

foo1:
    cmpl    %edi, %esi
    cmovle  %esi, %edi
    movl    %edi, %eax
    ret

foo2:
    subl    %esi, %edi
    movl    %edi, %eax
    sarl    $31,  %eax
    andl    %edi, %eax
    addl    %esi, %eax
    ret

... что, я уверен, не будет учитываться для предсказаний ветвлений, поскольку код не скачет. Кроме того, версия без оператора if на 2 инструкции длиннее. Я думаю, что я продолжу кодировать, и пусть компилятор сделает свое дело.

Answer 4

Как и при любой низкоуровневой оптимизации, протестируйте ее на целевой установке ЦП / платы.

На моем компиляторе (gcc 4.5.1 на x86_64) первым примером будет

cmpl    %ebx, %eax
cmovle  %eax, %esi

Второй пример становится

subl    %eax, %ebx
movl    %ebx, %edx
sarl    $31, %edx
andl    %ebx, %edx
leal    (%rdx,%rax), %esi

Не уверен, что первый вариант быстрее во всех случаях, но я бы поспорил, что это так.

Answer 5

Самая большая проблема заключается в том, что ваш второй пример не будет работать на 64-битных машинах .

Однако, даже если пренебречь этим, современные компиляторы достаточно умны, чтобы учитывать прогнозирование без ветвлений в каждомслучай возможен, и сравните предполагаемые скорости.Итак, ваш второй пример будет , скорее всего, на самом деле будет медленнее

Не будет никакой разницы между оператором if и использованием тернарного оператора, поскольку даже большинство тупых компиляторов достаточно умны, чтобы распознавать этот специальныйcase.

---

[Редактировать] Поскольку я думаю, что это такая интересная тема, я написал сообщение в блоге на нем.

Answer 6

Для чего-то столь же простого, как это, почему бы просто не поэкспериментировать и не попробовать?

Как правило, сначала нужно указать профиль, определить его как горячую точку, поэкспериментировать с изменением и просмотреть результат.

Я написал простую программу, которая сравнивает оба метода, передающих случайные числа (так что мы не видим идеальный прогноз ветвления), с Visual C ++ 2010. Разница между подходами на моей машине для 100 000 000 итераций?Всего менее 50 мс, и версия if имела тенденцию работать быстрее.Глядя на кодеген, компилятор успешно преобразовал простую инструкцию if в команду cmovl, полностью исключив переход.

Answer 7

В любом случае, сборка будет состоять только из нескольких инструкций, и в любом случае выполнение этих инструкций займет пикосекунды.

Я бы профилировал приложение, сконцентрировав ваши усилия по оптимизации на чем-то более стоящем.

Кроме того, время, сэкономленное этим типом оптимизации, не будет стоить времени, потраченного всеми, кто пытается его поддерживать.

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

low = (a < b) ? a : b;

Ясно и кратко.

Answer 8

Одна вещь, о которой следует опасаться, когда вы попадаете в действительно хрупкие виды хаков, - это как они могут взаимодействовать с оптимизацией компилятора, которая происходит после встраивания. Например, читаемая процедура

int foo (int a, int b) {
   return ((a < b) ? a : b);
}

В любом случае

может быть скомпилировано во что-то очень эффективное, но в некоторых случаях это может быть даже лучше. Предположим, например, что кто-то пишет

int bar = foo (x, x+3);

После встраивания компилятор распознает, что 3 является положительным, и затем может использовать тот факт, что переполнение со знаком не определено, чтобы полностью исключить тест, чтобы получить

int bar = x;

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

Answer 9

Мне просто интересно, какой из них будет более эффективным (или если разница в том, чтобы быть крошечным соответствующие), а также эффективность утверждения if-else против альтернатив в общем.

Настольные / серверные ЦП оптимизированы для конвейерной обработки. Второе теоретически быстрее, потому что ЦПУ не нужно разветвляться и может использовать несколько ALU для параллельной оценки частей выражения. Больше неразветвленного кода с смешанными независимыми операциями лучше для таких процессоров. (Но даже это теперь сводится на нет современными «условными» инструкциями процессора, которые позволяют сделать первый код также без ветвлений.)

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

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

Но в конце я бы сказал, что да, разница незначительна, чтобы иметь отношение. В долгосрочной перспективе читаемый код выигрывает.

То, как идут дела с процессором, теперь выгоднее тратить время на то, чтобы сделать код многопоточным и поддерживать OpenCL.

Answer 10

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