Loop desenrollar y optimización

Question

Dado el código:

for (int i = 0; i < n; ++i) 
{ 
    A(i) ; 
    B(i) ; 
    C(i) ; 
} 

Y la versión de optimización:

for (int i = 0; i < (n - 2); i+=3) 
{ 
    A(i) 
    A(i+1) 
    A(i+2) 
    B(i) 
    B(i+1) 
    B(i+2) 
    C(i) 
    C(i+1) 
    C(i+2) 
} 

Algo no está claro para mí: que es mejor? No puedo ver nada que funcione más rápido con la otra versión. Me estoy perdiendo de algo ?

Todo lo que veo es que cada instrucción es en función de la instrucción anterior, lo que significa que necesito esperar que la instrucción anterior acabaría con el fin de iniciar el uno después ...

Gracias

Answer 1

En la vista de alto nivel de un idioma, no verá la optimización. La mejora de la velocidad proviene de lo que el compilador hace con lo que tienes.

En el primer caso, es algo así como:

LOCATION_FLAG; 
DO_SOMETHING; 
TEST FOR LOOP COMPLETION;//Jumps to LOCATION_FLAG if false 

En el segundo que es algo así como:

LOCATION_FLAG; 
DO_SOMETHING; 
DO_SOMETHING; 
DO_SOMETHING; 
TEST FOR LOOP COMPLETION;//Jumps to LOCATION_FLAG if false 

Se puede ver en este último caso, la sobrecarga de pruebas y saltar es única 1 instrucción por 3. En el primero, es 1 instrucción por 1; por lo que sucede mucho más a menudo.

Por lo tanto, si tiene invariantes en los que puede confiar (una matriz de mod 3, para usar su ejemplo), entonces es más eficiente desenrollar bucles porque el ensamblaje subyacente está escrito más directamente.

Answer 2

Bien, si este código es "mejor" o "peor" depende totalmente de las implementaciones de A, B y C, que valores de n espera, qué compilador está utilizando y qué hardware está ejecutando.

Normalmente, la ventaja de desenrollar bucles es que se reduce la sobrecarga de hacer el bucle (es decir, aumentar i y compararlo con n). En este caso, podría reducirse en un factor de 3.

Answer 3

El desenrollado del bucle se utiliza para reducir el número de instrucciones de bifurcación de salto & que podrían hacer que el bucle sea más rápido pero aumentará el tamaño del binario. Dependiendo de la implementación y la plataforma, cualquiera podría ser más rápido.

Answer 4

Siempre que las funciones A(), B() y C() no modifiquen los mismos conjuntos de datos, la segunda versión proporciona más opciones de paralelización.

En la primera versión, las tres funciones podrían ejecutarse simultáneamente, suponiendo que no hay interdependencias. En la segunda versión, las tres funciones se podían ejecutar con los tres conjuntos de datos al mismo tiempo, suponiendo que tenía suficientes unidades de ejecución para hacerlo una y otra vez, sin interdependencias.

Answer 5

En general, no es una buena idea tratar de "inventar" optimizaciones, a menos que tenga pruebas sólidas de que obtendrá un aumento, porque muchas veces puede terminar introduciendo una degradación. Por lo general, la mejor forma de obtener tal evidencia es con un buen generador de perfiles. Probaría ambas versiones de este código con un generador de perfiles para ver la diferencia.

Además, muchas veces bucle desenrollado no es muy protable, como se ha mencionado anteriormente, depende en gran medida en la plataforma, compilador, etc.

Se puede jugar, además, con las opciones del compilador. Una opción interesante es gcc "-floop-optimizar", que se obtiene de forma automática con "O, O2, O3 y -Os"

EDITAR Además, mira a los "-funroll-loops" compilador opción.