¿Pueden los compiladores de C++ optimizar los enunciados "si" dentro de los bucles "for"?

optimization compiler-construction

Question

Considera un ejemplo como este:

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

Si el flag no cambia dentro de los bucles for , esto debería ser semánticamente equivalente a:

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

Solo en el primer caso, el código puede ser mucho más largo (por ejemplo, si se usan varios bucles for o si do_something() es un bloque de código que es en su mayoría idéntico a do_something_else() ), mientras que en el segundo caso, se verifica veces.

Tengo curiosidad de saber si los compiladores actuales de C ++ (más importante, g ++) podrían optimizar el segundo ejemplo para deshacerse de las repetidas pruebas dentro del ciclo for . Si es así, ¿en qué condiciones es esto posible?

Answer 1

Como muchos han dicho: depende.

Si quieres estar seguro, deberías tratar de forzar una decisión en tiempo de compilación. Las plantillas a menudo son útiles para esto:

for (condition)
  do_it<flag>();

Answer 2

En general, sí. Pero no hay garantía, y los lugares donde el compilador lo hará probablemente sean raros.

Lo que la mayoría de los compiladores hacen sin problemas es sacar las evaluaciones inmutables del ciclo, por ejemplo, si su condición es

if (a<b) ....

cuando a y b no se ven afectados por el bucle, la comparación se realizará una vez antes del bucle.

Esto significa que si el compilador puede determinar que la condición no cambia, la prueba es barata y el salto se predijo. Esto a su vez significa que la prueba en sí cuesta un ciclo o ningún ciclo en absoluto (realmente).

¿En qué casos dividir el bucle sería beneficioso?

a) un bucle muy ajustado donde el 1 ciclo es un costo significativo
b) todo el bucle con ambas partes no se ajusta al caché del código

Ahora, el compilador solo puede hacer suposiciones sobre el caché del código y, por lo general, puede ordenar el código de manera que una rama se ajuste al caché.

Sin ninguna prueba, espero que a) el único caso en el que se aplique dicha optimización, ya que es siempre la mejor opción:

¿En qué casos dividir el bucle sería malo?

Al dividir el bucle aumenta el tamaño del código más allá de la memoria caché de código, tendrá un golpe significativo. Ahora, eso solo te afecta si el bucle se llama dentro de otro bucle, pero eso es algo que el compilador generalmente no puede determinar.

[editar]
No pude hacer que VC9 dividiera el siguiente ciclo (uno de los pocos casos en los que podría ser realmente beneficioso)

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

[editar 2]
tenga en cuenta que con int flag = true; la segunda rama se optimiza. (y no, const no hace la diferencia aquí;))

Qué significa eso? O no es compatible con eso, no importa, mi análisis es incorrecto ;-)

En general, supongo que esta es una optimización que es valiosa solo en unos pocos casos, y se puede hacer fácilmente en la mano en la mayoría de los escenarios.

Answer 3

Estoy seguro de que si el compilador puede determinar que la bandera se mantendrá constante, puede hacer algunas modificaciones:

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

Si la flag no es const , el compilador no necesariamente puede optimizar el bucle, porque no puede estar seguro de que la flag no cambie. Puede si se hace un análisis estático, pero no todos los compiladores lo hacen, creo. const es la forma segura de decirle al compilador que la bandera no cambiará, después de eso depende del compilador.

Como de costumbre, haga un perfil y descubra si realmente es un problema.

Answer 4

Intento con GCC y -O3:

void foo();
void bar();

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

Resultado para principal:

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

Por lo tanto, optimiza la elección (y desenrolla bucles más pequeños).

Esta optimización no se realiza si doesnt_change es global.

Answer 5

Sí, si se determina que la bandera no cambia y do_something o do_something_else no pueden cambiarla, puede retirarse del bucle. He oído hablar de esto llamado elevación de lazo, pero Wikipedia tiene una entrada llamada "movimiento de código invariante de lazo".

Si flags es una variable local, el compilador debería poder hacer esta optimización ya que está garantizado que no tendrá ningún efecto en el comportamiento del código generado.

Si flags es una variable global, y usted llama a funciones dentro de su bucle, es posible que no realice la optimización, es posible que no pueda determinar si esas funciones modifican el global.

Esto también puede verse afectado por el tipo de optimización que usted hace: optimizar el tamaño favorecería la versión sin cable, mientras que la optimización para la velocidad probablemente favorecería la versión con cable.

En general, este no es el tipo de cosas por las que debe preocuparse, a menos que los perfiles le indiquen que la función es un punto de acceso y ve que se está generando un código que no es eficiente revisando el ensamblado que genera el compilador. Las micro optimizaciones como esta siempre deberían dejarse al compilador a menos que sea absolutamente necesario.

Answer 6

Se llama invariante de bucle y la optimización se denomina movimiento de código invariante de bucle y también elevación de código . El hecho de que esté en un condicionamiento definitivamente hará que el análisis del código sea más complejo y el compilador puede o no invertir el ciclo y el condicional dependiendo de qué tan inteligente sea el optimizador.

Hay una respuesta general para cualquier caso específico de este tipo de preguntas, y eso es compilar su programa y mirar el código generado.

Answer 7

Sería cauteloso para decir que lo hará. ¿Puede garantizarse que el valor no será modificado por esto u otro hilo?

Dicho esto, la segunda versión del código generalmente es más legible y probablemente sería lo último para optimizar en un bloque de código.