¿Cuándo, si alguna vez, sigue siendo útil el desenrollado de bucles?

He estado tratando de optimizar un 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) mediante el desenrollado de bucle. Aquí está el bucle interno que estoy tratando de acelerar:

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

Intenté desenrollarlo 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 no hizo ninguna diferencia, así que lo cambié de nuevo a la forma más legible. He tenido experiencias similares otras veces que he intentado desenrollar bucles. Dada la calidad de los predictores de rama en el hardware moderno, ¿cuándo, si es que alguna vez, el desenrollado de bucles sigue siendo una optimización útil?

El desenrollado de bucles tiene sentido si puede romper las cadenas de dependencia. Esto le da a una CPU fuera de servicio o súper escalar la posibilidad de programar mejor las cosas 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 se detiene porque tiene una falta 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 obtiene una pérdida de caché u otro bloqueo en un cálculo, todavía hay otras tres cadenas de dependencia que no dependen del bloqueo. Una CPU fuera de servicio puede ejecutarlos.

Esos no harían ninguna diferencia porque estás haciendo la misma cantidad de comparaciones. He aquí un mejor ejemplo. En vez de:

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

escribir:

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

Incluso entonces es casi seguro que no importará, pero ahora está haciendo 50 comparaciones en lugar de 200 (imagine que la comparación es más compleja).

Sin embargo, el desenrollado manual de bucles es en gran medida un artefacto de la historia. Es otra de la creciente lista de cosas que un buen compilador hará por usted cuando sea importante. Por ejemplo, la mayoría de la gente no se molesta en escribir x <<= 1o en x += xlugar de x *= 2. Simplemente escriba x *= 2y el compilador lo optimizará para que sea lo mejor.

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

Independientemente de la predicción de la rama en el hardware moderno, la mayoría de los compiladores realizan el desenrollado de bucles de todos modos.

Valdría la pena averiguar cuántas optimizaciones hace su compilador por 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 manuales casi nunca son efectivas.

Por lo que yo entiendo, los compiladores modernos ya desenrollan los bucles cuando corresponde; un ejemplo es gcc, si se pasan las marcas de optimización, 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 su compilador haga los casos triviales por usted. Por lo tanto, depende de usted asegurarse de que la mayor cantidad posible de sus bucles sea fácil para que el compilador determine cuántas iteraciones se necesitarán.

El desenrollado de bucles, ya sea un desenrollado manual o un desenrollado del compilador, a menudo puede ser contraproducente, especialmente con las CPU x86 más recientes (Core 2, Core i7). En pocas palabras: evalúe su código con y sin desenrollado de bucles en las CPU en las que planea implementar este código.

Intentar sin saberlo no es la forma de hacerlo.
¿Toma este tipo un alto porcentaje del tiempo total?

Todo lo que hace el desenrollado de bucle es reducir la sobrecarga del bucle de incrementar / disminuir, comparar la condición de parada y saltar. Si lo que está haciendo en el bucle requiere más ciclos de instrucción que la sobrecarga del bucle en sí, no verá mucha mejora porcentual.

A continuación, se muestra un ejemplo de cómo obtener el máximo rendimiento.

El desenrollado de bucles puede resultar útil en casos específicos. ¡La única ventaja no es saltarse algunas pruebas!

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

Sin embargo, como se dijo antes, depende mucho del bucle 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 del bucle depende completamente del tamaño del problema. Depende por completo de que su algoritmo pueda reducir el tamaño en grupos de trabajo más pequeños. Lo que hiciste arriba no se ve así. No estoy seguro de si se puede desenrollar una simulación de monte carlo.

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

El desenrollado de 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 abusar de los registros.

La comparación (hasta el final del ciclo) también es un gran inconveniente si la comparación es pesada (es decir, sin testinstrucciones), especialmente si depende de una función externa.

El desenrollado de bucles también ayuda a aumentar la conciencia de la CPU para la predicción de ramas, pero eso ocurre de todos modos.