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

Nada que ver con el montaje. Esto se debe a que la caché falla.

C Los arrays multidimensionales se almacenan con la última dimensión como la más rápida. Así que la primera versión perderá la caché en cada iteración, mientras que la segunda versión no lo hará.

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

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

Versión 1, por otro lado, está accediendo a los elementos en sentido de columna, y no en sentido 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 en caché. En el segundo programa que está escaneando linealmente a través de la memoria que se beneficia de almacenamiento en caché y prefetching. El patrón de uso de memoria de su primer programa está mucho más extendido y, por lo tanto, tiene un peor comportamiento de caché.

Además de las otras excelentes respuestas en cache hits, 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, porque necesitaría incrementar el puntero "p" con 4000 cada vez.

EDITAR: p++ e incluso *p++ = .. se puede compilar a una sola instrucción de CPU en la mayoría de las CPU. *p = ..; p += 4000 no se puede, por lo que hay menos beneficio en optimizarla. Es también 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 una prioridad.

Esta línea el culpable :

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

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

Lo intenté con

x[50000][50000];

Y el tiempo de ejecución es 13s para la versión 1 versus 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 clásico int P[3]; 0[P] = 0xBEEF;).

Al iterar sobre y, itera 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 trozos.

Al voltear el orden, 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 really old x86-CPUs esto no importaba mucho, hoy en día ' x86 hacer una gran cantidad de prefetching y almacenamiento en caché de datos. Es probable que produzca muchos errores de caché en su orden de iteración más lento.