c++ - terminar - sentencia break en c
¿Por qué hay una diferencia significativa en este C++ para el tiempo de ejecución del bucle? (8)
Basado en el concepto de localidad de referencia, es muy probable que un código acceda a ubicaciones de memoria adyacentes. Por lo tanto, se cargan más valores en el caché de lo que se solicita. Esto significa más visitas al caché. Su primer ejemplo lo satisface bien, mientras que el código del segundo ejemplo no lo es.
Esta pregunta ya tiene una respuesta aquí:
Estaba pasando por bucles y encontré una diferencia significativa en el acceso a los bucles. No puedo entender qué es lo que causa tanta diferencia en ambos casos.
Primer ejemplo:
Tiempo de ejecución; 8 segundos
for (int kk = 0; kk < 1000; kk++)
{
sum = 0;
for (int i = 0; i < 1024; i++)
for (int j = 0; j < 1024; j++)
{
sum += matrix[i][j];
}
}
Segundo ejemplo
Tiempo de ejecución: 23 segundos
for (int kk = 0; kk < 1000; kk++)
{
sum = 0;
for (int i = 0; i < 1024; i++)
for (int j = 0; j < 1024; j++)
{
sum += matrix[j][i];
}
}
Lo que causa tanta diferencia de tiempo de ejecución simplemente intercambiando
matrix[i][j]
a
matrix[j][i]
?
El hardware de memoria no está optimizado para entregar direcciones individuales: en su lugar, tiende a funcionar en fragmentos más grandes de memoria continua llamados líneas de caché . Cada vez que lee una entrada de su matriz, toda la línea de caché en la que se encuentra también se carga en la caché junto con ella.
El orden de bucle más rápido está configurado para leer la memoria en orden; cada vez que carga una línea de caché, utiliza todas las entradas en esa línea de caché. Cada vez que pasa por el bucle externo, lee cada entrada de matriz solo una vez.
Sin embargo, el orden de bucle más lento solo usa una sola entrada de cada línea de caché antes de continuar.
Por lo tanto, cada línea de caché debe cargarse varias veces, una para cada entrada de matriz en la línea.
por ejemplo, si un
double
es de 8 bytes y una línea de caché tiene 64 bytes de longitud, cada paso a través del bucle externo debe leer cada entrada de matriz
ocho
veces en lugar de una sola vez.
Dicho todo esto, si hubiera activado las optimizaciones, probablemente no vería ninguna diferencia: los optimizadores entienden este fenómeno, y los buenos son capaces de reconocer que pueden intercambiar qué bucle es el bucle interno y qué bucle es el bucle externo para este particular fragmento de código.
(también, un buen optimizador solo habría hecho una pasada a través del bucle más externo, porque reconoce que las primeras 999 veces son irrelevantes para el valor final de la
sum
)
Es un problema de memoria caché.
matrix[i][j]
tiene mejores resultados de caché que la
matrix[j][i]
, ya que la
matrix[i][j]
tiene más posibilidades de acceso continuo a la memoria.
Por ejemplo, cuando accedemos a la
matrix[i][0]
, el caché puede cargar un segmento continuo de memoria que contiene la
matrix[i][0]
, por lo tanto, acceder a la
matrix[i][1]
,
matrix[i][2]
, ..., se beneficiará de la velocidad de almacenamiento en caché, ya que la
matrix[i][1]
, la
matrix[i][2]
, ... están cerca de la
matrix[i][0]
.
Sin embargo, cuando accedemos a la
matrix[j][0]
, está lejos de la
matrix[j - 1][0]
y puede que no se haya almacenado en caché, y no puede beneficiarse de la velocidad de almacenamiento en caché.
Especialmente, una matriz normalmente se almacena como un gran segmento continuo de memoria, y el caché puede predicar el comportamiento del acceso a la memoria y siempre almacenar en caché la memoria.
Es por eso que la
matrix[i][j]
es más rápida.
Esto es típico en la optimización del rendimiento basada en caché de CPU.
La diferencia en el rendimiento es causada por la estrategia de almacenamiento en caché de la computadora.
La matriz de
matrix[i][j]
bidimensional
matrix[i][j]
se representa como una larga lista de valores en la memoria.
Por ejemplo, la matriz
A[3][4]
ve así:
1 1 1 1 2 2 2 2 3 3 3 3
En este ejemplo, cada entrada de A [0] [x] se establece en 1, cada entrada de A [1] [x] se establece en 2, ...
Si su primer ciclo se aplica a esta matriz, el orden de acceso es este:
1 2 3 4 5 6 7 8 9 10 11 12
Mientras que el segundo orden de acceso a los bucles se ve así:
1 4 7 10 2 5 8 11 3 6 9 12
Cuando el programa accede a un elemento de la matriz, también carga elementos posteriores.
Por ejemplo, si accede a
A[0][1]
,
A[0][2]
y
A[0][3]
se cargan.
De este modo, el primer bucle debe realizar menos operaciones de carga, ya que algunos elementos ya están en la memoria caché cuando es necesario. El segundo bucle carga entradas en la memoria caché que no son necesarias en ese momento, lo que resulta en más operaciones de carga.
La matriz se almacena en la memoria como un vector. Accediendo a ella de la primera manera se accede a la memoria secuencialmente. Acceder a ella de la segunda manera requiere saltar por las ubicaciones de memoria. Ver http://en.wikipedia.org/wiki/Row-major_order
La respuesta depende un poco de exactamente cómo se define la
matrix
.
En una matriz completamente asignada dinámicamente, tendría:
T **matrix;
matrix = new T*[n];
for(i = 0; i < n; i++)
{
t[i] = new T[m];
}
Por lo tanto, cada
matrix[j]
requerirá una nueva búsqueda de memoria para el puntero.
Si realiza el bucle
j
afuera, el bucle interno puede reutilizar el puntero para la
matrix[j]
cada vez para todo el bucle interno.
Si la matriz es una simple matriz 2D:
T matrix[n][m];
entonces la
matrix[j]
simplemente será una multiplicación por
1024 * sizeof(T)
, lo que se puede hacer agregando
1024 * sizeof(T)
el índice de bucle en el código optimizado, por lo que debería ser relativamente rápido en ambos sentidos.
Además de eso, tenemos factores de localidad de caché.
Las memorias caché tienen "líneas" de datos que normalmente son de 32 a 128 bytes por línea.
Entonces, si su código lee la dirección
X
, la memoria caché se cargará con valores de 32 a 128 bytes alrededor de
X
Entonces, si lo SIGUIENTE que necesita es solo el
sizeof(T)
hacia adelante desde la ubicación actual, es muy probable que ya esté en la caché [y los procesadores modernos también detectan que está dando vueltas en un bucle leyendo cada ubicación de memoria, y precarga el datos].
En el caso de
j
loop interno, está leyendo una nueva ubicación de
sizeof(T)*1024
distancia para cada loop [o posiblemente una distancia mayor si está asignada dinámicamente].
Esto significa que los datos que se cargan no serán útiles para el siguiente ciclo, porque no están en los próximos 32 a 128 bytes.
Y finalmente, es completamente posible que el primer ciclo esté más optimizado, gracias a las instrucciones SSE o similares, que permiten que el cálculo se ejecute aún más rápido. Pero esto es probablemente marginal para una matriz tan grande, ya que el rendimiento está muy limitado a la memoria en este tamaño.
Otras personas han hecho un buen trabajo explicando por qué una forma de su código hace un uso más eficiente de la memoria caché que la otra. Me gustaría agregar información de fondo que quizás no conozca: probablemente no se dé cuenta de lo caros que son los accesos a la memoria principal hoy en día.
Los números publicados en esta pregunta parecen estar en el estadio correcto para mí, y los reproduciré aquí porque son muy importantes:
Core i7 Xeon 5500 Series Data Source Latency (approximate)
L1 CACHE hit, ~4 cycles
L2 CACHE hit, ~10 cycles
L3 CACHE hit, line unshared ~40 cycles
L3 CACHE hit, shared line in another core ~65 cycles
L3 CACHE hit, modified in another core ~75 cycles remote
remote L3 CACHE ~100-300 cycles
Local Dram ~60 ns
Remote Dram ~100 ns
Tenga en cuenta el cambio en las unidades para las dos últimas entradas. Dependiendo exactamente del modelo que tenga, este procesador funciona a 2.9–3.2 GHz; para simplificar las matemáticas, llamémoslo 3 GHz. Entonces un ciclo es 0.33333 nanosegundos. Entonces los accesos DRAM también son 100-300 ciclos.
El punto es que la CPU podría haber ejecutado cientos de instrucciones en el tiempo que lleva leer una línea de caché de la memoria principal. Esto se llama el muro de la memoria . Debido a esto, el uso eficiente de la memoria caché es más importante que cualquier otro factor en el rendimiento general de las CPU modernas.
Si accede a j - i, la dimensión j se almacena en caché para que el código de la máquina no tenga que cambiarla cada vez, la segunda dimensión no se almacena en caché, por lo que realmente elimina la memoria caché cada vez que causa la diferencia.