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

Question

Mar 30, 2012, 04:17 AM

performance optimization c for-loop cpu-cache

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

Abajo hay dos programas que son casi idénticos, excepto que cambié lai yj variables alrededor. Ambos corren en diferentes cantidades de tiempo. ¿Alguien podría explicar por qué sucede esto?

Versión

#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

#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; }
   }
}