代码之家 › 专栏 › 技术社区 › Boris Grunwald

C语言中两种算法不同运行时间的混淆

Boris Grunwald · 技术社区 · 5 年前

我有一个数组长矩阵[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

有人能解释为什么会有这么大的差异吗?

5 回复 | 直到 5 年前

Eric Postpischil 5 年前

计算机通常使用 隐藏物 帮助加速对主存储器的访问。

通常用于主存储器的硬件速度相对较慢,从主存储器到处理器的数据可能需要许多处理器周期。因此,计算机通常包括一个较小的数量,非常快,但昂贵的内存称为缓存。计算机可能有几个层次的高速缓存,其中一部分内置于处理器或处理器芯片本身,另一部分则在处理器芯片之外。

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

程序最常访问的地方是内存中的连续位置。通常,程序读取数组的元素237后,很快就会读取238,然后再读取239,依此类推。它很少读7024,只是读237。

因此,高速缓存的操作被设计成在高速缓存中保持主内存的连续部分。你的 sum1 程序可以很好地处理这个问题,因为它最快地更改列索引,在处理所有列时保持行索引不变。它访问的数组元素在内存中连续排列。

你的 sum2 程序不能很好地处理这个问题,因为它最快地更改了行索引。这会在内存中跳来跳去,所以它所做的许多访问都不能被缓存满足,必须来自较慢的主内存。

Govind Parmar 5 年前

C使用行主顺序存储多维数组,如中所述 § 6.5.2.1 Array subscripting, paragraph 3 C标准:

连续的下标运算符指定多维数组对象的元素。如果e是尺寸为i x j x的n维数组(n>=2)。…x k,然后e(用作左值以外的值)转换为指向(n-1)维数组的指针,该数组的尺寸为j x。…x k.如果一元*运算符显式或隐式应用于此指针,则结果是引用的(n-1)维数组,如果将其用作左值以外的值,则该数组本身将转换为指针。 由此可知,数组按行主顺序存储(最后一个下标变化最快)。

强调我的。

这是一张图片 Wikipedia 与其他存储多维数组的方法相比,它演示了这种存储技术, 列主要顺序 :

第一个函数, sum1 ,根据二维数组在内存中的实际表示方式连续访问数据,因此来自该数组的数据已经在缓存中。

Jean-François Fabre 5 年前

在具有数据缓存的机器上(即使68030有一个),在连续的内存位置读/写数据要快得多,因为一个内存块(大小取决于处理器)从内存中提取一次,然后从缓存中调用(读操作)或一次全部写入(缓存刷新用于写操作)。

通过“跳过”数据(与以前的读取相差很远),CPU必须再次读取内存。

这就是为什么你的第一个片段更快。

对于更复杂的操作(例如快速傅立叶变换),如果数据被多次读取(与您的示例不同),许多库(例如fftw)建议使用步幅以适应您的数据组织(行/列)。从未使用它,总是先转置你的数据,使用1的步幅,它会比尝试不转置更快。

为了确保数据是连续的,不要使用二维符号。首先将数据定位在所选行中,并设置指向行开头的指针,然后在该行上使用内部循环。

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

如果您不能这样做,这意味着您的数据定向错误。

klutt Anjali Shah 5 年前

这是缓存的问题。

缓存将自动读取您请求的数据之后的数据。因此,如果您逐行读取数据,您请求的下一个数据将已经在缓存中。

Christian Gibbons 5 年前

在内存中,矩阵是线性对齐的,这样一行中的项在内存中彼此相邻。( spacial locality )。当您按顺序交叉项目,以便在移动到下一个项目之前浏览一行中的所有列时,当CPU遇到一个尚未加载到其缓存中的条目时,它会将该值连同一整块其他值一起加载到物理内存中,以便下一个数目的值已经被缓存它需要阅读它们的时间。

当您以另一种方式交叉它们时,它加载到内存中靠近它的其他值将不会是下一个读取的值,因此最终会出现更多的缓存未命中,因此当数据从内存层次结构的下一层引入时,CPU必须坐着等待。

当您回退到以前缓存的另一个条目时,它很可能已经从缓存中引导出来,而倾向于您自加载以来所使用的所有其他数据,因为它最近将不再被使用。( temporal locality )