关于C中两种算法的不同运行时间的混淆

Question

我有一个数组,long matrix[8*1024][8*1024]和两个函数sum1和sum2:

long sum1(long m[ROWS][COLS]) {
    long register sum = 0;
    int i,j;

    for (i=0; i < ROWS; i++) {
        for (j=0; j < COLS; j++) {
            sum += m[i][j];
        }
    }
    return sum;
}

long sum2(long m[ROWS][COLS]) {
    long register sum = 0;
    int i,j;

    for (j=0; j < COLS; j++) {
        for (i=0; i < ROWS; i++) {
            sum += m[i][j];
        }
    }

    return sum;
}

当我用给定的数组执行这两个函数时,我得到运行时间:

sum1:0.19s

sum2:1.25s

任何人都可以解释为什么会有这么大的差异？

Answer 1

C使用行主要排序来存储多维数组,如第6.5.2.1节" 数组下标", C标准第3段中所述:

连续的下标运算符指定多维数组对象的元素.如果E是维度为ixjx的n维数组(n> = 2)...xk,然后E(用作除左值之外)被转换为指向尺寸为jx的(n-1)维数组的指针...x k.如果将unary*运算符显式地应用于此指针,或者作为预订的结果隐式应用,则结果是引用的(n-1)维数组,如果用作除左值之外的其他数据本身将转换为指针.由此得出,数组以行主要顺序存储(最后一个下标变化最快).

强调我的.

这是来自维基百科的图像,它演示了这种存储技术与存储多维数组的其他方法相比,列主要排序:

第一个函数sum1根据2D数组在内存中实际表示的方式连续访问数据,因此来自数组的数据已经在缓存中.sum2需要在每次迭代时获取另一行,这不太可能在缓存中.

还有一些其他语言使用多维数组的列主要排序; 其中有R,FORTRAN和MATLAB.如果您使用这些语言编写了等效代码,您可以观察到更快的输出sum2.

Answer 2

计算机通常使用缓存来帮助加快对主存储器的访问.

通常用于主存储器的硬件​​相对较慢 - 数据可能需要许多处理器周期才能从主存储器传输到处理器.因此,计算机通常包括较小量非常快但昂贵的称为高速缓存的存储器.计算机可能具有多级缓存,其中一些内置于处理器或处理器芯片本身,其中一些位于处理器芯片外部.

由于缓存较小,因此无法将所有内容保存在主内存中.它通常甚至不能保存一个程序正在使用的所有内容.因此,处理器必须决定缓存中保留的内容.

程序的最频繁访问是存储器中的连续位置.通常,在程序读取数组的元素237之后,它将很快读取238,然后读取239,依此类推.阅读237之后读取7024的频率较低.

因此,缓存的操作被设计为保持在缓存中连续的主存储器的部分.您的sum1程序适用于此,因为它最快速地更改列索引,在处理所有列时保持行索引不变.它访问的数组元素在内存中连续排列.

您的sum2程序不能很好地使用它,因为它最快速地更改行索引.这会在内存中跳过,因此很多访问都不会被缓存所满足,并且必须来自较慢的主内存.

相关资源:多维数组的内存布局