内核中prefetch的问题

By Jonathan Corbet
May 24, 2011

翻译：曾怀东

随着经验的增长，软件开发者会发现微优化的努力并不值得，尤其是在缺少针对具体问题的硬数据（hard data）的时候。性能问题通常不是出在我们认为的位置，所以没有头绪地进行调整试图获得更好的效果可能是徒劳的，甚至可能使事情变得更糟糕。这是内核开 发人员得到的教训。

在内核层面，性能通常受缓存行为的影响。真正高性能要求只有命中cpu缓存才能够满足，内存访问相比较显得过于缓慢了。内核尽量地使用cache- hot memory；以及其它一些其它重要的工作，例如调整数据结构使得经常被访问的数据位于同一条cache line中。作为通用的准则，这些优化方法对性能的提升很明显。

百分百命中缓存是难以达到的，但是也可以想办法尽量提高命中率。如果内核知道最近将要访问的数据所处的位置，它可以使用CPU提供的 prefetch 指令将数据放入缓存。这种指令是通过内核prefetch()函数实现的；开发者已经在广泛使用这个函数。例如通常使用的宏：

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

这个宏是用于遍历一个链表。Prefetch()的思想是在处理当前实体的同时开始获取链表中下一个实体。希望在下一次循环开始前能够获取到数据，或者至少使这个数据已经开始传输。众所周知，链表是对缓存不友好的数据类型，所以这种类型的优化能够有效提升速度。

但实际上这样做并不能提升速度，至少在x86处理器上不能。

Andi Kleen可能是第一个对这一优化方法提出疑问的，去年九月他。他的patch引发了小规模的讨论，但是显然误入了歧途。最近，Linus在自己最喜欢的workloads（内核builds）之一上然后发现prefetch 指令集占据了极大比例。执行Prefetching所消耗的时间超出了缓存带来的好处；将prefetch()移除能够让made和build更快。

Ingo Molnar，牛人 Ingo，也，他进行了很有意义的研究。通过使用perf和一些细微的kernel调试，他证明了使用prefetch()结构造成了0.5%的性能下降。这不是一个简单的性能退化，它本来被指望带来更快的速度，一定有什么地方没有按照人们想象的方式运行。

Linus指出其中最明显的一个问题：他的测试引入了大量对单链哈希表（singly-linked hlist hash table lists）的遍历。这些列表比较短，所有没有足够的范围实现prefetching；事实上，大部分时间中，唯一的prefetch操作仅是在尝试使用 指向列表末端的空指针。Prefetching 一个空指针看起来没啥消耗，但实际上是有代价的: 在 x86 上（ARM 也是如此）的每一条这样的指令都会导致 a translation lookaside buffer miss and a pipeline stall. Ingo 测算得出空指针的 prefetch 大约消耗 20 个 CPU 周期.

很明显，空指针 prefetch 不是个好主意。如果CPU可以简单的忽略对使用空指针的prefetch尝试那么会好一些。但是，从软件层面解决并不是最好的办法。Ingo对只 prefetch非空指针版本的prefetch()函数进行了测试。这个版本确实性能更好。但是仍不如不使用prefetch的方案。

CPU设计者很清楚内存等待的代价；他们花费了大量的努力将任何可能的代价都降到最小。CPU有自己的内存prefetch单元，这些单元尝试预测 下一次需要的内存并提前对内存进行遍历。Ingo在他的测试中提到，即使没有任何软件层面的prefetch操作，cpu进行的prefetch操作数量 几乎是相同的。所以硬件prefetcher一直处于繁忙状态-并且在决定fetch哪些内容方面上它比软件层面表现得更优秀。将显式的prefetch 操作混入其中只会影响硬件的prefetch操作。

Ingo总结如下：所以即便将NULL的部分刨除，prefetches也明显是有害的。

他工作的成果之一：2.6.40（现在被起名叫3.0了），将prefetch()操作从链表，哈希表以及sk_buff表的遍历操作中移除，正如 Andi Kleen在九月份尝试做的那样。或者其他的prefetch操作也被移除的话性能也有提升的几率。内核中仍然存在prefetch()操作，不过只存在 于特定的能明确提升性能的场景。如同我们尝试的其他底层优化（立刻能想到的就是likely()），我们自以为prefetch能带来帮助，但并不是我们 真正需要做的工作。

这个事情的另一个经验是numbers matter。Andi在移除这些操作的时候是正确的，但是他不能说服社区接受自己的补丁。这一次，除了Linus注意到它并进行了研究外，更重要的原因 是基于性能的补丁确实需要用数据来证明自己能够达到设定的目标。如果Andi花些时间量化他的做法带来的影响，上一次可能就已经被大家接受了。