你能用C++缓存虚函数查找吗？

Question

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

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

在C++中是否有任何方法可以缓存此查找？我意识到解决方案可能非常糟糕.我愿意接受ABI /编译器特定的黑客攻击,如果有可能编写发现ABI /编译器相关方面的配置测试,那么即使不是真正可移植的,它也"实际上是可移植的".

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

Answer 1

虚函数调用有两个成本:vtable查找和函数调用.

vtable查找已由硬件处理.现代CPU(假设您没有使用非常简单的嵌入式CPU)将在其分支预测器中预测虚函数的地址,并与阵列查找并行地推测性地执行它. vtable查找与函数的推测执行并行发生的事实意味着,当您在描述的情况下在循环中执行时,与直接的非内联函数调用相比,虚函数调用几乎具有零开销.

我实际上在过去测试过这个,虽然是D编程语言,而不是C++.当在编译器设置中禁用内联并且我在循环中调用相同的函数几百万次时,无论函数是否为虚函数,时间都在彼此的epsilon之内.

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

Answer 2

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

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

你已经非常了解这个问题了.但是,我唯一可以说,如果虚拟函数调用很容易预测,那么您可以执行软件级优化.但是,如果不是(也就是说,你真的不知道虚拟功能的目标是什么),那么我认为现在还没有好的解决方案.即使对于CPU,在这种极端情况下也很难预测.

实际上,Visual C++的PGO(Profiling引导优化)等编译器具有虚拟调用推测优化(Link).如果分析结果可以枚举热的虚函数目标,则它转换为可以内联的直接调用.这也称为虚拟化.它也可以在一些Java动态优化器中找到.

2.对那些说不必要的人

如果你正在使用脚本语言,C#并关注编码效率,是的,它是没有价值的.但是,任何渴望保存单个循环以获得更好性能的人,那么间接分支仍然是重要的问题.即使是最新的CPU也无法处理虚拟呼叫.一个很好的例子是虚拟机或解释器,它通常具有非常大的开关盒.它的性能与间接分支的正确预测非常相关.所以,你不能简单地说它太低级别或没有必要.有数百人试图改善底层的表现.这就是为什么你可以简单地忽略这些细节:)

3.与虚拟功能相关的一些无聊的计算机架构事实

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

在分支预测中,有两个预测:(1)方向(即,分支是否采取？二进制答案),以及(2)分支目标(即,我将去哪里？它不是二进制答案).根据预测,CPU 推测性地执行代码.如果推测不正确,则CPU回滚并从错误预测的分支重新启动.程序员的观点完全隐藏了这一点.所以,你真的不知道CPU内部发生了什么,除非你用VTune进行分析,这给出了分支误预测率.

通常,分支方向预测是高度准确的(95%+),但仍然难以预测分支目标,尤其是虚拟呼叫和交换机情况(即跳转表).Vrtual调用是间接分支,需要更多的内存负载,并且CPU也需要分支目标预测.像英特尔的Nehalem和AMD的Phenom这样的现代CPU都有专门的间接分支目标表.

但是,我不认为查找vtable会产生很多开销.是的,它需要更多的内存负载,这可能会导致缓存未命中.但是,一旦vtable被加载到缓存中,那么它几乎就是缓存命中.如果您还关注该费用,您可以提前预先加载预取代码以加载vtable.但是,虚函数调用的真正困难在于CPU不能很好地预测虚拟调用的目标,这可能导致管道由于目标的错误预测而频繁流失.

Answer 3

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

1. 提供一个函数作为 .dll 的一部分，在内部直接调用正确的成员函数。你付出了间接跳转的成本，但至少你不用付出虚函数表查找的成本。您的情况可能会有所不同，但在某些平台上，您可以优化间接函数调用。
2. 重构您的应用程序，这样您就可以调用一个接受实例集合的单个函数，而不是为每个实例调用一个成员函数。Mike Acton 有一篇精彩的文章（针对特定平台和应用程序类型）介绍了为什么以及如何执行此操作。