Prefetch，性能，与毒药

在不同的领域，提高性能有着不同的实现方法。有的领域也许需要一个更优的算法，有的领域也许需要一些编程上的技巧。在 Kernel 领域，由于 Kernel 直接面对硬件，性能上的优化往往与硬件提供的功能息息相关。当代计算机硬件在性能上最突出的矛盾是 CPU 的运行速度远远超过内存的速度，如果所有内存引用的数据都需要直接从内存读/写的话，CPU 将不得不把时间花在对内存操作的等待上。为此，当代 CPU 都有一些快速的 CPU Cache 用来临时存放所需要的内存数据，以加快运行速度。Kernel 对性能的优化很大一部分就是利用 Cache 的优化，包括经常见到的仔细定义结构体的成员顺序，以使得那些通常需要一块访问的成员在一个 Cache line 内就可以访问到。

让事情更美好（或者更糟糕）的是 CPU 制造商也在想尽一切办法尽量减少内存访问所引起的延迟。常见的这样的高级 CPU 功能包括：Prefetch, Out-Of-Order Execution, Branch Prediction 等等，这些功能有的是纯硬件的，对操作系统透明；有的功能 CPU 会提供相应的指令可用。使用这些先进的硬件功能帮助 Kernel 提高性能，是非常诱人的。然而正如前面提到的那样，采用这些功能有时候并不见得一定能提高性能，由于这些硬件功能在实现细节上的不公开等种种原因，结果甚至更差。Prefetch 就是最近 Kernel 开发人员刚刚学到的一例。

Prefetch 简单的说就是 CPU 通过某种算法猜测接下来可能要执行的指令/数据，然后提前从内存里取出来并存放到 Cache 中，如果猜测的结果与实际执行的一样，则执行速度加快。Prefetch 分为硬件 Prefetch 与 软件 Prefetch。硬件 Prefetch 包括 Prefetch 指令与数据，指令的 Prefetch 相对容易理解，并且可以看出顺序执行的指令 Prefetch 的准确率高，而带有条件判断的语句则需要与 Branch Prediction 功能相结合。数据的 Prefetch 则牵涉到 CPU 对内存数据访问模式的分析，比指令 Prefetch 更加复杂，通常是 CPU 在探测到某些特定的事件后（一般是发生了连续的 Cache misses），触发 Prefetch 自动执行。硬件 Prefetch 对操作系统来说是透明的。软件 Prefetch 则是操作系统或应用程序明确要求 CPU 将某个地址的数据 Prefetch 到 Cache 中，以备以后使用。

Prefetch 由于简单的接口，并且以性能为目的，被 Kernel 开发人员大量使用。最常见的地方是 list.h 里的 prefetch() 宏：

#define list_for_each(pos, head) \
        for (pos = (head)->next; prefetch(pos->next), pos != (head); \
                pos = pos->next)

这里的 prefetch() 宏是对底层硬件平台 prefetch 指令的一个封装，不同的平台有自己的 prefetch 实现方式，一般是在平台的 processor.h 里定义的。上面这段代码使用 prefetch 的想法是，在处理链表中当前节点的同时，让 CPU 将下一个节点的数据提前取出来，并放到 Cache 中，这样当处理到下一个节点时，数据已经在 Cache 里了。通常来说，链表在内存中的存放并不像数组那样连续，因此很难通过 Cache 优化。软件 Prefetch 在这儿提供了将下一个节点数据提前拷贝到 Cache 中的可能。

如果一切都如这里分析的一样，内核大量的链表操作将因此变快。可惜，事实并非如此。

最先对这里的 prefetch 提出质疑的是 Andi Kleen，不过 Andi 的理由并不那么充分，他提交的将 prefetch 从 list.h 中去除的 patch 也没有获得通过。最近 Linus 也对 list.h 里的 prefetch 发表了看法，这一次是 Linus 在自己的机器上 build kernel 时发现了 prefetch 的问题，大量使用 prefetch 并没有带来性能上的改进，相反，去掉 prefetch 反而运行的更快。Ingo Molnar 随后跟进对这里的 prefetch 进行了研究，他重现了 Linus 的问题，并且确认在这里使用 prefetch 将降低约 0.5% 的性能。

虽然 0.5 并不是一个很大的数字，但这里的问题在于本来应该提高性能的地方，却降低了性能。Linus 的分析是，他的测试有相当一部分操作是遍历单向链表 hlist，这些单向链表都很短，并没有多少让 prefetch 提高的空间。甚至，大部分链表只有一个节点，因此这里的 prefetch 的地址是 NULL。很明显，按照一般的设想，CPU 在遇到 prefetch(NULL) 的情况时，应该什么也不做，但在 x86 机器上并非如此。根据 Ingo 的分析，prefetch(NULL) 大约需要 20 个 CPU cycles。Ingo 通过软件的方法绕过了 prefetch(NULL) 的问题，即只有在地址非 NULL 时才执行 prefetch 指令，并做了测试，虽然性能有所进步，但比起完全去掉 prefetch 来仍然要差。

根据 Ingo 的观测，无论在这里添加还是去除 prefetch 操作，CPU 总体上执行 prefetch 指令的次数相差并不大。也就是说，此时 CPU 里的硬件 prefetch 已经处于饱和的状态，如果再通过软件显式去 prefetch 某些数据，似乎干扰了 CPU 正常的硬件 prefetch 策略。所以最好的选择就是让硬件自己去 prefetch，硬件在决定哪些数据该 prefetch 时，表现更好。Ingo 据此得出的结论是：

So the conclusion is: prefetches are absolutely toxic, even if the NULL ones are excluded.

这个结论也与最初 Andi 邮件里的说法相似，Andi 曾引述来自硬件设计人员的反馈，表示硬件开发者并不赞成软件开发人员显式的去使用 prefetch，除非有特别好的理由，而这里的 prefetch 并不是。

最终的结果是在即将发布的 Linux 3.0 里，list 操作里的 prefetch 被拿掉。这个结果与 Andi 提交的 patch 并不完全一致，Andi 的 patch 是提供一个 CONFIG 开关来控制，并且对 K7 架构，prefetch 默认是打开的。

仍然有人认为 Linus 与 Ingo 的分析并不能完全说明所有情况，尤其是 Linus 明确表示在他的测试情况下，list 的长度都很短，如果某个另外的情况使得 list 很长，性能是否会完全不一样呢？是否所有硬件平台的 prefetch 都与 x86 类似呢？没有人能明确回答这样的问题。大多数性能问题，答案都来自于大量的测试以及可信的数据，很多时候理论上的分析，并不完全正确，甚至恰恰相反。在这里，我们最好相信硬件 prefetch 能做的更好。

Kernel 开发人员的这个教训似乎告诉我们 prefetch 真的是一剂毒药。但这并不表示在所有情况下，prefetch 都是有害的，有时候，以毒攻毒也是有用的，正确使用 prefetch 仍然能带来性能上的提升，前提是你深入理解了 prefetch 的毒性，当然更重要的还是枯燥乏味的测试与数据。

引用与致谢

• LWN 上非常棒的文章：The problem with prefetch，Prefetching considered harmful。
• 我爱 Wikipedia：Prefetching，CPU Cache。
• Ulrich Drepper 的：What every programmer should know about memory。
• GCC 对 prefetch 的支持：Data prefetch support。