c++ - 如何减轻 C++ 中由于虚函数调用而导致的分支错误预测？

Question

背景:我正在开发一种复杂语言的编译器(因此有许多不同类型的 AST 节点)。我需要一种遍历 AST 的方法，目前我使用虚拟函数为不同的 AST 节点创建迭代器。例如，operator++ 实现为:

namespace ast {

class Iterator {
  Iterator operator++() {
    if (++curr_it_)
      return curr_it_;

    auto curr_node_ = /* get the neighbor */;
    if (!curr_node_)
      return nullptr;

    return (curr_it_ = curr_node_->create_iterator());
  }
};

InternalIterator BinaryExpr::create_iterator() { /* ... */ }
InternalIterator ArrayLiteral::create_iterator() { /* ... */ }
InternalIterator FunctionCall::create_iterator() { /* ... */ }

}  // namespace ast

问题:分析结果显示，对 create_iterator 的调用导致 50% 的分支误预测率。我可以采取什么措施来缓解这种情况？

P.S.我使用valgrind --tool=cachegrind --branch-sim=yes来分析我的编译器，大多数错误预测来自间接函数调用。

Answer 1

如果您想减少分支错误预测，只有少数方法可以实现:

• 通过使用 CMOV 等条件指令或不涉及分支的特定于用例的指令序列来减少条件分支。例如，如果您的各种迭代器具有相同的行为但具有不同的数据跨步，那么您可以删除虚拟调用并通过 LUT 或其他内容设置跨步。在这里可能不可能。

• 重新排列数据以帮助分支预测器。在这里几乎肯定不可能。

• 如果分支不在分支缓存中而被错误预测，则否定分支条件。 (这是 PGO 要做的主要事情之一。)当然，如果您的错误预测率为 50%，则不适用。

• 重新排列代码，以便分支预测器更好地工作。这是极其繁琐且特定于处理器的(例如，您将针对 AMD 处理器的特定型号进行优化)，并且不太可能通过现代分支预测器产生太多好处。这里的一个异常(exception)是短循环[但不是太短]比长循环更容易预测，但在这种情况下您对此没有太多控制权。

该分支的预测效果很差，因为分支是该代码所做的。从高层次上来说，分支预测是一种动态优化低熵跟踪执行的方法。换句话说，这是 CPU 注意到并利用您所采用的分支模式的一种方式。如果没有可识别的模式，则分支(错误)预测不适用于您的情况。