Virtuelle Methoden gar nicht so schlimm?

[Nexus]

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).

[socco]

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.

[Ishildur]

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).

[Ishildur]

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

[volkard]

Ishildur schrieb:

...

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

[unskilled]

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

[Ishildur]

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.

[unskilled]

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

[volkard]

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.

[volkard]

unskilled schrieb:

templates nutzt anstatt polymorphismus

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

[Ishildur]

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?

[Ishildur]

@Volkard

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

Nein, das funktioniert IMHO eben nur, wenn der operator [] virtuell ist.

[volkard]

class Parser{
public:
 typedef RedBlackTree Dict;
private:
 Dict *tr;
public:
 Dict *GetCommands(void){return this->tr;}
};

und

Parser::Dict* d=p.GetCommands();

[Ishildur]

Hmmm....
Irgendwie stehe ich auf dem Schlauch, darüber muss ich einen Moment nachdenken :p

[Ishildur]

Ja nein, jtzt weiss ich natürlich, wieso das nicht geht. Der RedBlackTree hat unter Umständen auch Methoden, welche ein Dictionary nicht hat. Wenn ich nun nicht höllisch aufpasse und aus versehen eine Methode darauf aufrufe, welche das Dictionary resp. die anderen Implementationen von Dictionary (HashMap,BinaryTree) nicht kennen, kann ich den konkreten Typ nicht mehr auswechseln ohne Compilerfehler zu kassieren oder sehe ich das falsch?

[volkard]

Ishildur schrieb:

Ja nein, jtzt weiss ich natürlich, wieso das nicht geht. Der RedBlackTree hat unter Umständen auch Methoden, welche ein Dictionary nicht hat.

Du wolltest Austauschbarkeit, also ruf sowas nicht auf.

Ishildur schrieb:

Wenn ich nun nicht höllisch aufpasse und aus versehen eine Methode darauf aufrufe, welche das Dictionary resp. die anderen Implementationen von Dictionary (HashMap,BinaryTree) nicht kennen, kann ich den konkreten Typ nicht mehr auswechseln ohne Compilerfehler zu kassieren oder sehe ich das falsch?

Kein Grund, Angst zu haben.

Kannst während des Parserbauens und immermal zwischendurch auch gerne einen Angstwrapper einsetzen.

class MinimalDict//Nicht erben
{
   RedBlackTree imp;
   Value& operator[](key const& k){//Nur anbieten, was alle Dicts können
      return imp[k];
   }
};

class Parser{
public:
 typedef MinimalDict Dict;
private:
 Dict *tr;
public:
 Dict *GetCommands(void){return this->tr;}
};

Aber da sehe ich gar keinen Bedarf, weil Du gar nicht wahrnimmst, was Parser::Dict in Wirklichkeit für ein Typ ist. Du programmierst nur gegen die Dictionary-Schnittstelle.

[loks]

Ishildur schrieb:

"Programmiere gegen Interfaces und nicht gegen Implementierungen",

Ishildur schrieb:

Ja nein, jtzt weiss ich natürlich, wieso das nicht geht. Der RedBlackTree hat unter Umständen auch Methoden, welche ein Dictionary nicht hat.

In dem Fall hast Du den ersten Grundsatz nicht beachtet ...

[volkard]

Ishildur schrieb:

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

Da steht ja 0x00. Das ist vom Standard her nicht erlaubt. Nur 0 geht.

[Ishildur]

@loks

In dem Fall hast Du den ersten Grundsatz nicht beachtet ...

Wieso dass denn? Eine konkrete Implementation kann ja auch mehrere Interfaces implementieren (mache es jtzt der Einfachheit halber ohne Templates):

class Stack{
 void Push(void*) = 0;
 void *Pop(void)  = 0;
};
class Queue{
 void Enqueue(void*) = 0;
 void *DeQueue(void) = 0;
};
class Sequence{
 void *operator[](uint32 Index) = 0;
};
class Vector:public Sequence,public Stack,public Queue{
 void Push(void*){}
 void *Pop(void){return 0x00}
 void Enqueue(void*){}
 void *DeQueue(void){return 0x00}
 void *operator[](uint32 Index){return 0x00}
};
class LinkedList:public Stack{
 void Push(void*){}
 void *Pop(void){return 0x00};
};

Stack    *s = new Vector();      // OK, programmiere gegen Interface Stack
Stack    *s2 = new LinkedList(); // OK, programmiere gegen Interface Stack
Queue    *q = new Vector();      // OK, programmiere gegen Interface Queue
Sequence *q = new Vector();      // OK, programmiere gegen Interface Sequence
Vector   *v = new Vector();      // NICHT GUT, programmiere gegen Implementation Vector

In den ersten vier Fällen zwingt mich der Compiler, nur Methoden aufzurufen, welche das jeweilige Interface anbietet.

@volkard

Da steht ja 0x00. Das ist vom Standard her nicht erlaubt. Nur 0 geht.

Hmmm, das hatte ich nicht gewusst. In meinem Visual Studio funktionierts einwandfrei. Ich habe mir angewöhnt, für Adressen die Hex Notation zu verwendenden, damit ich gleich sehe, dass es um eine Adress zuweisung geht und weil es schliesslich einfach im Zusammenhang mit Memorydumps ist.

class MyClass{
 typedef Stk Vector;
 Stk;

 Stk *GetStack(void){return this->v}
};

MyClass mc;
MyClass::Stk st = mc.GetStack();

st.DeQueue(); // wird vom Compiler akzeptiert, weil MyClass::Stk eben letzen Endes die Implementation und nicht das Interface Stack repräsentiert.

class MyClass{
 typedef Stk LinkedList; // Nun muss ich doch refactoren, weil st Dequeue auf einem Stack aufgerufen wurde, welche nun von dieser Implementation nicht unterstützt wird.
 Stk;

 Stk *GetStack(void){return this->v}
};

[volkard]

Ishildur schrieb:

class MyClass{
 typedef Stk Vector;
 Stk;

 Stk *GetStack(void){return this->v}
};

MyClass mc;
MyClass::Stk* st = mc.GetStack();

st.DeQueue(); // wird vom Compiler akzeptiert, weil MyClass::Stk eben letzen Endes die Implementation und nicht das Interface Stack repräsentiert.

Dem könnte man abhelfen.

class MyClass{
 typedef StackWrapper<Vector> Stk;
 Stk;

 Stk *GetStack(void){return this->v}
};

MyClass mc;
MyClass::Stk* st = mc.GetStack();

st.DeQueue(); // wird vom Compiler NICHT akzeptiert

Es geht also ohne Laufzeitkosten. Aber ist in der Praxis gar nicht nötig, glaube ich.