¿Por qué el lazo de prueba inferior es preferible?

Escuché a alguien decir una vez que los compiladores mueven con frecuencia las condiciones de ciclo al final del ciclo. Es decir, los bucles como los siguientes:¿Por qué el lazo de prueba inferior es preferible?

while (condition) { 
    ... 
}

se cambia a:

if (condition) { 
    do { 
     ... 
    } while (condition); 
}

En cuanto a la optimización de la máquina independiente, por eso es preferible este último?

Fuente

2012-03-20 JohnTortugo

De hecho, el segundo ciclo no evalúa la condición en la parte superior del ciclo. Salta a la condición de tiempo, donde continúa como si acabara de terminar una iteración. –

Sin optimización del compilador, el primer bucle va a código ensamblador como esto:

@@: 
cmp ... ; or test ... 
jz @f 

... 
jmp @b

Considerando que el segundo bucle va a algo como esto:

jmp bottom 

    @@: 
... 

    bottom: 
cmp ... ; or test ... 
jz @b

saltos condicionales son por lo general predice que deben tomarse por lo que el primer método podría conducir a más flujos de caché de tubería/instrucción.

Sin embargo, lo más importante es que para el primer bucle, hay dos ramas disponibles por iteración de bucle (2N), mientras que en el segundo, cada iteración de bucle solo tiene una rama con una carga fija del primer salto incondicional (N+1).

Para obtener más información sobre la optimización de bucles, consulte la página 88 de este assembly optimisation guide.

Fuente

2012-03-20 00:25:03

+1 por mencionar el predictor de bifurcación, sin embargo, se olvidó del salto incondicional en el segundo ejemplo. (El segundo ejemplo es un bucle 'do', queremos un bucle 'while'.) Usted es incorrecto al decir que el segundo bucle ocupa menos espacio. –

@KendallFrey: Buena captura, actualizó el código. –

¿Tiene un CFG construido a partir de la segunda 'estructura de bucle' algún beneficio que no está presente al construirlo desde el primer bucle? Quiero decir, ¿es más propenso a la optimización? – JohnTortugo

Estás parcialmente equivocado. La optimización típica es la siguiente:

jmp $test; 
$loop: 
    ; loop statements 
$test: 
    test <condition>; 
    branch-true $loop;

en lugar de esto:

$loop: 
    test <condition>; 
    branch-false $end; 
    ; loop statements 
    branch loop; 
$end:

que tiene dos ramas en cada iteración del bucle. Otra ventaja es que la parte posterior al salto inicial es idéntica al código generado para do/while.

Fuente

2012-03-20 09:29:58 EJP

Para la vista de ensamblaje, un bucle es solo una instrucción de salto que salta hacia atrás del código. Entonces el compilador necesita insertar un salto al final del ciclo.

Muchos conjuntos de instrucciones, como x86, ARM, MIPS, todos proporcionan instrucciones de salto/derivación condicional. Si el salto tendrá lugar dependiendo de la condición especificada en la instrucción.

Por lo tanto, los compiladores prefieren este tipo de instrucciones y mueven la condición hasta el final del ciclo para hacer uso de las instrucciones.

Fuente

2012-03-20 14:36:27

¿Por qué el lazo de prueba inferior es preferible?

Respuesta

Cuestiones relacionadas