Ejecución del programa Speed ​​of C

Question

Tengo un problema en mi examen de la asignatura Principal of Programming Language. Me pareció que por mucho tiempo, pero yo todavía no entendía el problema

Problema: A continuación se muestra un programa en C, que se ejecuta en MSVC++ entorno 6.0 en un PC de configuración ~ CPU Intel a 1,8 GHz, 512 MB de RAM

#define M 10000 
#define N 5000 
int a[M][N]; 

void main() { 
    int i, j; 
    time_t start, stop; 

    // Part A 
    start = time(0); 
    for (i = 0; i < M; i++) 
     for (j = 0; j < N; j++) 
      a[i][j] = 0; 
    stop = time(0); 
    printf("%d\n", stop - start); 

    // Part B 
    start = time(0); 
    for (j = 0; j < N; j++) 
     for (i = 0; i < M; i++) 
      a[i][j] = 0; 
    stop = time(0); 
    printf("%d\n", stop - start); 
} 

Explique por qué la parte A solo se ejecuta en 1s, pero tomó la parte B 8s para finalizar?

Answer 1

orden de fila mayor contra orden de columna mayor.

Recuerde primero que todas las matrices multidimensionales se representan en la memoria como un bloque de memoria contiguo. Así, la matriz multidimensional A (m, n) podría estar representado en la memoria como

a00 a01 a02 a10 a11 ... A0N a12 ... A1N a20 ... AMN

en el primer bucle, se ejecuta a través de este bloque de memoria secuencialmente. Por lo tanto, se ejecuta a través de la matriz que atraviesa los elementos en el siguiente orden

a00 a01 a02 ... a0n a10 a11 a12 ... a1n a20 ... amn 

1 2 3   n n+1 n+2 n+3 ... 2n 2n+1 mn 

En el segundo bucle, se salta alrededor en la memoria y ejecuta a través de la matriz que atraviesa los elementos en el siguiente orden

a00 a10 a20 ... am0 a01 a11 a21 ... am1 a02 ... amn 

o, tal vez con mayor claridad,

a00 a01 a02 ... a10 a11 a12 ... a20 ... amn 
1 m+1 2m+1  2 m+2 2m+2  3  mn 

Todo lo que saltar alrededor realmente le duele porque no se gana ventajas del almacenamiento en caché. Cuando ejecuta secuencialmente la matriz, los elementos vecinos se cargan en la memoria caché. Cuando saltas la matriz, no obtienes estos beneficios y, en cambio, obtienes errores de caché que perjudican el rendimiento.

Answer 2

Debido a las optimizaciones arquitectónicas de hardware. La Parte A está ejecutando operaciones en direcciones de memoria secuenciales, lo que permite que el hardware acelere sustancialmente la forma en que se manejan los cálculos. La Parte B básicamente está saltando en la memoria todo el tiempo, lo que frustra muchas optimizaciones de hardware.

El concepto clave para este caso específico es processor cache.

Answer 3

Esto tiene que ver con cómo se distribuye la memoria de la matriz y cómo se carga en la memoria caché y se accede: en la versión A, al acceder a una celda de la matriz, los vecinos se cargan con ella en la memoria caché y el código luego accede de inmediato a esos vecinos. En la versión B, se accede a una celda (y sus vecinos se cargan en la memoria caché), pero el siguiente acceso está muy lejos, en la siguiente fila, y así se cargó toda la línea de caché pero solo se utilizó un valor, y otra línea de caché debe llenarse para cada acceso. De ahí la diferencia de velocidad.

Answer 4

La matriz que está declarando se presenta en línea en la memoria. Básicamente tienes un bloque grande de enteros M × N y C hace un pequeño truco para hacerte creer que es rectangular. Pero en realidad es plano.

Por lo tanto, cuando lo itera en línea (con M como la variable de bucle externo), entonces va realmente linealmente a través de la memoria. Algo que la memoria caché de la CPU maneja muy bien.

Sin embargo, cuando itera con N en el bucle externo, siempre está realizando saltos más o menos aleatorios en la memoria (al menos para el hardware se ve así). Está accediendo a la primera celda, luego mueve M enteros más y hace lo mismo, etc. Dado que sus páginas en la memoria son generalmente de alrededor de 4 KiB, esto hace que se acceda a otra página para cada iteración del ciclo interno. De esta manera, casi cualquier estrategia de almacenamiento en caché falla y ve una gran desaceleración.

Answer 5

El problema está aquí, cómo su matriz está puesta en la memoria.

En la memoria del ordenador, las matrices son normalmente asignados tal como, que las primeras todas las columnas de la primera fila se desconchaba, a continuación de la segunda fila y así sucesivamente.

La memoria de su computadora se ve mejor como una larga franja de bytes: es una matriz unidimensional de memoria, no bidimensional, por lo que las matrices multidimensionales deben asignarse de la manera descrita.

Ahora viene un problema adicional: las CPU modernas tienen cachés. Tienen múltiples cachés y tienen las llamadas "cache-lines" para el caché de primer nivel. Qué significa esto. El acceso a la memoria es rápido, pero no lo suficientemente rápido. Las CPU modernas son mucho más rápidas. Entonces tienen sus cachés en el chip que aceleran las cosas. Además, ya no acceden a ubicaciones de memoria única, pero llenan una línea de caché completa en una sola búsqueda. Esto también es para el rendimiento. Pero este comportamiento otorga a todas las operaciones ventajas que procesan datos linealmente. Cuando accede primero a todas las columnas de una fila, luego a la siguiente fila y así sucesivamente, de hecho está trabajando linealmente. Cuando procesa por primera vez todas las primeras columnas de todas las filas, "salta" en la memoria. Por lo tanto, siempre forzará que se llene una nueva línea de caché, solo se pueden procesar algunos bytes, entonces la línea de caché posiblemente se invalide en su siguiente salto ...

Por lo tanto, el orden de la columna principal es malo para procesadores modernos, ya que no funciona linealmente.