May 24, 2011
The problem with prefetch
翻译：曾怀东
随着经验的增长，软件开发者会发现微优化的努力并不值得，尤其是在缺少针对具体问题的硬数据（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可能是第一个对这一优化方法提出疑问的，去年九月他尝试移除list操作中的prefetch。他的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花些时间量化他的做法带来的影响，上一次可能就已经被大家接受了。
本站的feed
最新评论