¿Por qué el orden de los bucles afecta el rendimiento cuando se itera sobre una matriz 2D?

A continuación hay dos programas que son casi idénticos excepto que cambié el i y j variables alrededor. Ambos se ejecutan en diferentes cantidades de tiempo. ¿Alguien podría explicar por qué sucede esto?

Versión 1

#include <stdio.h>
#include <stdlib.h>

main () {
  int i,j;
  static int x[4000][4000];
  for (i = 0; i < 4000; i++) {
    for (j = 0; j < 4000; j++) {
      x[j][i] = i + j; }
  }
}

Versión 2

#include <stdio.h>
#include <stdlib.h>

main () {
  int i,j;
  static int x[4000][4000];
  for (j = 0; j < 4000; j++) {
     for (i = 0; i < 4000; i++) {
       x[j][i] = i + j; }
   }
}

Como han dicho otros, el problema es el almacenamiento en la ubicación de la memoria en la matriz: x[i][j]. Aquí hay una pequeña idea de por qué:

Tiene una matriz bidimensional, pero la memoria en la computadora es inherentemente unidimensional. Entonces, mientras imagina su matriz así:

0,0 | 0,1 | 0,2 | 0,3
----+-----+-----+----
1,0 | 1,1 | 1,2 | 1,3
----+-----+-----+----
2,0 | 2,1 | 2,2 | 2,3

Su computadora lo almacena en la memoria como una sola línea:

0,0 | 0,1 | 0,2 | 0,3 | 1,0 | 1,1 | 1,2 | 1,3 | 2,0 | 2,1 | 2,2 | 2,3

En el segundo ejemplo, accede a la matriz pasando primero por el segundo número, es decir:

x[0][0] 
        x[0][1]
                x[0][2]
                        x[0][3]
                                x[1][0] etc...

Lo que significa que los estás golpeando a todos en orden. Ahora mira la primera versión. Estás haciendo:

x[0][0]
                                x[1][0]
                                                                x[2][0]
        x[0][1]
                                        x[1][1] etc...

Debido a la forma en que C dispuso la matriz bidimensional en la memoria, le estás pidiendo que salte por todos lados. Pero ahora el truco: ¿Por qué importa esto? Todos los accesos a la memoria son iguales, ¿verdad?

No: por los cachés. Los datos de su memoria se transfieren a la CPU en pequeños fragmentos (llamados “líneas de caché”), generalmente de 64 bytes. Si tiene enteros de 4 bytes, eso significa que está obteniendo 16 enteros consecutivos en un paquete pequeño y ordenado. En realidad, es bastante lento recuperar estos fragmentos de memoria; su CPU puede hacer mucho trabajo en el tiempo que tarda en cargarse una sola línea de caché.

Ahora mire hacia atrás en el orden de los accesos: El segundo ejemplo es (1) tomar un trozo de 16 entradas, (2) modificarlas todas, (3) repetir 4000*4000/16 veces. Eso es bueno y rápido, y la CPU siempre tiene algo en lo que trabajar.

El primer ejemplo es (1) tomar un trozo de 16 entradas, (2) modificar solo una de ellas, (3) repetir 4000*4000 veces. Eso requerirá 16 veces el número de “obtenciones” de la memoria. Su CPU realmente tendrá que pasar tiempo sentado esperando que aparezca esa memoria, y mientras está sentado, está perdiendo un tiempo valioso.

Nota IMPORTANTE:

Ahora que tiene la respuesta, aquí hay una nota interesante: no hay una razón inherente por la que su segundo ejemplo tenga que ser el rápido. Por ejemplo, en Fortran, el primer ejemplo sería rápido y el segundo lento. Eso es porque en lugar de expandir las cosas en “filas” conceptuales como lo hace C, Fortran se expande en “columnas”, es decir:

0,0 | 1,0 | 2,0 | 0,1 | 1,1 | 2,1 | 0,2 | 1,2 | 2,2 | 0,3 | 1,3 | 2,3

El diseño de C se llama ‘fila principal’ y el de Fortran se llama ‘columna principal’. Como puede ver, es muy importante saber si su lenguaje de programación es de fila principal o de columna principal. Aquí hay un enlace para más información: http://en.wikipedia.org/wiki/Row-major_order

Nada que ver con el montaje. Esto es debido a fallas de caché.

Las matrices multidimensionales de C se almacenan con la última dimensión como la más rápida. Entonces, la primera versión perderá el caché en cada iteración, mientras que la segunda versión no. Entonces, la segunda versión debería ser sustancialmente más rápida.

Ver también: http://en.wikipedia.org/wiki/Loop_interchange.

La versión 2 se ejecutará mucho más rápido porque usa mejor el caché de su computadora que la versión 1. Si lo piensa bien, las matrices son solo áreas contiguas de memoria. Cuando solicita un elemento en una matriz, su sistema operativo probablemente traerá una página de memoria en el caché que contiene ese elemento. Sin embargo, dado que los siguientes elementos también están en esa página (porque son contiguos), ¡el próximo acceso ya estará en caché! Esto es lo que está haciendo la versión 2 para acelerar.

La versión 1, por otro lado, accede a los elementos en forma de columna y no en forma de fila. Este tipo de acceso no es contiguo a nivel de memoria, por lo que el programa no puede aprovechar tanto el almacenamiento en caché del sistema operativo.

El motivo es el acceso a datos locales de caché. En el segundo programa, está escaneando linealmente a través de la memoria, lo que se beneficia del almacenamiento en caché y la captación previa. El patrón de uso de memoria de su primer programa está mucho más disperso y, por lo tanto, tiene un peor comportamiento de caché.

Además de las otras excelentes respuestas sobre aciertos de caché, también existe una posible diferencia de optimización. Es probable que el compilador optimice su segundo ciclo en algo equivalente a:

for (j=0; j<4000; j++) {
  int *p = x[j];
  for (i=0; i<4000; i++) {
    *p++ = i+j;
  }
}

Esto es menos probable para el primer ciclo, porque necesitaría incrementar el puntero “p” con 4000 cada vez.

EDITAR: p++ e incluso *p++ = .. se puede compilar en una sola instrucción de CPU en la mayoría de las CPU. *p = ..; p += 4000 no puede, por lo que hay menos beneficio en optimizarlo. También es más difícil, porque el compilador necesita saber y usar el tamaño de la matriz interna. Y no ocurre tan a menudo en el ciclo interno en el código normal (ocurre solo para matrices multidimensionales, donde el último índice se mantiene constante en el ciclo y el penúltimo se escalona), por lo que la optimización es una prioridad menor. .

Esta línea el culpable:

x[j][i]=i+j;

La segunda versión usa memoria continua, por lo que será sustancialmente más rápida.

probé con

x[50000][50000];

y el tiempo de ejecución es de 13 s para la versión 1 frente a 0,6 s para la versión 2.

_{Intento dar una respuesta genérica.}

Porque i[y][x] es una abreviatura de *(i + y*array_width + x) en C (pruebe el elegante int P[3]; 0[P] = 0xBEEF;).

A medida que itera sobre yiteras sobre trozos de tamaño array_width * sizeof(array_element). Si tienes eso en tu bucle interno, entonces tendrás array_width * array_height iteraciones sobre esos fragmentos.

Al voltear el pedido, solo tendrá array_height iteraciones de fragmentos, y entre cualquier iteración de fragmentos, tendrá array_width iteraciones de solo sizeof(array_element).

Mientras que en las CPU x86 realmente antiguas esto no importaba mucho, los x86 de hoy en día realizan una gran cantidad de búsqueda previa y almacenamiento en caché de datos. Probablemente produzca muchos fallas de caché en su orden de iteración más lento.