如何缓解C++中AST遍历虚函数调用引发的分支预测失误？

背景 #

我正在开发一款复杂语言的编译器（存在多种不同类型的AST节点），目前通过虚函数为不同AST节点创建迭代器来遍历AST，核心的operator++实现如下：

namespace ast {

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

    auto curr_node_ = /* 获取相邻节点 */;
    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

通过valgrind --tool=cachegrind --branch-sim=yes做性能分析后发现，create_iterator的间接函数调用导致了50%的分支预测失误率，需要缓解这一问题。

可行优化方案 #

1. 类型标签+Switch分支表替代虚函数 #

给每个AST节点添加枚举类型的标签，在迭代器创建逻辑中用switch-case直接实例化对应迭代器，避免虚函数的间接跳转。编译器通常会将连续枚举的switch编译成跳转表，分支预测准确率远高于虚函数的动态分派：

enum class NodeType { BinaryExpr, ArrayLiteral, FunctionCall /* 其他节点类型 */ };

class ASTNode {
public:
    virtual NodeType get_type() const = 0;
    // 移除原有的create_iterator虚函数
};

// 修改Iterator的operator++逻辑：
Iterator Iterator::operator++() {
    if (++curr_it_)
        return curr_it_;

    auto curr_node_ = /* 获取相邻节点 */;
    if (!curr_node_)
        return nullptr;

    switch (curr_node_->get_type()) {
        case NodeType::BinaryExpr:
            curr_it_ = InternalIterator{static_cast<BinaryExpr*>(curr_node_)};
            break;
        case NodeType::ArrayLiteral:
            curr_it_ = InternalIterator{static_cast<ArrayLiteral*>(curr_node_)};
            break;
        case NodeType::FunctionCall:
            curr_it_ = InternalIterator{static_cast<FunctionCall*>(curr_node_)};
            break;
        // 补充其他节点类型的分支
    }
    return curr_it_;
}

2. 预缓存迭代器实例 #

如果迭代器内存开销不大，给每个AST节点预分配好对应的迭代器实例并存储在节点内部，遍历阶段直接获取预存实例，将虚函数调用的开销转移到节点构造期：

class ASTNode {
private:
    std::unique_ptr<InternalIterator> cached_iterator_;
protected:
    ASTNode() : cached_iterator_(create_cached_iterator()) {}
    virtual std::unique_ptr<InternalIterator> create_cached_iterator() = 0;
public:
    InternalIterator* get_iterator() { return cached_iterator_.get(); }
};

// 子类实现预创建逻辑：
std::unique_ptr<InternalIterator> BinaryExpr::create_cached_iterator() {
    return std::make_unique<BinaryExprIterator>(this);
}

// 修改Iterator的operator++：
Iterator Iterator::operator++() {
    if (++curr_it_)
        return curr_it_;

    auto curr_node_ = /* 获取相邻节点 */;
    if (!curr_node_)
        return nullptr;

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

3. 用访问者模式重构遍历逻辑 #

彻底替换迭代器模式为访问者模式，将遍历逻辑集中到访问者类中，减少动态分派的次数，同时让遍历路径更具规律性，提升分支预测准确率：

class ASTVisitor {
public:
    virtual void visit(BinaryExpr& node) = 0;
    virtual void visit(ArrayLiteral& node) = 0;
    virtual void visit(FunctionCall& node) = 0;
    // 其他节点类型的visit方法
};

class ASTNode {
public:
    virtual void accept(ASTVisitor& visitor) = 0;
};

void BinaryExpr::accept(ASTVisitor& visitor) { visitor.visit(*this); }
void ArrayLiteral::accept(ASTVisitor& visitor) { visitor.visit(*this); }

// 实现遍历逻辑的访问者：
class TraversalVisitor : public ASTVisitor {
public:
    void traverse(ASTNode* root) {
        if (!root) return;
        root->accept(*this);
        // 处理子节点/相邻节点的遍历逻辑
    }

    void visit(BinaryExpr& node) override {
        // 处理BinaryExpr节点的遍历逻辑
        traverse(node.left());
        traverse(node.right());
    }

    void visit(ArrayLiteral& node) override {
        // 处理ArrayLiteral节点的遍历逻辑
        for (auto elem : node.elements()) {
            traverse(elem);
        }
    }
};

4. 开启编译器去虚拟化优化 #

确保编译器能够自动对虚函数调用做去虚拟化：

• 在遍历的热点路径上，尽量让AST节点的类型在编译期可推导（避免无类型的基类指针随意跳转）
• 开启最高优化级别（如-O3），GCC/Clang等现代编译器在很多场景下能自动将虚函数调用转化为直接调用，消除间接分支。

内容的提问来源于stack exchange，提问作者rhanqtl