Могут ли компиляторы C ++ оптимизировать операторы if в циклах for?

Question

Рассмотрим пример, подобный этому:

if (flag)
  for (condition)
    do_something();
else
  for (condition)
    do_something_else();

Если flag не изменяется внутри циклов for, это должно быть семантически эквивалентно:

for (condition)
  if (flag)
    do_something();
  else
    do_something_else();

Только в первом случае код может быть намного длиннее (например, если используется несколько циклов for или если do_something() является блоком кода, который в основном идентичен do_something_else()), тогда как во втором случае, флаг проверяется много раз.

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

Answer 1

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

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

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

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

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

Answer 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 является глобальной.

Answer 3

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

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

for (condition)
  do_it<flag>();

Answer 4

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

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

if (a<b) ....

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

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

В каких случаях будет полезно разделение цикла?

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

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

Без какого-либо тестирования я буду ожидать 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;
}

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

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

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

Answer 5

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

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

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

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

Answer 6

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

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

Answer 7

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

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