内存管理 - 为什么某些初始化顺序更快？

计算科学 C 内存管理
2021-12-05 09:00:53 
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

float timedifference_msec(struct timeval t0, struct timeval t1) {
    return (t1.tv_sec - t0.tv_sec) * 1000.0f + (t1.tv_usec - t0.tv_usec) / 1000.0f;
}

int main()
{
    struct timeval t0;
    struct timeval t1;
    float elapsed;

    int ** a = malloc(10000*sizeof(int*));
    for(int i = 0; i < 10000; i++){
        a[i] = malloc(10000*sizeof(int));
    }

    gettimeofday(&t0, 0);
    for(int i = 0; i < 10000; i++){
        for(int j = 0; j< 10000; j++){
            a[j][i] = 0;
        }
    }
    gettimeofday(&t1, 0);

    elapsed = timedifference_msec(t0, t1);
    printf("%f\n", elapsed);


    gettimeofday(&t0, 0);
    for(int i = 0; i < 10000; i++){
        for(int j = 0; j< 10000; j++){
            a[i][j] = 0;
        }
    }
    gettimeofday(&t1, 0);
    elapsed = timedifference_msec(t0, t1);
    printf("%f", elapsed);

    return 0;
}

为什么第一个实现比另一个更快？

编辑：当我替换时，为什么我会更快：

int (*a)[num]  = malloc(num*num*sizeof(int));
memset(&a, 0, 10000*10000*sizeof(int));
2个回答

之所以会出现这种效果，是因为数据int** a在内存中的存储方式（根据 C/C++）。StackOverflow 上的这个问题有更多细节的答案（特别是许多用户在评论中指出的差异），int**以及它如何int[][]

看起来像一个数组数组 - 它只是在内存中连续布局。

值得一提malloc的是，由于使用了几个 s，整个数组可能不会完全连续地存储在内存中；但是，每一行 - 都会。问题来了：为了充分利用内存中数组的“部分”连续布局，您希望按照元素的存储顺序访问元素（如果可能）。这使得代码缓存友好。这个关于使代码缓存友好的问题有很多很好的建议，但在这里，内存布局是重要的。

查看数组存储方式的内存非常有用：这个 StackOverflow 答案在静态数组的具体示例中说明了这一点。在 C/C++ 中，布局是行优先的（相对于 Matlab 和 Fortran）；因此，逐行访问数组是有利的：

a[0][0] = 0.;
a[0][1] = 0.;
a[0][2] = 0.;
...
a[0][N-1] = 0.;
a[1][0] = 0.;
a[1][1] = 0.;
a[1][2] = 0.;
...
a[N-1][0] = 0.;
a[N-1][1] = 0.;
...
a[N-1][N-1] = 0.;

其中N是数组的大小（假设行大小 == 列大小）。

现在，这部分对应于“展开”的第二个实现：

for(int i = 0; i < 10000; i++){
    for(int j = 0; j< 10000; j++){
        a[i][j] = 0;
    }
}

这在我的机器上要快得多（gcc -O3）：1577.997070ms（对于第一个变体）与 45.952000ms（对于第二个变体）。实际数字并不准确也不重要，重要的是定性比较。

重要的是要注意，mallocs 不必（但可以）连续进行下一次分配（感谢@Brian Borcher 的评论）。因此，使用您分配int ** a数组的方式，您很可能无法使用上述循环在内存中完全连续地行走；但是，您仍然可以通过第二个实现更多地利用代码缓存友好性。

为了使代码更快，请考虑：

  • 使用适当大小a之一一次分配整个数组malloc
  • a[i+j*numRows]使用索引将矩阵视为一维数组
  • 阅读正确分配多维数组的最佳实践
  • 使用分配器，使您的数据在内存中对齐。mkl_malloc是一个例子；但是，还有许多其他可能性，并且您可能已经有了基于应用程序中已经使用的库的一种可能性。选择适当的对齐方式。

因此，第二个实现速度更快。

正确地注意到这是一个指向整数数组的指针数组：

在第一个版本中，代码访问每个连续整数数组的元素 0，然后访问元素 1，等等。这意味着它正在更改在每次内部迭代中取消引用的指针（指向整数数组） 。

在第二个版本中，代码访问第 0 个整数数组的每个元素，然后访问第 1 个整数数组的每个元素，等等。这意味着它正在更改哪个指针（指向整数数组）在每次外部迭代中取消引用。

这意味着第二个版本可以为每个外部迭代缓存指针（即在寄存器中），并为每个内部迭代重用它。所以第二个版本会减少很多指针解引用，节省时间。

其它你可能感兴趣的问题
上一篇对小矩阵进行对角化的最有效方法是什么？ 下一篇弯曲有限元内的点