Virtuelle Methoden gar nicht so schlimm?



  • unskilled schrieb:

    das ist doch müll
    alles, was bei virtuellen fkt. länger dauert, ist doch der lookup beim fkt.-aufruf.

    Nein, wie schon angemerkt wurde, können virtuelle Funktionen wesentlich teurer sein. Schlussendlich sind virtuelle Funktionen auch immer Grenzen, an denen der Compiler nicht rumoptimieren kann. Dagegen kann er eine normale Funktion inlinen, wodurch er sich das Rumschieben von Funktionsargumenten auf dem Stack spart, und danach können sogar noch Cacheoptimierungen etc kommen. Es gibt Spezialfälle, da kann man richtig viel rausholen.



  • wenn eine Virtuelle Funktion nur eine weitere Funktion aufruft gäbe es also kein inlining?



  • socco schrieb:

    wenn eine Virtuelle Funktion nur eine weitere Funktion aufruft gäbe es also kein inlining?

    Möglicherweise innerhalb der aufgerufenen Funktion, aber nicht über virtuelle Funktionsgrenzen hinweg. Aber auch da sollte man vorsichtig sein: Virtuelle Methoden sind nicht grundsätzlich langsamer, sondern nur, wenn man sie polymorph benutzt.

    struct MyClass
    {
        virtual void Foo();
    };
    
    int main()
    {
        MyClass a;
        a.Foo();
    }
    

    Hier kann der Aufruf von Foo() statisch gebunden werden, da bereits zur Kompilierzeit bekannt ist, welche Funktion aufgerufen werden muss. Dann fallen die erwähnten Probleme wieder weg.

    Allerdings habe ich teilweise wirklich das Gefühl, man macht sich zu viele Gedanken um solche Dinge. In den allerwenigsten Fällen kommt es vor, dass das Programm wegen virtuellen Funktionsaufrufen Probleme hat. Zumindest wenn man vernünftig programmiert und virtuelle Funktionen dort einsetzt, wo sie Sinn machen. Aber genau darum geht es: Einen Riesenaufwand zu betreiben, um virtuelle Funktionen loszuwerden, gleichzeitig aber die selbe Funktionalität manuell nachzubauen, ist etwas fragwürdig. Laufzeitpolymorphie ist ein mächtiges Sprachmittel, man sollte die Möglichkeiten nutzen.

    Klar gibt es vereinzelte Fälle, wo es wirklich kritisch sein kann. Teilweise sind auch Alternativen gar nicht so abwegig. Aber im Allgemeinen denke ich, Pauschalisierungen wie "virtuelle Funktionen sind langsam" haben sich schon in zu vielen Köpfen - besonders von weniger erfahrenen Programmierern - festgesetzt. Das ist eigentlich schade.



  • Mir ist das jetzt noch nie passiert, dass ich einen Engpass, wegen virtuellen Funktionen hatte. Das liegt aber wahrscheinlich hauptsächlich daran, dass virtuelle Funktionen in kritischen Punkten wahrscheinlich gar nie ins Konzept passen.

    Aber genau darum geht es: Einen Riesenaufwand zu betreiben, um virtuelle Funktionen loszuwerden, gleichzeitig aber die selbe Funktionalität manuell nachzubauen, ist etwas fragwürdig. Laufzeitpolymorphie ist ein mächtiges Sprachmittel, man sollte die Möglichkeiten nutzen.

    Jup, sehe ich auch so. Im Spieleprogrammierer.de Forum gabs mal wo einen Beitrag, dass er unbedingt virtuelle Funktionen vermeiden wollte, dann aber genau das gleiche selbst nachgebaut hat.. 🙂 (finds atm gerade nicht, schaue aber nachher nochmal, ob ich es finde.. ich fands recht amüsant.)



  • otze schrieb:

    Dagegen kann er eine normale Funktion inlinen, wodurch er sich das Rumschieben von Funktionsargumenten auf dem Stack spart

    das ist ja klar - aber wie gesagt: kein nachteil, der sich prozentual auf die laufzeit auswirken würde...
    (den nachteil hab ich übrigens schon zu fkt. hingeschrieben, weil ich virtuelle funktonsaufrufe mit funktionen verglichen habe und nicht mit ge-inline-tem code)
    und so extrem viel, wie du schreibst, sollte das auch nicht sein:
    durchschnittlich werden vll 2 parameter mit ner durchschnittsgröße von 4Byte(behaupte ich einfach mal so^^) übergeben:
    2xpush
    1xcall
    stack sichern (3 asm-befehle!?)
    //register sichern

    //register wiederherstellen
    1x add (stack wiederherstellen)

    register muss man logischerweise nur sichern und wiederherstellen, wenn man auch was in der fkt macht.
    bei trivialen fkt komm ich also auf 7 asm-befehle.
    virtuelle fkt. haben dann noch zusätzlich den lookup in der vtable als konstante kosten...
    kommen wir also auf max. 20 takte pro virtuellem fkt-aufruf im vergleich zu 0 takten bei inline-code.
    20 takte sind selbst auf nem rechenschieber (idR) noch zeitlich zu vernachlässigen...

    otze schrieb:

    Es gibt Spezialfälle, da kann man richtig viel rausholen.

    Japp - wie immer gibt es auch hier wieder eine Ausnahme - aber die Regel sieht eben anders aus...

    bb



  • Pauschalisierungen wie "virtuelle Funktionen sind langsam" haben sich schon in zu vielen Köpfen - besonders von weniger erfahrenen Programmierern - festgesetzt. Das ist eigentlich schade.

    Ich denke das liegt vor allem daran das die Anfänger noch nie ein großes Projekt realisiert haben und die Vererbung sowieso nie ganz richtig verstanden haben und deswegen sich auch dagegen streuben - ich spreche aus Erfahrung. Deswegen interessiert es mich jetzt auch so. Immerwieder sieht man das Erfahrene Programmierer interface Klassen usw. benutzen. Das erste was ich dann denke ist- wieso nimmt er nicht einfach ein konkretes Object und dessen interface, das wäre doch viel schneller und würde auch den Speicher schonen. Andrerseits ist dann der zweite Gedanke das der erfahrene Programmierer der vieleicht schon zich Bücher geschrieben hat, ja wissen muß was er da tut.
    Alles in allem scheint es so das man die Polymorphie ruhig nutzen kann, und erst wenn man ein konkretes Problem mit dem Speicher oder der Geschwindigkeit hat, überlegen sollte wo man das eine oder andere doch statisch bindet.

    Andrerseits hat auch die Polymorphie einige schwächen im Deisign, damit meine ich vor allem die "unreinen" virtuellen Funktionen, denn sie können sowohl als interface als auch als implementierung genutzt werden.
    Und man kann auch stark ins Schleudern kommen wenn man mit den Funktionsnamen und deren Gültigkeitsbereichen nicht aufpasst.



  • Die zu grunde liegende Frage ist falsch gestellt, bzw. es werden Äpfel mit Birnen verglichen.

    Natürlich ist der Aufruf einer virtuellen Methode zu Laufzeit aufwendiger als der einer statischen Methode. Jedoch erfüllt die virtuelle Methode gleichzeitig mehr Aufgaben die die statische Methode nicht leisten kann. Simples Beispiel:

    switch( this->TypeID )
    { 
       case ID1:  StaticMethod1(); break;
       case ID2:  StaticMethod2(); break;
       case ID3:  StaticMethod3(); break;
    ]
    

    gegen

    VirtualMethod();
    

    Um die Performance static vs virtuell vernünftig zu vergleichen müßte man das in den Tests berücksichtigen. Dabei ist der Mehraufwand den ein eigenes Typsystem mitbringt nicht zu unterschätzen.

    Ein Gedanke am Rande: Die "Kosten" einer virtuellen Funktion gemessen in Taktzyklen ist konstant. Die zur Verfügung stehende Rechenleistung steigert sich dagegen permanent(->siehe Mooresches Gesetz ) und drastisch. Die Diskussion über die "Kosten" virtueller Funktionen, setzt man sie in Relation zur Rechenleistung der Systeme wird daher zunehmend sinnloser 😉



  • unskilled schrieb:

    otze schrieb:

    Dagegen kann er eine normale Funktion inlinen, wodurch er sich das Rumschieben von Funktionsargumenten auf dem Stack spart

    das ist ja klar - aber wie gesagt: kein nachteil, der sich prozentual auf die laufzeit auswirken würde...

    Ich programmiere grad an einer Bibliothek, bei denen die Designer inzwischen davon ausgehen, dass sie ca Faktor 2 rausholen könnten, würden sie die Vererbungshierarchie weglassen. Polymorphie ist halt nicht so toll für Numbercrunching(mach mal eine svd auf einer 1000x1000 Matrix, bei der der Zugriff auf ein Element ein polymorpher Aufruf ist...)



  • wie machen es große Bibliotheken denn?

    Nehmen wir z.B. deirctX oder OpenGL - bei beiden würde sich doch eine Interface Klasse anbieten oder? Und beide haben keine Zeit zu verlieren.



  • socco schrieb:

    Nehmen wir z.B. deirctX oder OpenGL - bei beiden würde sich doch eine Interface Klasse anbieten oder? Und beide haben keine Zeit zu verlieren.

    In C sieht es anders aus, dort gibts weder Klassen im C++-Sinne noch Laufzeitpolymorphie (überhaupt ist Polymorphie kaum möglich).



  • aber es ist doch sehr intelligent gelöst, finde ich.
    Ich weiß allerdings nicht wie es gelöst ist.

    Ich habe grade mal ein paar Bücher durchgeblättert - Keine Ahnung ob ZFXEngine hier ein Begriff ist aber die ist z.B. so Konstruiert das die Application nur über eine interface Klasse die render Klasse ansprechen kann. Das heißt die gesammte Funktionalität der Engine ist virtuell.
    Ich kann mir vorstellen das es in so einer Struktur sehr bequem ist die engine zu bedienen. Und wenn ich das richtig verstanden habe

    alles, was bei virtuellen fkt. länger dauert, ist doch der lookup beim fkt.-aufruf.

    dann gäbe es praktich keinen GeschwindigkeitsNachteil.



  • Ich möchte mich an dieser Stelle herzlich für die vielen interessanten Beiträge bedanken! 🙂
    Mein persöhnliches Fazit sieht nun folgendermassen aus:
    Auf virtuelle Methoden sollte man dann verzichten, wenn man die entsprechenden Methoden eigentlich inline haben möchte, bspw. dann, wenn die entsprechenden Methoden der jeweiligen konkreten Klassen praktisch nichts tun, bspw. nur einen Wert zurückgeben (simple Accessor Methode).



  • Ich habe noch ein konkretes Beispiel, wo ich es nun doch für sinnvoll halte, nach Wegen zu suchen, virtuelle Methoden zu verhindern:

    Ich muss im Rahmen meiner Bachelorarbeit einige Datenstrukturen implementieren, welcher in der STL nicht vorhanden sind, und die sehr grosse Datenmengen enthalten. Durch diese Datenstrukturen muss schliesslich bis zu 100 mal und öfters pro Sekunde iteriert werden. Bspw:

    template<typename TKey,typename TValue> class Dictionary{
     virtual TValue &operator[](TKey &Key) = 0x00;
    };
    
    template<typename TKey,typename TValue> class HashMap:public Dictionary<TKey,TValue>{
     TValue &operator[](TKey &Key){};
    };
    
    template<typename TKey,typename TValue> class RedBlackTree:public Dictionary<TKey,TValue>{
     TValue &operator[](TKey &Key){}
    };
    

    Naja, bei diesem Beispiel gehts noch, immerhin kann der Funktionsaufruf im Verhätnis zu der Berechnung des Hashwertes sowie das eventuell erforderlichen DoubleHashings oder die Suche im RedBlack Tree im Verhältnis in Abhängigkeit zum LoadFactor und der daraus resultierenden Collisions resp. der Tiefe des RedBlack Trees doch vernachlässigbar werden.

    Ein noch deutlicheres Beispiel währe vielleicht folgendes (Welches ich aber nicht implementieren muss)

    template<typename T> class Sequence{
     virtual T &operator[](uint32 Index) = 0x00;
    };
    
    template<typename T> class Vector:public Sequence<T>{
    private:
     T *arItm;
    public:
     // Diese Operation dauert also nun ca. 4.5 mal länger, wenn der Datentyp Sequnce anstatt Vector ist. (Objekttyp in beiden Fällen Vector) weil der Compiler hier diese simple anweisung aufgrund des Polymorphismus nicht inlinen kann.
     TValue &operator[](uint32 Index){return this->arItm[Index]};
    };
    
    template<typename T> class LinkedList:public Sequence<T>{
     // Hier ist der polymorphe Aufruf IMHO wieder nicht von Bedeutung, weil die Lineare Suche n/2 = O(n) mit Hilfe von NodeHopping im Verhältnis deutlich Aufwändiger ist, als der Funktionsaufruf
     T &operator[](uint32){// lineare Suche durch Hopping}
    };
    

    Ich frage mich gerade, wie es diesbezüglich mit Iteratoren aussehen würde. Nehmen wir einmal an, ich möchte eine interface Klasse Collection, von welcher sämtliche konkreten Datenstrukturen abgeleitet werden sowie eine interface Klasse Iterator, von welcher sämtliche zu den jeweilig passenden Iteratoren abgeleitet werden.
    Siehe auch UML Diagramm http://de.wikipedia.org/wiki/Iterator_(Entwurfsmuster)

    Besonders folgender Satz:

    Polymorphe Iteratoren bieten eine hohe Flexibilität. Da Iteratoren meist in Schleifen verwendet werden, sind die Kosten dafür allerdings sehr hoch.

    Hat vielleicht jemand eine Idee, wie man hier die Laufzeitpolymorphie umgehen könnte und gleichzeitig einen generischen Iterator implementieren könnten. Ein Stichwort hierfür währe möglicherweise die statische Polymorphie mit Hilfe von Templates?

    Freundliche Grüsse
    Samuel Lörtscher



  • Ishildur schrieb:

    ...

    gefällt mir far nicht.
    warum überhaupt erben?



  • volkard schrieb:

    Ishildur schrieb:

    ...

    gefällt mir far nicht.
    warum überhaupt erben?

    und wenn schon erben(weil man codeduplikationen verhindern möchte), dann nicht die fkt schon in der basisklasse implementieren - du brauchst hier doch keinen polymorphismus. (typ sollte ja schon zur compilezeit feststehen -> templates sollten reichen, falls typedefs nicht ausreichen)

    von der performance her würde mich beim op[] die zusätzlichen kosten maximal bei vector spürbar stören.
    ansonsten hast du eh keine konstanten Laufzeiten (O(log n) bzw O(n log n)) - da kommts auch nicht mehr auf die paar Takte an...
    vom design her stört es mich so aber schon...
    wäre ein grund, es nicht zu verwenden : P

    bb



  • Hallo Volkard
    Ja das ist eine gute Frage. Also im Studium haben wir im Fach Softwareengineering als ersten Grundsatz gelernt, "Programmiere gegen Interfaces und nicht gegen Implementierungen", was meiner Meinung nach schon viel Sinn macht.

    Ein Beispiel:
    BinaryTree (unbalanced) vs. RedBlackTrees (balanced)

    Mutator Methoden wie Insert oder Remove ist beim BinaryTree deutlich schneller als beim RedBlackTree, weil der Verwalungsaufwand für das Balancing wegfällt. Im Gegenzug sind Accessor Methoden beim RedBlackTree deutlich performanter, weil der Tree eben balanced und somit die erforderliche Suchtiefe minimiert ist.

    Programmiere ich gegen ein Interface Tree, welche von den beiden konkreten Implementationen implementiert werden, dann kann ich diese jederzeit auswechseln, wenn ich feststellen sollte, dass das Verhältnis zwischen Mutator- und Accessor Methoden Calls nun doch anders ist, also zu Beginn angenommen.



  • Das kannst du auch, wenn du typedefs bzw templates nutzt anstatt polymorphismus - wie ich in meinem post bereits geschrieben habe(hast du evtl übersehen, weil du schon am schreiben warst!?).

    gn8



  • Ishildur schrieb:

    Hallo Volkard
    Ja das ist eine gute Frage. Also im Studium haben wir im Fach Softwareengineering als ersten Grundsatz gelernt, "Programmiere gegen Interfaces und nicht gegen Implementierungen", was meiner Meinung nach schon viel Sinn macht.

    Ja, aber das Interface ist hier die Definition, was ein Dictionary anzubieten hat und die Aussage, daß eine Hashmap ein Dictionary ist, ohne das in Code gießen zu müssen.

    Ishildur schrieb:

    Programmiere ich gegen ein Interface Tree, welche von den beiden konkreten Implementationen implementiert werden, dann kann ich diese jederzeit auswechseln, wenn ich feststellen sollte, dass das Verhältnis zwischen Mutator- und Accessor Methoden Calls nun doch anders ist, also zu Beginn angenommen.

    Kannste auch so, wenn beide Bäume Dictionaries sind, also den op[] wie spezifiziert anbieten.



  • unskilled schrieb:

    templates nutzt anstatt polymorphismus

    der austauschtrick bei den templates ist auch polymorphismus, um genau zu sein.



  • Hallo unskilled
    Ja ich war tatsächlich bereits am schreiben und habe deinen Beitrag erst nachträglich gesehen 😉
    Allerdings kann ich dir nicht ganz folgenden

    Beispiel:

    class Parser{
    private:
     RedBlackTree<char*,void(*)(void)> *tr;
    public:
     Dictionary<char*,void(*)(void)> *GetCommands(void){return this->tr;}
    };
    

    Hierbei ist eben auch die Idee, dass Klassen, welche mit dem Parser kommunizieren nicht wissen müssen, welche konkrete Implementation denn nun vom Parser gewählt wurde, weil sie selbst auch wieder "nur" Methoden des Interface aufrufen.

    class Parser{
    private:
     Hashmap<char*,void(*)(void)> *hm;
    public:
     Dictionary<char*,void(*)(void)> *GetCommands(void){return this->hm;}
    };
    

    Und der Rest der Applikation läuft immer noch ohne jegliches Refactoring...

    Mir ist nun nicht so ganz klar, wie du das mit templates oder typedefs realisieren willst?


Anmelden zum Antworten