llenar - recorrer una matriz en matlab
¿Por qué el orden de los bucles afecta el rendimiento al iterar sobre una matriz 2D? (7)
Posible duplicado:
¿Cuál de estos dos para bucles es más eficiente en términos de tiempo y rendimiento de caché?
A continuación hay dos programas que son casi idénticos, excepto que cambié las variables i y j . Ambos corren en diferentes cantidades de tiempo. ¿Podría alguien 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; }
}
}
Además de las otras excelentes respuestas sobre los aciertos de caché, también existe 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 pueden compilar en una sola instrucción de CPU en la mayoría de las CPU. *p = ..; p += 4000 *p = ..; p += 4000 no puede, por lo que hay menos beneficios en la optimización. También es más difícil, porque el compilador necesita saber y usar el tamaño de la matriz interna. Y no ocurre que a menudo en el bucle interno en el código normal (ocurre solo para arreglos multidimensionales, donde el último índice se mantiene constante en el bucle, y el segundo al último es escalonado), por lo que la optimización es una prioridad menor. .
Como han dicho otros, el problema es el almacenamiento en la ubicación de la memoria en la matriz: x[i][j] . Aquí hay un poco de idea de por qué:
Tiene una matriz bidimensional, pero la memoria en la computadora es inherentemente unidimensional. Así que mientras imaginas tu matriz como esta:
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 haciendo un bucle sobre el segundo número primero, es decir:
x[0][0]
x[0][1]
x[0][2]
x[0][3]
x[1][0] etc...
Lo que significa que 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 colocó la matriz 2-d en la memoria, le está pidiendo que salte por todos lados. Pero ahora para el pateador: ¿Por qué esto importa? Todos los accesos de memoria son los mismos, ¿verdad?
No: debido a los cachés. Los datos de su memoria se transfieren a la CPU en pequeñas porciones (llamadas ''líneas de caché''), generalmente 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 trozos de memoria; su CPU puede hacer mucho trabajo en el tiempo que tarda en cargarse una única línea de caché.
Ahora mire hacia atrás en el orden de accesos: el segundo ejemplo es (1) tomar una porción de 16 pulgadas, (2) modificarlos todos, (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) agarrar un trozo de 16 pulgadas, (2) modificar solo uno de ellos, (3) repetir 4000 * 4000 veces. Eso va a requerir 16 veces el número de "capturas" de la memoria. Tu CPU realmente tendrá que pasar tiempo sentado esperando a que aparezca esa memoria, y mientras está sentado estás perdiendo un tiempo valioso.
Nota IMPORTANTE:
Ahora que tiene la respuesta, aquí hay una nota interesante: no hay ninguna razón inherente para que su segundo ejemplo sea el más 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-mayor'' y el de Fortran se llama ''columna-mayor''. Como puede ver, es muy importante saber si su lenguaje de programación es importante en la fila o en la columna principal. Aquí hay un enlace para obtener más información: http://en.wikipedia.org/wiki/Row-major_order
El motivo es el acceso a datos de caché local. En el segundo programa, está escaneando linealmente a través de la memoria, lo que se beneficia del almacenamiento en caché y la captura previa. 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é.
Esta línea el culpable:
x[j][i]=i+j;
La segunda versión utiliza memoria continua, por lo tanto será sustancialmente más rápida.
Lo intenté con
x[50000][50000];
y el tiempo de ejecución es de 13 segundos para la versión 1 frente a 0,6 para la versión 2.
La versión 2 se ejecutará mucho más rápido porque utiliza el caché de su computadora mejor que la versión 1. Si lo piensa, los arreglos son solo áreas contiguas de la memoria. Cuando solicite 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 acelerar su velocidad.
La versión 1, por otro lado, está accediendo a los elementos de la columna y no de la fila. Este tipo de acceso no es contiguo en el nivel de memoria, por lo que el programa no puede aprovechar tanto el almacenamiento en caché del sistema operativo.
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. Por lo tanto, la primera versión perderá el caché en cada iteración, mientras que la segunda versión no lo hará. Así que la segunda versión debería ser sustancialmente más rápida.
Véase también: http://en.wikipedia.org/wiki/Loop_interchange .
Intento dar una respuesta genérica.
Debido a que i[y][x] es una abreviatura de *(i + y*array_width + x) en C (pruebe el classy int P[3]; 0[P] = 0xBEEF; ).
A medida que itera sobre y , itera sobre trozos de tamaño array_width * sizeof(array_element) . Si tiene eso en su bucle interno, entonces tendrá array_width * array_height sobre esos trozos.
Al cambiar el orden, solo tendrá una array_height de iteraciones de trozos de array_height , y entre cualquier parte de iteración, tendrá array_width iteraciones de array_width de array_width único sizeof(array_element) .
Si bien en las x86 CPU realmente antiguas esto no importaba mucho, en la actualidad el x86 realiza muchas tareas de precarga y almacenamiento en caché de datos. Es probable que produzca muchos errores de caché en su orden de iteración más lento.