Могут ли компиляторы С++ оптимизировать выражения "if" внутри циклов "for"?

Ответ 1

Да, если определено, что флаг не изменяется и не может быть изменен do_something или do_something_else, его можно вытащить за пределы цикла. Я слышал об этом названии петли, но в Википедии есть запись

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

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

На это может повлиять и ваша оптимизация - оптимизация для размера будет способствовать не-hoist версии, а оптимизация для скорости, вероятно, будет способствовать поднятой версии.

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

Ответ 2

Пробовал GCC и -O3:

void foo();
void bar();

int main()
{
    bool doesnt_change = true;
    for (int i = 0; i != 3; ++i) {
        if (doesnt_change) {
            foo();
        }
        else {
            bar();
        }
    }
}

Результат для основного:

_main:
pushl   %ebp
movl    %esp, %ebp
andl    $-16, %esp
call    ___main
call    __Z3foov
call    __Z3foov
call    __Z3foov
xorl    %eax, %eax
leave
ret

Таким образом, он оптимизирует выбор (и разворачивает меньшие циклы).

Эта оптимизация не выполняется, если doesnt_change является глобальным.

Ответ 3

Я уверен, что компилятор может определить, что флаг останется постоянным, он может сделать несколько shufflling:

const bool flag = /* ... */;
for (..;..;..;)
{
    if (flag)
    {
        // ...
    }
    else
    {
        // ...
    }
}

Если flag не const, компилятор не может оптимизировать цикл, потому что он не может быть уверен, что flag не изменится. Может быть, если он делает статический анализ, но не все компиляторы, я думаю. const - это верный способ сообщить компилятору, что флаг не изменится, после чего он до компилятора.

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

Ответ 4

Как правило, да. Но нет никакой гарантии, и места, где это сделает компилятор, вероятно, редки.

То, что большинство компиляторов делает без проблем, - это вытащить неизменяемые оценки из цикла, например. если ваше состояние

if (a<b) ....

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

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

В каких случаях расщепление цикла было бы полезным?

a) очень плотный цикл, где 1 цикл является значительной стоимостью б) весь цикл с обеими частями не соответствует кешу кода

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

Без какого-либо тестирования I'dexpect a) единственный случай, когда такая оптимизация будет применена, потому что это всегда лучший выбор:

В каких случаях расщепление цикла было бы плохим?

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

[править]
Я не мог заставить VC9 разбить следующий цикл (один из немногих случаев, когда это может быть полезно)

extern volatile int vflag = 0;

int foo(int count)
{
   int sum = 0;
   int flag = vflag;
   for(int i=0; i<count; ++i)
   {
      if (flag)
         sum += i;
      else
         sum -= i;
   }

   return sum;
}

[edit 2]
обратите внимание, что при int flag = true; вторая ветвь будет оптимизирована. (и нет, const не имеет значения здесь;))

Что это значит? Либо это не поддерживает это, это не имеет значения, ro мой анализ неправильный;-)

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

Ответ 5

Как многие говорили: это зависит.

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

for (condition)
  do_it<flag>();

Ответ 6

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

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

Ответ 7

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

Тем не менее, вторая версия кода, как правило, более читабельна и, вероятно, последняя вещь должна быть оптимизирована в блоке кода.