6

我有一个 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!
        }
    }
};
4

2 回答 2

2

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

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

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

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

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

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

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

4)您说“对子向量的 f() 调用必须有序”-是吗?

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

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

我的主要观点是——以某种方式改变系统架构可以带来很多性能优势。

记住:访问已经在 L1/L2 缓存中的东西是好的,必须去 L3/RAM 获取数据更糟糕;按顺序访问内存是好的,跳过内存是不好的;在紧密循环中调用相同的方法(可能内联它)是好的,在紧密循环中调用许多不同的方法更糟糕。

如果这是你的程序的一部分,它的性能真的很重要,你应该考虑改变你的系统架构以允许前面提到的一些优化。我知道这可能看起来令人生畏,但这就是我们正在玩的游戏。有时,如果您要解决的问题允许,您需要牺牲“干净”的 OOP 和抽象来提高性能。

于 2020-03-21T02:20:54.287 回答
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);

显式静态调度的替代方法是将子类或成员函数标记为 final。

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

于 2020-03-21T00:34:42.833 回答