Workaround für virtual function templates !

Eine Frage, die ich in mehreren Foren gefunden habe - nur keine befriedigende Lösung. Ich denke, jetzt habe ich eine gefunden. Diese will ich hier mal zur Diskussion stellen..

Folgender Code ist leider verboten. C++ erlaubt keine template-Methoden, die gleichzeitig als "virtual" deklariert werden.

Mein Beispiel:
Ein Raumschiff wird von einer Waffe getroffen. Wir brauchen das Raumschiff und seinen Typ (nur zur Laufzeit bekannt), und wir brauchen den Typ der Waffe (bekannt zur compile-Zeit).

Ansatz I (gewünscht, aber nicht erlaubt!!!)

struct Spaceship {
    template<class Weapon> virtual void hit()=0;  // not allowed
};

struct XWing : Spaceship {
    template<class Weapon> void hit() {
        cout<<"\nX-Wing was hit by a "<<Weapon::toString();
    }
};

struct BWing : Spaceship{
    template<class Weapon> void hit() {
        cout<<"\nB-Wing was hit by a "<<Weapon::toString();
    }
}

//-----------------------------------------------------------------------

struct Missile {
    static char* toString() {
        return "missile";
    }
};

struct LaserGun {
    static char* toString() {
        return "laser gun";
    }
};

//-----------------------------------------------------------------------

int main()
{
    Spaceship* spaceship = new XWing();
    spaceship.hit<Missile>();
    char s;
    cin>>s;
    return 0;
}

Ansatz II (maximale performance, aber zuviel Code).
Problem: code size = number of spaceships * number of weapons !!

struct Spaceship {
    virtual void hit_by_missile()=0;
    virtual void hit_by_laser()=0;
};

struct XWing : Spaceship {
    void hit_by_missile() {
        cout<<"\nX-Wing was hit by a missile";
    }
    void hit_by_laser() {
        cout<<"\nX-Wing was hit by a laser";
    }
};

struct BWing : Spaceship {
    void hit_by_missile() {
        cout<<"\nB-Wing was hit by a missile";
    }
    void hit_by_laser() {
        cout<<"\nB-Wing was hit by a laser";
    }
}

//-----------------------------------------------------------------------

int main()
{
    Spaceship* spaceship = new XWing();
    spaceship.hit_by_missile();
    char s;
    cin>>s;
    return 0;
}

Ansatz III (Performance-Overhead durch unnötigen runtime polymorphism)
Problem: performance loss, because the weapon type is evaluated at run time.

struct Spaceship {
    template<class Weapon> virtual void hit()=0;
};

struct XWing : Spaceship {
    void hit(Weapon* weapon) {
        cout<<"\nX-Wing was hit by a "<<weapon->toString();
    }
};

struct BWing : Spaceship {
    void hit(Weapon* weapon) {
        cout<<"\nB-Wing was hit by a "<<weapon->toString();
    }
}

//-----------------------------------------------------------------------

struct Weapon {
    virtual char* toString()=0;
};

struct Missile : Weapon {
    char* toString() {
        return "missile";
    }
};

struct LaserGun : Weapon {
    char* toString() {
        return "laser gun";
    }
};

//-----------------------------------------------------------------------

int main()
{
    Spaceship* spaceship = new XWing();
    Weapon* weapon = new Missile();
    spaceship.hit(weapon);
    char s;
    cin>>s;
    return 0;
}

Mein Workaround !! (kein overhead?)
Wenn diese Version die gleiche Performance hat wie Ansatz II, dann bin ich glücklich. Wie seht ihr das?

Spaceship::AfraidOf<Missile>     Spaceship::AfraidOf<LaserGun>
                     |_________________________________|
                                      |
                               Spaceship::Ship
             _________________________|________________________
            |                |                |                |
  XWing::AfraidOf<Missile>   |     BWing::AfraidOf<Missile>    |
            |                |                |                |
            |    XWing::AfraidOf<LaserGun>    |   BWing::AfraidOf<LaserGun>
            |________________|                |________________|
                     |                                   |
                XWing::Ship                         BWing::Ship

struct Missile {
    static char* toString() {return "missile";}
};

struct LaserGun {
    static char* toString() {return "laser gun";}
};

//-----------------------------------------------------------------------

struct Spaceship {

    template<class W> struct AfraidOfWeapon {
        virtual void hit(W* w)=0;
    };

    struct Ship : AfraidOfWeapon<Missile>, AfraidOfWeapon<LaserGun> {
        template<class W> void hit() {
            W w;
            ((AfraidOfWeapon<W>*)this)->hit((W*)0);
        }
    };
};

//-----------------------------------------------------------------------

struct XWing {
    template<class W> struct AfraidOfWeapon : virtual Spaceship::Ship {
        void hit(W* w) {
            cout<<"\nX-Wing was hit by a "<<W::toString();
        }
    };
    struct Ship : AfraidOfWeapon<Missile>, AfraidOfWeapon<LaserGun> {};
};

//-----------------------------------------------------------------------

int main()
{
    Spaceship::Ship* spaceship = new XWing::Ship();
    spaceship->hit<Missile>();
    return 0;
}

Hallo,

ich kann leider nicht ganz folgen. Vielleicht ist das Beispiel für mich zu Simpel gewählt. Worauf willst Du hinaus?
Das was du machst bekommt man ja auch einfach so hin:

struct Spaceship {
    template virtual void hit(string weaponname) = 0;  // not allowed
};

struct XWing : Spaceship {
    template void hit(string name) {
        cout<<"\nX-Wing was hit by a "<< name }
};

struct BWing : Spaceship{
    template void hit(string name) {
        cout<<"\nB-Wing was hit by a "<< name;
    }

Anstatt einem string könnte man natürlich auch was anderes übergeben. Z.B. stärke oder sons was.

Natürlich ist das Beispiel sehr einfach gewählt. Mein Code zuhause ist zu kompliziert um das hier zu diskutieren.

Der Vorteil von template parametern ist, daß sie während des compilierens ausgewertet werden. Das heißt, der Compiler kennt dann schon fast alle Informationen und kann sehr stark optimieren. Zum Beispiel, wenn die Klasse "Missile" eine "static const int power=100" Variable hat, dann kann der Compiler diesen Wert schon in verschiedenen Rechnungen verwursten. Das bringt einen Performancegewinn in der Laufzeit!

Die Aussage, dass templates einen performance gewinn bringen ist im allgemeinen falsch.
Das muss man von Fall zu Fall unterscheiden.
Einfach einen Wert als compile time konstante wird keinen großen performance gewinn bringen. Oft ist es sogar so dass man durch die Verwendung von templates eine schlechtere cache hit rate bekommt und dann der Code viel langsamer läuft.

Es gibt aber diese Fälle wo templates einfach schneller sind. Als Beispiel seien nur mal die Tricks aus dem template meta programming genannt.

Mein Programm zuhause ist so ein Fall, da bin ich mir ziemlich sicher. Wenn der Compiler mitspielt, und mir alles schön vereinfacht. Die Methoden sind sehr kurz und werden häufig aufgerufen, deswegen zählt jeder Rechenschritt. Insbesondere will ich mir ellenlange if-else oder switch Geschichten ersparen, die gehen ja auch auf die Rechenzeit.

Dein Argument mit dem Caching meint, daß mehr Speicherplatz für Programmcode verwendet wird, und deswegen nicht alles in die schnelleren cache level passt? Ich fürchte ich bin da nicht so gut informiert..

Bevor ich's vergesse will ich noch das Wort "inline" in die Bahn werfen (das macht der Compiler ja angeblich automatisch wenn's sinnvoll erscheint).

Ansonsten, stell dir einfach vor die Weapon-Klassen enthalten jede Menge konstante Daten, ebenso wie die Klassen XWing und BWing. In der Funktion hit() müssen all diese Werte auf komplizierte Weise verrechnet werden, aber nur um am Ende einen einzigen Wert zu erhalten.

Es ist ja wohl klar daß es schneller geht wenn der Wert nicht jedesmal neu berechnet werden muss, wenn ein XWing von einer Missile getroffen wird.

Das enspricht nun zwar nicht ganz meinem eigenen Projekt, aber es macht deutlich daß die Idee in bestimmten Fällen Sinn macht. Genau wie template metaprogramming, das ist ja auch nur für spezialfälle gedacht, aber dort kann es sehr hilfreich sein.

hustbaer

Visitor pattern?

class Spaceship
{
public:
    virtual void Visit(Laser* w) = 0;
    virtual void Visit(PPG* w) = 0;
    virtual void Visit(Railgun* w) = 0;
};

class Weapon
{
public:
    virtual void Accept(Spaceship* ship) = 0;
};

class Laser : public Weapon
{
public:
    virtual void Accept(Spaceship* ship)
    {
        ship->Visit(this);
    }
};

class PPG : public Weapon
{
public:
    virtual void Accept(Spaceship* ship)
    {
        ship->Visit(this);
    }
};

class Railgun : public Weapon
{
public:
    virtual void Accept(Spaceship* ship)
    {
        ship->Visit(this);
    }
};

Knuddlbaer

Das wäre dann vermutlich wieder zu viel virtual.

IMHO macht das von Visitorpattern sinn, ich würde mir dann mit einem Profiler die Stellen der Zeitknappheit aufdecken lassen und das ggf. umstricken.

Der Workarround hat was, ob das aber die Zeit die man für den einen virtuellen Aufruf spart rechtfertig kann man imho ohne profiler nicht sagen.

Simon2

lemonhead schrieb:

...
Ansatz III (Performance-Overhead durch unnötigen runtime polymorphism)
Problem: performance loss, because the weapon type is evaluated at run time.
struct Spaceship {
    template<class Weapon> virtual void hit()=0;
};
...

Ich vermute, hier ist ein Tippfehler und eigentlich

struct Spaceship {
    virtual void hit(Weapon*)=0;
};

gemeint (bei Ansatz III).

Ich durchdenke gerade Deinen Workaround ... mal meine Fragen:

Müssen SpaceShip und XWing structs sein ? Würden namespaces nicht auch reichen ?
Der Compiler kann den Zusammenhang zwischen SpaceShip::Ship und XWing::Ship nicht mehr nachvollziehen, oder ? Klappt das überhaupt zuverlässig ? Letztlich "hoffst" Du doch nur, dass diese beiden Klassen dieselbe Stuktur haben - oder sicherst Du das noch irgendwie ab (was Du hier nur nicht zeigst) ? Klappt das

lemonhead schrieb:

Spaceship::Ship* spaceship = new XWing::Ship();
...

überhaupt so ? (musst Du da nicht casten ?)

Insgesamt gibt's das Beispiel doch in einem "exceptional-Buch", oder ?
Ich meine, dass Sutter da zu dem Ergebnis kam, dass es in C++ nicht wirklich zufriedenstellend zu lösen sein, weil C++ kein "double-dispatching" beherrscht....
Hmmmm, nochmal drüber nachdenken.

Gruß,

Simon2.

Was den Fehler in Ansatz III angeht hast du absolut Recht. Werde ich mal korrigieren.

Zu dem Workaround - namespace hätte es auch getan denke ich. Zuhause gibt es für den X-Wing noch template Parameter, deswegen benutze ich ein struct oder class (struct ist für beispiele dieser art besser, weil alles automatisch public ist)

Also bei mir zuhause klappt der Code exakt so wie er im Workaround steht (mit #include <iostream> und using namespace std)! Dh es wird die Message für den X-Wing ausgegeben.
Wie die Klassen über Vererbung zusammenhängen sieht man in dem Diagramm was ich in Asciiart gemalt hab. Wichtig ist natürlich, von Spaceship::Ship nach XWing::AfraidOfWeapon<..> als virtuell zu deklarieren.

Ziel ist, daß ein dem Ansatz II äquivalenter Code automatisch durch die templates erzeugt wird.
Ich mache mir noch Sorgen, ob der "Schein-Parameter" bei "virtual hit(W*)" einen Overhead macht.

Simon2

lemonhead schrieb:

...
Wie die Klassen über Vererbung zusammenhängen ...

*hand-vor-die-stirn-klatsch*

lemonhead schrieb:

...
struct XWing {
    template<class W> struct AfraidOfWeapon : virtual Spaceship::Ship 
...

Da steht's doch !! Lesen, Simon2, lesen !!!!

OK, muß ich mir nochmal neu ansehen - hatte nicht gesehen, dass XWing::AfraidOfWeapon anders definiert ist als SpaceShip::AfraidOfWeapon ....

Gruß,

Simon2.

jo dann denk mal weiter drüber nach bin gespannt! aber ehrlich ich würd gern wissen ob es gegenüber version 2 ein performance nachteil gibt. weil, eigentlich geht es ja nur darum den code für ansatz II automatisch vom compiler generieren zu lassen!

Simon2

lemonhead schrieb:

jo dann denk mal weiter drüber nach :)...

Jo, hab's nun durchschaut (denke ich) ... template, vtable-Polymorpiee, overloading, .... Du nutzt eigentlich alles an Techniken für generische Programmierung, die C++ hergibt ;)...

Finde es gut, sehr lehrreich und auch (typ-)sicher. Ob es aber schnell genug ist, kann ich so nicht beurteilen. Ein dynamisches Erweitern um weitere "Waffen" (zur Laufzeit) ist halt nicht mehr möglich und insgesamt ist natürlich eine "Vererbungsexplosion" bei zunehmender Waffenzahl kommt natürlich auch auf das Programm zu, aber das sind wohl ein gewollte Zugeständnisse an die Perfomance ... (bzw. eine Technik, die ein "gemäßigtes" und festes Sortiment an Waffen voraussetzt).

Ob es jetzt tatsächlich schnell genug ist, kann ich leider nicht beurteilen (da Du aber nur eine vtable-Indirektion hast statt 2, vermute ich es stark).

Gruß,

Simon2.

lolz

Warum abstrahierst du die Kollisionserkennung nicht aus und verwendest Kollisionsmodelle und prüfst dann einfach zwei Kollisionsmodelle auf eine mögliche Kollision. Dann hast du diese fest verdrahtete Struktur nicht (mehr).
So wird es bei allen Physik-Engines gemacht, du erstellst einfach ein Kollisionsmodell in der Physik-Engine die berechnet die Auswirkungen auf die (vereinfachte Welt) und liefert dir Transformations-Matrizen mit denen du die Auswirkungen auf die echte Welt übertragen kannst.

Die Effekte kannst du dann ebenfalls auskoppeln indem du Informationen über die Modelle in den Modellen speicherst und so den richtigen Effekt lädst, wenn z.B. ein Laser auf Metall (eines Raumschiffs) trifft.

Ist jetzt recht knapp gefasst, bei sowas Komplexen aber ich hoffe du verstehst was ich meine

von wegen physik-engines!!!
also, vielleicht sollte ich doch etwas mehr zu meinem eigentlichen projekt sagen. Ich versuche es mal.
Also, stell dir einen endlichen Automat vor. Die Spaceships sind die Zustände, die Waffentypen sind das Alphabet. Es gibt 500 Zustände, die sich aber in 5 Typen kategorisieren lassen. Jeder dieser Zustandstypen hat einen charakteristischen Umgang mit dem Eingabealphabet.
Das Alphabet wiederum hat 6 Zeichen, und es ist zur Compilezeit bekannt welche Befehle (Zeichen) der Automat kriegt.

struct StatePilotBase {
    template<int symbol> processSymbol()=0;
};

template<int state_type> struct StatePilotT {
    template<int symbol> processSymbol() {
        StateBlock& block = ((StateMachine*)this)->state_blocks[ ((StateMachine*)this)->state_block_index ];
        ... // process information from block
        ((StateMachine*)this)->state_pilot = ...
        ((StateMachine*)this)->state_block = ...
    }
};

struct StateBlock {
    ...
};

struct StateMachine :
    StatePilotT<0>, StatePilotT<1>,
    StatePilotT<2>, StatePilotT<3>,
    StatePilotT<4>
{
    StateMachine() {
        ... // fill state_blocks
        ... // set start state
    }

    template<int symbol> void processSymbol() {
        state_pilot->processSymbol<symbol>();
    }

    vector<StateBlock> state_blocks;

    // current state description
    int state_block_index;
    StatePilot* state_pilot;
};

so ich hoffe da ist jetzt kein fehler drin, ich kann ja als nicht-member nicht mehr editieren..

oh toll, es fehlt natürlich das wort "virtual void" in

struct StatePilotBase {
    template<int symbol> virtual void processSymbol()=0;
};

Hier ist natürlich auch klar daß dies mit normalem c++ nicht geht.

Simon2

lemonhead schrieb:

von wegen physik-engines!!!...

Hi,

auch wenn ich das schon so verstanden hatte, dass es Dir weder um spaceships, noch um physikalische Kollisionen geht, ist der Vergleich vielleicht gar nicht so schlecht. Prinzipiell macht es ja keinen Unterschied, ob Spaceships auf Waffen oder "Zustände" auf "Befehle" reagieren müssen (was Du ja mit Deinem ursprünglichen Beispiel schon ausgenutzt hast). Ich habe wirklich keine Ahnung vo Spieleprogrammierung, aber vielleicht kannst Du da ja tatsächlich noch die eine oder andere sinnvolle Idee abgreifen und auf Dein Programm übertragen.

Wenn natürlich wirklich Dein Befehlssatz eher fix und stark beschränkt bleiben wird, wäre das wohl die "Kanonen/Spatzen-Geschichte".

lemonhead schrieb:

...ich kann ja als nicht-member nicht mehr editieren..

... was sich ja aber mit ein paar Clicks kostenlos ändern ließe

Gruß,

Simon2.

lemonhead

bin drin
Das einzige was es kostet ist meine Emailadresse. Ich könnte zwar auf trashmail zurückgreifen, aber dann kriege ich keine Benachrichtigungen.

Simon2 schrieb:

Wenn natürlich wirklich Dein Befehlssatz eher fix und stark beschränkt bleiben wird, wäre das wohl die "Kanonen/Spatzen-Geschichte".

Eigentlich will ich der StateMachine ein paar template-Parameter geben, aus denen berechnet sich dann die Menge der möglichen Befehle (Alphabet). Es geht um Geometrie, die Parameter wären dann die Dimension, topologische Orientierbarkeit etc. Diese Parameter kennt man ja im allgemeinen vorher.

Das mit den Kollisionen hab ich aber noch nicht ganz kapiert. Wo bezieht sich lolz jetzt auf physikalische Begriffe, und wo auf Programmierkonstrukte?

Simon2

lemonhead schrieb:

...aber dann kriege ich keine Benachrichtigungen....

Das ist aber kein Nachteil gegenüber dem Leben als Unregistrierter ...

lemonhead schrieb:

...Wo bezieht sich lolz jetzt auf physikalische Begriffe, und wo auf Programmierkonstrukte?

Naja, ich (Ahnungsloser) hatte unter "Kollisionsmodell" ein Programmiermodell verstanden, aber es ist genauso möglich, dass es sich dabei um ein "physikalisches Modell von Kollisionen" gemeint ist - das Dir wirklich nicht weiterhilft...

Irgendwie habe ich nicht den Eindruck, Dir wirklich weiterhelfen zu können .... (und habe wahrscheinlich mehr von Dir gelernt als andersherum - nun: Danke).

Gruß,

Simon2.

lolz

Ich ging davon aus, dass du wirklich ein Spiel programmieren möchtest.
Kannst mein Posting also getrost vergessen.

lemonhead

Ich habe die Idee mal in einem anderen Forum diskutiert, siehe
http://www.gamedev.net/community/forums/topic.asp?topic_id=424879

Basierend auf einem Vorschlag von einem Member dort komme ich auf die folgende, noch elegantere Version.

DelegatorBase<Missile>         DelegatorBase<LaserGun>
                                     \         / 
                                      \       / 
    XWing                           SpaceshipBase                        BWing
      | \             ______________/   /   \   \_________________       / |
      |  \           /                 /     \                    \     /  |
      |   \_________/______           /       \                 ___\___/   |
      |            /       \         /         \               /    \      |
      |           /         \       /           \             /      \     |
 DelegatorT<XWing, Missile>  \     /    DelegatorT<BWing, Missile>    \    |
         \                    \   /             |                      \   |
          \      DelegatorT<XWing, LaserGun>    |     DelegatorT<BWing, LaserGun>   
           \             /                      |           / 
            \           /                       |          / 
          SpaceshipT<XWing>                  SpaceshipT<BWing>

//                                                         general framework
//---------------------------------------------------------------------------

template<struct Weapon> struct DelegatorBase {
    virtual void hit_v(Weapon*)=0;
};

struct SpaceshipBase :
    DelegatorBase<Weapon_1>,  // can be achieved in code size O(1)
    ...,
    DelegatorBase<Weapon_k>
{
    template<struct Weapon> hit() {hit_v((Weapon*)0);}
};

template<struct ShipType, struct Weapon> struct DelegatorT :
    virtual ShipType,
    virtual SpaceshipBase
{
    virtual void hit_v(Weapon*) {hit_impl<Weapon>();}
};

template<struct ShipType> struct SpaceshipT :
    DelegatorT<ShipType, Weapon_1>,  // can be achieved in code size O(1)
    ...,
    DelegatorT<ShipType, Weapon_k>
{
};

//                                                       specific spaceships
//---------------------------------------------------------------------------

struct Type_XWing {
    template<struct Weapon> void hit_impl() {...}
};

struct Type_StarDestroyer {
    template<struct Weapon> void hit_impl() {...}
};

//                                                          specific weapons
//---------------------------------------------------------------------------

struct Missile {...};

template<int n> struct RailgunT  // Railgun type n
{...};

//                                                                     usage
//---------------------------------------------------------------------------

void main() {
    SpaceshipBase* spaceship = new SpaceshipT<Type_XWing>();
    spaceship->hit<Missile>();
}

Vorteil: Beim Implementieren der Schiffstypen muss man sich nicht mehr mit der komplizierten Architektur herumschlagen.