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

Question

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

#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 i7920处理器有一个256KB的L2缓存，行大小为64字节。如果您的数据适合缓存，那么您访问它的顺序并不重要。优化代码使其对缓存友好的所有问题都必须针对两件事：如果可能，将对内存的访问拆分到块中，这样块就适合缓存了。对那个块做所有可能的计算，然后带来下一个块，用它做计算，等等。另一件事，（您正在尝试做的一件事）是以连续的方式访问内存。当您从内存请求一个数据（比方说一个int-4字节）时，整个缓存行被带到缓存中（在我的例子中是64字节：即16个相邻的整数（包括您请求的整数）被带到缓存中）。下面是行顺序对列顺序的播放。在行顺序中，每16个内存请求有1个缓存丢失；在列顺序中，每一个请求都有一个缓存丢失（但仅当数据不适合缓存；如果数据适合缓存，那么得到的比率与行顺序相同，因为从请求行中的第一个元素开始，这些行仍然在缓存中；当然，相关性可以发挥作用，即使不是所有缓存都被数据填满，也可以重写缓存行）。

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