Pourquoi ne peut-polymorphisme de l'exécution être résolu au moment de la compilation?

Question

Considérer:

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

Pourquoi est-ce que le code de cause polymorphisme de l'exécution et pourquoi ne peut-il pas être résolu au moment de la compilation?

Answer 1

Parce que dans le cas général, il est impossible au moment de la compilation afin de déterminer quel type, il le sera au moment de l'exécution. Votre exemple peut être résolu au moment de la compilation (voir la réponse de @Quentin), mais le cas peut être construit qui ne peut pas, comme:

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

EDIT: Merci à @phn, voici une bien meilleure affaire. Quelque chose comme:

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

Aussi, en corollaire de Turing est la preuve, il peut être montré que dans le cas général, il est mathématiquement impossible pour un compilateur C++ pour savoir ce qu'est une classe de base d'un pointeur au moment de l'exécution.

Supposons que nous avons un compilateur C++-comme la fonction:

bool bp_points_to_base(const string& program_file);

Qui prend comme entrée program_file: le nom de toute C++ code source fichier texte où un pointeur bp (comme dans l'OP) appelle ses virtual fonction membre show(). Et peut déterminer dans le cas général (au point de séquence A où l' virtual fonction membre show() est d'abord appelée par le biais d' bp): si le pointeur bp de points à une instance d' Base ou pas.

Considérons le fragment suivant du programme en 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

Maintenant, si bp_points_to_base détermine qu' "q.cpp": bp de points à une instance d' Base à A alors "q.cpp" les points de bp d'autre chose en A. Et si elle détermine qu' "q.cpp": bp ne pointe pas vers une instance d' Base à A, alors "q.cpp" les points de bp à une instance d' Base à A. C'est une contradiction. Donc, notre hypothèse de départ est incorrect. Donc, bp_points_to_base ne peuvent pas être écrits pour le cas général.

Answer 2

Les compilateurs régulièrement devirtualise de tels appels, lorsque le type statique de l'objet est connu. Coller votre code est en Compilateur Explorer produit de l'assemblage suivant:

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"

Même si vous ne pouvez pas lire l'assemblée, vous pouvez voir que seulement "In Derived \n" est présent dans le fichier exécutable. Non seulement a-répartition dynamique en été optimisé, donc a l'ensemble de la classe de base.

Answer 3

Pourquoi ce code causer des temps d'exécution de polymorphisme et pourquoi ne peut-il pas être résolu au moment de la compilation?

Ce qui vous fait penser qu'il fait?

Vous faites une hypothèse commune: juste parce que la langue identifie ce cas que l'utilisation de temps d'exécution polymorphisme ne signifie pas que la mise en œuvre est tenu de les expédier, au moment de l'exécution. La Norme C++ est un soi-disant "comme-si" la règle: les effets observables de la Norme C++ règles sont décrites à l'égard d'une machine abstraite, et les implémentations sont libres d'atteindre ladite effets observables toutefois ils le souhaitent.

---

En fait, devirtualization est le terme général utilisé pour parler des optimisations du compilateur visant à régler les appels de méthodes virtuelles au moment de la compilation.

Le but n'est pas tant pour se raser les presque invisible à l'appel virtuel, les frais généraux (si la direction de la prévision), il est à propos de la suppression d'une boîte noire. Les meilleurs gains, en termes d'optimisations, sont indexées sur l'in-lining appels: cela ouvre la constante de propagation et d'un tas d'optimisation, et inline ne peut être atteint lorsque le corps de la fonction appelée est connu au moment de la compilation (car il s'agit de la suppression de l'appel et de le remplacer par le corps de la fonction).

Certains devirtualization possibilités:

• un appel à un final méthode ou un virtual méthode de final classe sont trivialement devirtualized
• un appel à un virtual méthode d'une classe définie dans un espace de noms anonymes peuvent être devirtualized si cette classe est une feuille dans la hiérarchie
• un appel à un virtual méthode via une classe de base peut être devirtualized si le type dynamique de l'objet peut être établie au moment de la compilation (ce qui est le cas de votre exemple, avec la construction en cours, dans la même fonction)

Pour l'état de l'art, cependant, vous aurez envie de lire Honza Hubička Blog. Honza est un gcc développeur et l'année dernière, il a travaillé sur spéculative devirtualization: l'objectif est de calculer les probabilités de la dynamique de type A, B ou C, puis éventuellement en devirtualize l'appelle un peu comme la transformation:

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

dans:

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 fait un 5-partie post:

• Devirtualization en C++, partie 1
• Devirtualization en C++, partie 2 (bas-niveau moyen-fin devirtualization par transfert de magasins de charges)
• Devirtualization en C++, partie 3 (construction de la hiérarchie de type)
• Devirtualization en C++, partie 4 (analyse de l'héritage de type graphique pour le plaisir et le profit)
• Devirtualization en C++, partie 5 (feedback conduit devirtualization)

Answer 4

Il y a beaucoup de raisons pourquoi les compilateurs ne peuvent pas en général de remplacer le moteur d'exécution de la décision avec les appels statiques, surtout parce qu'il comporte de l'information non disponible au moment de la compilation, par exemple, de la configuration ou de la saisie de l'utilisateur. A côté de cela, je tiens à souligner deux autres raisons pour lesquelles ce n'est pas possible en général.

Tout d'abord, la compilation C++ modèle est basé sur des unités de compilation. Quand une unité est compilé, le compilateur ne connaît que ce qui est défini dans le fichier source(s) en cours d'élaboration. Considérons une unité de compilation avec une classe de base et une fonction prise d'une référence à la classe de base:

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

Lorsqu'il est compilé séparément, le compilateur n'a pas de connaissances sur les types qui implémentent Base et donc ne peut pas supprimer la dynamique de l'expédition. Il a également pas quelque chose que nous voulons parce que nous voulons pouvoir étendre le programme avec de nouvelles fonctionnalités par la mise en œuvre de l'interface. Il peut être possible de le faire au moment de la liaison, mais seulement sous l'hypothèse que le programme est entièrement terminée. Bibliothèques dynamiques peut casser cette hypothèse, et comme on peut le voir dans la suite, il y aura toujours des cas où il n'est pas possible à tous.

Une raison plus fondamentale vient de la Compilation de la théorie. Même avec l'information complète, il n'est pas possible de définir un algorithme qui calcule si une ligne dans un programme sera atteint ou non. Si vous pouviez vous pourriez résoudre le Problème de l'Arrêt: pour un programme d' P,- je créer un nouveau programme P' par l'ajout d'une ligne supplémentaire à la fin de l' P. L'algorithme serait maintenant en mesure de décider si cette ligne est atteint, ce qui résout le Problème de l'Arrêt.

Être incapable de décider, en général, signifie que les compilateurs ne peut pas décider quelle valeur est affectée à des variables, en général, par exemple

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

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

b->polymorphicFunction();

Même lorsque tous les paramètres sont connus au moment de la compilation, il n'est pas possible de prouver en général qui chemin à travers le programme et qui de type statique b . Des Approximations peuvent être et sont faits par l'optimisation des compilateurs, mais il y a toujours des cas où il ne fonctionne pas.

Ceci dit, les compilateurs C++ essayez très difficile de l'enlever répartition dynamique, car elle ouvre de nombreux autres l'optimisation des chances principalement d'être en mesure de l'inclure et de propager la connaissance à travers le code. Si vous êtes intéressant, vous pouvez trouver une intéressante graves de messages de blog pour le CCG devirtualization mise en œuvre.

Answer 5

Qui pourrait facilement être résolu au moment de la compilation si l'optimiseur choisit de le faire.

La norme spécifie le même comportement que si le polymorphisme de l'exécution avait eu lieu. Il n'est pas spécifique qui sera atteint par le biais de réels polymorphisme de l'exécution.