38

假设我在抽象基类指针 mypointer->foo() 上有一个虚函数调用 foo()。当我的应用程序启动时，根据文件的内容，它选择实例化一个特定的具体类并将 mypointer 分配给该实例。在应用程序的余生中，mypointer 将始终指向该具体类型的对象。我无法知道这个具体类型是什么（它可能由动态加载库中的工厂实例化）。我只知道在第一次创建具体类型的实例后类型将保持不变。指针可能并不总是指向同一个对象，但该对象总是具有相同的具体类型。请注意，类型在技术上是在“运行时”确定的，因为它基于文件的内容，但在“启动”（加载文件）之后，类型是固定的。

但是，在 C++ 中，每次在应用程序的整个持续时间内调用 foo 时，我都会支付虚函数查找成本。编译器无法优化查找，因为它无法知道具体类型在运行时不会发生变化（即使它是有史以来最神奇的编译器，它也无法推测动态加载的行为图书馆）。在 Java 或 .NET 等 JIT 编译语言中，JIT 可以检测到重复使用相同的类型并进行内联缓存。我基本上是在寻找一种方法来手动为 C++ 中的特定指针执行此操作。

C++ 中有什么方法可以缓存这个查找吗？我意识到解决方案可能非常骇人听闻。如果可以编写配置测试来发现 ABI/编译器的相关方面，那么我愿意接受 ABI/编译器特定的 hack，即使它不是真正可移植的，它也是“实际上可移植的”。

更新：对于反对者：如果这不值得优化，那么我怀疑现代 JIT 会这样做。您是否认为 Sun 和 MS 的工程师正在浪费时间实施内联缓存，并且没有对其进行基准测试以确保有改进？

4

9 回答 9

39

虚函数调用有两个成本：vtable 查找和函数调用。

vtable 查找已经由硬件处理。现代 CPU（假设您不是在非常简单的嵌入式 CPU 上工作）将在其分支预测器中预测虚拟函数的地址，并推测性地与数组查找并行执行它。 vtable 查找与函数的推测执行并行发生的事实意味着，在您描述的情况下在循环中执行时，与直接的非内联函数调用相比，虚函数调用的开销几乎为零。

我过去实际上已经对此进行了测试，尽管使用的是 D 编程语言，而不是 C++。当在编译器设置中禁用内联并且我在循环中调用相同的函数数百万次时，无论该函数是否为虚拟函数，时间都在彼此的 epsilon 范围内。

虚函数的第二个也是更重要的成本是它们在大多数情况下阻止了函数的内联。这比听起来更重要，因为内联是一种优化，它可以启用其他几种优化，例如在某些情况下进行常量折叠。如果不重新编译代码，就无法内联函数。JIT 解决了这个问题，因为它们在执行应用程序期间不断地重新编译代码。

于 2010-01-26T18:52:52.297 回答
20

为什么虚拟通话很贵？因为在运行时执行代码之前，您根本不知道分支目标。即使是现代 CPU 仍然可以完美地处理虚拟调用和间接调用。不能简单地说它没有成本，因为我们只是拥有更快的 CPU。不它不是。

1.我们怎样才能让它快点？

你已经对这个问题有了相当深刻的理解。但是，我只能说，如果虚函数调用很容易预测，那么您可以执行软件级优化。但是，如果不是（即，您真的不知道虚函数的目标是什么），那么我认为目前没有好的解决方案。即使对于 CPU，在这种极端情况下也很难预测。

实际上，Visual C++ 的 PGO（Profilingguided optimization）等编译器具有虚拟调用推测优化（Link）。如果分析结果可以枚举热的虚函数目标，那么它将转换为可以内联的直接调用。这也称为去虚拟化。它也可以在一些 Java 动态优化器中找到。

2. 对于那些说没有必要的人

如果您使用脚本语言、C# 并且担心编码效率，是的，它毫无价值。但是，如果任何人都渴望节省单个循环以获得更好的性能，那么间接分支仍然是一个重要的问题。即使是最新的 CPU 也不能很好地处理虚拟呼叫。一个很好的例子是虚拟机或解释器，它们通常有一个非常大的 switch-case。它的性能与间接分支的正确预测非常相关。所以，你不能简单地说它太低级或没有必要。有数百人正在努力提高底层的性能。这就是为什么你可以简单地忽略这些细节:)

3. 一些与虚函数相关的枯燥的计算机架构事实

dsimcha 为 CPU 如何有效处理虚拟调用写了一个很好的答案。但是，它并不完全正确。首先，所有现代 CPU 都有分支预测器，它从字面上预测分支的结果以增加流水线吞吐量（或者，指令级别的更多并行性，或ILP。我什至可以说单线程 CPU 性能完全取决于你有多少可以从单个线程中提取ILP。分支预测是获得更高ILP的最关键因素）。

在分支预测中，有两个预测：（1）方向（即，分支被采用？或不被采用？二进制答案），和（2）分支目标（即，我将去哪里？它不是二进制答案）。基于预测，CPU推测性地执行代码。如果推测不正确，则 CPU 回滚并从错误预测的分支重新启动。这对程序员来说是完全隐藏的。因此，除非您使用 VTune 进行分析，否则您并不真正知道 CPU 内部发生了什么，这会给出分支错误预测率。

一般来说，分支方向预测是高度准确的（95%+），但仍然很难预测分支目标，尤其是虚拟调用和 switch-case（即跳转表）。虚拟调用是间接分支，需要更多的内存负载，并且 CPU 需要分支目标预测。现代 CPU 像 Intel 的 Nehalem 和 AMD 的 Phenom 都有专门的间接分支目标表。

但是，我不认为查找 vtable 会产生很多开销。是的，它需要更多的内存负载，这可能会导致缓存未命中。但是，一旦 vtable 被加载到缓存中，那么它几乎就是缓存命中。如果您还担心该成本，您可以提前将预取代码加载到 vtable 中。但是，虚函数调用的真正难点在于CPU无法很好地预测虚调用的目标，这可能导致由于目标的错误预测而导致流水线频繁流失。

于 2010-01-26T19:48:04.593 回答
4

因此，假设这是您要解决的基本问题（以避免过早的优化参数），并且忽略平台和编译器特定的hackery，您可以在复杂性的两端做两件事之一：

  1. 提供一个函数作为 .dll 的一部分，该函数在内部直接调用正确的成员函数。您支付了间接跳转的成本，但至少您不支付 vtable 查找的成本。您的里程可能会有所不同，但在某些平台上，您可以优化间接函数调用。
  2. 重构您的应用程序，而不是调用每个实例的成员函数，而是调用单个函数，该函数采用一组实例。Mike Acton 有一篇精彩的文章（针对特定平台和应用程序类型），介绍了为什么以及如何执行此操作。
于 2010-01-26T18:52:42.380 回答
4

所有答案都是针对最简单的场景，调用虚拟方法只需要获取要调用的实际方法的地址。在一般情况下，当多重继承和虚拟继承发挥作用时，调用虚拟方法需要移动this指针。

方法分派机制可以通过多种方式实现，但通常会发现虚拟表中的条目不是实际调用的方法，而是编译器插入的一些中间“蹦床”代码，用于重定位this指针在调用实际方法之前。

当调度是最简单的，只是一个额外的指针重定向，那么试图优化它是没有意义的。当问题更复杂时，任何解决方案都将依赖于编译器并且是骇人听闻的。此外，您甚至不知道自己处于什么场景：如果对象是从 dll 加载的，那么您并不真正知道返回的实际实例属于简单的线性继承层次结构还是更复杂的场景。

于 2010-01-26T19:28:49.857 回答
2

我最近问了一个非常相似的问题，得到的答案是它可以作为 GCC 扩展，但不能移植：

C ++：指向虚拟成员函数的单态版本的指针？

特别是，我还用 Clang 尝试过它，它不支持这个扩展（即使它支持许多其他 GCC 扩展）。

于 2011-03-19T12:07:17.003 回答
2

您不能使用方法指针，因为指向成员函数的指针不被视为协变返回类型。请参见下面的示例：

#include <iostream>

struct base;
struct der;

typedef void(base::*pt2base)();
typedef void(der::*pt2der)();

struct base {
    virtual pt2base method() = 0;
    virtual void testmethod() = 0;
    virtual ~base() {}
};

struct der : base {
    void testmethod() {
        std::cout << "Hello from der" << std::endl;
    }
    pt2der method() { **// this is invalid because pt2der isn't a covariant of pt2base**
        return &der::testmethod;
    }
};

另一种选择是声明方法pt2base method()，但返回无效，因为 der::testmethod 不是 pt2base 类型。

此外，即使您有一个接收 ptr 或对基类型的引用的方法，您也必须在该方法中将其动态转换为派生类型，以执行任何特别多态的操作，这会增加我们试图节省的成本。

于 2010-01-26T20:34:21.563 回答
2

我见过避免虚函数调用是有益的情况。在我看来，这不是其中一种情况，因为您确实在多态地使用该函数。你只是在追逐一个额外的地址间接，而不是一个巨大的打击，而且在某些情况下可能会被部分优化掉。如果它确实很重要，您可能需要重组代码，以便减少诸如虚函数调用之类的类型相关选择，将其拉到循环之外。

如果您真的认为值得一试，您可以设置一个单独的函数指针，指向特定于该类的非虚拟函数。我可能（但可能不会）考虑这样做。

class MyConcrete : public MyBase
{
public:
  static void foo_nonvirtual(MyBase* obj);
  virtual void foo()
  { foo_nonvirtual(this); }
};

void (*f_ptr)(MyBase* obj) = &MyConcrete::foo_nonvirtual;
// Call f_ptr instead of obj->foo() in your code.
// Still not as good a solution as restructuring the algorithm.

除了让算法本身更明智之外，我怀疑任何手动优化虚函数调用的尝试都会导致比它解决的问题更多的问题。

于 2010-01-26T19:05:38.280 回答
2

因此，您基本上想要做的是将运行时多态性转换为编译时多态性。现在您仍然需要构建您的应用程序，以便它可以处理多个“案例”，但是一旦确定了哪个案例适用于运行，那就是持续时间。

这是运行时多态案例的模型：

struct Base {
  virtual void doit(int&)=0;
};

struct Foo : public Base {
  virtual void doit(int& n) {--n;}
};

struct Bar : public Base {
  virtual void doit(int& n) {++n;}
};

void work(Base* it,int& n) {
  for (unsigned int i=0;i<4000000000u;i++) it->doit(n);
}

int main(int argc,char**) {
  int n=0;

  if (argc>1)
    work(new Foo,n);
  else
    work(new Bar,n);

  return n;
}

这需要大约 14 秒才能在我的 Core2 上执行，使用 gcc 4.3.2（32 位 Debian）-O3选项编译。

现在假设我们用模板化版本替换“工作”版本（模板化在它将要处理的具体类型上）：

template <typename T> void work(T* it,int& n) {
  for (unsigned int i=0;i<4000000000u;i++) it->T::doit(n);
}

main实际上不需要更新，但请注意，work现在的 2 次调用触发了两个不同且特定于类型的函数的实例化和调用（参见之前的一个多态函数）。

嘿 presto 在 0.001 秒内运行。对于 2 行更改来说，这是一个不错的加速因素！但是，请注意，大幅加速完全归功于编译器，一旦work消除了函数中运行时多态的可能性，只需优化循环并将结果直接编译到代码中即可。但这实际上说明了重要的一点：根据我的经验，使用这种技巧的主要收益来自改进内联和优化的机会，它们允许编译器在生成较少多态、更具体的函数时，而不是仅仅删除vtable 间接（这真的很便宜）。

但我真的不建议做这样的事情，除非分析绝对表明运行时多态性真的会影响你的性能。一旦有人继承Foo或Bar尝试将其传递给实际用于其基础的函数，它也会咬你。

您可能会发现这个相关问题也很有趣。

于 2010-01-26T22:39:51.657 回答
0

你可以使用方法指针吗？

这里的目标是编译器将使用已解析方法或函数的位置加载指针。这会发生一次。分配后，代码将以更直接的方式访问该方法。

我知道指向对象的指针并通过对象点访问该方法会调用运行时多态性。但是，应该有一种方法可以将方法指针加载到已解析的方法，避免多态性并直接调用该函数。

我检查了社区 wiki 以引入更多讨论。

于 2010-01-26T19:58:21.793 回答