Técnicas de optimización de bucles | conjunto 2

Requisito previo: optimización de bucles | Serie 1

1. Loop Fission: mejora la localidad de referencia:
en esto, un bucle se divide en múltiples bucles sobre el mismo rango de índice, pero cada nuevo bucle contiene solo una parte específica del cuerpo del bucle original. Esto puede mejorar la localidad de referencia.

Antes de la optimización:

for(i=0;i<100;i++)                          
{a[i]=…
b[i]=…
}

Después de la optimización:

for(i=0;i<100;i++)
a[i]=…
for(i=0;i<100;i++)
b[i]=…

2. Intercambio de bucles: mejora la localidad de referencia:
en estas optimizaciones, se intercambian bucles internos con bucles externos. Cuando las variables de bucle se indexan en una array, dicha transformación puede mejorar la localidad de referencia, según el diseño de la array.

Antes de la optimización:

for(i=0;i<100;i++)
for(j=0;j<100;j++)
a[j][i]=…

Después de la optimización:

for(j=0;j<100;j++)
for(i=0;i<100;i++)
a[j][i]=…

3. Inversión de bucle:
invierte el orden en que se asignan los valores a la variable de índice. Esto puede ayudar a eliminar dependencias y así permitir otras optimizaciones.

Antes de la optimización:

for(i=0;i<100;i++)
a[99-i]=…  

Después de la optimización:

for(i=99;i>=0;i--)
a[i]=…

4. Desenrollado de bucles : minimiza las pruebas y los saltos, pero aumenta el tamaño del código.
El objetivo del desenrollado de bucles es aumentar la velocidad de un programa al reducir las instrucciones que controlan el bucle, como la aritmética de punteros y la condición de prueba de «fin de bucle» en cada iteración. Para eliminar o reducir esta sobrecarga computacional, los bucles se pueden reescribir como una secuencia repetida de declaraciones independientes similares.

Antes de la optimización:

for(i=0;i<100;i++)
a[i]=…  

Después de la optimización:

for(i=0;i<100;i+=2)
{a[i]=…
a[i+1]=…
}

5. División de bucles:
intenta simplificar un bucle o eliminar las dependencias dividiéndolo en múltiples bucles que tienen el mismo cuerpo pero iteran sobre diferentes partes del rango del índice.

Antes de la optimización:

for(i=0;i<100;i++)
if(i<50)
a[i]=…
else
b[i]=…

Después de la optimización:

for(i=0;i<50;i++)
a[i]=…
for(;i<100;i++)
b[i]=…

6. Loop Peeling: caso especial de división de loops:
un caso especial de división de loops es loop peeling, que puede simplificar un ciclo con una primera iteración problemática realizando esa iteración por separado antes de ingresar al ciclo.

Antes de la optimización:

for(i=0;i<100;i++)
if(i==0)
a[i]=…
else
b[i]=…

Después de la optimización:

a[0]=…
for(i=1;i<100;i++)
b[i]=…

7. Desconexión:
mueve un condicional desde el interior de un ciclo hacia el exterior duplicando el cuerpo del ciclo y colocando una versión del mismo dentro de cada una de las cláusulas if y else del condicional.

Antes de la optimización:

for(i=0;i<100;i++)
if(x>y)
a[i]=…
else
b[i]=…

Después de la optimización:

if(x>y)
for(i=0;i<100;i++)
a[i]=…
else
for(i=0;i<100;i++)
b[i]=…  

8. Reemplazo de prueba de bucle: aumenta la posibilidad de eliminación de código muerto –

Antes de la optimización:

i=0;
val=0;
while(i<100)
{val+=5;
i++;
}

Después de la optimización:

i=0;
val=0;
while(val<500)
{val+=5;
i++;
}