为什么循环的顺序会影响2D数组的迭代性能？

Question

为什么循环的顺序会影响2D数组的迭代性能？

下面是两个几乎相同的程序，除了我切换了i和j变量在附近。它们都在不同的时间里运行。有人能解释一下为什么会这样吗？

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

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

Answer 1

和集会无关。这是因为缓存丢失.C多维数组的存储速度最快。因此，第一个版本在每次迭代时都会错过缓存，而第二个版本则不会，因此第二个版本应该更快。另见：http://en.wikipedia.org/wiki/Loop_interchange.

Answer 2

版本2的运行速度要快得多，因为它比版本1更好地使用了计算机的缓存。当您请求数组中的元素时，操作系统可能会将一个内存页引入包含该元素的缓存中。但是，由于接下来的几个元素也在页面上(因为它们是连续的)，下一个访问将已经在缓存中了！这是第二版正在做的，以加快它的速度。另一方面，版本1是按列访问元素，而不是按行访问元素。这种访问在内存级别并不是连续的，因此程序无法充分利用OS缓存。