Creo que lo que está viendo son los efectos de locality of reference en la jerarquía de memoria de la computadora.
Típicamente, la memoria del ordenador está segregada en diferentes tipos que tienen diferentes características de rendimiento (esto se llama a menudo el memory hierarchy). La memoria más rápida se encuentra en los registros del procesador, que (generalmente) se puede acceder y leer en un solo ciclo de reloj. Sin embargo, generalmente hay solo un puñado de estos registros (por lo general, no más de 1 KB). La memoria principal de la computadora, por otro lado, es enorme (digamos, 8GB), pero es mucho más lenta de acceder. Para mejorar el rendimiento, la computadora generalmente se construye físicamente para tener several levels of caches entre el procesador y la memoria principal. Estas memorias caché son más lentas que los registros pero mucho más rápidas que la memoria principal, por lo que si haces un acceso a la memoria que busca algo en la memoria caché, tiende a ser mucho más rápido que si tienes que ir a la memoria principal (por lo general, entre 5-25x) Más rápido). Al acceder a la memoria, el procesador comprueba primero el caché de la memoria para ese valor antes de volver a la memoria principal para leer el valor. Si accedes constantemente a los valores en el caché, terminarás con un rendimiento mucho mejor que si te estás salteando memoria, accediendo aleatoriamente a los valores.
La mayoría de los programas están escritos de forma que si se lee un solo byte en la memoria en la memoria, el programa leerá también múltiples valores diferentes de esa región de memoria. En consecuencia, estas memorias caché generalmente están diseñadas para que cuando lea un único valor de la memoria, un bloque de memoria (generalmente entre 1 KB y 1 MB) de valores alrededor de ese valor individual también se arrastre a la memoria caché. De esta forma, si su programa lee los valores cercanos, ya están en la caché y no tiene que ir a la memoria principal.
Ahora, un último detalle: en C/C++, las matrices se almacenan en orden de fila mayor, lo que significa que todos los valores en una sola fila de una matriz se almacenan uno al lado del otro. Por lo tanto, en la memoria la matriz se ve como la primera fila, luego la segunda fila, luego la tercera fila, etc.
Dado esto, veamos su código. La primera versión se ve así:
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++)
c[i][j] = c[i][j] + a[i][k]*b[k][j];
Ahora, veamos la línea más interna de código. En cada iteración, el valor de k está cambiando en aumento. Esto significa que cuando se ejecuta el bucle más interno, es probable que cada iteración del bucle tenga una falta de caché al cargar el valor de b[k][j].La razón de esto es que debido a que la matriz está almacenada en orden mayor de fila, cada vez que incrementa k, se salta una fila entera de la matriz y se adentra mucho más en la memoria, posiblemente mucho más allá de los valores que guardó en caché . Sin embargo, no se lo pierda al buscar c[i][j] (ya que i y j son lo mismo), ni probablemente perderá a[i][k], porque los valores están en orden mayor de fila y si el valor de a[i][k] está en caché del anterior iteración, el valor de a[i][k] leído en esta iteración proviene de una ubicación de memoria adyacente. En consecuencia, en cada iteración del ciclo más interno, es probable que tenga una falla en la caché.
Pero considerar esta segunda versión:
for (int i = 0; i < n; i++)
for (int k = 0; k < n; k++)
for (int j = 0; j < n; j++)
c[i][j] = c[i][j] + a[i][k]*b[k][j];
Ahora, ya que está aumentando j en cada iteración, vamos a pensar en la cantidad de caché echa de menos es probable que tenga en la cuenta interna. Debido a que los valores están en orden mayor de fila, es probable que el valor de c[i][j] esté en la memoria caché, porque el valor de c[i][j] de la iteración anterior probablemente también esté en la memoria caché y listo para ser leído. Del mismo modo, b[k][j] probablemente está almacenado en la memoria caché, y dado que i y k no están cambiando, es probable que a[i][k] esté almacenado en la memoria caché. Esto significa que en cada iteración del ciclo interno, es probable que no tenga errores de caché.
En general, esto significa que es improbable que la segunda versión del código tenga omisiones de caché en cada iteración del ciclo, mientras que la primera versión casi seguro lo hará. En consecuencia, es probable que el segundo ciclo sea más rápido que el primero, como has visto.
Curiosamente, muchos compiladores están comenzando a tener soporte de prototipo para detectar que la segunda versión del código es más rápida que la primera. Algunos intentarán reescribir automáticamente el código para maximizar el paralelismo. Si tiene una copia del Purple Dragon Book, el Capítulo 11 explica cómo funcionan estos compiladores.
Además, puede optimizar el rendimiento de este bucle aún más utilizando bucles más complejos. Una técnica llamada blocking, por ejemplo, puede usarse para aumentar notablemente el rendimiento dividiendo la matriz en subregiones que pueden mantenerse en caché durante más tiempo, y luego usando múltiples operaciones en estos bloques para calcular el resultado global.
Espero que esto ayude!
+1 ¡Gran explicación! También la sugerencia @Kerrek SB sobre la depuración de la memoria caché agrega muchos más detalles técnicos. – rbaleksandar