为什么迭代2D数组行主要比列主要更快？

Question

这是简单的C++代码,用于比较迭代的2D数组行major和column major.

#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

现在的问题是为什么row major比列major更快？

Answer 1

这显然取决于你所使用的机器,但一般来说:

1. 您的计算机将部分程序存储器存储在缓存中,该缓存的延迟小于主存储器(即使在补偿缓存命中时间时).

2. C数组按行主要顺序存储.这意味着如果您要求元素x,则元素x+1将存储在主存储器中直接x位于存储位置的位置.

3. 您的计算机缓存通常会"先发制人"使用尚未使用的内存地址填充缓存,但这些内存在本地已接近程序已使用的内存.想想你的计算机说:"好吧,你想要地址X的内存,所以我假设你很快会想要X + 1的内存,因此我会先发制人地抓住你并将其放在你的缓存中" .

因此,当你通过行major来枚举你的数组时,你会以一种连续的方式在内存中枚举它,你的机器已经自由地将这些地址预先加载到缓存中,因为它猜想你想要它.因此,您可以获得更高的缓存命中率.当你以另一种不连续的方式枚举一个数组时,你的机器很可能无法预测你正在应用的内存访问模式,所以它不能预先将内存地址拉入缓存中,而且你不会招致那么多缓存命中,因此必须更频繁地访问主内存,这比缓存慢.

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

Answer 2

你的数组实际上是一个参差不齐的数组,因此行主要不完全是一个因素.

您会看到更好的性能迭代列然后行,因为行内存是线性布局的,顺序读取很容易让缓存预测器预测,并且您将指针解引用分摊到第二维,因为它只需要执行一次每排.

当您遍历行然后遍历列时,每次迭代都会引发指向第二维的指针.因此,通过遍历行,您将添加指针取消引用.除了内在成本之外,它对缓存预测也是不利的.

如果你想要一个真正的二维数组,使用行主要排序在内存中,你会想...

int A[1000][1000];

这以行主顺序连续排列内存,而不是一个指向数组的指针数组(它们没有连续排列).使用row-major对此数组进行迭代仍然比迭代column-major执行得更快,因为空间局部性和缓存预测.