c++ - 处理连续 block 与非连续内存块时的效率

Question

我有一个结构

struct A
{
int v[10000000];
};

如果我有 A a[2]; 并希望计算值的总和，这两种方法中哪种方法最快？

int method_1(const A &a[],int length)
{
int total = 0;
for(int i=0;i<length;i++)
for(int j=0;j<10000000;j++)
total+=a[i][j];

return total;
}


int method_2(const A &a[],int length)
{
int total = 0;
for(int j=0;j<10000000;j++)
for(int i=0;i<length;i++)
total+=a[i][j];

return total;
}

a[2] 被声明为结构 A 的两个连续 block :

----a[0]----/--- a[1]----

[][][][][][][][]/[][][][][][][][]

所以，我可能会想说 method_1 更快，这是基于 block 是连续的直觉，并且每个 block 的 v 的迭代也是连续的。

我真正感兴趣的是内存是如何被真正访问的，以及如何访问它是最有效的方式。

编辑

我已经将 v 的大小从 32 更改为 10000000，因为很明显，我指的是一般情况

Answer 1

每次读取内存片段时，整个缓存行都会从主内存读取到 CPU 缓存，今天您可能有 32 字节长的缓存行。主要是因为这种读取连续内存块的速度很快。

现在有不止一个缓存行...

在您的情况下，这两种情况可能具有相似的性能，因为两个数组很可能不会碰撞到同一缓存行中，因此两者可能位于不同行的缓存中，因此我怀疑性能会相似。

在这种情况下，您可能会考虑改变性能的一个相关因素是不使用 [] 运算符，而是使用像这样的“迭代器”进行更多迭代:

int method_1(const A &a[],int length)
{
    int total = 0;
    for(const A* aIt=a;aIt<a+length;++aIt)
        for(const v* vIt=aIt->v;vIt<aIt->v+10000000;++vIt)
            total+=*vIt;

    return total;
}

这样您就可以避免使用 double []，它只是乘以数组元素的 sizeof(它可能会被优化，但可能不会，如果不是，那么在调用数百万次时会很昂贵)。你的编译器可能足够聪明来优化代码，就像我展示的只使用加法一样，但是......它很可能不是，而且我已经看到当对每个元素执行的操作是与增量一样微不足道 - 您最好对此进行衡量，看看这些选项在您的环境中如何发挥作用。