Inversión de bucle

En informática , la inversión de bucles es una optimización del compilador y una transformación de bucles en la que un bucle while se reemplaza por un bloque if que contiene un bucle do...while . ^{[ 1 ]} Cuando se usa correctamente, puede mejorar el rendimiento debido a la segmentación de instrucciones o a evitar instrucciones de salto para reducir la predicción errónea de bifurcaciones . ^{[ 1 ]}

En un bucle while (iteración indefinida), la condición debe comprobarse en cada iteración. Si la condición falla, se sale del bucle. Al colocar la condición al final del cuerpo del bucle, la inversión del bucle evita cualquier salto al final de la última iteración.

void pre_inversion () { while ( /* condición */ ) { /* cuerpo del bucle */ } }

es equivalente a:

void post_inversión () { if ( /* condición */ ) { do { /* cuerpo del bucle */ } while ( /* condición */ ); } }

No se produce ningún cambio en el rendimiento para las iteraciones iniciales y no finales del bucle, incluso cuando no se entra en él porque la condición es falsa. Sin embargo, la iteración final tiene 2 instrucciones de salto menos cuando se entra en el bucle porque el bucle do-while no necesita saltar al inicio del bucle while para evaluar la condición del bucle. ^{[ 1 ]}

int i , a [ 100 ]; i = 0 ; while ( i < 100 ) { a [ i ] = 0 ; i ++ ; }

es equivalente a:

int i , a [ 100 ]; i = 0 ; if ( i < 100 ) { do { a [ i ] = 0 ; i ++ ; } while ( i < 100 ); }

A pesar de la aparente mayor complejidad del segundo ejemplo, en realidad podría ejecutarse más rápido en las CPU modernas porque utilizan una segmentación de instrucciones . Por naturaleza, cualquier salto en el código provoca una pausa en la segmentación , lo que perjudica el rendimiento.

Además, la inversión de bucles permite un movimiento de código seguro e invariante al bucle .

 i := 0 L1: si i >= 100 ir a L2 a[i] := 0 i := i + 1 ir a L1 L2: 

Si me hubiera inicializado a 100, las instrucciones ejecutadas en tiempo de ejecución habrían sido:

 si i >= 100  ir a L2 

Supongamos que i se inicializó con un valor menor que 100. Ahora veamos las instrucciones ejecutadas en el momento en que i se incrementó a 99 en el bucle:

 ir a L1  si i < 100  a[i] := 0  i := i + 1  ir a L1  si i >= 100  ir a L2  <<en L2>> 

Ahora, veamos la versión optimizada:

 i := 0 Si i >= 100, ir a L2 L1: a[i] := 0 i := i + 1 Si i < 100, ir a L1 L2:

Veamos de nuevo las instrucciones que se ejecutan si i se inicializa a 100:

 si i >= 100  ir a L2 

No desperdiciamos ningún ciclo en comparación con la versión original. Ahora consideremos el caso en el que i se ha incrementado:

 si i < 100  ir a L1  a[i] := 0  i := i + 1  si i < 100  <<en L2>> 

Como puede verse, se han eliminado dos instrucciones goto (y, por lo tanto, dos pausas en la canalización) durante la ejecución.