c++ - 现代 CPU 内循环间接优化

Question

来自 http://www.boost.org/community/implementation_variations.html

“...编码差异，例如将类从虚拟成员更改为非虚拟成员或删除间接级别，除非深入内部循环，否则不太可能产生任何可测量的差异。即使在内部循环中，现代 CPU 也经常执行此类在相同数量的时钟周期内竞争代码序列!”

我试图理解“即使在内部循环”部分。具体来说，CPU 实现了哪些机制来在相同数量的时钟周期内执行两个代码(虚拟与非虚拟或额外的间接级别)？我知道指令流水线和缓存，但是如何在与非虚拟调用相同的时钟周期数内执行虚拟调用？间接如何“丢失”？

Answer 1

缓存(例如 branch target caching )、并行加载单元(流水线的一部分，但也包括不会拖延流水线的“命中未命中”之类的东西)和 out-of-order execution可能有助于改造load - load - branch变成更接近固定的东西 branch .流水线的解码或分支预测阶段的指令折叠/消除(对此的正确术语是什么？)也可能有所贡献。

但是，所有这些都依赖于很多不同的东西:有多少个不同的分支目标(例如，您可能会触发多少个不同的虚拟重载)，您循环了多少个东西(分支目标缓存“热”了吗？ icache/dcache 怎么样？)，虚拟表或间接表如何在内存中布局(它们是缓存友好的，还是每个新的 vtable 加载可能会驱逐旧的 vtable？)，缓存是否由于以下原因反复失效多核乒乓球等...

(免责声明:我绝对不是这里的专家，我的很多知识都来自研究有序嵌入式处理器，所以其中一些是推断。如果您有更正，请随时发表评论!)

确定特定程序是否会出现问题的正确方法当然是分析。如果可以，请在硬件计数器的帮助下进行操作——它们可以告诉您很多有关管道各个阶段发生的情况。

编辑:

正如 Hans Passant 在上述评论中指出的那样Modern CPU Inner Loop Indirection Optimizations ，让这两件事花费相同的时间的关键是能够有效地“退出”每个周期多于一条指令。指令消除可以帮助解决这个问题，但 superscalar design可能更重要(击中未命中是一个非常小的和具体的例子，完全冗余的负载单元可能更好)。

让我们假设一个理想情况，并假设直接分支只是一条指令:

branch dest

...一个间接分支是三个(也许你可以把它分成两个，但它大于一个):

load vtable from this
load dest from vtable
branch dest

让我们假设一个绝对完美的情况:*这个和整个 vtable 都在 L1 缓存中，L1 缓存足够快，可以支持两个加载的每条指令成本摊销一个周期。 (您甚至可以假设处理器对加载重新排序并将它们与较早的指令混合，以便让它们有时间在分支之前完成；这对于本示例无关紧要。)还假设分支目标缓存很热，并且没有管道分支的刷新成本，分支指令归结为单个周期(摊销)。

因此，第一个示例的理论最短时间为 1 个周期(摊销)。

第二个例子的理论最小值，没有指令消除或冗余功能单元或允许每个周期退出多于一条指令的东西，是 3 个周期(有 3 个指令)!

间接加载总是会更慢，因为有更多指令，直到您进入超标量设计之类的东西，允许每个周期退出一条以上指令。

一旦你有了这个，两个例子的最小值就会变成 0 到 1 个周期之间的东西，同样，前提是其他一切都是理想的。可以说，与第一个示例相比，第二个示例必须有更理想的条件才能实际达到理论最小值，但现在可以了。

在您关心的某些情况下，对于任一示例，您可能都不会达到该最小值。要么分支目标缓存是冷的，要么 vtable 不在数据缓存中，要么机器无法重新排序指令以充分利用冗余功能单元。

...这就是分析的用武之地，无论如何这通常是一个好主意。

首先，您可以支持对虚拟的轻微偏执。见 Noel Llopis's article on data oriented design ，优Pitfalls of Object-Oriented Programming slides , 和 Mike Acton's grumpy-yet-educational presentations .现在，如果您正在处理大量数据，您会突然进入 CPU 可能已经满意的模式。

像 virtual 这样的高级语言特性通常是表达性和控制性之间的权衡。不过，老实说，我认为，只要提高您对 virtual 实际在做什么的认识(不要害怕不时阅读反汇编 View ，并且一定要查看您的 CPU 架构手册)，您会倾向于使用它当它有意义时而不是当它没有意义时，如果需要，分析器可以覆盖其余部分。

关于“不要使用虚拟”或“虚拟使用不太可能产生显着差异”的一刀切声明让我很不高兴。现实通常更复杂，要么你会处于一种你足够关心或避免它的情况，要么你处于其他 95% 的情况下，除了可能的教育内容外，它可能不值得关心。