¿Cuándo, si alguna vez, el bucle sigue siendo útil?

Question

He intentado optimizar un código extremadamente preciso para el rendimiento (un algoritmo de ordenamiento rápido que se llama millones y millones de veces dentro de una simulación de monte carlo) al desenrollarlo. Aquí está el bucle interno que estoy tratando de acelerar:

// Search for elements to swap. 
while(myArray[++index1] < pivot) {} 
while(pivot < myArray[--index2]) {} 

me trataron desenrollando a algo como:

while(true) { 
    if(myArray[++index1] < pivot) break; 
    if(myArray[++index1] < pivot) break; 
    // More unrolling 
} 


while(true) { 
    if(pivot < myArray[--index2]) break; 
    if(pivot < myArray[--index2]) break; 
    // More unrolling 
} 

Esto hizo absolutamente ninguna diferencia, así que cambió de nuevo a la forma más fácil de leer. He tenido experiencias similares otras veces que he intentado desenrollar loop. Dada la calidad de los predictores de bifurcaciones en el hardware moderno, ¿cuándo, si alguna vez, el bucle se está desenrollando sigue siendo una optimización útil?

Answer 1

El desenrollado de bucles tiene sentido si puede romper las cadenas de dependencia. Esto da a una CPU fuera de servicio o súper escalar la posibilidad de programar las cosas mejor y por lo tanto correr más rápido.

Un ejemplo simple:

for (int i=0; i<n; i++) 
{ 
    sum += data[i]; 
} 

Aquí la cadena de dependencias de los argumentos es muy corto. Si obtienes un puesto porque tienes un error de caché en la matriz de datos, la CPU no puede hacer nada más que esperar.

Por otro lado este código:

for (int i=0; i<n; i+=4) 
{ 
    sum1 += data[i+0]; 
    sum2 += data[i+1]; 
    sum3 += data[i+2]; 
    sum4 += data[i+3]; 
} 
sum = sum1 + sum2 + sum3 + sum4; 

podría correr más rápido. Si obtienes un error de caché u otro puesto en un cálculo, existen otras tres cadenas de dependencia que no dependen del puesto. Una CPU fuera de servicio puede ejecutar estos.

Answer 2

Eso no haría ninguna diferencia porque estás haciendo el mismo número de comparaciones. Aquí hay un mejor ejemplo. En lugar de:

for (int i=0; i<200; i++) { 
    doStuff(); 
} 

escritura:

for (int i=0; i<50; i++) { 
    doStuff(); 
    doStuff(); 
    doStuff(); 
    doStuff(); 
} 

Incluso entonces es casi seguro que no importa, sino que ahora está haciendo comparaciones en lugar de 50 200 (imaginar la comparación es más complejo).

Manual desenrollar bucle en general es en gran medida un artefacto de la historia sin embargo. Es otra de la creciente lista de cosas que un buen compilador hará por ti cuando sea importante. Por ejemplo, la mayoría de las personas no se molestan en escribir x << 1 o x += x en lugar de x *= 2. Simplemente escriba x *= 2 y el compilador lo optimizará para lo que sea mejor.

Básicamente cada vez hay menos necesidad de adivinar su compilador.

Answer 3

El desenrollado del lazo depende completamente del tamaño de su problema. Es completamente dependiente de que su algoritmo sea capaz de reducir el tamaño en grupos de trabajo más pequeños. Lo que hiciste arriba no se ve así. No estoy seguro si una simulación de monte carlo puede incluso desenrollarse.

I buen escenario para desenrollar el bucle sería rotar una imagen. Dado que podría rotar grupos de trabajo separados. Para que esto funcione, debería reducir el número de iteraciones.

Answer 4

Independientemente de la predicción de bifurcación en hardware moderno, la mayoría de los compiladores se desenrollan para usted de todos modos.

Valdría la pena averiguar cuántas optimizaciones hace su compilador para usted.

Encontré Felix von Leitner's presentation muy esclarecedor sobre el tema. Te recomiendo que lo leas. Resumen: los compiladores modernos son MUY inteligentes, por lo que las optimizaciones de mano casi nunca son efectivas.

Answer 5

El desenrollado del bucle sigue siendo útil si hay muchas variables locales tanto dentro como con el bucle. Para reutilizar esos registros más en lugar de guardar uno para el índice de bucle.

En su ejemplo, utiliza una pequeña cantidad de variables locales, sin sobreutilizar los registros.

La comparación (al final del bucle) también es un inconveniente importante si la comparación es pesada (es decir, no instrucciones test), especialmente si depende de una función externa.

El desenrollado del bucle también ayuda a aumentar el conocimiento de la CPU para la predicción de bifurcación, pero eso ocurre de todos modos.

Answer 6

Por lo que yo entiendo, los compiladores modernos ya desenrollar bucles en su caso - un ejemplo es gcc, si se aprueba los parámetros de optimización que el manual dice que:

Desenrollar bucles cuyo número de iteraciones puede se determinará en tiempo de compilación o al ingresar al bucle .

Por lo tanto, en la práctica, es probable que su compilador le haga los casos más triviales. Depende de usted, por lo tanto, asegurarse de que el número de bucles sea lo más fácil posible para que el compilador determine cuántas iteraciones se necesitarán.

Answer 7

El desenrollado en bucle, ya sea desenrollando las manos o desenrollando el compilador, a menudo puede ser contraproducente, especialmente con las CPU x86 más recientes (Core 2, Core i7). En pocas palabras: compare su código con y sin bucle en cualquiera de las CPU en las que planea implementar este código.

Answer 8

Probar sin saber no es la manera de hacerlo.
¿Este tipo toma un alto porcentaje del tiempo total?

Todo lo que se desenrolla de bucle es reducir la sobrecarga de bucle de incrementar/disminuir, comparando para la condición de parada y saltando. Si lo que está haciendo en el ciclo requiere más ciclos de instrucción que la sobrecarga del ciclo en sí, no verá una gran mejora porcentual.

Here's an example of how to get maximum performance.

Answer 9

Loop desenrollar puede ser útil en casos específicos. ¡La única ganancia es no saltearse algunas pruebas!

Puede, por ejemplo, permitir el reemplazo escalar, la inserción eficiente de la recuperación previa del software ... Se sorprendería de lo útil que puede ser (puede obtener aceleración del 10% en la mayoría de los bucles incluso con -O3) desenrollando agresivamente.

Como se dijo antes, depende mucho del ciclo y el compilador y el experimento son necesarios. Es difícil hacer una regla (o la heurística del compilador para desenrollar sería perfecta)