performance - 我们什么时候应该使用预取？

Question

一些 CPU 和编译器提供预取指令。例如:GCC Document 中的 __builtin_prefetch .虽然 GCC 的文档中有评论，但对我来说太短了。

我想知道，在实践中，我们应该什么时候使用预取？有一些例子吗？谢谢!

Answer 1

这个问题实际上与编译器无关，因为它们只是提供了一些钩子(Hook)来将预取指令插入到您的汇编代码/二进制文件中。不同的编译器可能提供不同的内在格式，但您可以忽略所有这些并(小心地)将其直接添加到汇编代码中。

现在真正的问题似乎是“预取什么时候有用”，答案是 - 在任何情况下，您受限于内存延迟，并且访问模式不规则且无法区分硬件预取(组织在流中)或跨步)，或者当您怀疑有太多不同的流需要硬件同时跟踪时。
大多数编译器很少会为您插入他们自己的预取，因此基本上取决于您自己的代码和对预取如何有用的基准测试。

@Mysticial 的链接显示了一个很好的例子，但这里有一个更直接的例子，我认为硬件无法捕捉到它:

#include "stdio.h"
#include "sys/timeb.h"
#include "emmintrin.h"

#define N 4096
#define REP 200
#define ELEM int

int main() {
    int i,j, k, b;
    const int blksize = 64 / sizeof(ELEM);
    ELEM __attribute ((aligned(4096))) a[N][N];
    for (i = 0; i < N; ++i) {
        for (j = 0; j < N; ++j) {
            a[i][j] = 1;
        }
    }
    unsigned long long int sum = 0;
    struct timeb start, end;
    unsigned long long delta;

    ftime(&start);
    for (k = 0; k < REP; ++k) {
        for (i = 0; i < N; ++i) {
            for (j = 0; j < N; j ++) {
                sum += a[i][j];
            }
        }
    }
    ftime(&end);
    delta = (end.time * 1000 + end.millitm) - (start.time * 1000 + start.millitm);
    printf ("Prefetching off: N=%d, sum=%lld, time=%lld\n", N, sum, delta); 

    ftime(&start);
    sum = 0;
    for (k = 0; k < REP; ++k) {
        for (i = 0; i < N; ++i) {
            for (j = 0; j < N; j += blksize) {
                for (b = 0; b < blksize; ++b) {
                    sum += a[i][j+b];
                }
                _mm_prefetch(&a[i+1][j], _MM_HINT_T2);
            }
        }
    }
    ftime(&end);
    delta = (end.time * 1000 + end.millitm) - (start.time * 1000 + start.millitm);
    printf ("Prefetching on:  N=%d, sum=%lld, time=%lld\n", N, sum, delta); 
}

我在这里所做的是遍历每个矩阵行(享受硬件预取器对连续行的帮助)，但是从驻留在不同页面中的下一行中预取具有相同列索引的元素(硬件预取应该很难按下)去抓)。我对数据求和，这样它就不会被优化掉，重要的是我基本上只是遍历一个矩阵，应该非常简单且易于检测，但仍然可以获得加速。

使用 gcc 4.8.1 -O3 构建，它让我在 Intel Xeon X5670 上提升了近 20%:

Prefetching off: N=4096, sum=3355443200, time=1839
Prefetching on:  N=4096, sum=3355443200, time=1502

请注意，即使我使控制流更复杂(额外的循环嵌套级别)，也会收到加速，分支预测器应该很容易捕捉到那个短 block 大小循环的模式，并且它节省了不需要的预取的执行。

请注意 Ivybridge 及以后的 should have a "next-page prefetcher" ，因此硬件可能能够在这些 CPU 上缓解这种情况(如果有人有可用的并且愿意尝试，我会很高兴知道)。在这种情况下，我会修改基准以对每第二行求和(并且预取每次都会向前看两行)，这应该会让硬件预取器感到困惑。

Skylake 结果

以下是 Skylake i7-6700-HQ 的一些结果，运行频率为 2.6 GHz(无涡轮)， gcc :

编译标志: -O3 -march=native

Prefetching off: N=4096, sum=28147495993344000, time=896
Prefetching on:  N=4096, sum=28147495993344000, time=1222
Prefetching off: N=4096, sum=28147495993344000, time=886
Prefetching on:  N=4096, sum=28147495993344000, time=1291
Prefetching off: N=4096, sum=28147495993344000, time=890
Prefetching on:  N=4096, sum=28147495993344000, time=1234
Prefetching off: N=4096, sum=28147495993344000, time=848
Prefetching on:  N=4096, sum=28147495993344000, time=1220
Prefetching off: N=4096, sum=28147495993344000, time=852
Prefetching on:  N=4096, sum=28147495993344000, time=1253

编译标志: -O2 -march=native

Prefetching off: N=4096, sum=28147495993344000, time=1955
Prefetching on:  N=4096, sum=28147495993344000, time=1813
Prefetching off: N=4096, sum=28147495993344000, time=1956
Prefetching on:  N=4096, sum=28147495993344000, time=1814
Prefetching off: N=4096, sum=28147495993344000, time=1955
Prefetching on:  N=4096, sum=28147495993344000, time=1811
Prefetching off: N=4096, sum=28147495993344000, time=1961
Prefetching on:  N=4096, sum=28147495993344000, time=1811
Prefetching off: N=4096, sum=28147495993344000, time=1965
Prefetching on:  N=4096, sum=28147495993344000, time=1814

因此，根据您是否使用 -O3，使用预取会慢 40% 或快 8%。或 -O2分别针对此特定示例。 -O3 的大幅放缓实际上是由于代码生成怪癖:在 -O3没有预取的循环是矢量化的，但是预取变体循环的额外复杂性无论如何都阻止了我的 gcc 版本的矢量化。

所以 -O2结果可能是更多的苹果对苹果， yield 大约是我们在 Leeor 的 Westmere 上看到的一半(8% 对 16% 的加速)。仍然值得注意的是，您必须小心不要更改代码生成，以免大大减慢速度。

这个测试可能并不理想，因为去 int通过 int意味着大量的 CPU 开销，而不是强调内存子系统(这就是向量化有很大帮助的原因)。