为什么糟糕的初始化像这样的二维数组？(Why is it worse to initialize a

for(int i = 0; i<100; i++)

    for(int j = 0; j<100; j++)

         array[j][i] = 0;
         // array[i][j] = 0;

我的教授说，这是更加昂贵的第一种方式初始化一个二维数组，而不是第二。一个人能解释这是怎么回事，这使得该情况下，发动机罩的下面？或者说，初始化的两个装置具有相同的性能？

Answer 1:

作为@dlev提到的，这是因为引用的局部性 ，并与如何在电脑正常运行的物理硬件做。

在计算机内部，有许多不同类型的存储器。通常，只有某些存储器位置（寄存器）可具有对它们执行实际操作; 的其余时间，如果你对数据进行操作，你必须从内存中加载到寄存器中，执行一些运算，然后将它写回。

主存储器（RAM）是多少，比寄存器慢得多，往往由几百到几千倍。因此，从内存中读取应尽量避免，如果在所有可能的。为了解决这个问题，大多数计算机通常具有的记忆称为特殊区域的高速缓存。缓存的工作是认为，最近已经从内存中存取数据，以便如果同样的存储区再次访问，值可以从缓存（快）拉，而不是从主内存（慢）。通常，高速缓存被设计为使得如果一个值从存储器，该值，加上一大堆相邻值的读入，被拉入高速缓存中。这样，如果你遍历数组，然后读取第一个值后，该值从阵列的其余部分将坐在缓存，可以更有效地访问。

您的代码是慢于它需要的原因是，它不按顺序访问各数组元素。在C中，2D阵列在布置行优先顺序，这意味着存储器被安排为

A[0][0] A[0][4] A[0][5] ... A[1][0] A[1][6] A[1][7] ... A[2][0] A[2][8] A[2][9] ...

因此，如果你用这个循环：

for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
        // Do something with A[i][j]
    }
}

然后你得到优秀的地方，因为你将访问在它们出现在内存中的顺序数组元素。这使得读取数主内存非常小的，因为一切是典型的高速缓存，并准备去。

但是，如果您交换的循环，因为你所做的，你访问跳来跳去在内存中，并不一定是连续的。这意味着，你将有很多的高速缓存未命中的在你下一次读取的存储器地址不在缓存中。这增加了缓存负载的数量，可在节目显着放缓。

编译器开始变得足够聪明的自动交换这样的循环，但我们仍然是一个办法远离能够忽略这些细节。作为一般规则，写C或C ++多维数组的代码时，尝试以行优先顺序，而不是列优先的顺序进行迭代。你可以在你的程序获得显着的速度提升。

希望这可以帮助！

Answer 2:

我可能会得到downvoted这一点，但如果你是编程C，那么“最好”是最有可能的：

memset的（阵列，0，的sizeof（阵列））;

然后，你可以推迟优化的所有责任（你显然是担心），以memset的实施。任何特定的硬件优势，可以在那里完成。

http://en.wikipedia.org/wiki/Sizeof#Using_sizeof_with_arrays/

http://www.cplusplus.com/reference/clibrary/cstring/memset/

另一种看法是，如果你是init'ing为零，问自己，为什么？如果阵列是静态的（这对于这个大它可能是？），然后将CSTARTUP初始化为零你。同样，这可能会使用您的硬件最有效的方式。

Answer 3:

我有点迟到了，并且有一个很好的答案了。不过，我想我可以通过展示一个如何回答这个问题，实验使用分析工具（在Linux上）做出贡献。

我将使用perf在Ubuntu 10.10包装工具linux-tools-common 。

下面是我写来回答这个问题小C程序：

// test.c
#define DIM 1024

int main()
{
    int v[DIM][DIM];
    unsigned i, j;

    for (i = 0; i < DIM; i++) {
        for (j = 0; j < DIM; j++) {
#ifdef ROW_MAJOR_ORDER
            v[i][j] = 0;
#else
            v[j][i] = 0;
#endif
        }
    }

    return 0;
}

然后编译两个不同的版本：

$ gcc test.c -O0 -DROW_MAJOR_ORDER -o row-maj
$ gcc test.c -O0 -o row-min

注意：我已禁用的优化与-O0所以GCC有没有机会重新安排我们的循环更有效率。

我们可以列出可用的性能统计信息perf做perf list 。在这种情况下，我们感兴趣的是高速缓存未命中是事件cache-misses 。

现在，作为运行程序无数次的各个版本，并取平均值作为简单：

$ perf stat -e cache-misses -r 100 ./row-min

 Performance counter stats for './row-min' (100 runs):

             286468  cache-misses               ( +-   0.810% )

        0.016588860  seconds time elapsed   ( +-   0.926% )

$ perf stat -e cache-misses -r 100 ./row-maj

 Performance counter stats for './row-maj' (100 runs):

               9594  cache-misses               ( +-   1.203% )

        0.006791615  seconds time elapsed   ( +-   0.840% )

而现在我们已经实验验证，你其实看多级高速缓存未命中的两个命令与“行小调”版本。