Warum kann der Laufzeitpolymorphismus zur Kompilierungszeit nicht gelöst werden?

Erwägen:

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

Warum verursacht dieser Code Laufzeitpolymorphismus und warum kann er zur Kompilierungszeit nicht gelöst werden?

Da es im allgemeinen Fall zur Kompilierungszeit unmöglich ist , zu bestimmen, um welchen Typ es sich zur Laufzeit handelt. Ihr Beispiel kann zur Kompilierungszeit aufgelöst werden (siehe Antwort von @Quentin), es können jedoch Fälle erstellt werden, die dies nicht können, z.

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

EDIT: Dank @nwp ist hier ein viel besserer Fall. Etwas wie:

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

Durch die Folge von Turings Beweis kann auch gezeigt werden, dass es für einen C ++ - Compiler im allgemeinen Fall mathematisch unmöglich ist, zu wissen, auf was ein Basisklassenzeiger zur Laufzeit zeigt.

Angenommen, wir haben eine C ++ - Compiler-ähnliche Funktion:

bool bp_points_to_base(const string& program_file);

Dies wird als Eingabe verwendet program_file: Der Name einer C ++ - Quellcode-Textdatei, in der ein Zeiger bp(wie im OP) seine virtualMitgliedsfunktion aufruft show(). Und kann im allgemeinen Fall (an dem Sequenzpunkt, an Adem die virtualElementfunktion show()zum ersten Mal aufgerufen wird bp) bestimmen, ob der Zeiger bpauf eine Instanz von zeigt Baseoder nicht.

Betrachten Sie das folgende Fragment des C ++ - Programms "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

Wenn nun bp_points_to_basefestgestellt wird, dass in "q.cpp": bpauf eine Instanz von Baseat zeigt, zeigt A"q.cpp" bpauf etwas anderes bei A. Und wenn es feststellt, dass in "q.cpp": bpnicht auf eine Instanz von Baseat zeigt A, dann zeigt "q.cpp" bpauf eine Instanz von Baseat A. Dies ist ein Widerspruch. Unsere anfängliche Annahme ist also falsch. So bp_points_to_basekann nicht geschrieben werden den allgemeinen Fall .

Compiler devirtualisieren solche Aufrufe routinemäßig, wenn der statische Typ des Objekts bekannt ist. Wenn Sie Ihren Code unverändert in den Compiler Explorer einfügen, wird die folgende Assembly erstellt:

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"

Auch wenn Sie Assembly nicht lesen können, können Sie sehen, dass nur "In Derived \n"die ausführbare Datei vorhanden ist. Der dynamische Versand wurde nicht nur optimiert, sondern auch die gesamte Basisklasse.

Warum verursacht dieser Code Laufzeitpolymorphismus und warum kann er nicht in der Kompilierungszeit gelöst werden?

Was lässt Sie denken, dass es tut?

Sie gehen häufig davon aus: Nur weil die Sprache diesen Fall als Laufzeitpolymorphismus identifiziert, bedeutet dies nicht, dass eine Implementierung zur Laufzeit für den Versand gehalten wird. Der C ++ - Standard hat eine sogenannte "Als-ob" -Regel: Die beobachtbaren Auswirkungen der C ++ - Standardregeln werden in Bezug auf eine abstrakte Maschine beschrieben, und Implementierungen können diese beobachtbaren Effekte nach Belieben erzielen.

Tatsächlich ist Devirtualisierung das allgemeine Wort für Compiler-Optimierungen, die darauf abzielen, Aufrufe virtueller Methoden zur Kompilierungszeit aufzulösen .

Das Ziel besteht nicht so sehr darin, den nahezu unmerklichen Overhead für virtuelle Anrufe zu reduzieren (wenn die Verzweigungsvorhersage gut funktioniert), sondern darin, eine Black Box zu entfernen. Die besten Gewinne in Bezug auf Optimierungen werden durch Inlining der Aufrufe erzielt: Dies eröffnet eine konstante Ausbreitung und eine ganze Reihe von Optimierungen, und Inlining kann nur erreicht werden, wenn der Hauptteil der aufgerufenen Funktion zur Kompilierungszeit bekannt ist (seit Dabei wurde der Aufruf entfernt und durch den Funktionskörper ersetzt.

Einige Devirtualisierungsmöglichkeiten:

• Ein Aufruf einer finalMethode oder einer virtualMethode einer finalKlasse wird trivial devirtualisiert
• Ein Aufruf einer virtualMethode einer Klasse, die in einem anonymen Namespace definiert ist, kann devirtualisiert werden, wenn diese Klasse ein Blatt in der Hierarchie ist
• Ein Aufruf einer virtualMethode über eine Basisklasse kann devirtualisiert werden, wenn der dynamische Typ des Objekts zur Kompilierungszeit festgelegt werden kann (was in Ihrem Beispiel der Fall ist, wenn sich die Konstruktion in derselben Funktion befindet).

Für den Stand der Technik sollten Sie jedoch den Blog von Honza Hubička lesen. Honza ist ein gcc-Entwickler und hat letztes Jahr an der spekulativen Devirtualisierung gearbeitet : Das Ziel ist es, die Wahrscheinlichkeiten des dynamischen Typs A, B oder C zu berechnen und die Aufrufe dann spekulativ zu devirtualisieren, ähnlich wie beim Transformieren:

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

in:

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 hat einen 5-teiligen Beitrag geschrieben:

• Devirtualisierung in C ++, Teil 1
• Devirtualisierung in C ++, Teil 2 (Low-Level-Devirtualisierung am mittleren Ende durch Weiterleiten von Speichern an Lasten)
• Devirtualisierung in C ++, Teil 3 (Aufbau der Typhierarchie)
• Devirtualisierung in C ++, Teil 4 (Analyse des Typvererbungsdiagramms für Spaß und Gewinn)
• Devirtualisierung in C ++, Teil 5 (Feedback-gesteuerte Devirtualisierung)

Es gibt viele Gründe, warum Compiler die Laufzeitentscheidung im Allgemeinen nicht durch statische Aufrufe ersetzen können, hauptsächlich weil es sich um Informationen handelt, die zur Kompilierungszeit nicht verfügbar sind, z. B. Konfiguration oder Benutzereingaben. Abgesehen davon möchte ich zwei weitere Gründe nennen, warum dies im Allgemeinen nicht möglich ist.

Erstens basiert das C ++ - Kompilierungsmodell auf separaten Kompilierungseinheiten. Wenn eine Einheit kompiliert wird, weiß der Compiler nur, was in den zu kompilierenden Quelldateien definiert ist. Stellen Sie sich eine Kompilierungseinheit mit einer Basisklasse und einer Funktion vor, die auf die Basisklasse verweist:

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

Bei einer separaten Kompilierung kennt der Compiler die implementierten Typen Basenicht und kann den dynamischen Versand daher nicht entfernen. Es ist auch nicht etwas, was wir wollen, weil wir das Programm durch Implementierung der Schnittstelle mit neuen Funktionen erweitern wollen. Möglicherweise ist dies zum Zeitpunkt der Verknüpfung möglich , jedoch nur unter der Annahme, dass das Programm vollständig abgeschlossen ist. Dynamische Bibliotheken können diese Annahme brechen, und wie im Folgenden zu sehen ist, wird es immer Fälle geben, in denen dies überhaupt nicht möglich ist.

Ein grundlegenderer Grund ist die Berechenbarkeitstheorie. Selbst mit vollständigen Informationen ist es nicht möglich, einen Algorithmus zu definieren, der berechnet, ob eine bestimmte Zeile in einem Programm erreicht wird oder nicht. Wenn Sie könnten, könnten Sie das Halteproblem lösen: Für ein Programm Perstelle ich ein neues Programm, P'indem ich am Ende eine zusätzliche Zeile hinzufüge P. Der Algorithmus könnte nun entscheiden, ob diese Linie erreicht ist, wodurch das Halteproblem gelöst wird.

Im Allgemeinen nicht entscheiden zu können bedeutet, dass Compiler nicht entscheiden können, welcher Wert Variablen im Allgemeinen zugewiesen wird, z

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

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

b->polymorphicFunction();

Selbst wenn alle Parameter zur Kompilierungszeit bekannt sind, ist es nicht möglich, allgemein zu beweisen, welcher Pfad durch das Programm genommen wird und welchen statischen Typ bhaben wird. Annäherungen können und werden durch Optimierung von Compilern vorgenommen, aber es gibt immer Fälle, in denen dies nicht funktioniert.

Trotzdem bemühen sich C ++ - Compiler sehr, den dynamischen Versand zu entfernen, da dies viele andere Optimierungsmöglichkeiten eröffnet, vor allem durch die Möglichkeit, Wissen über den Code zu integrieren und zu verbreiten. Wenn Sie interessant sind, finden Sie eine Reihe interessanter Blog-Beiträge für die Implementierung der GCC- Devirtualisierung.

Dies könnte zur Kompilierungszeit leicht behoben werden, wenn der Optimierer dies wünscht.

Der Standard spezifiziert das gleiche Verhalten, als ob der Laufzeitpolymorphismus aufgetreten wäre. Es ist nicht spezifisch, dass dies durch tatsächlichen Laufzeitpolymorphismus erreicht wird.

Grundsätzlich sollte der Compiler in der Lage sein herauszufinden, dass dies in Ihrem sehr einfachen Fall nicht zu einem Laufzeitpolymorphismus führen sollte. Höchstwahrscheinlich gibt es Compiler, die das tatsächlich tun, aber das ist meistens eine Vermutung.

Das Problem ist der allgemeine Fall, wenn Sie tatsächlich einen Komplex erstellen, und abgesehen von den Fällen mit Bibliotheksabhängigkeiten oder der Komplexität der Analyse mehrerer Kompilierungseinheiten nach der Kompilierung, bei denen mehrere Versionen desselben Codes beibehalten werden müssten, wodurch AST ausgeblasen würde Generation , das eigentliche Problem läuft auf Entscheidbarkeit und das Problem des Stillstands hinaus.

Letzteres erlaubt es nicht, das Problem zu lösen, wenn ein Anruf im allgemeinen Fall devirtualisiert werden kann.

Das Problem beim Anhalten besteht darin, zu entscheiden, ob ein Programm mit einer Eingabe angehalten wird ( wir sagen, das Programm-Eingabe-Paar wird angehalten ). Es ist bekannt, dass es keinen allgemeinen Algorithmus gibt, z. B. einen Compiler , der alle möglichen Programm-Eingabe-Paare löst.

Damit der Compiler für ein Programm entscheiden kann, ob ein Aufruf virtuell erfolgen soll oder nicht, sollte er dies für alle möglichen Programm-Eingabe-Paare entscheiden können.

Dazu müsste der Compiler einen Algorithmus A haben, der entscheidet, dass das gegebene Programm P1 und das Programm P2, in dem P2 einen virtuellen Aufruf ausführt, dann P3 {while ({P1, I}! = {P2, I})} programmieren hält für jede Eingabe I an.

Damit der Compiler alle möglichen Devirtualisierungen herausfinden kann, sollte er in der Lage sein, für jedes Paar (P3, I) über alle möglichen P3 und I zu entscheiden, was für alle unentscheidbar ist, weil A nicht existiert. Es kann jedoch für bestimmte Fälle entschieden werden, die ins Auge gefasst werden können.

Deshalb kann in Ihrem Fall der Anruf devirtualisiert werden, aber auf keinen Fall.