c++ - 为什么这个虚函数调用如此昂贵？

Question

我最近修改了一个程序以使用虚函数(用静态调用代替序列 if if-else 条件。)修改后的程序运行速度比原始程序慢 8%。这似乎使用虚函数的成本太高了，所以我一定是在设置类层次结构和虚函数的方式上做了一些低效的事情；但是，我不知道如何找出问题所在。 (我在 Mac 上使用 clang 和在 Linux 上使用 gcc 时看到类似的性能下降。)

该程序用于研究不同的社区检测算法。该程序使用嵌套循环将一系列用户指定的目标函数应用于各种(图形、分区)对。

这是原始代码的粗略轮廓

int main(int argc, char* argv[]) {
    bool use_m1;
    bool use_m2;
    ...
    bool use_m10;

    //  set the various "use" flags based on argv

    for (Graph& g : graphsToStudy()) {
        for (Partition& p : allPartitions()) {
            if (use_m1) {
                M1::evaluate(g, p);
            }
            if (use_m2) {
                M2::evaluate(g,p);
            }
            // and so on
        }
    }

为了使代码更易于维护，我为不同的目标函数创建了一个类结构，并遍历了一个指针数组:

class ObjectiveFunction {
public:
    virtual double eval(Graph& g, Partition& p) = 0;
}

class ObjFn1 : public ObjectiveFunction {
public:
    virtual double eval(Graph& g, Partition& p) {
        return M1::evaluate(g,p);
   }
}

class ObjFn2 : public ObjectiveFunction {
public:
    virtual double eval(Graph& g, Partition& p) {
        return M2::evaluate(g,p);
   }
}


int main(int argc, char* argv[]) {
    vector<ObjectiveFunction*> funcs;
    fill_funcs_based_on_opts(funcs, argc, argv);

    for (Graph& g : graphsToStudy()) {
        for (Partition& p : allPartitions()) {
            // funcs contains one object for each function selected by user.
            for (ObjectiveFunction* fp : funcs) {
                fp->evaluate(g, p);
            }
        }
    }

鉴于生成图和分区以及目标函数本身的计算量适中，因此添加虚函数调用应该几乎不会引起注意。任何我可能做错的想法；或者如何追踪它？我尝试使用 callgrind，但没有看到任何见解。

也许我只是错误地解释了 callgrind_annotate 的输出。在下面的示例中，Neo::Context::evaluatePartition 类似于上面示例中的 ObjFn1::evaluate。

1. 为什么这个函数列出了四次不同的时间源文件？此方法仅从函数 main 中调用在 timeMetrics.cpp 中。

2. src/lib/PartitionIterator.h:main 指的是什么？没有 PartitionIterator.h 中的主要函数。

3. 为什么 414,219,420 在源代码列表中出现两次 评估分区？不是第一个数字应该代表 函数调用的开销？

---

35,139,513,913  PROGRAM TOTALS
17,029,020,600  src/lib/metrics/Neo.h:gvcd::metrics::Neo::Context<unsigned int, unsigned char, unsigned int>::evaluatePartition(gvcd::Partition<unsigned int, unsigned int> const&, bool)  [bin/timeMetrics_v]  
7,168,741,865  /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/vector:gvcd::Partition<unsigned int, unsigned int>::buildMembersh ipList()  
4,418,473,884  src/lib/Partition.h:gvcd::Partition<unsigned int, unsigned int>::buildMembershipList() [bin/timeMetrics_v]  
1,459,239,657  src/lib/PartitionIterator.h:main  
1,288,682,640  /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/vector:gvcd::metrics::Neo::Context<unsigned int, unsigned char, u nsigned int>::evaluatePartition(gvcd::Partition<unsigned int, unsigned int> const&, bool)  
1,058,560,740  src/lib/Partition.h:gvcd::metrics::Neo::Context<unsigned int, unsigned char, unsigned int>::evaluatePartition(gvcd::Partition<unsigned int, unsigned int> const&, bool)  
1,012,736,608  src/perfEval/timeMetrics.cpp:main [bin/timeMetrics_v]    443,847,782  /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/vector:main 
368,372,912  /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/memory:gvcd::Partition<unsigned int, unsigned int>::buildMembersh ipList()    
322,170,738  /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/ostream:main
    92,048,760  src/lib/SmallGraph.h:gvcd::metrics::Neo::Context<unsigned int, unsigned char, unsigned int>::evaluatePartition(gvcd::Partition<unsigned int, unsigned int> const&, bool)
    84,549,144  ???:szone_free_definite_size [/usr/lib/system/libsystem_malloc.dylib]
    54,212,938  ???:tiny_free_list_add_ptr [/usr/lib/system/libsystem_malloc.dylib]



            .          virtual double
  414,219,420          evaluatePartition(const Partition <VertexID, SetBitmap> &p, bool raw = false) {
  414,219,420            uint_wn_t raw_answer = Neo::evaluatePartition(*(this->g), p);
            .            return (double) (raw ? raw_answer : max_neo - raw_answer);
            .          }
            .        }; // end Context

Answer 1

让我们先解决显而易见的问题:

在这两个版本中你都这样做:

foreach (Graph g : graphsToStudy()) {
    foreach (Partition p : allPartitions()) {

除非图表/分区很容易复制而且很小，否则您的大部分工作都将在这里。

foreach (Graph& g : graphsToStudy()) {
           // ^
    foreach (Partition& p : allPartitions()) {
                   // ^

我的第二个问题。这看起来不像是虚函数的正确用法。在这个用例中，您的原始代码看起来完全没问题，其中在每个 (g, p) 对象对上调用了多个版本的 evaluate()。

现在，如果您只调用每个 evaluate() 函数，那么它可能是一个更好的用例，但您不再需要该内部循环:

 foreach (ObjectiveFunction* fp : funcs) {