为什么不能在编译时解决运行时多态性?

考虑:

#include<iostream> using namespace std; class Base { public: virtual void show() { cout<<" In Base \n"; } }; class Derived: public Base { public: void show() { cout<<"In Derived \n"; } }; int main(void) { Base *bp = new Derived; bp->show(); // RUN-TIME POLYMORPHISM return 0; } 

为什么这段代码会导致运行时多态性,为什么不能在编译时解决呢?

因为在一般情况下,在编译时不可能确定运行时的types。 你的例子可以在编译时parsing(参见@Quentin的答案),但是可以构造不能的例子,例如:

 Base *bp; if (rand() % 10 < 5) bp = new Derived; else bp = new Base; bp->show(); // only known at run time 

编辑:感谢@ nwp,这是一个更好的情况。 就像是:

 Base *bp; char c; std::cin >> c; if (c == 'd') bp = new Derived; else bp = new Base; bp->show(); // only known at run time 

而且,根据图灵certificate的推论,可以certificate在一般情况下 ,C ++编译器在运行时不可能知道基类指针指向什么。

假设我们有一个类似C ++编译器的函数:

 bool bp_points_to_base(const string& program_file); 

program_file其inputprogram_file任何 C ++源代码文本文件的名称,其中指针bp (与OP中一样)调用其virtual成员函数show() 。 并且可以在一般情况下 (在序列点A处,通过bp首先调用virtual成员函数show() )确定:指针bp是否指向Base的实例。

考虑下面的C ++程序“q.cpp”的片段:

 Base *bp; if (bp_points_to_base("q.cpp")) // invokes bp_points_to_base on itself bp = new Derived; else bp = new Base; bp->show(); // sequence point A 

现在,如果bp_points_to_base确定在“q.cpp”中: bp指向A处的Base实例,则“q.cpp”将bp指向AA其他内容。 如果确定在“q.cpp”中: bp没有指向A处的Base实例,则“q.cpp”将bp指向A处的Base实例。 这是一个矛盾。 所以我们最初的假设是错误的。 所以bp_points_to_base不能写成一般情况

当对象的静态types已知时,编译器会常规地虚拟化这些调用。 将代码原样粘贴到编译器资源pipe理器中,生成以下程序集:

 main: # @main pushq %rax movl std::cout, %edi movl $.L.str, %esi movl $12, %edx callq std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long) xorl %eax, %eax popq %rdx retq pushq %rax movl std::__ioinit, %edi callq std::ios_base::Init::Init() movl std::ios_base::Init::~Init(), %edi movl std::__ioinit, %esi movl $__dso_handle, %edx popq %rax jmp __cxa_atexit # TAILCALL .L.str: .asciz "In Derived \n" 

即使无法读取程序集,也可以看到只有"In Derived \n"存在于可执行文件中。 dynamic调度不仅被优化了,而且整个基类也是如此。

为什么这段代码会导致运行时多态性,为什么不能在编译时解决呢?

是什么让你觉得它呢?

您正在做出一个共同的假设:仅仅因为语言将这种情况识别为使用运行时多态并不意味着实现在运行时被分派。 C ++标准有一个所谓的“as-if”规则:C ++标准规则的可观察效果是关于抽象机器描述的,实现可以自由地实现所希望的所述可观察效果。


实际上, 虚拟化是用来说明编译器优化的通用词,旨在解决在编译时对虚拟方法的调用。

目标不是要削减几乎不明显的虚拟呼叫开销(如果分支预测工作正常),而是要消除黑盒子。 就优化而言,最好的收益是内联调用的关键:这将开启不断的传播和大量的优化,并且内联只能在被调用的函数的主体在编译时已知的时候才能实现(因为它涉及到删除调用,并由函数体取代它)。

一些虚拟化机会:

  • final方法或final类的virtual方法的调用是平凡的虚拟化
  • 在匿名命名空间中定义的类的virtual方法的调用可以是virtual ,如果该类是层次结构中的叶
  • 如果可以在编译时build立对象的dynamictypes,那么通过基类对virtual方法的调用可以是非virtual (这是你的例子的情况,其构造在相同的function中)

但是,对于最新的技术水平,您将需要阅读HonzaHubička的博客。 Honza是一名gcc开发人员,去年他从事推测性虚拟化 :他的目标是计算dynamictypes为A,B或C的概率,然后推测性地将这些调用虚拟化为转换:

 Base& b = ...; b.call(); 

成:

 Base& b = ...; if (b.vptr == &VTableOfA) { static_cast<A&>(b).call(); } else if (b.vptr == &VTableOfB) { static_cast<B&>(b).call(); } else if (b.vptr == &VTableOfC) { static_cast<C&>(b).call(); } else { b.call(); } // virtual call as last resort 

Honza做了一个5部分的职位:

  • C ++中的虚拟化,第1部分
  • C ++中的虚拟化,第2部分(将存储转发到负载的低级中端虚拟化)
  • C ++中的Devirtualization,第3部分(构buildtypes层次结构)
  • 在C ++中的虚拟化,第4部分(分析typesinheritance图的乐趣和利润)
  • C ++中的虚拟化,第5部分(反馈驱动的虚拟化)

编译器通常不能用静态调用replace运行时决策有很多原因,主要是因为它涉及编译时不可用的信息,例如configuration或用户input。 除此之外,我想指出另外两个原因,一般来说这是不可能的。

首先,C ++编译模型基于单独的编译单元。 当一个单元被编译时,编译器只知道被编译的源文件中定义了什么。 考虑一个带有基类的编译单元和一个引用基类的函数:

 struct Base { virtual void polymorphic() = 0; }; void foo(Base& b) {b.polymorphic();} 

当单独编译时,编译器不了解实现Base的types,因此不能删除dynamic分派。 这也不是我们想要的,因为我们希望能够通过实现接口来扩展程序的新function。 在链接的时候可以做到这一点,但只能在程序完全完成的前提下进行。 dynamic库可以打破这个假设,正如在下面可以看到的那样,总会有一些情况是完全不可能的。

一个更根本的原因来自可计算性理论。 即使有完整的信息,也不可能定义一个algorithm来计算程序中某一行是否到达。 如果你能解决停机问题:对于程序P ,我通过在P的末尾添加一个额外的行来创build一个新的程序P' 。 该algorithm现在可以决定是否到达该行,从而解决了停机问题。

一般无法做出决定意味着编译器无法决定将哪个值分配给variables,例如

 bool someFunction( /* arbitrary parameters */ ) { // ... } // ... Base* b = nullptr; if (someFunction( ... )) b = new Derived1(); else b = new Derived2(); b->polymorphicFunction(); 

即使在编译时已知所有参数,也不可能一般地certificate程序将采用哪条path以及哪个静态typesb具有。 近似值可以通过优化编译器来完成,但是总有些情况下它不起作用。

话虽如此,C ++编译器非常努力地去除dynamic调度,因为它打开了许多其他优化机会,主要是通过代码内联和传播知识。 如果你有兴趣, 你可以find一个有趣的,关于GCC虚拟化实现的博客post 。

如果优化器select这样做,那么编译时就可以很容易地解决这个问题。

该标准指定了与运行时多态性发生时相同的行为。 它并不具体是通过实际的运行时多态性来实现的。

基本上编译器应该能够弄清楚,这不应该导致运行时多态性在你的非常简单的情况下。 很可能有编译器,实际上这样做,但这主要是一个猜想。

问题是一般情况下,当你实际上正在构build一个复杂的案例,一些案件与图书馆的依赖,或复杂的分析后编译多个编译单元,这将需要保持相同的代码的多个版本,这会吹出AST一代 ,真正的问题归结为可判定性和停止问题。

如果在一般情况下可以虚拟化一个呼叫,则后者不允许解决问题。

暂停问题是决定一个给定input的程序是否会暂停( 我们说程序input对暂停 )。 众所周知,没有通用algorithm,例如编译器 ,可以解决所有可能的程序input对。

为了使编译器能够决定任何程序是否应该调用虚拟调用,它应该能够决定所有可能的程序input对。

为了做到这一点,编译器需要有一个algorithmA,它决定给定的程序P1和程序P2,其中P2进行虚拟呼叫,然后程序P3 {while({P1,I}!= {P2,I})}停止任何inputI.

因此编译器能够找出所有可能的虚拟化应该能够决定对任何可能的P3和I中的任何对(P3,I);对于所有可能的,因为A不存在是不可判定的。 然而,可以决定具体的情况,可以是眼睛。

这就是为什么在你的情况下,这个调用可以是虚拟化的,但不是任何情况。