Warum ist rtti so langsam?

Naja, zunächst mal verwendet der gcc dem vendor-neutral C++ ABI entsprechende Namen, d.h. zum Beispiel: typeid(double).name() ist nicht "double", sondern "d". Wenn es zu einem String-Vergleich kommt, werden Basistypen und einige Typen aus der Standardbibliothek also praktisch sonderbehandelt.

Ich vermute aber, dass in derart einfachem Code ohne dynamisch dazugeladene Komponenten die Bedingung __name[0] != '*' nie hält und im Ungleichheitsfall unabhängig vom Namen der betreffenden Typen immer nur die Zeiger verglichen und über das erste Zeichen des Namens festgestellt wird, dass ein String-Vergleich einen auch nicht weiterbrächte. Ich hätte jetzt nicht zwingend vorhergesagt, dass das in der Performance einen Faktor von 2 ausmacht, aber etwas in der Größenordnung scheint realistisch.

hustbaer

Dass type_info Vergleiche so oft so langsam sind, liegt eigentlich nur daran, dass viele Compiler die ABI nicht völlig frei wählen/definieren können, bzw. es aus bestimmten Gründen nicht wollen.
MSVC versucht nicht all zu oft mit "seiner" eigenen ABI zu brechen, und GCC möchte gern die "Vendor-Neutral C++ ABI" verwenden.

Sonst könnte man z.B. inetwa sowas machen:

struct _TypeInfoData
{
    long long _HashCode;   // Hashcode von _TypeName, nach irgendeinem genau definierten, schlauen Algorithmus
    char const* _TypeName; // Zero-padded auf z.B. Vielfache von 8 Byte
};

class type_info
{
public:
    // ...

    bool operator == (type_info const& other) const
    {
        if (other._Data == _Data)
            return true;  // Adresse gleich -> muss gleicher Typ sein
        else if (other._Data->_HashCode != _Data->HashCode)
            return false; // Hashcode unterschiedlich -> muss anderer Typ sein
        else
                          // Doof, wir müssen vergleichen
            return fast_8b_padded_strcmp(other._Data->_TypeName, _Data->_TypeName) == 0;
    }

    // Analog dazu operator != () und before()

private:
    type_info(_TypeInfoData const* data) : _Data(data) {}

    type_info(type_info const&);
    type_info& operator =(type_info const&);

    _TypeInfoData const* _Data;
};

Ein wirklicher String-Vergleich wäre damit nur mehr in einigen wenigen Fällen nötig (=wenn die _TypeInfoData Instanzen in verschiedenen DLLs/SOs stehen, der Typ aber der selbe ist, oder wenn man sehr sehr viel Pech mit dem Hashcode hat).

Macht aber (fast?) keiner, weil keiner mit "seiner" ABI brechen will. Über ähnliche Mechanismen liesse sich vermutlich auch dynamic_cast etwas beschleunigen. Macht aber auch (fast?) keiner.

-----

BTW: nachdem ich gerade es sebst ergoogelt habe, und nicht uninteressant finde: die "Vendor-Neutral C++ ABI" die GCC verwendet ist die, die ursprünglich für Itanium definiert wurde, und ist (laut Wikipedia) hier dokumentiert:

http://sourcery.mentor.com/public/cxx-abi/abi.html
http://sourcery.mentor.com/public/cxx-abi/abi-eh.html

Athar

Kann ich übrigens nicht nachvollziehen, gcc 4.5 und 4.6 optimieren die zweite Schleife vollständig weg (und die dummy-Variable auch).

GorbGorb

Danke für die Erklärungen,
ich werde dann meine eigene rtti mit uints verwenden, mit der Möglichkeit für dlls auf die eingebaute rtti zurückzufallen.

knivil

Hast du Optimierung angeschaltet?

GorbGorb

knivil schrieb:

Hast du Optimierung angeschaltet?

ja -O3 bzw halt die normalen release Einstellungen von msvc++.

dot

Natürlich ist es interessant wie RTTI vom Compiler umgesetzt wird, aber ich würde mir an deiner Stelle vor allem überlegen, warum genau ich eigentlich RTTI verwenden will und was ich besser machen kann, sodass ich ohne auskomm...

GorbGorb

Ich habe nicht vor eine dynamic_cast oder typeid Orgie anzurichten, keine Sorge.

Orgie der Gewalt

dot

GorbGorb schrieb:

Ich habe nicht vor eine dynamic_cast oder typeid Orgie anzurichten, keine Sorge.

Es ist aber sehr wahrscheinlich, dass du gerade dabei bist, dir basierend auf typeid einfach nur eine Art dynamic_cast zu basteln, auch wenns auf den ersten Blick vielleicht nicht direkt danach aussieht...

hustbaer

dot schrieb:

GorbGorb schrieb:

Ich habe nicht vor eine dynamic_cast oder typeid Orgie anzurichten, keine Sorge.

Es ist aber sehr wahrscheinlich, dass du gerade dabei bist, dir basierend auf typeid einfach nur eine Art dynamic_cast zu basteln, auch wenns auf den ersten Blick vielleicht nicht direkt danach aussieht...

Wobei dynamic_cast auch nicht unbedingt schneller sein wird als typeid()...

dot

hustbaer schrieb:

dot schrieb:

GorbGorb schrieb:

Ich habe nicht vor eine dynamic_cast oder typeid Orgie anzurichten, keine Sorge.

Es ist aber sehr wahrscheinlich, dass du gerade dabei bist, dir basierend auf typeid einfach nur eine Art dynamic_cast zu basteln, auch wenns auf den ersten Blick vielleicht nicht direkt danach aussieht...

Wobei dynamic_cast auch nicht unbedingt schneller sein wird als typeid()...

Normalerweise dürfte sogar eher das Gegenteil der Fall sein, da dynamic_cast die komplette Hierarchie beachten muss...
Aber darum gehts mir auch nicht. Mir geht's darum, dass typeid und dynamic_cast meist Sympton eines Designproblems sind. Es wäre also sinnvoll, zumindest mal zu reflektieren, was man da eigentlich gerade zu tun gedenkt, anstatt mit dem Kopf durch die Wand zu laufen.

GorbGorb

Ich will component based design umsetzen, d.h. ich brauche eine Klasse "entity" die beliebige Komponententypen aufnehmen kann (und twar nicht immer die gleichen).
Das könnte ich jetzt so machen, dass etwas baue wie entity< ComponentA , ComponentB , ComponentC > . Das wird aber dann nicht mehr funktionieren, wenn ich zur Laufzeit neue entity "Arten" erstellen will (z.B. weil ich eine Datei einlese, in der festgelegt ist, welche components zu einer entity gehören). Und dazu brauche ich rtti. Das wird nur im framework verwendet, in der Logik für mein Programm brauche ich es nicht.

hustbaer

Wo genau brauchst du dabei RTTI für was genau?

GorbGorb

Ich übergebe diese entity einem entity_system, das Komponenten in Abhängigkeit von ihrem Typ an spezielle container weitergibt:

entity -> entity_system -> (über virtuelle Funktion) -> meta_entity_system<...> (kennt den Typ der folgenden container) -> container< ComponentType* >

entity_system weiß noch nicht, für welche Typen es container gibt. Dadurch muss ich nicht alles, das entity_system verwendet, neu compilen, wenn ich einen neuen Komponententyp einbaue.
In meta_entity_system muss ich dann aber wissen, welche Komponententypen in der entity stecken, also brauche ich rtti.

dot

Nurmal rein prinzipiell: Wie kann deine Anwendung was mit einer zur Compiletime der Anwendung unbekannten Schnittstelle anfangen?

Edit: Ok, es könnte eine neue Komponente was mit einer neuen Schnittstellen anfangen. RTTI wäre da theoretisch eine Lösung, wird praktisch aber schon rein auf technischer Ebene nicht unproblematisch sein, da die Typen, mit denen du es da zu tun hast, wohl aus verschiedenen dlls stammen müssen. Fakt ist, dass Code nur Schnittstellen verwenden kann, die zur Compiletime bekannt sind. Ich denk, dass es da eine bessere Lösung geben muss. Ich frag mich eben grad, was genau der Sinn davon ist, die Komponenten zentral zu verwalten, wenn es doch offenbar an zentraler Stelle nicht genug Information dafür geben kann.

Zumal Zentralisierung der grundlegenden Idee des komponentenbasierten Designs völlig zuwiderläuft. Man will da doch eigentlich erreichen, dass die Komponenten ihre jeweilige Implementation untereinander überhaupt nicht kennen müssen. Auch sehe ich nicht, wie du Komponenten in Klassen quetschen willst, wenn CBSE sich von Objektorientierung genau dadurch abgrenzt, dass eine Schnittstelle auch von etwas anderem als Objekten getragen werden kann (wie Funktionen, Sockets oder was auch immer).

Geht es dir um eine Art Framework zur Verwaltung von Metadaten, d.h. Abhängigkeitsauflösung zur Laufzeit? Das wäre vorstellbar, aber dafür solltest du keine Typidentifikation zur Laufzeit brauchen. Das ginge wahrscheinlich sogar ohne virtuelle Methoden.

GorbGorb

Es geht mir nicht primär um dlls, sondern darum dass ich code nicht ständig neu compilen will. Vielleicht kams nicht ganz so klar rüber: Ich kenne die Typen aller Komponenten beim compilen, aber nicht alle Kombinationen (naja, rein theoretisch wäre das schon möglich, aber ich bezweifle, dass es sinnvoll ist, beim compilen schon alles mit allem zu kombinieren, weil das ziemlich schnell sehr viele Möglichkeiten werden).
@seldon: Irgendwo muss ich meiner entity sagen, welche Komponenten zu ihr gehören. Danach werden die Komponenten dann aber auf getrennte container aufgeteilt. Da Komponenten bei mir allein aus Daten bestehen und von mehreren subsystems für jeweils einen bestimmten Komponententyp bearbeitet werden, weiß ich auch nicht, was du mit Schnittstellen genau meinst.

Wahrscheinlich reden wir gerade völlig aneinander vorbei. Ich rede hiervon.

So richtig klar ist mir nicht, was du unter "componend based design" verstehst; wenn Komponenten bei dir bloß Daten sind, ist es jedenfalls nicht das, was ich meinte. Kannst du vielleicht etwas genauer beschreiben, was du eigentlich erreichen willst?

GorbGorb

Ok stimmt, ich meine was anderes:
-> http://t-machine.org/index.php/2007/09/03/entity-systems-are-the-future-of-mmog-development-part-1/

Im Grunde geht es darum, dass man statt mit einer Klassenhierarchie mit aus mehreren Komponenten zusammengesetzten Objekten (entities) arbeitet. Eine entity ist nur eine einzigartie id, der mehrere Komponenten zugeordnet sind.
Die Komponenten werden dann seperat voneinder gespeichert. Da Komponenten nur aus Daten bestehen werden sie von einem bestimmten subsystem bearbeitet. Wie aus dem Artikel hervorgeht, wird das bei der Spieleprogrammierung verwendet.
Als Beispiel könnte etwa eine entity einen Baum im Spiel repräsentieren. Die entity hätte dann eine RenderComponent, eine PhysicsComponent, DestructibleComponent, ...
Es gäbe ein RenderSystem, das alle RenderComponents abarbeitet, ein PhysicsSystem für die Physik etc.
Der Vorteil ist, dass man damit verschiedene Aspekte trennen kann, statt sie in einem großen god object zu verwursteln. Abgesehen von weniger schmutzigem code kann man so leichter multi threaden und nutzt den cache durch seperate Speicherung der Komponenten besser.