¿gcc optimiza mi ciclo con la condición?

Question

Tengo el siguiente ciclo:

//condition will be set here to true or false 

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

Supuesto: Un ciclo si no una condición más rápido que con una condición. (¿Es esto cierto?) Pregunta: ¿GCC factorizará mi if, si condition se ha establecido fuera del ciclo for, y el ciclo en sí no toca condition?

Si no es así, debería cambiar el if y la for, duplicar código, violar seco, etc.

Answer 1

Para aquellos que no desean leer una publicación larga, esta optimización se llama (en LLVM) Loop Unswitch.

¿Por qué no preguntarle a un compilador?

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

se transforma en el formulario SSA (a través de LLVM try out):

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 
} 

No muy legible tal vez, por lo que quiero señalar lo que hay aquí:

• entry: comprobar si argc es igual a 0, si es así, vaya a bb5 (salir) else vaya a bb.nph
• bb.nph: calcular el valor de condition, si es verdad, ir a bb3.us bien ir a bb3
• bb3.us y bb3: bucles para la verdadera y falsa condición respectivamente
• bb5: salida

Un compilador puede bastante Transforme mucho su código como lo desee, siempre y cuando el efecto sea similar al que solicitó. En este caso, se ha vuelto a escribir de manera efectiva el código como:

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

Es una forma de optimización de invariantes de bucle, combinada aquí con un primer control para evitar el cálculo de la condición si el bucle no se va a poner ejecutado.

Para aquellos de nosotros que pensarían que la primera solución es más clara, estamos muy contentos de que el compilador nos haga la optimización esencial para nosotros.

Answer 2

Cualquier compilador de optimización decente hará si condition se puede probar que no cambia durante la iteración.

Además, incluso si el compilador de hecho no hace esto, haría bien en respaldar su decisión de volver a escribir el código en un formato menos legible con datos duros de creación de perfiles. No optimice prematuramente. No vale la pena darles a los lectores el código "¿eh?" momento para reducir algunos milisegundos (y los "lectores" definitivamente se incluyen en un futuro).

Answer 3

No recomendaría tomar ninguna medida aquí, por los habituales argumentos de "optimización prematura". Mantener el código claro es lo más importante, y si todo el programa es demasiado lento, es posible que desee crear un perfil y encontrar los cuellos de botella reales (que generalmente no puede adivinar) después de que el programa haya sido completamente depurado.

Incluso si el compilador no optimiza este caso particular para usted, puede querer saber que la CPU hace alguna forma de branch prediction que reducirá en gran medida el tiempo necesario para procesar la condición en caso de que la condición sea predecible.

De hecho, la mayoría de las instrucciones de proceso de CPU en un pipeline y para el momento en que se debe determinar la dirección de salto, la variable de condición puede ser desconocida. Esto provocaría un puesto en la línea, y aquí es donde la mayoría de los procesadores modernos intentan adivinar (de hecho, de manera inteligente) dónde saltará el programa. Si la variable de condición es realmente conocida (como lo es en su caso), la conjetura será perfecta.

Así que dudo que incluso con un compilador "tonto", realmente verías una diferencia entre las dos opciones, al menos en las máquinas modernas.