Designfrage

Bloops

Hallo!

Ich steh gerade vor einem Problem und überlege, wie ich es am besten anpacken soll. Ich habe einen Algorithmus, welcher in eine Klasse gepackt ist. Das sieht prinzipiell dann so aus:

class Algorithmus
{
public:
    Algorithmus(InitInfo initInfo);
    Result compute(); // called once by user

private:
    void methodA(Params params); // called once
    void methodB(Params params); // called several times
    void methodC(Params params); // called 10.000.000 times
    void methodD(Params params); // called 10.000.000 times
    ...

    SomeType state1_;
    SomeType state2_;
    SomeType state3_;
    ...
}

Das ist jetzt natürlich nur exemplarisch. Randbedingung hierbei ist, dass compute() mehrmals pro Sekunde aufgerufen wird und seinerseits dann die entsprechenden Klassenmethoden (bzw. diese sich untereinander) aufruft. Da das ganze Programm zumindest weiche Echtzeit "garantieren" sollte, ist die Implementierung also aufgrund der häufigen Aufrufe von methodC() und methodD() absolut relevant und es handelt sich hierbei nicht um premature optimization. Also bitte nicht meckern

So weit, so gut. - Nun zur eigentlichen Problembeschreibung: Abhängig von zwei Parametern besitzt der Algorithmus eine leicht andere Funktionsweise (z. B. anderes Abbruchkriterium, andere Speicherverwaltung usw.), der Großteil der Funktionalität ist jedoch hiervon unabhängig. Jetzt stellt sich für mich die Frage, wie ich diese parameterabhängige Funktionsweise möglichst effizient und aber auch designtechnisch sauber implementieren sollte.

Möglichkeiten, an die ich gedacht habe:

Naive Lösung:

class Algorithmus
{
public:
    Algorithmus(InitInfo initInfo, int param1, bool param2);
    ...

private:
    ...
    void methodD(Params params) // called 10.000.000 times
    {
        if (param1_ > 42)
        {
            // do it this way
        }
        else
        {
            // do it that way

            if (param2_)
                doSomeExtraWork();
        }
    }
    ...

    int param1_;
    bool param2_;
    ...
}

Problem hierbei: die if-Abfrage wird 10.000.000 mal ausgeführt, obwohl bei Konstruktion des Algorithmus -Objekts (eigentlich sogar zur Compilezeit) bereits feststeht, welcher Zweig der aktive ist. Außerdem wird der Code tendenziell unübersichtlich, da diese Verzweigungen an einigen Stellen drin sein müssten.

Template-basiert:

template<int param1, bool param2>
class Algorithmus
{
public:
    Algorithmus(InitInfo initInfo);
    ...

private:
    ...
    void methodD(Params params) // called 10.000.000 times
    {
        if (param1 > 42)
        {
            // do it this way
        }
        else
        {
            // do it that way

            if (param2)
                doSomeExtraWork();
        }
    }
    ...
}

Hier sollte der Compiler direkt die toten Zweige und somit die if-Abfragen eliminieren können, allerdings bleibt der Code unübersichtlich.

Template-Spezialisierungen:
Was nett wäre, wäre, dass die relevanten Funktionen einfach spezialisiert würden, aber nur einzelne Funktionen und nicht die ganze Klasse zu spezialisieren ist meines Wissens ja nicht möglich...

template<int param1, bool param2>
class Algorithmus
{
public:
    Algorithmus(InitInfo initInfo);
    ...
}

template<int param1>
Algorithmus<param1, true>::methodD(Params params)
{
    ...
}

template<int param1>
Algorithmus<param1, false>::methodD(Params params)
{
    ...
}

Ist mein Problem irgendwie klar geworden?

Würde mich über Ideen/Vorschläge freuen.

Grüße

SeppJ

Template-Spezialisierungen:
Was nett wäre, wäre, dass die relevanten Funktionen einfach spezialisiert würden, aber nur einzelne Funktionen und nicht die ganze Klasse zu spezialisieren ist meines Wissens ja nicht möglich...

Dann erb doch die Gemeinsamkeiten von einer dritten Klasse.

ConfusedGuy

ich verweise hierbei auf das state pattern http://de.wikipedia.org/wiki/Zustand_(Entwurfsmuster) bzw. command pattern http://de.wikipedia.org/wiki/Kommando_(Entwurfsmuster)
auf diese weise kannst du teile des algos in klassen verpacken und diese dann die entsprechenden teile behandeln lassen.

so kannst du die ifs in methodenaufrufe umwandeln. udh auf modernen cpus sind ifs ziemlich teuer wenn die sprungvorhersage schiefgeht.

class Algorithmus
{
public:
    Algorithmus(InitInfo initInfo, int param1, bool param2)
    {
       if(param1 > 42)
       {
          algo = AlgoGroesser42;
       }
       else
       {
           algo = AlgoKleiner42;
       }
    }
    ...

private:
    ...
    void methodD(Params params) // called 10.000.000 times
    {
       algo.do();

       //für param2 auf ähnliche weise in AlgoKleiner42
       if (param2_)
           doSomeExtraWork();
        }
    }
    ...

    int param1_;
    bool param2_;
    Algo algo;
    ...
}

verständlich?

btw. das ginge auch mit funktions pointern die du entsprechend setzt.

theta

ConfusedGuy schrieb:

ich verweise hierbei auf das state pattern

Wohl eher Strategy...

ConfusedGuy

mh, ja. das trifft es wohl besser.
aber sind die beiden da nich eh sehr ähnlich?

hat das ding nun wieder eine methode die param2 auf true oder false setzt und betrachtest du param2 damit quasi als state passt auch das statepattern wieder. aber daran will ich dass nun nicht festmachen.(entsprechend geht das auch mit param1)

aber der mechanismus ist der selbe, ob nun state pattern oder strategy pattern, wie von dir zu recht genannt.

Bloops

Vielen Dank euch für die Antworten. An das Strategy-Pattern oder Policies (Template-basiert) habe ich auch schon gedacht. Hier sehe ich jedoch das Problem, dass die Funktionalität von z. B. methodD() nicht für sich abgeschlossen herausgenommen werden kann. Alle Funktionen greifen auf eine Vielzahl der privaten Membervariablen zu, so dass also dann den einzelnen Strategies/Policies noch ein Instanzzeiger übergeben werden müsste oder zumindest dürften die Strategies keine eigene Klasse sein, sondern nur verschiedene Memberfunktionen.

Vielleicht ist der Weg über das Ableiten von einer gemeinsamen Basisklasse doch der beste... Hierbei steigt dann natürlich die Anzahl der abgeleiteten Klassen exponentiell mit der Parameterzahl des Algorithmus. Ich bin noch unentschlossen.

Grüße

Hallo

Vielleicht kann man hier auch eine Generische Programmierung benutzen.

So zum Beispiel:

template< bool t, int t1, int t2 >
struct Select
{
    enum { num = t1 };
};

template< int t1, int t2 >
struct Select <true, t1, t2>
{
    enum { num = t2 };
};

template< int t1, typename t2 >
struct cTest
{
    enum FuncType
    {
        Func1,
        Func2
    };

    typedef typename Select< (t1 > 42), Func1, Func2  >::type   tFuncType;

    void foo()
    {
        void (cTest::*fptr[])() =
        {
            &cTest::func1,
            &cTest::func2
        };

        *fptr[tFuncType::num]();
    }

    void func1();
    void func2();

};

Der Compiler Optimiert dann alles überflüssige raus.

Lichtlein

SeppJ

Bloops schrieb:

Vielleicht ist der Weg über das Ableiten von einer gemeinsamen Basisklasse doch der beste... Hierbei steigt dann natürlich die Anzahl der abgeleiteten Klassen exponentiell mit der Parameterzahl des Algorithmus. Ich bin noch unentschlossen.

Meine Güte, was hast du denn vor? Wieviele unterschiedliche Anpassungen eines Algorithmus kann es denn geben?

Bevor du jetzt zu tief in das Thema einsteigst, vergleich doch einmal die Methode mit der if-Abfrage und eine handoptimierte Version. Wenn bei der Abfrage nämlich immer das gleiche passiert, kann die sehr gut vom Prozessor optimiert werden. Und dann lohnt es sich eventuell überhaupt nicht, wenn du jetzt tagelang darüber nachdenkst wie du diese eine Abfrage einsparst.

Template-Spezialisierungen:
Was nett wäre, wäre, dass die relevanten Funktionen einfach spezialisiert würden, aber nur einzelne Funktionen und nicht die ganze Klasse zu spezialisieren ist meines Wissens ja nicht möglich...

Du kannst die Methoden auch überladen.

z.B. so:

#include <iostream>
using namespace std;
template <int T>
struct int2type
{
	enum {e = T};
};
template <int T1, int T2>
class Algorithmus
{
	void method (int2type<1>,int2type<0>) const { cout << "parma1 größer 42, param2 false\n";}
	void method (int2type<1>,int2type<1>) const { cout << "parma1 größer 42, param2 true\n";}
	void method (int2type<0>,int2type<0>) const { cout << "parma1 kleiner/gleich 42, param2 false\n";}
	void method (int2type<0>,int2type<1>) const { cout << "parma1 kleiner/gleich 42, param2 true\n";}
public:
	void run_method() const { method(int2type<T1>(),int2type<T2>());}
};
int main()
{
	int const param1 = 42;
	bool const param2 = true;
	Algorithmus<(param1>42?1:0),param2> al;
	al.run_method();
}

hustbaer

Bloops schrieb:

Da das ganze Programm zumindest weiche Echtzeit "garantieren" sollte, ist die Implementierung also aufgrund der häufigen Aufrufe von methodC() und methodD() absolut relevant und es handelt sich hierbei nicht um premature optimization. Also bitte nicht meckern

So lange du nicht den Profiler drüberlaufen hast lassen ist es trotzdem premature. Warum? Weil du keine Ahnung hast wo die Zeit draufgeht. Blind rumoptimieren macht keinen Sinn. Und Optimieren, wenn etwas bereits schnell genug ist, macht auch keinen Sinn. Auch wenn "soft realtime" gefragt ist und Schleifen vorhanden sind die 10M mal durchlaufen werden. Schnell genug ist schnell genug, daran ändert auch die Anforderung "soft realtime" nix.

Bloops

hustbaer schrieb:

So lange du nicht den Profiler drüberlaufen hast lassen ist es trotzdem premature. Warum? Weil du keine Ahnung hast wo die Zeit draufgeht.

Und woher weißt du das? Ich habe sehr wohl einen Profiler drüberlaufen lassen und weiß genau, an welchen Stellen sich die Flaschenhälse befinden.

@einwurf: Auf die Idee kam ich noch gar nicht. Der Ansatz ist mir jetzt auf den ersten Blick relativ sympatisch.

SeppJ schrieb:

Meine Güte, was hast du denn vor? Wieviele unterschiedliche Anpassungen eines Algorithmus kann es denn geben?

Vermutlich werden es drei sein, was in meinem Fall dann 2^3 = 8 Kombinationen wären, wobei nicht alle Parameter für alle Funktionen relevant sind. Mal hängt eine Funktion nur von einem ab, mal von allen dreien und mal von gar keinem.

@Lichtlein: Huh... Eigentlich bin ich auf der Suche nach einer Implementierung, die das Ganze übersichtlicher gestaltet...

Daher würde ich am liebsten auch die ganzen if-Abfragen innerhalb der Funktionen verhindern, selbst wenn sie vom Prozessor recht effizient ausgewertet werden können.

Vielen Dank übrigens allgemein euch allen für die vielen Anregungen. Sind viele interessante Denkanstöße dabei.

Grüße

volkard

hustbaer schrieb:

Bloops schrieb:

Da das ganze Programm zumindest weiche Echtzeit "garantieren" sollte, ist die Implementierung also aufgrund der häufigen Aufrufe von methodC() und methodD() absolut relevant und es handelt sich hierbei nicht um premature optimization. Also bitte nicht meckern

So lange du nicht den Profiler drüberlaufen hast lassen ist es trotzdem premature. Warum? Weil du keine Ahnung hast wo die Zeit draufgeht. Blind rumoptimieren macht keinen Sinn.

Die Entwürfe sind offensichtlich unbefriedigend. Um das zu sehen, brauche ich keinen Profiler.

nurf

Bloops schrieb:

Problem hierbei: die if-Abfrage wird 10.000.000 Millionen mal ausgeführt, obwohl bei Konstruktion des Algorithmus -Objekts (eigentlich sogar zur Compilezeit) bereits feststeht, welcher Zweig der aktive ist.

Also wenn es tatsächlich zur Compile-Zeit feststeht kann man noch besser in die Trick-Kiste greifen.

Ich würde den Algorithmus selbst als Template-Policy umsetzen.
Die Extra-Work als Sonderfall könnte man als Template-Decorator realisieren.

Quasi sowas wie

typedef Algorithm < NormalCalculation > standard;
typedef Algorithm < ExtraCalculation < NormalCalculation > > mitExtra;
// Standard mit anderer Schreibweise
typedef Algorithm < NoExtraCalculation < NormalCalculation > > standardWithNoop;

Zuerst wird vom innersten Template compute aufgerufen und dann vom darüberliegenden.