避免重复 C++ 虚拟 table 查找

Question

我有一个 C++ 程序，它在执行二进制文件时读取配置文件，根据配置文件创建多个子 class 实例，然后定期迭代这些实例并调用它们各自的虚函数.

gprof 告诉我这些函数调用占用了很多时间（前面提到的迭代发生非常频繁），所以我想以某种方式尽量避免重复的虚函数调用。

代码类似下面。一旦程序在程序开始时填充向量 v，该向量在程序的其余部分将不再更改，因此每次我想调用时重复进行虚拟 table 查找似乎效率低下F（）。我认为一定有一种方法可以以某种方式缓存或保存函数指针，但我不确定如何。

希望您有任何关于加快速度的建议。谢谢！

编辑：抱歉，我忘了提到子实例向量的函数调用 f() 必须按从 0 到 v.size() - 1 的顺序，所以我无法分组v 的具有相同派生类型的元素在一起。

此外，这是用 -O3 -std=c++14 构建的

class Parent {
public:
    virtual void f() { } 
};

class Child1 : public Parent {
public:
    void f() { /* do stuff for child1 */ }
};

//...

class Child9 : public Parent {
public:
    void f() { /* do stuff for child9 */ }
};

int main() {
    vector<Parent*> v;

    // read config file and add Child instances to v based on the file contents

    while (true) {
        // do other stuff
        for (size_t i = 0; i != v.size(); ++i) {
             v[i]->f(); // expensive to do the same virtual table lookups every loop!
        }
    }
};

Answer 1

编辑：对于混合在一起的任意子类型的向量，我建议使用虚拟调用。

如果根据配置，只有一个子类型的向量 - 或者如果您可以将不同的类型分离到单独的容器中，那么在这种情况下，编译时多态性可能是一个选项，而不是运行时一。例如：

template<class Child, class Range>
void f_for(Range& r) {
    for (Parent* p : r) {
        Child* c = static_cast<Child*>(p);
        c->Child::f(); // use static dispatch to avoid virtual lookup
    }
}

...

if (config)
    f_for<Child1>(v);
else
    f_for<Child2>(v);

替代显式静态分派的方法是标记子 class 或成员函数 final。

您甚至可以扩展程序的静态部分，以便您可以直接使用 vector<Child1> 或 vector<Child2>，避免额外的间接访问。此时甚至不需要继承。

Answer 2

根据评论中的一些问题和您的回答，这里有一些注意事项。

1) 您的问题（如果有的话，您的解决方案可能已经接近最佳，具体取决于您未提及的细节）很可能在其他地方，而不是在虚函数调用的开销中。

如果你真的运行这是一个紧密的循环，并且在 f() 的实现中没有太多涉及大量内存的事情，你的 vtables 可能保留在 L1 缓存中，并且在现代硬件上，如果有的话，虚函数调用开销绝对是最小的。

2) 你说 "the functions f() themselves are very simple, for example one of them just multiplies the values at two memory addresses and stores the product in a third address" - 这可能不像你想象的那么无辜。作为参考，转到 L1 缓存将花费您大约 3 个周期，转到 RAM 可能花费 60-200，具体取决于您的硬件。

如果你有足够的这些对象（这样就不可能将它们引用的所有内存都保存在 L1 缓存中），并且它们引用的内存位置基本上是随机的（这样预取是无效的），and/or 你在程序的其余部分接触了足够多的东西（这样所有相关数据都从向量循环之间的缓存中腾出），从 memory/lower 级别的缓存中获取和存储值的成本在最坏的情况下，将比虚函数调用的成本高出几个数量级。

3) 您遍历指向对象的指针向量 - 而不是对象本身。

根据您分配对象的方式和它们的大小，这可能不是问题 - 如果您在一个紧密的循环中分配它们并且您的分配器很好地打包它们，预取将为您创造奇迹。但是，如果您 allocate/free 很多其他东西，并且在这些对象之间混合分配，它们最终可能会稀疏地分布在内存中基本上随机的位置；然后按创建顺序迭代它们将涉及从内存中进行大量随机读取，这将再次比任何虚拟函数开销慢得多。

4) 你说 "calls to f() for the vector of children has to be in order" - 他们是吗？

如果他们这样做了，那么在某些方面你就不走运了。但是，如果您可以重新设计您的系统，以便它们可以按类型排序调用，那么在各个方面都可以获得很大的速度 - 您可能可以为每种类型的对象分配一个数组（很好，密集打包在内存中），按顺序迭代它们（预取器友好），并在组中调用您的 f() 以获得单个众所周知的类型（内联友好，指令缓存友好）。

5) 最后 - 如果上述 none 适用并且您的问题确实在虚函数调用中（不太可能），那么，是的，您可以尝试存储指向您需要的确切函数的指针以某种方式调用每个对象 - 手动或使用其他人建议的类型擦除/鸭子打字方法之一。

我的主要观点是 - 以某些方式更改系统架构可以获得很多性能优势。

记住：访问已经在 L1/L2 缓存中的东西很好，必须去 L3/RAM 获取数据更糟糕；按顺序访问内存是好的，遍历内存是不好的；在紧密循环中调用相同的方法（可能内联它）很好，在紧密循环中调用许多不同的方法更糟。

如果这是您程序中性能真正重要的一部分，您应该考虑更改系统的体系结构以允许进行前面提到的一些优化。我知道这可能看起来令人生畏，但这就是我们正在玩的游戏。有时您需要牺牲 "clean" OOP 和抽象以获得性能，如果您正在解决的问题允许的话。

避免重复 C++ 虚拟 table 查找

Avoiding repeated C++ virtual table lookup

c++

optimization

virtual-functions

vtable

virtual-table