c - 了解如何编写缓存友好的代码

Question

我一直在努力理解如何编写缓存友好的代码。因此，作为第一步，我试图了解数组行优先访问和列优先访问之间的性能差异。

所以我创建了一个大小为 512×512 的 int 数组，因此总大小为 1MB。我的一级缓存32KB，二级缓存256KB，三级缓存3MB。所以我的数组适合 L3 缓存。

我简单地计算了行主序和列主序的数组元素之和，并比较了它们的速度。一直以来，专栏主要顺序略快。我预计行主要订单会比其他订单更快(可能快几倍)。

我认为问题可能是由于数组的尺寸太小，所以我制作了另一个尺寸为 8192×8192 (256 MB) 的数组。结果还是一样。

下面是我使用的代码片段:

#include "time.h"
#include <stdio.h>

#define S 512
#define M S
#define N S

int main() {
    // Summing in the row major order
    int x = 0;
    int iter = 25000;
    int i, j;
    int k[M][N];
    int sum = 0;    
    clock_t start, end;

    start = clock();
    while(x < iter) {
        for (i = 0; i < M; i++) {
            for(j = 0; j < N; j++) {
                sum += k[i][j];
            }
        }

        x++;
    }
    end = clock();
    printf("%i\n", end-start);

    // Summing in the column major order
    x = 0;
    sum = 0;
    int h[M][N];

    start = clock();
    while(x < iter) {
        for (j = 0; j < N; j++) {
            for(i = 0; i < M; i++){
                sum += k[i][j];
            }
        }

        x++;
    }
    end = clock();
    printf("%i\n", end-start);
}

问题:有人可以告诉我我的错误是什么以及为什么我得到这个结果吗？

Answer 1

我真的不知道您为什么会出现这种行为，但让我澄清一些事情。

考虑缓存时至少要考虑两件事:缓存大小和缓存行大小。例如，我的 Intel i7 920 处理器有一个 256KB 的 L2 高速缓存，行大小为 64 字节。如果您的数据适合缓存，那么您访问它的顺序就无关紧要了。将代码优化为缓存友好的所有问题必须针对两件事:如果可能的话，将对内存的访问分成 block ，以便 block 适合缓存。用那个 block 做所有可能的计算，然后带下一个 block ，用它做计算等等。另一件事(您正在尝试做的事情)是以连续的方式访问内存。当您从内存中请求数据时(比如说一个 int - 4 字节)，整个 cache line 都会被带到缓存中(在我的例子中是 64 字节:即 16 个相邻的整数(包括您请求)被带到缓存)。这是播放行顺序与列顺序的对比。使用行顺序，每 16 个内存请求有 1 个缓存未命中，使用列顺序，每个请求都会有一个缓存未命中(但前提是您的数据不适合缓存；如果您的数据适合缓存，那么您会得到与行顺序相同的比率，因为你仍然有缓存中的行，从你请求行中的第一个元素时开始；当然，关联性可以发挥作用，即使不是所有缓存都被填充，也可以重写缓存行与您的数据)。

关于你的问题，正如我所说，当数据适合缓存时，访问顺序并不重要，但是当你进行第二次求和时，数据已经在缓存中从你做第一个总和的时候开始，所以这就是它更快的原因。如果你先做列顺序求和，你应该看到行顺序求和变得更快，因为它是在之后完成的。但是，当数据足够大时，您不应该得到相同的行为。尝试以下操作:在两个总和之间，对另一个大数据做一些事情以使整个缓存无效。

编辑

I see a 3-4x speedup for row major (although I expected >8x speedup. any idea why?). [..] it would be great if you could tell me why speedup is only 3x

不是说以“正确的方式”访问矩阵并没有太大改善，更像是以“错误的方式”访问矩阵并没有那么大的伤害，如果这有任何意义的话。

虽然我无法为您提供具体而准确的答案，但我可以告诉您的是，现代处理器具有非常复杂且极其高效的缓存模型。它们非常强大，例如，在许多常见情况下，它们可以掩盖缓存级别，使您看起来像是拥有一个大的一级缓存而不是三级缓存(从从适合 L2 的尺码到只适合 L3 的尺码)。在较旧的处理器(比方说 10 岁)中运行您的代码，您可能会看到预期的加速。然而，现代处理器具有对缓存未命中有很大帮助的机制。桌面处理器的设计理念是快速运行“错误代码”，因此在改进“错误代码”性能方面进行了大量投资，因为绝大多数桌面应用程序不是由了解分支问题或缓存模型的人编写的。这与高性能市场相反，在高性能市场中，专用处理器会使错误代码受到很大伤害，因为它们实现了处理“错误代码”(或根本不实现)的弱机制。这些机制占用大量晶体管，因此会增加功耗和产生的热量，但它们值得在大多数代码都是“错误代码”的台式机处理器中实现。