Laufzeit von dynamic_cast
-
Wie sieht eigentlich in der Praxis die Laufzeit von dynamic_cast aus? Wie funktioniert dynamic_cast?
-
Wie sieht eigentlich in der Praxis die Laufzeit von dynamic_cast aus?
Da die Implementation nicht standardisiert ist, wirst du wohl schlicht und einfach ein wenig nachmessen müssen.
Wie funktioniert dynamic_cast?
Über das RTTI-Sytem. Ein häufiger Ansatz ist die Verwendung der vtable.
Für jeden polymorphen Typen reserviert man einen extra Slot in der vtable für Type-InformationenHat man nun:
if (pType pf = dynamic_cast<pType>(pt))Erstellt der Compiler einen Typdeskriptor für pf.
Der Typdeskriptor für pt wird zur Laufzeit aus der vtable geholt (er muss ja garantiert da sein, da ein down- bzw. crosscast nur mit polymorphen Typen funktioniert).
Etwa so:
static_cast<type_info*>(pt->vptr[0])->_type_descriptor;Die runtime lib kann dann zur Laufzeit die beiden Deskriptoren vergleichen und im Falle des Erfolgs die entsprechende Offsetverschiebung durchführen.
-
es ist also möglich, dynamic_cast in O(1) durchzuführen?
ps: genaue zeiten sind mir egal.
-
es ist also möglich, dynamic_cast in O(1) durchzuführen?
Ich bin kein Compilerbauer, würde das aber ehrlich gesagt bezweifeln. Ich würde spontan eher auf ein log n mäßiges Verhalten bezügiich der Vererbungstiefe tippen (der Zugriff auf die Typinformationen ist natürlich in konstanter Zeit möglich, nur geht das auch für den Vergleich?)
Ab wie gesagt, kenne ich nicht die Tricks, die die cleveren Compilerbauer so drauf haben.
-
HumeSikkins schrieb:
es ist also möglich, dynamic_cast in O(1) durchzuführen?
Ich bin kein Compilerbauer, würde das aber ehrlich gesagt bezweifeln. Ich würde spontan eher auf ein log n mäßiges Verhalten bezügiich der Vererbungstiefe tippen (der Zugriff auf die Typinformationen ist natürlich in konstanter Zeit möglich, nur geht das auch für den Vergleich?)
Ab wie gesagt, kenne ich nicht die Tricks, die die cleveren Compilerbauer so drauf haben.
Der Compiler könnte eine große Adjazenz-Tabelle erzeugen. (bool dyncast_possible[notypes][notypes])
Die würde zum Beispiel beim gcc mit den vielen shared libraries aber erst rt erzeugt. (Man braucht ja kontinuierliche IDs und eine kontinuierliche Tabelle)
-
Wie immer kann man sich Performance mit mehr Speicherverbrauch erkaufen. Aber ob dem Compilerbauer das ein O(1) wert ist?