performance - ¿Cuándo, si es que alguna vez, el bucle sigue siendo útil?
language-agnostic optimization (9)
He estado tratando de optimizar algún código extremadamente crítico para el rendimiento (un algoritmo de clasificación rápida que se llama millones y millones de veces dentro de una simulación de monte carlo) al desenrollar el bucle. Aquí está el ciclo interno que estoy tratando de acelerar:
// Search for elements to swap.
while(myArray[++index1] < pivot) {}
while(pivot < myArray[--index2]) {}
Intenté desenrollarme algo así 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 no hizo absolutamente ninguna diferencia, así que lo cambié a la forma más legible. 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?
El desenrollado de bucles 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 ... En realidad, te sorprendería lo útil que puede ser (puedes obtener fácilmente un 10% de aceleración en la mayoría de los bucles incluso con -O3) al desenrollar agresivamente.
Sin embargo, 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)
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 simple ejemplo:
for (int i=0; i<n; i++)
{
sum += data[i];
}
Aquí la cadena de dependencia de los argumentos es muy corta. 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.
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, usa una pequeña cantidad de variables locales, sin sobreutilizar los registros.
La comparación (con el extremo del bucle) también es un inconveniente importante si la comparación es pesada (es decir, sin instrucción de test ), especialmente si depende de una función externa.
El despliegue 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.
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.
El buen escenario para desenrollar el lazo 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.
El despliegue de bucles, ya sea desenrollando manualmente o desenrollando el compilador, a menudo puede ser contraproducente, particularmente con CPUs 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.
Esos no harían ninguna diferencia porque estás haciendo la misma cantidad de comparaciones. Aquí hay un mejor ejemplo. En lugar de:
for (int i=0; i<200; i++) {
doStuff();
}
escribir:
for (int i=0; i<50; i++) {
doStuff();
doStuff();
doStuff();
doStuff();
}
Incluso entonces, seguramente no importará, pero ahora se hacen 50 comparaciones en lugar de 200 (imagine que la comparación es más compleja).
Sin embargo, el desenrollamiento manual de bucles es, en general, un artefacto de la historia. 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 lugar de x *= 2 . Simplemente escribe x *= 2 y el compilador lo optimizará para lo que sea mejor.
Básicamente cada vez hay menos necesidad de adivinar tu compilador.
Independientemente de la predicción de ramas en el 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é la presentación de Felix von Leitner muy esclarecedora 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.
Intentar sin saber no es la forma de hacerlo.
¿Este tipo toma un alto porcentaje del tiempo total?
Todo lo que se desenrolla del bucle es reducir la sobrecarga del 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.
Por lo que yo entiendo, los compiladores modernos ya desenrollan bucles en su caso, un ejemplo es gcc, si pasa la optimización lo indica el manual dice que lo hará:
Desenrolle los bucles cuyo número de iteraciones se puede determinar en el momento de la compilación o al ingresar al bucle.
Entonces, en la práctica, es probable que tu compilador te 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.