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

Question

考虑:

#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;
}

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

Answer 1

因为在一般情况下,在编译时不可能确定它在运行时的类型.您的示例可以在编译时解决(请参阅@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 

另外,根据图灵证明的推论,可以证明,在一般情况下,C++编译器在数学上不可能知道基类指针在运行时指向的内容.

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

bool bp_points_to_base(const string& program_file);

这需要输入program_file:任何 C++源代码文本文件的名称,其中指针bp(如在OP中)调用其virtual成员函数show().并且可以在一般情况下确定(在首次调用成员函数的序列点A处):指针是否指向实例.virtualshow()bpbpBase

考虑以下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指向Baseat 的实例,A则"q.cpp"指向bp其他位置A.如果它确定在"q.cpp"中:bp不指向Baseat 的实例A,则"q.cpp"指向at bp的实例.这是一个矛盾.所以我们最初的假设不正确.因此不能为一般情况编写.BaseAbp_points_to_base

Answer 2

当已知对象的静态类型时,编译器通常会对此类调用进行虚拟化.将代码按原样粘贴到Compiler Explorer中会生成以下程序集:

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"可执行文件中存在.动态调度不仅已经过优化,整个基类也是如此.

Answer 3

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

是什么让你认为它呢？

您正在做出一个共同的假设:仅仅因为语言将此情况识别为使用运行时多态并不意味着在运行时执行调度.C++标准有一个所谓的"as-if"规则:C++标准规则的可观察效果是针对抽象机器描述的,并且实现可以自由地实现所述可观察的效果.

实际上,虚拟化是用于谈论编译器优化的一般词,旨在解决在编译时对虚拟方法的调用.

目标不是削减几乎无法察觉的虚拟调用开销(如果分支预测工作正常),那就是删除黑盒子.在优化方面,最好的收益是内联调用:这会打开常量传播和大量优化,并且只有在编译时调用函数体时才能实现内联(从那时起)它涉及删除调用并由函数体替换它).

一些虚拟化机会:

• 对类的final方法或virtual方法的调用final是非常简单的
• virtual如果该类是层次结构中的叶子,则可以对匿名命名空间中定义的类的方法的调用进行虚拟化
• virtual如果可以在编译时建立对象的动态类型,则可以对通过基类调用方法进行虚拟化(在您的示例中,构造在同一函数中)

但是,对于最先进的技术,您将需要阅读HonzaHubička的博客.Honza是一名gcc开发人员,去年他致力于推测性虚拟化:目标是计算动态类型的概率为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做了一个由五部分组成的帖子:

• C++中的虚拟化,第1部分
• C++中的虚拟化,第2部分(通过将存储转发到负载的低级中端虚拟化)
• C++中的虚拟化,第3部分(构建类型层次结构)
• C++中的虚拟化,第4部分(分析类型继承图以获得乐趣和利润)
• C++中的虚拟化,第5部分(反馈驱动的虚拟化)

Answer 4

编译器通常无法用静态调用替换运行时决策的原因有很多,主要是因为它涉及编译时不可用的信息,例如配置或用户输入.除此之外,我想指出为什么一般不可能这样做的另外两个原因.

首先,C++编译模型基于单独的编译单元.编译一个单元时,编译器只知道正在编译的源文件中定义的内容.考虑一个带有基类的编译单元和一个引用基类的函数:

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

单独编译时,编译器不了解实现的类型,Base因此无法删除动态调度.它也不是我们想要的东西,因为我们希望能够通过实现接口来扩展具有新功能的程序.在链接时可以这样做,但只能在程序完全完成的假设下进行.动态库可以打破这种假设,并且如下所示,总会出现根本不可能的情况.

一个更根本的原因来自可计算性理论.即使有完整的信息,也无法定义一种算法来计算是否达到程序中的某一行.如果你能解决暂停问题:对于一个程序P,我P'通过在末尾添加一行来创建一个新程序P.该算法现在能够确定是否到达该行,这解决了停止问题.

一般无法决定意味着编译器无法决定通常将哪个值分配给变量,例如

bool someFunction( /* arbitrary parameters */ ) {
     // ...
}

// ...
Base* b = nullptr;
if (someFunction( ... ))
    b = new Derived1();
else
    b = new Derived2();

b->polymorphicFunction();

即使在编译时已知所有参数,也不可能一般地证明将通过程序的哪条路径以及哪种静态类型b将具有.可以通过优化编译器来实现近似,但总有一些情况下它不起作用.

话虽如此,C++编译器非常努力地去除动态调度,因为它打开了许多其他优化机会,主要是因为能够通过代码内联和传播知识.如果您感兴趣,可以在GCC虚拟化实施中找到一篇有趣的博客文章.

Answer 5

如果优化器选择这样做,那么在编译时可以很容易地解决这个问题.

该标准指定了与运行时多态性发生时相同的行为.它没有具体通过实际运行时多态性实现.