避免重复的 C++ 虚拟表查找

Question

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

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

代码类似于以下内容。一旦程序在程序开始时填充向量 v，该向量在程序的其余部分将不再改变，因此每次我想调用 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

根据评论中的一些问题和您的回答，以下是一些注意事项。

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

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

2）你说“函数 f() 本身非常简单，例如其中一个函数只是将两个内存地址处的值相乘并将乘积存储在第三个地址中” - 这可能并不像你期望的那么无辜。作为参考，进入 L1 缓存将花费您大约 3 个周期，进入 RAM 可能会花费 60-200 个周期，具体取决于您的硬件。

如果您有足够的这些对象（因此不可能将它们引用的所有内存保留在一级缓存中），并且它们引用的内存位置基本上是随机的（因此预取无效），并且/或者您在程序的其余部分（以便在向量上的循环之间从缓存中腾出所有相关数据），从内存/较低级别的缓存获取和存储值的成本将超过虚拟函数调用的成本在最坏的情况下会增加几个数量级。

3）您迭代指向对象的指针向量 - 而不是对象本身。

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

4）你说“对子向量的 f() 调用必须按顺序”——是吗？

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

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

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

请记住：访问 L1/L2 缓存中已有的内容是好的，必须访问 L3/RAM 才能获取数据则更糟糕；按顺序访问内存是好的，跳过内存是不好的；在紧密循环中调用相同的方法（可能会内联它）是好的，在紧密循环中调用许多不同的方法则更糟糕。

如果这是您的程序的一部分，其性能确实很重要，那么您应该考虑更改系统的体系结构以允许进行一些前面提到的优化。我知道这可能看起来令人畏惧，但这就是我们正在玩的游戏。有时，如果您要解决的问题允许，您需要牺牲“干净”的 OOP 和抽象来提高性能。