C程序执行速度

Question

我的考试主题是编程语言的主要问题.我想了很久但我还是不明白这个问题

问题:下面是一个程序C,它在配置为~CPU Intel 1.8GHz,Ram 512MB的PC上的MSVC++ 6.0环境中执行

#define M 10000
#define N 5000
int a[M][N];

void main() {
    int i, j;
    time_t start, stop;

    // Part A
    start = time(0);
    for (i = 0; i < M; i++)
        for (j = 0; j < N; j++)
            a[i][j] = 0;
    stop = time(0);
    printf("%d\n", stop - start);

    // Part B
    start = time(0);
    for (j = 0; j < N; j++)
        for (i = 0; i < M; i++)
            a[i][j] = 0;
    stop = time(0);
    printf("%d\n", stop - start);
}

解释为什么A部分只在执行1秒,但它采取了B部分787-8完成？

Answer 1

这与数组内存的布局方式以及如何将其加载到缓存中并进行访问有关:在版本A中,当访问数组的单元格时,邻居会将其加载到缓存中,然后立即将代码加载到缓存中访问这些邻居.在版本B中,访问一个单元格(并将其邻居加载到缓存中),但下一行访问距离很远,在下一行,因此整个缓存行已加载但只使用了一个值,另一个缓存行必须为每次访问填写.因此速度差异.

Answer 2

行主要订单与列主要订单.

首先回想一下,所有多维数组都在内存中表示为一个连续的内存块.因此,多维数组A(m,n)可以在存储器中表示为

a00 a01 a02 ... a0n a10 a11 a12 ... a1n a20 ... amn

在第一个循环中,按顺序运行此内存块.因此,您按以下顺序遍历遍历元素的数组

a00  a01  a02  ...  a0n  a10  a11  a12  ...  a1n  a20 ... amn

1    2    3         n    n+1  n+2  n+3 ...   2n   2n+1    mn

在第二个循环中,您在内存中跳过并按以下顺序遍历遍历元素的数组

a00  a10  a20  ...  am0  a01  a11  a21  ...  am1  a02  ...  amn

或者,或许更清楚,

a00  a01  a02  ...  a10  a11  a12  ...  a20 ... amn
1    m+1  2m+1      2    m+2  2m+2      3       mn

所有跳过的东西真的会伤害你,因为你没有从缓存中获益.按顺序运行数组时,相邻元素将加载到缓存中.当您浏览阵列时,您不会获得这些好处,而是继续获得缓存未命中,从而损害性能.

Answer 3

由于硬件架构优化.A部分正在对顺序存储器地址执行操作,这允许硬件大大加速计算的处理方式.B部分基本上一直在内存中跳转,这使许多硬件优化失败.

这种特定情况的关键概念是处理器缓存.

Answer 4

您声明的数组在内存中按行排列.基本上你有一大块M×N整数,C做了一些小技巧让你相信它是矩形的.但实际上它是平的.

因此,当您按行迭代(使用M作为外部循环变量)时,您实际上是通过内存线性地进行.CPU缓存处理的东西非常好.

但是,当您在外部循环中使用N进行迭代时,您总是在内存中进行或多或少的随机跳转(至少对于看起来像这样的硬件).您正在访问第一个单元格,然后进一步移动M个整数,并执行相同的操作等.由于您的内存页面通常大约为4 KiB,这会导致内循环的每次迭代都会访问另一个页面.这样几乎任何缓存策略都会失败,你会看到一个重大的放缓.