Разница в скорости между If-Else и троичным оператором в C ...?

Question

Итак, по предложению коллеги, я только что проверил разницу в скорости между троичным оператором и эквивалентным блоком If-Else ... и кажется, что троичный оператор выдает код, который в 1–2 раза быстрее, чем If- Else. Мой код:

  gettimeofday(&tv3, 0);
  for(i = 0; i < N; i++)
  {
     a = i & 1;
     if(a) a = b; else a = c;
  }
  gettimeofday(&tv4, 0);


  gettimeofday(&tv1, 0);
  for(i = 0; i < N; i++)
  {
     a = i & 1;
     a = a ? b : c;
  }
  gettimeofday(&tv2, 0);

(Извините за использование gettimeofday, а не clock_gettime ... Я постараюсь улучшить себя.)

Я попытался изменить порядок, в котором я рассчитывал блоки, но результаты, кажется, сохраняются. Что дает? Кроме того, If-Else демонстрирует гораздо большую изменчивость с точки зрения скорости выполнения. Должен ли я проверять сборку, создаваемую gcc?

Кстати, это все на нулевом уровне оптимизации (-O0).

Я воображаю это, или я что-то не принимаю во внимание, или это машинно-зависимая вещь, или что? Любая помощь приветствуется.

Answer 1

Есть хороший шанс, что троичный оператор будет скомпилирован в cmov, тогда как if / else приведет к cmp + jmp. Просто посмотрите на сборку (используя -S), чтобы быть уверенным. С включенными оптимизациями это больше не будет иметь значения, так как любой хороший компилятор должен генерировать один и тот же код в обоих случаях.

Answer 2

Вы могли бы также пойти полностью без ответвлений и измерить, если это имеет какое-либо значение:

int m = -(i & 1);
a = (b & m) | (c & ~m);

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

Answer 3

Это хорошее объяснение: http://www.nynaeve.net/?p=178

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

Answer 4

Если таковые имеются, измените свой компилятор!

Для вопросов такого рода я использую страницу Try Out LLVM .Это старая версия LLVM (все еще использующая интерфейс gcc), но это старые приемы.

Вот мой маленький пример программы (ваша упрощенная версия):

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

int main (int argc, char* argv[]) {
  int N = atoi(argv[0]);

  int a = 0, d = 0, b = atoi(argv[1]), c = atoi(argv[2]);

  int i;
  for(i = 0; i < N; i++)
  {
     a = i & 1;
     if(a) a = b+i; else a = c+i;
  }

  for(i = 0; i < N; i++)
  {
     d = i & 1;
     d = d ? b+i : c+i;
  }

  printf("%d %d", a, d);

  return 0;
}

И есть соответствующий сгенерированный IR LLVM:

define i32 @main(i32 %argc, i8** nocapture %argv) nounwind {
entry:
  %0 = load i8** %argv, align 8                   ; <i8*> [#uses=1]
  %N = tail call i32 @atoi(i8* %0) nounwind readonly ; <i32> [#uses=5]

  %2 = getelementptr inbounds i8** %argv, i64 1   ; <i8**> [#uses=1]
  %3 = load i8** %2, align 8                      ; <i8*> [#uses=1]
  %b = tail call i32 @atoi(i8* %3) nounwind readonly ; <i32> [#uses=2]

  %5 = getelementptr inbounds i8** %argv, i64 2   ; <i8**> [#uses=1]
  %6 = load i8** %5, align 8                      ; <i8*> [#uses=1]
  %c = tail call i32 @atoi(i8* %6) nounwind readonly ; <i32> [#uses=2]

  %8 = icmp sgt i32 %N, 0                         ; <i1> [#uses=2]
  br i1 %8, label %bb, label %bb11

bb:                                               ; preds = %bb, %entry
  %9 = phi i32 [ %10, %bb ], [ 0, %entry ]        ; <i32> [#uses=2]
  %10 = add nsw i32 %9, 1                         ; <i32> [#uses=2]
  %exitcond22 = icmp eq i32 %10, %N               ; <i1> [#uses=1]
  br i1 %exitcond22, label %bb10.preheader, label %bb

bb10.preheader:                                   ; preds = %bb
  %11 = and i32 %9, 1                             ; <i32> [#uses=1]
  %12 = icmp eq i32 %11, 0                        ; <i1> [#uses=1]
  %.pn13 = select i1 %12, i32 %c, i32 %b          ; <i32> [#uses=1]
  %tmp21 = add i32 %N, -1                         ; <i32> [#uses=1]
  %a.1 = add i32 %.pn13, %tmp21                   ; <i32> [#uses=2]
  br i1 %8, label %bb6, label %bb11

bb6:                                              ; preds = %bb6, %bb10.preheader
  %13 = phi i32 [ %14, %bb6 ], [ 0, %bb10.preheader ] ; <i32> [#uses=2]
  %14 = add nsw i32 %13, 1                        ; <i32> [#uses=2]
  %exitcond = icmp eq i32 %14, %N                 ; <i1> [#uses=1]
  br i1 %exitcond, label %bb10.bb11_crit_edge, label %bb6

bb10.bb11_crit_edge:                              ; preds = %bb6
  %15 = and i32 %13, 1                            ; <i32> [#uses=1]
  %16 = icmp eq i32 %15, 0                        ; <i1> [#uses=1]
  %.pn = select i1 %16, i32 %c, i32 %b            ; <i32> [#uses=1]
  %tmp = add i32 %N, -1                           ; <i32> [#uses=1]
  %d.1 = add i32 %.pn, %tmp                       ; <i32> [#uses=1]
  br label %bb11

bb11:                                             ; preds = %bb10.bb11_crit_edge, %bb10.preheader, %entry
  %a.0 = phi i32 [ %a.1, %bb10.bb11_crit_edge ], [ %a.1, %bb10.preheader ], [ 0, %entry ] ; <i32> [#uses=1]
  %d.0 = phi i32 [ %d.1, %bb10.bb11_crit_edge ], [ 0, %bb10.preheader ], [ 0, %entry ] ; <i32> [#uses=1]
  %17 = tail call i32 (i8*, ...)* @printf(i8* noalias getelementptr inbounds ([6 x i8]* @.str, i64 0, i64 0), i32 %a.0, i32 %d.0) nounwind ; <i32> [#uses=0]
  ret i32 0
}

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

Важными битами являются эти два блока:

  %.pn13 = select i1 %12, i32 %c, i32 %b          ; <i32> [#uses=1]
  %tmp21 = add i32 %N, -1                         ; <i32> [#uses=1]
  %a.1 = add i32 %.pn13, %tmp21                   ; <i32> [#uses=2]

  %.pn = select i1 %16, i32 %c, i32 %b            ; <i32> [#uses=1]
  %tmp = add i32 %N, -1                           ; <i32> [#uses=1]
  %d.1 = add i32 %.pn, %tmp                       ; <i32> [#uses=1]

Которые соответственно устанавливают a и d.

И вывод такой: Без разницы

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

Answer 5

Поймите, что компилятору полностью следует, как он интерпретирует троичное выражение (если вы на самом деле не заставляете его использовать (inline) asm).Он может так же легко понять троичное выражение, как и «if..else» на своем языке внутреннего представления, и в зависимости от целевого бэкэнда он может выбрать генерацию инструкции условного перемещения (на x86 CMOVcc такой. Должны также бытьдля мин / макс, абс и т. д.).Основной мотивацией использования условного перемещения является перенос риска ошибочного прогнозирования ветвления в операцию перемещения памяти / регистра.Предостережение к этой инструкции заключается в том, что почти все время регистр операнда, который будет загружен по условию, должен быть оценен до формы регистра, чтобы воспользоваться командой cmov.

Это означает, что процесс безусловной оценкиТеперь должно быть безусловным, и это будет увеличивать длину безусловного пути программы.Но следует понимать, что ошибочный прогноз ветвления чаще всего разрешается как «очистка» конвейера, что означает, что инструкции, которые должны были бы завершиться, игнорируются (переключаются на инструкции без операций).Это означает, что фактическое количество выполняемых команд выше из-за остановок или NOP, а эффект масштабируется с глубиной конвейера процессора и уровнем неправильного прогнозирования.

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

Это, возможно, основные причины, по которым компиляторам трудно использовать команду cmov, поскольку определение эвристики в значительной степени зависит от информации о профилировании во время выполнения.Более разумно использовать это на JIT-компиляторе, поскольку он может обеспечить обратную связь с инструментарием во время выполнения и создать более сильную эвристику для использования этого («Действительно ли ветка непредсказуема?»).На стороне статического компилятора без обучающих данных или профилировщика наиболее трудно предположить, когда это будет полезно.Тем не менее, простая отрицательная эвристика, как упоминалось выше, если компилятор знает, что набор данных является полностью случайным или форсирует cond.в секунду.оценка является дорогостоящей (возможно, из-за неснижаемых, дорогостоящих операций, таких как деление fp), она не будет делать хороших эвристик.

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

Answer 6

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