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

Question

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

ccachingoptimization

4

我一直在试图理解如何编写cache-friendly代码。因此，作为第一步，我尝试了解数组行主要访问和列主要访问之间的性能差异。

于是我创建了一个大小为512×512的整数数组，总大小为1MB。我的L1缓存为32KB，L2缓存为256KB，L3缓存为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);
}

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

- Abid Rahman K

1

感谢 @MOHAMED 进行格式化。 - Abid Rahman K

你能发布你的结果（实际计数值）吗？我自己也不确定，但我发现人们使用 printf 语句来确保编译器不会优化未使用的部分。由于您的“矩阵”未初始化、被汇总且未使用，它们可能被优化掉了？ - nonsensickle

你尝试过更改计算两个条件的顺序吗？ - jmpyle771

请确保您在编译时不使用任何优化标志。编译器足够智能，可以反转循环（使内部循环成为外部循环）。 - bolov

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- bolov · Accepted Answer

我不知道你为什么会出现这种情况，但是让我澄清一些事情。

想要考虑缓存时至少有两个因素：缓存大小和缓存行大小。例如，我的Intel i7 920处理器具有256KB的L2缓存，带有64字节的行大小。如果你的数据适合放在缓存中，那么以哪种顺序访问它并不重要。优化代码使其对缓存友好的所有问题都必须针对两个方面：如有可能，请将对内存的访问拆分成多个块，以便块适合于缓存。使用该块进行所有计算，然后获取下一个块，对其进行计算，依此类推。另一件事（您正在尝试的）是以连续方式访问内存。当您从内存请求数据时（假设是int-4字节），整个缓存行将被带入缓存（在我的情况下为64字节：即16个相邻的整数（包括您请求的一个）将被带入缓存）。行顺序与列顺序相比就会体现出来。使用行顺序，每16个内存请求会有1个缓存未命中；使用列顺序，则每个请求都会有一个缓存未命中（但仅当您的数据不适合缓存时才会有这种情况；如果您的数据适合缓存，则仍然会得到与行顺序相同的比率，因为您仍然拥有来自之前请求线首元素时的缓存中的行；当然，关联性可能会发挥作用，并且即使没有填充您的数据，缓存行也可能被重写）。

关于你的问题，如我所说，当数据适合放在缓存中时，访问顺序并不是那么重要，但是当您进行第二次求和时，从第一次求和开始，数据已经在缓存中了，这就是为什么它更快的原因。如果您先用列顺序进行求和，您应该会看到行顺序求和变得更快，只是因为它在后面完成。但是，当数据足够大时，您不应该得到相同的结果。尝试以下操作：在两个求和之间，使用另一个大型数据进行某些操作，以使整个缓存失效。

编辑

我注意到按行主要的矩阵访问方式只提高了3-4倍的速度（尽管我预计会提高8倍以上的速度。你知道为什么吗？）[...]如果您能告诉我为什么加速只有3倍，那就太好了。

并不是说以“正确”的方式访问矩阵不会有多大改善，而更像是以“错误”的方式访问矩阵不会对性能造成太大影响，如果这样说有意义的话。

尽管我不能给出具体和确切的答案，但是我可以告诉您的是，现代处理器拥有非常复杂和极其高效的缓存模型。它们是如此强大，例如，在许多常见情况下，它们可以掩盖缓存层级，使得似乎您拥有一个大的一级缓存而不是一个三级缓存（当您将数据大小从适合于L2的大小增加到仅适合于L3的大小时，您不会看到惩罚）。在旧处理器上运行您的代码（比方说10年前的），您可能会看到您期望的加速。然而，现代处理器具有帮助使用缓存失败的机制。桌面处理器的设计理念是快速运行“糟糕的代码”，因此在提高“糟糕的代码”性能方面投资了很多，因为大多数桌面应用程序并非由了解分支问题或缓存模型的人编写。这与高性能市场相反，那里的专门处理器会使得糟糕的代码极为痛苦，因为它们实现了弱的处理糟糕代码的机制（或者根本没有实现）。这些机制占用了很多晶体管，因此增加了功耗和产生的热量，但是在大多数代码都是“糟糕代码”的桌面处理器中值得实现。