Подтвердить что ты не робот

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

Мне нужна программа для получения меньшего из двух чисел, и мне интересно, если использовать стандарт "если x меньше y" 

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 в сравнении с альтернативами вообще.

4b9b3361

ОТВЕТЫ

Ответ 1

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

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

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

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

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

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

Итак,

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

становится

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

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

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

Ответ 2

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

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

Ответ 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

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

Ответ 4

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

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

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

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

Ответ 5

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

В моем компиляторе (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

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

Ответ 6

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

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

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

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

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

Ясный и краткий.

Ответ 7

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

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

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

Ответ 8

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

Ответ 9

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

Настольные/серверные ЦП оптимизированы для конвейерной обработки. Во-вторых, теоретически быстрее, потому что CPU не имеет ветки и может использовать несколько ALU для оценки частей выражения параллельно. Для таких процессоров лучше использовать не ветвящийся код с промежуточными независимыми операциями. (Но даже это теперь отрицается современными "условными" инструкциями CPU, которые также позволяют сделать первый код без ветвей.)

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

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

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

Как бы то ни было на фронте ЦП, более полезно потратить время на создание многопоточного кода и возможности OpenCL.

Ответ 10

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

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

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

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

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

int bar = x;

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

Ответ 11

Почему low = a; в if и low = a; в else? И, почему 31? Если 31 имеет какое-либо отношение к размеру слова процессора, что делать, если код должен быть запущен на процессоре разного размера?

. Если... хороший способ выглядит более читаемым. Мне нравятся программы для чтения, как для компиляторов, так и для читателей.

Ответ 12

Результаты профиля с gcc -o foo -g -p -O0, Solaris 9 v240

 %Time Seconds Cumsecs  #Calls   msec/call  Name
  36.8    0.21    0.21 8424829      0.0000  foo2
  28.1    0.16    0.37       1    160.      main
  17.5    0.10    0.4716850667      0.0000  _mcount
  17.5    0.10    0.57 8424829      0.0000  foo1
   0.0    0.00    0.57       4      0.      atexit
   0.0    0.00    0.57       1      0.      _fpsetsticky
   0.0    0.00    0.57       1      0.      _exithandle
   0.0    0.00    0.57       1      0.      _profil
   0.0    0.00    0.57    1000      0.000   rand
   0.0    0.00    0.57       1      0.      exit

код:

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 = (a < b) ? a : b;
   return low;
}


int main()
{
    int low=0;
    int a=0;
    int b=0;
    int i=500;
    while (i--)
    {
       for(a=rand(), b=rand(); a; a--)
       {
           low=foo1(a,b,low);
           low=foo2(a,b,low);
       }        
    }
    return 0;
}

Основываясь на данных, в приведенной выше среде полная противоположность нескольким убеждениям, изложенным здесь, не была найдена. Обратите внимание на "в этой среде". Если конструкция была быстрее, чем тройная?: construct

Ответ 13

Я написал симулятор тройной логики не так давно, и этот вопрос был жизнеспособен мне, поскольку он напрямую влияет на скорость выполнения моего интерпретатора; Мне потребовалось как можно быстрее смоделировать тонны и тонны тройных логических ворот.

В двоичной кодированной тройной системе один трит упаковывается в два бита. Самый значительный бит означает отрицательный и наименее значимый, положительный. Случай "11" не должен происходить, но его нужно обрабатывать надлежащим образом и обрабатывать как 0.

Рассмотрим функцию inline int bct_decoder( unsigned bctData ), которая должна вернуть наш форматированный трит как регулярное целое число -1, 0 или 1; Как я заметил, существует 4 подхода: я назвал их "cond", "mod", "math" и "lut"; Давайте исследуем их

Сначала основываются на jz | jnz и jl | jb условных переходах, таким образом, cond. Его производительность не очень хороша, потому что полагается на предсказатель ветвления. И еще хуже - он меняется, потому что неизвестно, будет ли одна ветвь или две априори. И вот пример:

inline int bct_decoder_cond( unsigned bctData ) {
   unsigned lsB = bctData & 1;
   unsigned msB = bctData >> 1;
   return
       ( lsB == msB ) ? 0 : // most possible -> make zero fastest branch
       ( lsB > msB ) ? 1 : -1;
}

Это самая медленная версия, в худшем случае она может включать в себя 2 ветки, и это то, где двоичная логика терпит неудачу. На моем 3770k он производит около 200MIPS в среднем по случайным данным. (здесь и после - каждый тест является средним от 1000 попыток на случайно заполненном наборе данных 2mb)

Далее опирается на оператор modulo, и его скорость находится где-то между первым и третьим, но определенно быстрее - 600 MIPS:

inline int bct_decoder_mod( unsigned bctData ) {
    return ( int )( ( bctData + 1 ) % 3 ) - 1;
}

Следующий - это разветвленный подход, который включает только математику, таким образом математику; он вообще не предполагает скачкообразных прыжков:

inline int bct_decoder_math( unsigned bctData ) {
    return ( int )( bctData & 1 ) - ( int )( bctData >> 1 );
}

Это делает то, что должно, и ведет себя действительно здорово. Для сравнения, оценка производительности составляет 1000 MIPS, и она в 5 раз быстрее, чем разветвленная версия. Вероятно, разветвленная версия замедляется из-за отсутствия встроенной 2-битной подписанной поддержки int. Но в моем приложении это довольно хорошая версия сама по себе.

Если этого недостаточно, мы можем пойти дальше, имея что-то особенное. Далее вызывается подход к поисковой таблице:

inline int bct_decoder_lut( unsigned bctData ) {
    static const int decoderLUT[] = { 0, 1, -1, 0 };
    return decoderLUT[ bctData & 0x3 ];
}

В моем случае один trit занимал только 2 бита, поэтому таблица lut была только 2b * 4 = 8 байтов, и стоило попробовать. Он подходит в кеше и работает быстро в 1400-1600 MIPS, здесь моя точность измерения снижается. И это 1.5x ускорение от быстрого математического подхода. Это потому, что вы просто предварительно рассчитали результат и одну инструкцию AND. К сожалению, кэши малы и (если длина вашего индекса больше нескольких бит), вы просто не можете его использовать.

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

Ответ 14

Если вы действительно не пытаетесь сэкономить на эффективности, я не думаю, что это то, о чем вам нужно беспокоиться.

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

Ответ 15

Если это для Gnu С++, попробуйте это

int min = i <? j;

Я не профилировал его, но я думаю, что он определенно победит.