替代的虚函数调用实现?

49

C++通过虚拟机制支持动态绑定。但据我所知,虚拟机制是编译器的实现细节,标准只规定了特定情况下应该发生的行为。大多数编译器都通过虚拟表和虚拟指针来实现虚拟机制。这不涉及虚拟指针和表的实现细节。我的问题是:

  1. 是否有任何编译器以除了虚拟指针和虚拟表机制之外的其他方式实现虚拟函数的动态调度?据我所见,大多数编译器(如G++、Microsoft Visual Studio)都是通过虚拟表和指针机制来实现的。那么实际上还存在其他的编译器实现方式吗?
  2. 仅具有一个虚拟函数的任何类的sizeof将是该编译器上指针(在this中的vptr)的大小。因此,鉴于虚拟指针和TBL机制本身是编译器的实现,我上述说法是否总是正确的?

2
@Als...我也对同样的问题思考了很长时间,从未想过发起讨论。感谢你的启动,Als。 - Nawaz
1
如果你想知道在不同编译器生成的模块之间使用接口(虚基类)是否安全,请记住,即使两个编译器都使用虚表,虚表布局也必须匹配。(还有调用约定和其他一些东西。)COM的工作假设给定平台上的所有编译器都可以创建兼容的虚表(对于该平台),尽管我认为这种假设在某些编译器上失败了(或者至少很难满足)。 - Leo Davidson
非常好的问题。我相信可能会有编译器,而不是使用vptr,将整个函数表存储在每个对象中。在某些非常特定的情况下,这可能很有价值,因为在虚拟函数调用期间,这种方法可以节省额外的内存间接引用。在驱动程序开发中,这可能是至关重要的:这种间接引用可能导致对分页内存的访问。 - valdo
@valdo: 然而,在一般情况下,那会浪费很多内存空间。 - Johan Kotlinski
别忘了,如果你启用了RTTI编译... - rwong
@kotlinski:当然。这就是为什么我说在某些非常特定的情况下,这可能是有意义的。 - valdo
11个回答

22

并非对象中的vtable指针始终是最有效的。我的另一种语言的编译器曾经出于类似原因使用对象内指针,但现在不再这样做:它使用单独的数据结构将对象地址映射到所需的元数据,在我的系统中,这实际上是用于垃圾收集器的形状信息。

对于单个简单对象,该实现会多花费一些存储空间,但对于具有许多基类的复杂对象来说更加高效,而且对于数组来说也要高效得多,因为所有对象在数组中只需要一个映射表条目。特别是在我的实现中,可以在对象内部的任何点给定指针时找到元数据。

实际的查找非常快速,存储要求非常低,因为我使用了全球最佳的数据结构:Judy 数组。

我还不知道有哪个 C++ 编译器使用除 vtable 指针之外的其他方式,但这并不是唯一的方式。实际上,由于具有基类的类的初始化语义使任何实现变得混乱,因为完整类型必须随着对象的构建而来回移动。由于这些语义,复杂的 mixin 对象会导致生成大量的 vtable,大型对象和缓慢的对象初始化。这可能不仅是 vtable 技术的后果,还因为需要完全遵循子对象的运行时类型始终正确的要求。实际上,在构建期间没有必要这样做,因为构造函数不是方法,不能明智地使用虚拟分派:但在析构期间这一点并不那么清楚,因为析构函数是真正的方法。


3
为什么您首先想要使用虚拟对象创建数组?考虑到数组是同类的(至少在C++中),这似乎非常无用。但对于数组来说,使用虚拟对象会显着提高效率。 - Johan Kotlinski
3
最后一段中提到了同样的原因使得需要在构造和销毁期间跟踪具体类型。虽然构造函数和析构函数都不是真正的成员函数,但它们可以调用其他成员函数,包括虚成员函数。不同的编程语言以不同的方式解决这个问题,C++在每个阶段都跟踪对象的类型,而Java则始终将对象视为最派生类型。两种方法都不完美,但这是一个必须做出的设计决策。 - David Rodríguez - dribeas
@David 你确定析构函数不是真正的成员函数吗?如果我没记错,当使用“placement new”时,你必须在释放、删除、回滚等操作之前手动调用dtor,以便在对象所在的内存中调用dtor。(如果你想要调用dtor) - KitsuneYMG
@KitsuneYMG:它们不是真正的、常见的成员函数。虽然你可以使用放置new触发对构造函数的调用,也可以手动调用析构函数,就像它是一个成员函数一样,但它们具有非常特定的行为,与成员函数不同。特别是当正在执行构造函数或析构函数时,对对象上的虚函数的调用将不会被多态地分派(更准确地说,它不会在正在构造/析构的类型下进行多态分派)。 - David Rodríguez - dribeas
另外需要注意的是:你实际上可以通过动态分派从构造函数中调用虚方法,只需要通过一层间接调用即可。你可以调用一个函数,该函数接受对基类型的引用并调用虚函数,间接函数必须使用虚分派,因为它不知道对象的确切类型。 - David Rodríguez - dribeas
显示剩余4条评论

8
据我所知,所有的C++实现都使用虚表指针,尽管通过在对象中保留一个小的类型索引(1-2B),并随后通过小的表查找获取虚表和类型信息是非常容易的(也许不会有太大性能问题,因为缓存)。另一种有趣的方法可能是BIBOP(http://foldoc.org/BIBOP)——页面的大袋子,但它对C++有问题。思路是:将相同类型的对象放在同一页上。通过对对象指针的低位进行简单地与运算,可以获得页面顶部的类型描述符/虚表的指针。(当然,对于栈上的对象效果不好!)
另外一种方法是在对象指针本身中编码特定的类型标签/索引。例如,如果构造时所有对象都是16字节对齐的,则可以使用4个LSB来放置4位类型标签(这些位数不够)。或者(尤其适用于嵌入式系统),如果地址中有保证的未使用的更高有效位,则可以将更多的标记位放置在那里,并通过移位和掩码恢复它们。
虽然这两种方案对于其他语言实现很有趣(有时也会使用),但它们对于C++来说存在问题。某些C++语义(例如,在基类对象构造和析构期间调用哪些基类虚函数覆盖)会驱使您采用一种模型,在该模型中存在某些在进入基类构造函数/析构函数时修改的对象状态。
您可能会发现我关于Microsoft C++对象模型实现的旧教程很有趣。 http://www.openrce.org/articles/files/jangrayhood.pdf 愉快的编码!

所以它被称为BIBOP,甚至可能在实际语言中存在! :) 堆栈分配对象问题可以通过将整个堆栈视为一个单独的巨大对象,并带有令人困惑的大量thunk“方法”,在某个地方查找this并相应转发来解决。 - j_random_hacker

6
  1. 我认为现代编译器除了vptr/vtable之外没有其他的方法。实际上,很难想出其他不仅仅是简单低效的方法。

    然而,在这种方法中仍然有相当大的设计折衷空间。也许特别是关于虚继承的处理方式。因此,将其实现定义是有意义的。

    如果您对此类内容感兴趣,我强烈建议阅读《C++对象模型内幕》

  2. sizeof class 取决于编译器。如果您想要可移植的代码,请不要做任何假设。


我记得几周/几个月前,Matthieu在评论中指出确实有其他的实现方式。但我无法确定这是理论上的还是已经存在的编译器,也不确定是否涉及C++,并且也找不到相关信息。抱歉。 - sbi
不,我并不是说在所有编译器中大小都将固定相同。问题是,在特定的编译器上,它是否等于指针的大小?这个问题是因为 IMU 中的 vptr 占用了指针大小,但由于某些编译器可能没有 vptr,因为虚拟机制是实现相关的,那么这个事实会如何影响语句呢? - Alok Save
@Als:这是人们所期望的,但并不保证。 - Johan Kotlinski
6
例如,如果我们的应用程序最多有256个类,编译器和链接器可以将typeid打包在一个char中,并在查找表中找到vptr。这样,我们就可以使sizeof(T)等于1。 - Johan Kotlinski

5
我所知道的所有当前编译器都使用vtable机制。
这是可能的一个优化,因为C++是静态类型检查的。
在一些更动态的语言中,相反地,在对象的最派生类中开始搜索调用虚拟成员函数的实现,沿着基类链往上搜索。例如,这就是原始Smalltalk的工作方式。而C++标准描述了虚拟调用的效果,“好像”使用了这样的搜索。
在上世纪90年代的Borland/Turbo Pascal中,这种动态搜索被用于查找Windows API“窗口消息”的处理程序。并且我认为可能是Borland C++中也是如此。它除了常规的vtable机制之外,仅用于消息处理程序。
如果它在Borland/Turbo C++中使用 - 我记不清了 - 那么它是支持一种语言扩展的,该扩展允许您将消息ID与消息处理程序函数相关联。
正式地说不是(即使假设使用vtable机制),这取决于编译器。由于标准不需要vtable机制,因此它对每个对象中vtable指针的放置位置没有任何规定。而其他规则允许编译器自由添加填充、未使用的字节在结尾处。
但实际上也许是这样。;-)
但这不是您应该依赖的东西,也不是您需要依赖的东西。但在另一个方向上,您可以“要求”这样做,例如如果您正在定义ABI。那么任何不符合您要求的编译器都不符合您的要求。
问候 & hth.

这是一种优化,因为C++具有静态类型检查的特性,所以它是可能的,这是C++设计的一部分。 - curiousguy
@curiousguy:抱歉,我不理解你的评论。 - Cheers and hth. - Alf
C++的类型检查是基于类标识(类名),而不是类结构(内容)。静态类型检查可以使用类型标识或类型内容,因此具有等效定义的两个类可以被认为是类型兼容的甚至具有相同的类型。 - curiousguy
还是不太明白,很抱歉。我想你的意思是可能设计一些静态类型,在这些类型中vtable并不实用。当然。 - Cheers and hth. - Alf

4
在尝试想象一种替代方案时,我想到了以下方案,类似于Yttril's answer。据我所知,没有编译器使用它!通过提供足够大的虚拟地址空间和灵活的操作系统内存分配例程,可以使new在固定且不重叠的地址范围内分配不同类型的对象。然后,可以使用右移操作快速推断对象的类型,并使用结果索引vtable表,从而每个对象可以节省1个vtable指针。乍一看,这个方案可能会遇到堆栈分配对象的问题,但是可以进行清理处理:
  1. 对于每个栈分配的对象,编译器会添加代码,在对象创建时向全局数组中添加一个记录 (地址范围,类型) 对,并在销毁时删除该记录。
  2. 包含栈的地址范围将映射到一个单独的虚表,其中包含大量的 thunk,这些 thunk 读取 this 指针,扫描数组以查找相应地址处对象的类型(vptr),并调用指向的虚表中的相应方法。(即第42个 thunk 将调用虚表中的第42个方法——如果任何类中使用的最多的虚函数是 n,则至少需要 n 个 thunk。)

这种方案显然会产生非常大的开销(至少需要O(log n)的查找时间)用于基于堆栈的对象进行虚方法调用。在不存在基于堆栈对象的数组或组合(包含在另一个对象中)时,可以使用更简单和更快速的方法,在对象之前将vptr放置在堆栈上(请注意,它不被视为对象的一部分,并且不会按照sizeof所测量的大小进行贡献)。在这种情况下,thunks只需从this减去sizeof (vptr)即可找到正确的vptr并像以前一样转发。


该方法将允许通过其地址来确定对象的堆栈性质。 - Ben Voigt
1
@Ben Voigt:不确定您的意思……是的,除非你在设备驱动程序中做了极端奇怪的事情,“堆栈性”已经由地址“确定”了。 - j_random_hacker
1
哦,现在我明白你在做什么了...但是我认为让调用站点测试堆栈地址比所有这些thunk/shim更便宜。 - Ben Voigt

4

据我所知,Eiffel使用了一种不同的方法,所有对方法的覆盖最终都会合并在同一个地址中,并编译一个序言来检查对象类型(因此每个对象必须有一个类型ID,但它不是指向VMT的指针)。当然,这对于C++来说需要在链接时创建最终函数。

然而,我不知道任何使用这种方法的C++编译器。


4
有没有其他编译器实现虚拟机制的方式,而不是使用虚拟指针和虚拟表机制?就我所见,大多数(例如g++、Microsoft Visual Studio)都是通过虚拟表和指针机制来实现的。因此,实际上是否有其他编译器实现呢?
据我所知,没有使用C++编译器实现的其他方式,但你可能会发现了解二叉树调度很有趣。如果你有兴趣以任何方式利用虚拟调度表的预期,你应该知道编译器可以在编译时 - 在类型在编译时已知的情况下 - 有时可以解析虚拟函数调用,因此可能不会查询表。
对于只有一个虚函数的任何类,其大小将是编译器中指针(this中的vptr)的大小,因此,假设没有具有自己虚成员的基类和没有虚基类,这个说法是否总是正确的?
假设没有具有自己虚成员的基类和没有虚基类,这个说法极有可能是正确的。可以想象替代方案 - 例如,整个程序分析揭示了类层次结构中仅有一个成员,并且切换到编译时调度。如果需要运行时调度,则难以想象为什么任何编译器都会引入进一步的间接性。尽管如此,标准故意没有精确规定这些事情,以便实现可以变化或在将来变化。

1
各种Inria项目(Smalleifell,Cecil)都使用BTDs。他们甚至在JVM中进行了测试。最近,Nim也使用了它。 - Fizz

3

C++/CLI偏离了这两种假设。如果您定义一个ref class,它根本不会被编译成机器代码;相反,编译器将其编译为.NET托管代码。在中间语言中,类是一种内置的特性,并且虚方法集合是在元数据中定义的,而不是在方法表中。

实现对象布局和调度的具体策略取决于VM。在Mono中,只包含一个虚方法的对象在MonoObject结构中需要两个指针来存储;第二个用于对象的同步。由于这是实现定义的,而且也没什么用处,所以C++/CLI不支持ref classes的sizeof操作。


3
这与原问题有何关联?他询问的是C++,而不是基于CLR的语言... - Jörgen Sigvardsson
2
它展示了编译器可能需要偏离传统实现策略的条件。此外,“C ++”是否包括“标准C ++”和“C ++ / CLI”存在争议。 - Martin v. Löwis

3
  1. 我从未听说过或见过任何使用其他实现的编译器。虚函数表之所以如此流行,是因为它不仅是最高效的实现方式,而且是最容易设计和最明显的实现方式。

  2. 在几乎任何你想使用的编译器上,这几乎肯定是正确的。然而,并非总是如此——即使情况几乎总是如此,你也不能依赖它。你喜欢的编译器也可能改变它的对齐方式,增加它的大小,玩个乐子,但不告诉你。据我记忆,它还可以插入任何调试信息和任何它喜欢的内容。


1
第二部分的推理非常有道理,但这是否意味着无法估计编译器可能分配给类或结构体的大小,完全由编译器自行决定?再想一想...我们可以反驳说这正是sizeof()存在的原因。 - Alok Save

1

首先,提到了Borland对C++的专有扩展——动态分派虚拟表(DDVT),你可以在一个名为DDISPATC.ZIP的文件中阅读相关内容。Borland Pascal同时具备虚拟方法动态方法,而Delphi还引入了一种“消息”语法,类似于动态方法,但用于处理消息。目前我不确定Borland C++是否具有同样的功能。Pascal和Delphi都没有多重继承,因此Borland C++ DDVT可能与Pascal或Delphi不同。

其次,在1990年代及早期,有人试验不同的对象模型,Borland并不是最先进的。我个人认为关闭IBM SOMobjects对我们所有人造成了损害。在关闭SOM之前,有过使用Direct-to-SOM C ++编译器进行实验。因此,SOM代替了C ++调用方法的方式。它在许多方面类似于C ++ vtable,但也有几个例外。首先,为了防止脆弱的基类问题,程序不使用vtable内部的偏移量,因为它们不知道这个偏移量。如果基类引入新方法,则它可能会改变。而是调用在运行时创建的具有此知识的thunk,该thunk具有其汇编代码中的这些知识。还有一个区别。在C ++中,当使用多重继承时,对象可以包含多个VMT IIRC。与C ++相比,每个SOM对象仅有一个VMT,因此分派代码应与“call dword ptr [VMT + offset]”不同。

这里有一份与SOM相关的文档,SOM中发布到发布的二进制兼容性。您可以在其中找到我所知道的另外一些项目,例如Delta/C++Sun OBI的比较。它们解决了SOM解决的问题子集,并通过这样做也略微调整了调用代码。

我最近发现Visual Age C++ v3.5 for Windows编译器片段足以让事情运行并实际接触它。大多数用户不太可能获取OS/2 VM来使用DTS C++,但拥有Windows编译器完全是另一回事。 VAC v3.5是第一个也是最后一个支持Direct-to-SOM C++功能的版本。VAC v3.6.5和v4.0不适合。

  1. 从IBM FTP下载VAC 3.5 fixpak 9。这个fixpak包含很多文件,所以你甚至不需要完整的编译器(我有3.5.7版本,但fixpak 9足够大,可以进行一些测试)。
  2. 解压到例如C:\ home \ OCTAGRAM \ DTS
  3. 启动命令行并在其中运行后续命令
  4. 运行:set SOMBASE = C:\ home \ OCTAGRAM \ DTS \ ibmcppw
  5. 运行:C:\ home \ OCTAGRAM \ DTS \ ibmcppw \ bin \ SOMENV.BAT
  6. 运行:cd C:\ home \ OCTAGRAM \ DTS \ ibmcppw \ samples \ compiler \ dts
  7. 运行:nmake clean
  8. 运行:nmake
  9. hhmain.exe和它的dll在不同的目录中,因此我们必须想办法让它们相互找到;由于我正在进行几个实验,所以我执行了“set PATH =%PATH%; C:\ home \ OCTAGRAM \ DTS \ ibmcppw \ samples \ compiler \ dts \ xhmain \ dtsdll”一次,但你可以将dll复制到hhmain.exe附近
  10. 运行:hhmain.exe
我用这种方式得到了输出:

Local anInfo->x = 5
Local anInfo->_get_x() = 5
Local anInfo->y = A
Local anInfo->_get_y() = B
{An instance of class info at address 0092E318

}

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接