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缓存对齐.当你循环j遍历时Matrix[i][j],元素Matrix[i][0],Matrix[i][1]... aso在连续的地址处对齐(实际上在不同的地址处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]... aso地址Matrix[1][j]是Matrix[0][j]+2048*sizeof(Matrix[0][0])- 假设您为数组分配了2048个条目Matrix[0].

因此Matrix[0][j],在另一个缓存块中Matrix[1][j],要求获取在RAM中而不是在缓存中进行访问.

在第二种情况下,每次迭代都可以访问RAM.