Насколько эффективен оператор 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

Обновлен ответ с учетом текущего (2018) состояния векторизации компилятора. Пожалуйста, смотрите ответ Данбена для общего случая, когда векторизация не имеет значения.

Сводка TLDR : избегание if s может помочь с векторизацией.

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

Используя предоставленный пример OP:

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

Многие компиляторы могут векторизовать это примерно так:

__m128i low128i(__m128i a, __m128i b){
  __m128i diff, tmp;
  diff = _mm_sub_epi32(a,b);
  tmp = _mm_srai_epi32(diff, 31);
  tmp = _mm_and_si128(tmp,diff);
  return _mm_add_epi32(tmp,b);
}

Эта оптимизация потребует, чтобы данные были размещены таким образом, чтобы это было возможно, но их можно расширить до __m256i с помощью avx2 или __m512i с помощью avx512 (и даже развернуть циклы, чтобы воспользоваться преимуществами дополнительных регистров) или другими Симд инструкции по другим архитектурам. Еще одним плюсом является то, что все эти инструкции являются командами с низкой задержкой и высокой пропускной способностью (задержки ~ 1 и взаимные пропускные способности в диапазоне от 0,33 до 0,5 - так очень быстро по сравнению с не векторизованным кодом)

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

void lowhi128i(__m128i *a, __m128i *b){ // does both low and high
  __m128i _a=*a, _b=*b;
  __m128i lomask =  _mm_cmpgt_epi32(_a,_b),
  __m128i himask =  _mm_cmpgt_epi32(_b,_a);
  _mm_maskmoveu_si128(_b,lomask,a);
  _mm_maskmoveu_si128(_a,himask,b);
}

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

Answer 2

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

В двоично-кодированной троичной системе один трит упакован в два бита.Наиболее значимый бит означает отрицательный, а наименее значимый - положительный.Случай "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 он дает в среднем около 200 МИПС на случайных данных.(здесь и после - каждый тест является средним из 1000 попыток для случайно заполненного набора данных 2 МБ)

Далее следует оператор по модулю, и его скорость находится где-то между первым и третьим, но определенно быстрее - 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 ];
}

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

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

Answer 3

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

int min = i <? j;

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

Answer 4

Результаты профиля

с 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;
}

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

Answer 5

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

Answer 6

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

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