Gcc оптимизирует мой цикл с условием?

Question

У меня следующий цикл:

//condition will be set here to true or false

for (int i = 0; i < LARGE_NUMBER; i++) {
    if (condition) {
        //do foo
    } else {
        //do bar
    }
}

Предположение: цикл, если быстрее без условия, чем с условием. (Это правда?) Вопрос: Изменит ли gcc мой if, если condition было установлено вне цикла for, а сам цикл не касается condition?

Если нет, я должен поменять if и for, дублировать код, нарушить DRY и т. Д.

Answer 1

Для тех, кто не хочет читать длинный пост, эта оптимизация называется (в LLVM) Loop Unswitch .

Почему бы не спросить компилятор?

void foo(char* c);

int main(int argc, char **argv) {
  bool const condition = argc % 2;

  for (int i = 0; i != argc; ++i) {
    if (condition) {
      foo(argv[1]);
    } else {
      foo(argv[0]);
    }
  }
  return 0; 
}

Преобразуется в форму SSA (через LLVM try ):

define i32 @main(i32 %argc, i8** nocapture %argv) {
entry:
  %0 = icmp eq i32 %argc, 0                       ; <i1> [#uses=1]
  br i1 %0, label %bb5, label %bb.nph

bb.nph:                                           ; preds = %entry
  %1 = and i32 %argc, 1                           ; <i32> [#uses=1]
  %toBool = icmp eq i32 %1, 0                     ; <i1> [#uses=1]
  %2 = getelementptr inbounds i8** %argv, i64 1   ; <i8**> [#uses=1]
  br i1 %toBool, label %bb3.us, label %bb3

bb3.us:                                           ; preds = %bb3.us, %bb.nph
  %i.07.us = phi i32 [ %4, %bb3.us ], [ 0, %bb.nph ] ; <i32> [#uses=1]
  %3 = load i8** %argv, align 8                   ; <i8*> [#uses=1]
  tail call void @_Z3fooPc(i8* %3)
  %4 = add nsw i32 %i.07.us, 1                    ; <i32> [#uses=2]
  %exitcond = icmp eq i32 %4, %argc               ; <i1> [#uses=1]
  br i1 %exitcond, label %bb5, label %bb3.us

bb3:                                              ; preds = %bb3, %bb.nph
  %i.07 = phi i32 [ %6, %bb3 ], [ 0, %bb.nph ]    ; <i32> [#uses=1]
  %5 = load i8** %2, align 8                      ; <i8*> [#uses=1]
  tail call void @_Z3fooPc(i8* %5)
  %6 = add nsw i32 %i.07, 1                       ; <i32> [#uses=2]
  %exitcond8 = icmp eq i32 %6, %argc              ; <i1> [#uses=1]
  br i1 %exitcond8, label %bb5, label %bb3

bb5:                                              ; preds = %bb3, %bb3.us, %entry
  ret i32 0
}

Возможно, не слишком читабельно, поэтому позвольте мне указать, что здесь:

• entry: проверить, равен ли argc 0, если это так, перейти к bb5 (выход), иначе перейти к bb.nph
• bb.nph: вычислить значение condition, если это правда, перейдите к bb3.us, иначе перейдите к bb3
• bb3.us и bb3: циклы для условий истинного и ложного соответственно
• bb5:exit

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

int main(int argc, char**argv) {
  if (argc != 0)
  {
    int i = 0;
    if (argc % 2) {
      do {
        foo(argv[1]);
        ++i;
      } while (i != argc);
    } else {
      do {
        foo(argv[0]);
        ++i;
      } while (i != argc);
    }
  }
  return 0;
}

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

Для тех из нас, кто думает, что первое решение более понятно, мы очень рады, что компилятор проводит для нас тщательную оптимизацию!

Answer 2

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

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

Answer 3

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

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

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

Так что я сомневаюсь, что даже с «тупым» компилятором вы действительно увидите разницу между этими двумя опциямиПо крайней мере, на современных машинах.