为什么循环的顺序会影响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缓存。