c - 关于C中两种算法不同运行时间的困惑

This question already has answers here:

Accessing elements of a matrix row-wise versus column-wise

(3个答案)

去年关闭。

我有一个数组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;
}

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

1和:0.19s

sum2:1.25秒

谁能解释为什么会有如此巨大的差异？

最佳答案

计算机通常使用缓存来帮助加快对主内存的访问。

通常用于主内存的硬件相对较慢-数据从主内存到处理器可能需要花费很多处理器周期。因此，计算机通常包括少量的非常快速但昂贵的内存，称为高速缓存。计算机可能具有多个级别的缓存，其中一些缓存内置在处理器或处理器芯片本身中，而某些缓存位于处理器芯片之外。

由于缓存较小，因此无法将所有内容保存在主内存中。它通常甚至无法保存一个程序正在使用的所有内容。因此，处理器必须对缓存中保留的内容进行决策。

程序最常访问的是存储器中的连续位置。很多时候，程序读取数组的元素237之后，很快就会读取238，然后是239，依此类推。读取237之后，读取7024的频率降低了。

因此，缓存操作旨在将连续的主内存部分保留在缓存中。您的sum1程序与此配合得很好，因为它可以最快速地更改列索引，并在处理所有列时使行索引保持不变。它访问的数组元素在内存中连续布置。

您的sum2程序不能很好地与此配合，因为它最快速地更改了行索引。这会在内存中跳来跳去，因此高速缓存无法满足它进行的许多访问，而必须来自较慢的主内存。

相关资源:Memory layout of multi-dimensional arrays

关于c - 关于C中两种算法不同运行时间的困惑，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/60496498/

上一篇：c++ - 如何正确使用C++ 11风格的内存池？

下一篇：c++ - macOS上缺少Qt库

相关文章：

c++ - 如何自动向下滚动 richedit 文本框 win32 c/c++

c - 为什么我的字符串的第一个字母不打印？

c - 使用 Windows 和 C 编译器在 64 位系统上运行 32 位 C 代码

c - 内联汇编和函数覆盖导致段错误

c - 我需要混合使用 strtok 和 strtok_single

c++ - putc 和 ungetc 有什么区别？

c - 函数调用时指针更改大小(使用 gdb 检查)

Java线程概念

c - 为什么我的 fork 进程没有返回我想要取回的值？

c - 这个程序创建了多少个进程？