Warum ist rtti so langsam?

GorbGorb

Hallo,

ich will gerade in einem Projekt die rtti verwenden, und verstehe einfach nicht, warum sie so langsam ist. Hier ein simpler Test typeid == typeid vs int == int:

#include <ctime>
#include <iostream>
#include <typeinfo>

const unsigned int loops = 100000000;

int main()
{
    volatile unsigned int a = 1;
	volatile unsigned int b = 2;

	unsigned int dummy = 0;

	unsigned int t = std::clock();
	for( unsigned int i = 0 ; i < loops ; ++i )
	{
		if( a == b )
			++dummy;
	}
	std::cout<< std::clock() - t <<std::endl;

	t = std::clock();
	for( unsigned int i = 0 ; i < loops ; ++i )
	{
		if( typeid( int ) == typeid( double ) )
			++dummy;
	}
	std::cout<< std::clock() - t <<std::endl;

	std::cin.get();
}

Auf meinem Rechner ist die Ausgabe
- mit VC++2010 release: 209 ; 1932
- mit mingw und gcc -03: 190 ; 1979

Warum ist das so? Müsste ich rtti selbst bauen, würde ich typeid einfach als einzigartigen uint Wert umsetzen.
Warum schneidet typeid also auf den beiden compilern (ich nehme mal an, dass das bei anderen nicht viel anders sein wird) so viel schlechter ab? Und warum optimiert keiner der beiden compiler die zweite Schleife einfach weg?

EDIT: Ich glaube ich habe grade herausgefunden, warum es so lahm ist: Anscheinend Vergleichen die beiden compiler die Namen der beiden types miteinander, d.h. strcmp. Das erscheint mir doch ziemlich seltsam. Warum sollte man sowas machen? Nur damit typeid auch über dll Grenzen funktioniert? Dafür muss es doch wohl bessere Lösungen geben als sowas unsicheres - was ist wenn verschiedene Typen gleich heißen? Bin ernsthaft etwas verwirrt

typeid muss per Standard ein type_info-Objekt zurückliefern, mit einfachem int wird das also nichts. Auch bekäme man Probleme damit, die typeids verschiedener Bibliotheken getrennt zu halten.

Überhaupt führt die Existenz von Laufzeitlinkern (d.h. dlopen/LoadLibrary etc.) hier unter Umständen zu gewissen Schwierigkeiten. Vermutlich benutzt die GNU-Implementation folgende Variante des operator==:

bool operator==(const type_info& __arg) const
    {
      return ((__name == __arg.__name)
              || (__name[0] != '*' &&
                  __builtin_strcmp (__name, __arg.__name) == 0));
    }

Übersetz den Code mal mit

if( typeid( int ) == typeid( int ) )

. Wahrscheinlich fällt der Unterschied dann wesentlich kleiner aus.

Najo, bei typeid wird wohl immer ein Lookup gemacht werden, mitsamt den ganzen Folgen (Tables nicht im Cache etc)

GorbGorb

Ok, muss mich nochmal verbessern:
In VC++ scheinen die Kosten für typeid == typeid unabhängig davon, ob die beiden Typen gleich sind, mit der Länge der Namen zuzunehmen.
In gcc scheint die Dauer für operator== konstant zu bleiben, d.h. ist unabhängig von der Länge des Namens. Dafür halbiert sich die Dauer aber in etwa, wenn die beiden Typen gleich sind.
Das Verhalten von VC++ kann ich ja nachvollziehen (finde es aber nicht so toll), aber was der gcc intern macht bleibt mir ein Rätsel.

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.