¿Pueden los compiladores de C++ optimizar las instrucciones "if" dentro de los bucles "for"?

Question

Consideremos un ejemplo como este:

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

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

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

Sólo en el primer caso, el código podría ser mucho más tiempo (por ejemplo, si se usan varios for bucles 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, la bandera se verifica muchas veces.

Tengo curiosidad por saber si los compiladores de C++ actuales (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

Sí, si se determina que el indicador no cambia y do_something o do_something_else no lo pueden cambiar, se puede sacar del bucle. He oído hablar de esto llamado elevación de bucle, pero Wikipedia tiene un entry llamado "movimiento de código invariante de bucle".

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 realiza: optimizar el tamaño favorecería a la versión sin cable, mientras que la optimización de la velocidad probablemente favorecería la versión con cable.

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

Answer 2

Estoy seguro que si el compilador puede determinar que la bandera se mantendrá constante, se puede hacer un poco de shufflling:

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

Si el flag no es const, el compilador puede no necesariamente optimizar el bucle, porque No puedo estar seguro de que 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 3

Se llama lazo invariante y la optimización de bucle se llama código invariante movimiento y también código de elevación. 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 pregunta, y eso es compilar su programa y mirar el código generado.

Answer 4

Tendría cuidado de 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 es generalmente más legible y probablemente sería lo último para optimizar en un bloque de código.

Answer 5

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

Lo que hacen la mayoría de los compiladores sin problemas es levantar las evaluaciones inmutables fuera de circuito, p. 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 lazo muy estrecho donde el 1 ciclo es un costo significativo
b) todo el circuito con las dos partes no se ajusta al código de caché

Ahora, el compilador sólo puede hacer suposiciones sobre el código caché y, por lo general, puede solicitar el código de forma que una rama se ajuste al caché.

Sin ninguna prueba, I'dexpect a) el único caso en el que se aplicaría tal optimización, robaba es nto siempre la mejor opción:

¿En qué casos dividir el bucle serían malos?

Al dividir el bucle aumenta el tamaño del código más allá de la memoria caché de código, recibirá 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 conseguir VC9 para dividir el siguiente bucle (uno de los pocos casos en los que en realidad podría ser 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 una diferencia aquí;))

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

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

Answer 6

Como muchos han dicho: depende.

Si quiere estar seguro, debe intentar forzar una decisión en tiempo de compilación. Plantillas menudo son útiles para esto:

for (condition) 
    do_it<flag>(); 

Answer 7

intentado 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 de 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 que optimizar la elección de distancia (y desenrolla bucles más pequeños).

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