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

360

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; }
   }
}
marca
fuente
26
en.wikipedia.org/wiki/…
Brendan Long
77
¿Puedes agregar algunos resultados de referencia?
naught101
3
Relacionado: stackoverflow.com/questions/9888154/…
Thomas Padron-McCarthy
14
@ naught101 Los puntos de referencia mostrarán una diferencia de rendimiento de entre 3 y 10 veces. Esto es básico C / C ++, estoy completamente perplejo de cómo esto obtuvo tantos votos ...
TC1
12
@ TC1: No creo que sea tan básico; Quizás intermedio. Pero no debería sorprendernos que las cosas "básicas" tienden a ser útiles para más personas, de ahí los muchos votos positivos. Además, esta es una pregunta difícil de google, incluso si es "básica".
LarsH

Respuestas:

595

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

Robert Martin
fuente
14
Esta es una respuesta bastante completa; es lo que me enseñaron cuando se trata de errores de caché y administración de memoria.
Makoto
77
Tiene las versiones "primera" y "segunda" en el sentido incorrecto; El primer ejemplo varía el primer índice en el bucle interno, y será el ejemplo de ejecución más lento.
caf
Gran respuesta. Si Mark quiere leer más acerca de esa cuestión, recomendaría un libro como Write Great Code.
wkl
8
Puntos de bonificación por señalar que C cambió el orden de las filas de Fortran. Para la computación científica, el tamaño de la caché L2 lo es todo porque si todas sus matrices se ajustan a L2, la computación puede completarse sin ir a la memoria principal.
Michael Shopsin
68

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 .

Oliver Charlesworth
fuente
23

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.

Oleksi
fuente
Con estos tamaños de matriz, probablemente el administrador de caché en la CPU en lugar de en el sistema operativo es el responsable aquí.
krlmlr
12

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.

Codificador de longitud variable
fuente
11

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 .

fishinear
fuente
No entiendo qué 'porque necesitaría saltar el puntero "p" con 4000 cada vez' significa.
Veedrac
@Veedrac El puntero debería incrementarse con 4000 dentro del bucle interno: p += 4000isop++
fishinear
¿Por qué el compilador encontraría eso un problema? iya se incrementa en un valor no unitario, dado que es un incremento de puntero.
Veedrac
He agregado más explicaciones
fishinear
Intenta escribir int *f(int *p) { *p++ = 10; return p; } int *g(int *p) { *p = 10; p += 4000; return p; }en gcc.godbolt.org . Los dos parecen compilar básicamente lo mismo.
Veedrac
7

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.

Nicolas Modrzyk
fuente
4

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.

Sebastian Mach
fuente