¿Por qué el orden de los bucles afecta el rendimiento al iterar sobre una matriz 2D?

A continuación hay dos programas que son casi idénticos, excepto que cambié las variables iy j. Ambos corren 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 otros han dicho, la cuestión es la tienda a la posición de memoria en la matriz: x[i][j]. Aquí hay una idea de por qué:

Tiene una matriz bidimensional, pero la memoria en la computadora es inherentemente unidimensional. Entonces, mientras imaginas tu 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 al recorrer primero 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 presentó la matriz de 2-d en la memoria, le está pidiendo que salte por todo el lugar. Pero ahora para el pateador: ¿Por qué importa esto? Todos los accesos a la memoria son iguales, ¿verdad?

No: por cachés. Los datos de su memoria se transfieren a la CPU en pequeños fragmentos (llamados 'líneas de caché'), generalmente 64 bytes. Si tiene enteros de 4 bytes, eso significa que está obteniendo 16 enteros consecutivos en un pequeño paquete ordenado. En realidad, es bastante lento obtener estos trozos de memoria; su CPU puede hacer mucho trabajo en el tiempo que tarda en cargar 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 ints, (2) modificarlos todos, (3) repetir 4000 * 4000/16 veces. Eso es bueno y rápido, y la CPU siempre tiene algo en qué trabajar.

El primer ejemplo es (1) tomar un trozo de 16 pulgadas, (2) modificar solo uno de ellos, (3) repetir 4000 * 4000 veces. Eso requerirá 16 veces el número de "recuperaciones" de la memoria. Su CPU realmente tendrá que pasar tiempo sentado esperando a 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 para que su segundo ejemplo tenga que ser 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 'row-major' y Fortran's se llama 'column-major'. Como puede ver, ¡es muy importante saber si su lenguaje de programación es mayor de fila o mayor de columna! Aquí hay un enlace para obtener más información: http://en.wikipedia.org/wiki/Row-major_order

Nada que ver con el montaje. Esto se debe a errores de caché .

Las matrices multidimensionales 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 la memoria caché de su computadora mejor que la versión 1. Si lo piensa, los arreglos son solo áreas contiguas de memoria. Cuando solicita un elemento en una matriz, su sistema operativo probablemente traerá una página de memoria al 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 acelerarlo.

La versión 1, por otro lado, está accediendo a los elementos en columna, y no en 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 en 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 extendido y, por lo tanto, tiene un comportamiento de caché peor.

Además de las otras excelentes respuestas sobre los éxitos de caché, también hay una posible diferencia de optimización. Es probable que el compilador optimice su segundo bucle 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 bucle, ya que 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 += 4000no 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 bucle interno en el código normal (ocurre solo para matrices multidimensionales, donde el último índice se mantiene constante en el bucle, y el penúltimo se escalona), por lo que la optimización es menos prioritaria .

Esta línea el culpable:

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

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

Lo intenté con

x[50000][50000];

y el tiempo de ejecución es 13 segundos para la versión 1 versus 0.6 segundos para la versión 2.

_{Intento dar una respuesta genérica.}

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

A medida que itera y, itera sobre trozos de tamaño array_width * sizeof(array_element). Si tiene eso en su bucle interno, tendrá array_width * array_heightiteraciones sobre esos fragmentos.

Al cambiar el orden, solo tendrá array_heightiteraciones de fragmentos, y entre cualquier iteración de fragmentos, solo tendrá array_widthiteraciones sizeof(array_element).

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