为什么迭代 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

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

您的计算机将部分程序内存存储在缓存中，该缓存的延迟比主内存小得多（即使在补偿缓存命中时间时也是如此）。
C 数组按行主要顺序连续存储。这意味着如果您请求元素 x，那么元素 x+1 将存储在主内存中紧跟在 x 存储位置之后的位置。
您的计算机缓存通常 "pre-emptively" 使用尚未使用但在本地接近您的程序已使用内存的内存地址填充缓存。把你的电脑想象成这样："well, you wanted memory at address X so I am going to assume that you will shortly want memory at X+1, therefore I will pre-emptively grab that for you and place it in your cache".

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

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

Answer 2

您的数组实际上是一个 ragged array，因此行专业并不完全是一个因素。

您发现在列上迭代比在行上迭代性能更好，因为行内存是线性布局的，缓存预测器很容易预测顺序读取，并且您将指针取消引用分摊到第二个维度，因为它只每行需要完成一次。

当您遍历行然后遍历列时，每次迭代都会导致对第二个维度的指针取消引用。因此，通过遍历行，您将添加一个指针取消引用。除了内在成本外，它对缓存预测不利。

如果你想要一个真正的二维数组，使用行优先排序在内存中布局，你会想要...

int A[1000][1000];

这会以行优先顺序连续布置内存，而不是一个指向数组的指针数组（它们不是连续布置的）。由于空间局部性和缓存预测，使用行优先迭代此数组仍然比迭代列优先执行得更快。

Answer 3

简短的回答是 CPU 缓存。 Scott Mayers 解释得很清楚 here

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

Why is iterating 2D array row major faster than column major?

c++

arrays

compiler-construction

iteration