c++ - 为什么迭代 2D 数组行专业比列专业更快？

Question

这是比较迭代二维数组行主和列主的简单 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:

Row Major : 0.002431

Column Major : 0.017186

d = 10^4:

Row Major : 0.237995

Column Major : 2.04471

d = 10^5

Row Major : 53.9561

Column Major : 444.339

现在的问题是为什么行优先比列优先快？

Answer 1

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

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

2. C 数组以连续的行主要顺序存储。这意味着如果您请求元素 x，则元素 x+1 将存储在主内存中紧跟在 x 存储位置之后的位置。

3. 您的计算机缓存通常会“先发制人”地用尚未使用但在本地接近您的程序已使用内存的内存地址填充缓存。把你的计算机想象成这样:“好吧，你想要地址 X 的内存，所以我假设你很快就会想要 X+1 的内存，因此我会先发制人地为你抓取它并将它放入你的缓存中” .

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

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