为什么逐列复制2D数组比C中的逐行复制？

Question

#include <stdio.h>
#include <time.h>

#define N  32768

char a[N][N];
char b[N][N];

int main() {
    int i, j;

    printf("address of a[%d][%d] = %p\n", N, N, &a[N][N]);
    printf("address of b[%5d][%5d] = %p\n", 0, 0, &b[0][0]);

    clock_t start = clock();
    for (j = 0; j < N; j++)
        for (i = 0; i < N; i++)
            a[i][j] = b[i][j];
    clock_t end = clock();
    float seconds = (float)(end - start) / CLOCKS_PER_SEC;
    printf("time taken: %f secs\n", seconds);

    start = clock();
    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
            a[i][j] = b[i][j];
    end = clock();
    seconds = (float)(end - start) / CLOCKS_PER_SEC;
    printf("time taken: %f secs\n", seconds);

    return 0;
}

输出:

address of a[32768][32768] = 0x80609080
address of b[    0][    0] = 0x601080
time taken: 18.063229 secs
time taken: 3.079248 secs

为什么逐列复制所需的行数几乎是逐行复制的6倍？我知道2D数组基本上是一个nxn大小的数组,其中A [i] [j] = A [i*n + j],但是使用简单的代数,我计算出一个图灵机头(在主内存上)必须要去旅行距离在这两种情况下.这里nxn是数组的大小,x是第一个数组的最后一个元素和第二个数组的第一个元素之间的距离.

Answer 1

它几乎归结为这个图像(来源):

访问数据时,CPU不仅会加载单个值,还会将相邻数据加载到CPU的L1缓存中.在逐行迭代数组时,自动加载到缓存中的项实际上是接下来处理的项.但是,当您按列进行迭代时,每次加载整个"缓存行"数据(每个CPU的大小不同)时,只使用一个项目,然后必须加载下一行,从而有效地使缓存无意义.

在维基百科的条目和,作为一个高层次的概述,这PDF应该帮助你了解CPU的缓存是如何工作的.

编辑:评论中的chqrlie当然是正确的.这里的一个相关因素是,只有极少数列同时适合L1缓存.如果您的行要小得多(比如,二维数组的总大小只有几千字节),那么您可能看不到迭代每列的性能影响.

Answer 2

虽然通常将数组绘制为矩形，但数组元素在内存中的寻址是线性的：0 到 1 减去可用字节数（几乎在所有机器上）。

内存层次结构（例如，寄存器 < L1 缓存 < L2 缓存 < RAM < 磁盘上的交换空间）针对内存访问本地化的情况进行了优化：时间上连续的访问接触靠近的地址。它们针对地址线性顺序的顺序访问进行了更高程度的优化（例如，使用预取策略）；例如 100,101,102...

在 C 中，矩形数组通过连接所有行按线性顺序排列（其他语言如 FORTRAN 和 Common Lisp 则连接列）。因此，读取或写入数组的最有效方法是读取第一行的所有列，然后逐行移动到其余列。

如果您向下查看列，则连续触摸相隔 N 个字节，其中 N 是一行中的字节数：100、10100、20100、30100...对于 N=10000 字节的情况。那么第二列是 101 ,10101、20101 等。对于大多数缓存方案来说，这绝对是最坏的情况。

在最坏的情况下，每次访问都可能导致页面错误。如今，即使在一台普通机器上，也需要一个巨大的数组才能实现这一点。但如果发生这种情况，每次触摸都会花费约 10 毫秒的头部搜索时间。顺序访问每次需要几纳秒。这相差超过一百万倍。在这种情况下，计算实际上停止了。它有一个名字：磁盘抖动。

在更正常的情况下，仅涉及缓存错误，而不涉及页面错误，您可能会看到系数为 100。还是值得关注的。