Dos cuerpos de bucle o uno (resultado idéntico)

Question

Hace mucho tiempo me pregunto qué es más eficiente en cuanto a hacer un mejor uso de cachés de CPU (que se sabe que se benefician de la localidad de referencia): dos bucles iterando sobre el mismo conjunto matemático de números, cada uno con un cuerpo de bucle diferente, o tener un bucle que "concatena" los dos cuerpos en uno, y así logra el resultado total idéntico, pero ¿todo en sí mismo?

En mi opinión, tener dos bucles introduciría menos errores de caché y desalojos porque más instrucciones y datos utilizados por el bucle cabían en la memoria caché. ¿Estoy en lo cierto?

Suponiendo:

1. Costo de f y g cada uno es insignificante en comparación con el costo de completar todo el circuito que contiene cada
2. f y g uso más de cada caché por sí mismo, por lo que la memoria caché ser invalidado por una llamada después de otra (que sería el caso con una versión de cuerpo de bucle único)
3. CPU Intel Core Duo
4. código fuente del lenguaje C
5. gcc compilador, no cambia

El conjunto se repiten a lo largo es un conjunto matemático, no un recipiente de números en la memoria como un vector o una lista. Vea el ejemplo a continuación.

Por favor, no hay respuestas de la "optimización prematura es malo" carácter :-)

Un ejemplo de la versión de dos bucles que estoy abogando por:

int j = 0, k = 0; 

for(int i = 0; i < 1000000; i++) 
{ 
    j += f(i); 
} 

for(int i = 0; i < 1000000; i++) 
{ 
    k += g(i); 
} 

Answer 1

puedo ver tres variables (incluso en un aparentemente simple trozo de código):

• ¿Qué f()g() y lo hacen? ¿Puede uno de ellos invalidar todas las líneas de caché de instrucciones (empujando efectivamente el otro)? ¿Puede suceder eso también en el caché de instrucciones L2 (poco probable)? Entonces, mantener solo uno de ellos podría ser beneficioso. Nota: La inversa no implica "tener un solo ciclo", debido a que:
• Haz f()g() y operan sobre grandes cantidades de datos, de acuerdo con i?Entonces, sería bueno saber si operan en el mismo conjunto de datos - de nuevo, debe considerar si operar en dos conjuntos diferentes lo arruina por falta de memoria caché.
• Si f() y g() son tan primitivos como usted dice primero, y estoy asumiendo tanto el tamaño del código como el tiempo de ejecución y la complejidad del código, los problemas de localización en caché no surgirán en pequeños fragmentos de código como este: su La mayor preocupación sería si se programara algún otro proceso con trabajo real que hacer e invalidara todas las cachés hasta que fuera el turno de su proceso para ejecutarse.

Pensamiento final: dado que tales procesos como los anteriores pueden ser una ocurrencia rara en su sistema (y estoy usando bastante "raro"), podría considerar hacer ambas funciones en línea y dejar que el compilador Desenrollar el bucle. Esto se debe a que para la memoria caché de instrucciones, la falla a L2 no es gran cosa, y la probabilidad de que la única línea de caché que contiene i, j, k se invalide en ese bucle no se ve tan horrible. Sin embargo, si ese no es el caso, algunos detalles más serían útiles.

Answer 2

Esto parece como algo que el compilador podría optimizar para usted así que en vez de tratar de resolverlo usted mismo y hacerlo rápido, use cualquier método que haga que su código sea más claro y legible. Si realmente debes saber, mide ambos métodos para el tamaño de entrada y el tipo de cálculo que usa tu aplicación (prueba el código que tienes ahora pero repite tus cálculos muchas veces y deshabilita la optimización).

Answer 3

Medir es conocer.

Answer 4

Intuitivamente, un bucle es mejor: aumenta i un millón de veces menos y todos los demás recuentos de operación siguen siendo los mismos.

Por otro lado, depende completamente de f y g. Si ambos son lo suficientemente grandes como para que cada uno de sus códigos o datos almacenables en caché casi llenen un caché crítico, el intercambio entre f y g puede anular por completo cualquier beneficio de bucle único.

Como dices: depende.

Answer 5

Su pregunta no es lo suficientemente clara como para dar una respuesta remotamente precisa, pero creo que entiendo hacia dónde se dirige. Los datos sobre los que está iterando son lo suficientemente grandes como para que, antes de llegar al final, empiece a desalojar los datos para que la segunda vez (segundo ciclo) pueda iterar sobre ellos, si no todos tendrán que leerse nuevamente.

Si los dos bucles se unieron para que cada elemento/bloque se obtenga para la primera operación y luego ya esté en caché para la segunda operación, no importa qué tan grande sea la información relativa al caché, si no todos las segundas operaciones tomarán sus datos del caché.

Varias cosas como la naturaleza de la memoria caché, el bucle que es desalojado por los datos que se obtienen y los datos de desalojo pueden causar algunos errores en la segunda operación. En una PC con un sistema operativo, se producirán muchos desalojos con otros programas que reciben bloqueos de tiempo. Pero asumiendo un mundo ideal, la primera operación en el índice i de los datos lo recuperará de la memoria, la segunda operación lo tomará de la memoria caché.

El ajuste de una memoria caché es difícil en el mejor de los casos. Demuestro regularmente que incluso con un sistema integrado, sin interrupciones, una sola tarea, el mismo código fuente. El tiempo/desempeño de ejecución puede variar dramáticamente simplemente cambiando las opciones de optimización del compilador, cambiando compiladores, ambas marcas de compiladores o versiones de compiladores, gcc 2.x vs 3.x vs 4.x (gcc no necesariamente produce código más rápido con versiones más nuevas por cierto) (y un compilador que es bastante bueno en muchos objetivos no es realmente bueno en ningún objetivo en particular). El mismo código Los diferentes compiladores u opciones pueden cambiar el tiempo de ejecución varias veces, 3 veces más rápido, 10 veces más rápido, etc. Una vez que ingresas a las pruebas con o sin un caché, se vuelve aún más interesante. Agregue un solo nop en su código de inicio para que todo su programa mueva una instrucción en la memoria y sus líneas de caché ahora lleguen a diferentes lugares. Misma compilación del mismo código. Repita esto con dos nops, tres nops, etc. Mismo compilador, mismo código que puede ver decenas de porcentajes (para las pruebas que realicé ese día con ese compilador) las diferencias son cada vez mejores. Eso no significa que no puedas sintonizar un caché, solo significa que tratar de descubrir si tu afinación te ayuda o duele puede ser difícil. La respuesta normal es simplemente "cronometrar y ver", pero eso ya no funciona, y es posible que obtengas excelentes resultados en tu computadora ese día con ese programa con ese compilador. Pero mañana, en su computadora o cualquier otro día en otra computadora, puede estar haciendo las cosas más lentamente, no más rápido. Debe comprender por qué este o aquel cambio lo hizo más rápido, tal vez no tuvo nada que ver con su código, su programa de correo electrónico puede haber estado descargando una gran cantidad de correo en segundo plano durante una prueba y no durante la otra.

Suponiendo que haya entendido bien su pregunta, creo que, en general, el bucle único es más rápido.

Answer 6

Si encontré en código la versión de dos bucles, sin comentarios explicativos, me pregunto por qué el programador lo hizo así, y probablemente considere que la técnica es de dudosa calidad, mientras que una versión de un ciclo No sea sorprendente, comentado o no.

Pero si encontré la versión de dos bucles junto con un comentario como "Estoy usando dos bucles porque funciona un X% más rápido en la memoria caché de la CPU Y", al menos ya no me desconcertaría el código, aunque aún cuestionaría si era cierto y aplicable a otras máquinas.

Answer 7

Romper los lazos en trozos más pequeños es una buena idea .. Podría mejora la proporción de aciertos de caché mucho y puede hacer una gran diferencia en el rendimiento ...

de su ejemplo:

int j = 0, k = 0; 

for(int i = 0; i < 1000000; i++) 
{ 
    j += f(i); 
} 

for(int i = 0; i < 1000000; i++) 
{ 
    k += g(i); 
} 

lo haría o bien se funden los dos bucles en un bucle como este:

int j = 0, k = 0; 

for(int i = 0; i < 1000000; i++) 
{ 
    j += f(i); 
    k += g(i); 
} 

Por si esto no es posible hacer la optimización denominada Loop-Revestimientos:

#define TILE_SIZE 1000 /* or whatever you like - pick a number that keeps */ 
         /* the working-set below your first level cache size */ 

int i=0; 
int elements = 100000; 

do { 
    int n = i+TILE_SIZE; 
    if (n > elements) n = elements; 

    // perform loop A 
    for (int a=i; a<n; a++) 
    { 
    j += f(i); 
    } 

    // perform loop B 
    for (int a=i; a<n; a++) 
    { 
    k += g(i); 
    } 

    i += n 
} while (i != elements) 

El truco con azulejos de bucle es, que si los bucles comparten un patrón de acceso al segundo cuerpo del bucle tiene la oportunidad de volver a utilizar los datos que ya se ha leído en la memoria caché por el primer cuerpo del bucle. Esto no sucederá si ejecuta el bucle A un millón de veces porque la memoria caché no es lo suficientemente grande como para contener todos estos datos.

Romper el ciclo en trozos más pequeños y ejecutarlos uno tras otro ayudará mucho aquí. El truco es limitar el conjunto de trabajo de la memoria por debajo del tamaño de su primer nivel de caché. Mi objetivo es la mitad del tamaño del caché, por lo que otros hilos que se ejecutan en el medio no estropean tanto mi caché ...