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

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

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

我的教授说，与第二种方式相比，以第一种方式初始化二维数组的成本要高得多。有人可以解释导致这种情况的引擎盖下发生了什么吗？或者，这两种初始化方式是否具有相同的性能？

4

4 回答 4

23

正如@dlev 提到的，这是由于参考的局部性，并且与计算机中物理硬件的工作方式有关。

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

主存储器 (RAM) 比寄存器慢得多，通常要慢数百到数千倍。因此，应尽可能避免从内存中读取。为了解决这个问题，大多数计算机通常具有称为缓存的特殊内存区域。缓存的工作是保存最近从内存中访问过的数据，这样如果再次访问相同的内存区域，则可以从缓存中（快速）而不是从主内存（慢）中提取值。通常，缓存的设计是这样的，如果从内存中读取一个值，则该值加上一大堆相邻的值被拉入缓存。这样，如果您遍历数组，则在读取第一个值之后，数组中的其余值将位于缓存中，并且可以更有效地访问。

您的代码比它需要的慢的原因是它没有按顺序访问数组元素。在 C 中，二维数组以行优先顺序排列，这意味着内存排列为

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 循环：

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

然后您将获得极好的局部性，因为您将按照数组元素在内存中出现的顺序访问它们。这使得主内存的读取次数非常少，因为所有内容通常都在缓存中并准备就绪。

但是，如果您像您所做的那样交换循环，您的访问会在内存中跳转并且不一定是连续的。这意味着您将有很多缓存未命中，其中您接下来读取的内存地址不在缓存中。这会增加缓存加载的数量，这会大大降低程序的速度。

编译器开始变得足够聪明，可以自动交换这样的循环，但我们距离忽略这些细节还有很长的路要走。作为一般规则，在为多维数组编写 C 或 C++ 代码时，请尝试以行优先顺序而不是列优先顺序进行迭代。您可以在程序中获得明显的加速。

希望这可以帮助！

于 2012-06-22T00:13:33.133 回答
4

我可能会因此而被否决，但是如果您正在编写 C 语言，那么“最好的”很可能是：

memset（数组，0，sizeof（数组））；

然后，您可以将所有优化（您显然担心）的责任推迟到 memset 的实现上。任何特定的硬件优势都可以在那里实现。

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

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

另一个观察是，如果你初始化为零，问问自己为什么？如果您的数组是静态的（对于这么大的可能是哪个？），那么 cstartup 将为您初始化为零。同样，这可能会为您的硬件使用最有效的方式。

于 2012-06-22T01:26:46.463 回答
4

我参加聚会有点晚了，已经有一个很好的答案。但是，我认为我可以通过演示如何使用分析工具（在 Linux 上）通过实验回答这个问题来做出贡献。

我将使用perfUbuntu 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% )

现在我们已经通过实验验证，您确实看到“row-minor”版本的缓存未命中率增加了两个数量级。

于 2012-07-10T14:38:08.193 回答
2

如果您查看每种技术访问的内存位置，第二个将访问连续字节，而第一个将跳跃 100 个字节。如果您采用第二种方式，内存缓存的工作效率会更高。

于 2012-06-22T00:13:54.387 回答