为什么迭代二维数组行优先比列优先更快？

下面是简单的 C++ 代码，用于比较迭代二维数组行主要与列主要。

#include <iostream>
#include <ctime>

using namespace std;

const int d = 10000;

int** A = new int* [d];

int main(int argc, const char * argv[]) {
    for(int i = 0; i < d; ++i)
        A[i] = new int [d];
    
    clock_t ColMajor = clock();
    
    for(int b = 0; b < d; ++b)
        for(int a = 0; a < d; ++a)
            A[a][b]++;
    
    double col = static_cast<double>(clock() - ColMajor) / CLOCKS_PER_SEC;
    
    clock_t RowMajor = clock();
    for(int a = 0; a < d; ++a)
        for(int b = 0; b < d; ++b)
            A[a][b]++;
    
    double row = static_cast<double>(clock() - RowMajor) / CLOCKS_PER_SEC;
    

    
    cout << "Row Major : " << row;
    cout << "\nColumn Major : " << col;

    return 0;
}

不同值的结果d:

d = 10^3 :

行专业：0.002431

列专业：0.017186

d = 10^4 :

行专业：0.237995

列专业：2.04471

d = 10^5

行专业：53.9561

栏目专业：444.339

现在的问题是为什么行专业比列专业更快？

这显然取决于您所使用的机器，但一般来说：

1. 您的计算机将部分程序内存存储在缓存中，该缓存的延迟比主内存小得多（即使在补偿缓存命中时间时也是如此）。

2. C 数组按行主顺序连续存储。这意味着如果您要求元素x，然后元素x+1存储在主存储器中紧随其后的位置x被储存了。

3. 计算机缓存通常会“抢先”使用尚未使用但本地接近程序已使用的内存的内存地址填充缓存。想象一下你的计算机在说：“好吧，你想要地址 X 处的内存，所以我假设你很快就会想要 X+1 处的内存，因此我会抢先为你获取该内存并将其放入你的缓存中” 。

当您通过行主序枚举数组时，您是以连续方式存储在内存中的方式枚举它，并且您的机器已经为您预先将这些地址加载到缓存中because它猜你想要它。因此，您可以获得更高的缓存命中率。当您以另一种非连续方式枚举数组时，您的机器可能无法预测您正在应用的内存访问模式，因此它无法为您预先将内存地址拉入缓存，并且您将无法不会产生那么多的缓存命中，因此必须更频繁地访问主内存，这比缓存慢。

另外，这可能更适合https://cs.stackexchange.com/ https://cs.stackexchange.com/因为系统缓存的行为方式是在硬件中实现的，空间局部性问题似乎更适合那里。