为什么这个C++ for循环的执行时间存在显着差异？

Question

我正在经历循环,发现访问循环有显着差异.我无法理解在两种情况下造成这种差异的原因是什么？

第一个例子:

执行时间处理时间; 8秒

for (int kk = 0; kk < 1000; kk++)
{
    sum = 0;
    for (int i = 0; i < 1024; i++)
        for (int j = 0; j < 1024; j++)
        {
            sum += matrix[i][j];
        }
}

第二个例子:

执行时间:23秒

for (int kk = 0; kk < 1000; kk++)
{
    sum = 0;
    for (int i = 0; i < 1024; i++)
        for (int j = 0; j < 1024; j++)
        {
            sum += matrix[j][i];
        }
}

是什么导致如此多的执行时间差异只是交换

matrix[i][j] 

至

matrix[j][i]

？

Answer 1

这是内存缓存的问题.

matrix[i][j]具有更好的缓存命中率matrix[j][i],因为matrix[i][j]具有更多的连续内存访问机会.

例如,当我们访问matrix[i][0],高速缓存可以加载的含有存储器的连续数据段matrix[i][0],从而,访问matrix[i][1],matrix[i][2],...,将受益于缓存的速度,因为matrix[i][1],matrix[i][2],...是接近matrix[i][0].

但是,当我们访问时matrix[j][0],它远离matrix[j - 1][0]缓存,可能没有缓存,并且无法从缓存速度中受益.特别是,矩阵通常存储为连续的大段存储器,并且压缩器可以预测存储器访问的行为并且总是缓存存储器.

这就是为什么matrix[i][j]更快.这在基于CPU缓存的性能优化中是典型的.

Answer 2

性能的差异是由计算机的缓存策略引起的.

二维数组matrix[i][j]表示为存储器中的长列表值.

例如,数组A[3][4]看起来像:

1 1 1 1   2 2 2 2   3 3 3 3

在此示例中,A [0] [x]的每个条目都设置为1,A [1] [x]的每个条目都设置为2,...

如果您的第一个循环应用于此矩阵,则访问顺序如下:

1 2 3 4   5 6 7 8   9 10 11 12

而第二个循环访问顺序如下所示:

1 4 7 10  2 5 8 11  3 6 9 12

当程序访问数组的元素时,它也会加载后续元素.

例如,如果您访问A[0][1],A[0][2]并A[0][3]加载了.

因此,第一循环必须执行较少的加载操作,因为一些元素在需要时已经在高速缓存中.第二个循环将条目加载到当时不需要的缓存中,从而导致更多的加载操作.

Answer 3

其他人已经很好地解释了为什么一种形式的代码比另一种形式更有效地使用内存缓存.我想补充一些你可能不知道的背景信息:你可能没有意识到现在的主存储器访问有多昂贵.

这个问题中贴出的数字看起来对我来说是正确的,我会在这里重现它们,因为它们非常重要:

Core i7 Xeon 5500 Series Data Source Latency (approximate)
L1 CACHE hit, ~4 cycles
L2 CACHE hit, ~10 cycles
L3 CACHE hit, line unshared ~40 cycles
L3 CACHE hit, shared line in another core ~65 cycles
L3 CACHE hit, modified in another core ~75 cycles remote
remote L3 CACHE ~100-300 cycles
Local Dram ~60 ns
Remote Dram ~100 ns

请注意最后两个条目的单位更改.根据您的具体型号,该处理器的运行频率为2.9-3.2 GHz; 为了简化数学运算,我们只需称它为3 GHz.所以一个周期是0.33333纳秒.因此DRAM访问也是100-300个周期.

关键是CPU 在从主存储器读取一个高速缓存行所花费的时间内可能已经执行了数百条指令.这被称为记忆墙.因此,有效使用内存缓存比现代CPU的整体性能中的任何其他因素更重要.

Answer 4

答案取决于具体如何matrix定义.在完全动态分配的数组中,您将拥有:

T **matrix;
matrix = new T*[n];
for(i = 0; i < n; i++)
{
   t[i] = new T[m]; 
}

因此,每个matrix[j]都需要对指针进行新的内存查找.如果在j外部执行循环,则内部循环可以matrix[j]为整个内部循环重复使用指针.

如果矩阵是一个简单的2D数组:

T matrix[n][m];

那么它matrix[j]只是乘以1024 * sizeof(T)- 这可以通过1024 * sizeof(T)在优化代码中添加循环索引来完成,因此无论如何都应该相对较快.

最重要的是,我们有缓存局部因素.高速缓存具有"行"数据,每行通常为32到128个字节.因此,如果您的代码读取地址X,则缓存将加载32到128个字节的值X.因此,如果您需要的NEXT事物仅从sizeof(T)当前位置向前移动,则很可能已经在缓存中[并且现代处理器还检测到您将在循环中读取每个存储器位置,并预加载数据].

j在内循环的情况下,您正在sizeof(T)*1024为每个循环读取一个新的距离位置[或者如果它是动态分配的话,可能是更大的距离].这意味着正在加载的数据对下一个循环没有用,因为它不在接下来的32到128个字节中.

最后,由于SSE指令或类似指令,第一个循环完全可能更加优化,这使得计算运行得更快.但这对于如此大的矩阵来说可能是微不足道的,因为性能在这个大小上具有很高的内存限制.

Answer 5

内存硬件未针对单个地址进行优化:相反,它倾向于在称为缓存行的较大块连续内存上运行.每次读取矩阵的一个条目时,它所在的整个缓存行也会随之加载到缓存中.

设置更快的循环顺序以按顺序读取存储器; 每次加载缓存行时,都使用该缓存行中的所有条目.每次通过外部循环,您只需一次读取每个矩阵条目.

但是,较慢的循环排序仅在继续之前使用来自每个缓存行的单个条目.因此,每个高速缓存行必须多次加载,对于行中的每个矩阵条目一次.例如,如果a double是8个字节并且高速缓存行是64字节长,则每个通过外部循环必须读取每个矩阵条目八次而不是一次.

所有这一切,如果你已经转向优化,你可能会看到没有区别:优化者理解这种现象,好的能够识别他们可以交换哪个循环是内循环,哪个循环是这个特定的外循环代码段.

(另外,一个好的优化器只能通过最外层循环完成一次,因为它识别前999次通过与最终值无关sum)

Answer 6

矩阵作为向量存储在存储器中.以第一种方式访问​​它顺序访问内存.以第二种方式访问​​它需要跳过内存位置.见http://en.wikipedia.org/wiki/Row-major_order

Answer 7

如果你访问j - i,j维度被缓存,所以机器代码不必每次都改变它,第二个维度没有被缓存,所以你实际上每次导致差异时都会删除缓存.