c - C 中的矩阵计算

Question

我最近注意到，在 C 中访问矩阵的方式看似很小的变化可能会对性能产生很大的影响。 例如，假设我们有这两个 C 代码片段。这个:

for(i = 0; i < 2048; i++)
{
    for(j = 0; j < 2048; j++) {
            Matrix[i][j] = 9999;    
    }
}

还有这个:

for(j = 0; j < 2048; j++)
{
    for(i = 0; i < 2048; i++) {
            Matrix[i][j] = 9999;    
    }
}

第二个版本比第一个版本慢 2 倍。为什么？我认为这与内存管理有关:在每个循环中，第一个版本访问内存中彼此相邻的位置，而第二个版本必须“跳转”到每个循环中的不同区域。 这种直觉是对的吗？ 此外，如果我将矩阵变小(例如 64x64)，那么性能上没有差异。为什么？ 如果有人能提供直观而严谨的解释，我将不胜感激。 顺便说一下，我使用的是 Ubuntu 14.04 LTS。

Answer 1

        for(i=0;i<2048;i++)
        {
                for(j=0;j<2048;j++) {
                        Matrix[i][j]=9999;    
                }
        }

这种形式使用了 L1、L2 和 L3 缓存对齐方式。当您在 Matrix[i][j] 上使用 j 循环时，元素 Matrix[i][0]、Matrix[ i][1]...a.s.o.在连续的地址对齐(实际上是在 sizeof(Matrix[i][0]) 不同的地址处)，因此访问 Matrix[i][0] 会带来缓存内存下一个变量 Matrix[i][1].

另一方面，

        for(j=0;j<2048;j++)
        {
                for(i=0;i<2048;i++) {
                        Matrix[i][j]=9999;    
                }
        }

内部循环按顺序访问 Matrix[0][j], Matrix[1][j]... a.s.o. Matrix[1][j] 的地址是 Matrix[0][j]+2048*sizeof(Matrix[0][0])——假设你为数组 Matrix[0] 分配了 2048 个条目。

因此 Matrix[0][j] 位于与 Matrix[1][j] 不同的另一个缓存 block 中，需要取回在 RAM 中进行访问在缓存中。

在第二种情况下，每次迭代都会访问 RAM。