Operatoren langsam, wie so...?

hustbaer

orkun schrieb:

Okay, also ihr denkt der Author hatte langeweile beim implementieren und kommentieren der Methoden:

00046                 /* arithmetic operations - fast! */
00047                 inline void set_add(const hk_Vector3& a, const hk_Vector3& b);
00048                 inline void set_sub(const hk_Vector3& a, const hk_Vector3& b);
00049                 inline void set_cross(const hk_Vector3& a, const hk_Vector3& b);
00050 
00051                 inline void set_mul(hk_real r, const hk_Vector3& a);
00052                 inline void set_mul3(const hk_Diagonal_Matrix& a, const hk_Vector3& b);
00053                 inline void set_mul3( const hk_Matrix3& a, const hk_Vector3& b ); 
00054                 inline void add_mul(hk_real r, const hk_Vector3& a);
00055                 inline void set_interpolate( const hk_Vector3& a, const hk_Vector3& b, hk_real t);

die sind wohl nur zufällig da... alles klar...

Ich glaube du bist ein bisschen doof. Welche dieser Funktionen würdest du denn durch einen überladenen Operator ersetzen? Und welchen? Und wie?
Willst du statt set_add einen operator + (std::pair<hk_Vector3 const&, hk_Vector3 const&>) machen oder wie stellst du dir das vor?

Meep Meep

hustbaer schrieb:

Ich glaube du bist ein bisschen doof. Welche dieser Funktionen würdest du denn durch einen überladenen Operator ersetzen? Und welchen? Und wie?
Willst du statt set_add einen operator + (std::pair<hk_Vector3 const&, hk_Vector3 const&>) machen oder wie stellst du dir das vor?

ich denkmal das 'set_add' den operator+ und den operator= ersetzen soll.
ich glaub der programmierer hat den aufwand mit den funktionen deshalb betrieben, um temporaere objecte zu vermeiden.

bin mir fast sicher das das ungefaehr so aussieht:

class hk_Vector3;

class hkVector3ExpressionPlus
{
   public:
      hkVector3ExpressionPlus(const hk_Vector3 &v1, const hk_Vector3 &v2) : vec1(v1), vec2(v2) { }

   const hk_Vector3 &vec1, &vec2;
};

inline const hkVector3ExpressionPlus operator+ (const hk_Vector3& a, const hk_Vector3& b)
{
   return hkVector3ExpressionPlus(a,b);
} 

class hk_Vector3
{
   public:
      ...
      /* expression operators */
      inline void operator= (ConsT hkVector3ExpressionPlus HK_REF v)
      {
         /* hier kommt der teil den ich mir denke */
         set_add(v.vec1, v.vec2);
      } 
      ...
      /* arithmetic operations - fast */
      ...
      inline void set_add(const hk_Vector3& a, const hk_Vector3& b)
      {
         /* hier wird er wahrscheinlich die addition und die zuweisung machen */
      }
      ...
};

/* damit kann man nu folgendes schreiben: */
hk_Vector3 a,b,c;

a = b + c; /* <- schlussendlich wird dann hier vom kompiler implizit die 'set_add'-memberfunktion eingesetzt. 
somit wird das temporaere object, welches von 'b + c' erzeugt werden wuerde, vermieden. deshalb wahrscheinlich der kommentar mit 'fast'*/

und nachdem ich grad so schoen am traeumen bin, geh ich jetz schlafen.

gute nacht

Meep Meep

otze

@Meep Meep
jep, denke ich auch, die dinger werden ja auch "expression operators" genannt. imho eine sehr geile idee, komplexe operationen auf diese Weise effizient und lesbar zu machen.

hustbaer

Hah, hab ich wieder mal das offensichtliche übersehen
Trotzdem würde ich das nicht so machen wenn ich will dass es unbedingt und auf jeden Fall schnell geht... ich persönlich finde da die "set_add" Funktion besser.

groovemaster

orkun schrieb:

Warum sind eigentlich operatoren langsamer als "normale" funktionen...?

In der Theorie nicht, in der Praxis leider schon. Das hat vor allem mit den von Meep Meep bereits angesprochenen temporären Objekten zu tun, die Compiler nicht vollständig eliminieren können. Dort gab es immer mal wieder diverse Lösungsansätze. Alexandrescu hat auch mal etwas dazu verfasst, Stichwort Mojo. Ein bekannte Lösung für binäre Operatoren sind Expression Templates. Allerdings ist sowas weder elegant zu implementieren, noch einfach zu warten. Jedenfalls kann das ziemlich komplexe Ausmasze annehmen.

Sry wenn dich einige hier anmachen, aber deine Frage ist durchaus berechtigt.

orkun schrieb:

ich möchte eine eine 3D Vectorklasse schreiben, lohnt es sich mit SSE oder mit 3DNow! zu implementieren?

SSE bzw. 3DNow lohnt sich immer. Ob man das selber implementiert, hängt von den Fähigkeiten deines Compilers ab.

orkun schrieb:

Welche operationen sollte ich als inline assembler implementieren?

Gar keine. Aktuelle Compiler sollten entsprechende Intrinsics kennen.

hustbaer

groovemaster schrieb:

orkun schrieb:

Warum sind eigentlich operatoren langsamer als "normale" funktionen...?

In der Theorie nicht, in der Praxis leider schon. Das hat vor allem mit den von Meep Meep bereits angesprochenen temporären Objekten zu tun, die Compiler nicht vollständig eliminieren können. Dort gab es immer mal wieder diverse Lösungsansätze. Alexandrescu hat auch mal etwas dazu verfasst, Stichwort Mojo. Ein bekannte Lösung für binäre Operatoren sind Expression Templates. Allerdings ist sowas weder elegant zu implementieren, noch einfach zu warten. Jedenfalls kann das ziemlich komplexe Ausmasze annehmen.

Sry wenn dich einige hier anmachen, aber deine Frage ist durchaus berechtigt.

Ist sie finde ich nicht. (Ich vor allem habe mich auch am Ton des OP mehr gestossen als an seiner Frage. Etwas nicht zu wissen und zu fragen ist OK, auf richtige Antworten dann aber patzig zu werden ... vertrage ich nicht ganz.)

Ein überladener Operator ++ ist nicht langsamer als eine "increment" Memberfunktion.
Ein überladener Operator += ist auch nicht langsamer als eine "add" Memberfunktion.
Beides sind üblicherweise Memberfunktionen und werden ganz genau gleich aufgerufen.

D.h. solange man nicht anfängt Äpfel mit Birnen zu vergleichen...

Ein Aufruf von Operator + der ein Temporary zurückliefert + ein Aufruf von Operator = mit diesem Temporary als Argument, dann vielleicht noch darauf besteht dass Operator = eine Referenz auf *this zurückliefert ... wenn du das mit dem Aufruf einer einzigen Funktion die void zurückliefert vergleichen willst ... ich finde den Vergleich auf jeden Fall unsinnig.

----

Wo ich dir natürlich zustimme: mit überladenen Operatoren kann man schwerer optimieren als mit Memberfunktionen. Was aber einfach daran liegt dass Operatoren eine vorgegebene Anzahl an Parametern haben, und Memberfunktionen nicht. Wo wir dann auch wieder bei den Äpfeln und Birnen wären, man soll eben keinen Apfel den Job einer Birne machen lassen.

orkun

Es geht in diesem Thread um Optimierungstechniken von Funktionen und Operatoren (auch mit SSE, MMX etc.) Ich habe behauptet, dass man Operatoren nur schwer optimieren kann und dass sie deshalb langsam sind.
Der Code war nur ein Beispiel für eine Optimierungstechnik. (meine Meinung nach eine schöne UND aufwendige Technik)
Ich habe genervt beantwortet, weil die Optimierungstechnik, die da benutzt wird, ignoriert wurde. Man muss ja nicht unbediengt die ganze Implementierung sehen, um zu wissen was die Klasse macht.

Jetzt habe ich noch eine Frage an die jenigen die Sachlich diskutieren können und mir bei meinem Problem helfen wollen:

Was genau ist der Unterschied zwischen Inline-Assembler-Code und Verwendung von Intrinsics.
Inline-Assembler, wird ja immer noch benutzt, obwohl es mit Intrinsics einfacher geht.

PS: Ich werde jetzt dafür kein Beispielcode verwerden, ihr wisst schon warum...

Meep Meep

wenn du inline assembler verwendest hast du die komplette kontrolle ueber den generierten code, aber auch die komplette verantwortung dafuer.
meines wissens kann der kompiler jedoch selbst keine optimierungen mehr an dem code vornehmen.

intrinsics erscheinen wie normale funktionen, werden jedch direkt in maschinencode umgesetzt.

ob der kompiler damit noch optimieren kann entzieht sich meinem wissen.
hab auch irgendwo im internet mal gelesen, das mit VC auf nem 64-bit windows kein inline assembler mehr moeglich sein soll. kann jetzt aber die quelle dazu nicht angeben. schon zu lange her. also mit vorsicht zu geniesen.

Meep Meep

Meep Meep

orkun schrieb:

Es geht in diesem Thread um Optimierungstechniken von Funktionen und Operatoren (auch mit SSE, MMX etc.) Ich habe behauptet, dass man Operatoren nur schwer optimieren kann und dass sie deshalb langsam sind.

sah fuer mich nicht so aus

orkun schrieb:

Warum sind eigentlich operatoren langsamer als "normale" funktionen...?

orkun schrieb:

Man muss ja nicht unbediengt die ganze Implementierung sehen, um zu wissen was die Klasse macht.

haette die sache aber unter umstaenden vereinfacht

Meep Meep

Simon2

orkun schrieb:

...Ich habe behauptet, dass man Operatoren nur schwer optimieren kann und dass sie deshalb langsam sind....

Ist trotzdem Quatsch !
Was Du vielleicht meinst, ist, dass bestimmte Aufrufsemantiken weniger Optimierungstechniken zulassen als andere. Ob diese in f() oder in operator_() umgesetzt wird, spielt keine Rolle.

Gruß,

Simon2.

otze

orkun schrieb:

Es geht in diesem Thread um Optimierungstechniken von Funktionen und Operatoren (auch mit SSE, MMX etc.) Ich habe behauptet, dass man Operatoren nur schwer optimieren kann und dass sie deshalb langsam sind.

Nein, hast du nicht.

du hast neben dem von Meep meep zitiertem teil auch folgendes geschrieben:

Warum wird in Real Time Rendering oder Physik Engines auf operatoren verzichtet...?

Beispielsweise Havok Vectorklasse sieht so aus:

und pastest danach einen code, der ganz offensichtlich auf operatoren aufbaut, nur dass er sie intelligent nutzt, und nachdem wir den code mühevoll aufdröseln, wirst du patzig und behauptest "Das hab ich doch alles schon gewusst".

<°(((><

orkun

Oh man, ohne deine Hilfe hätte ich eine Woche lang auf die Implementierung der Methoden gestart und nicht gewusst was die Klasse macht, danke dass du mir alles erklärt hast...

Jetzt mal im Ernst:
Okay, ich bin Student und lebe seit einpaar Jahren in Deutschland. Ich habe meine Frage sehr schlecht formulieren(auch überschrift schlecht formuliert). Ich wollte eigentlich mehr über Optimierungstechniken wissen ...und worum geht's denn jetzt in diesem Thread...???
Naja egal... Nachdem mehrmals geschrieben wurde, dass ein Operator auch eine Funktion ist, habe ich geschrieben, dass in 3D engines auf operatoren verzichtet wird, deshalb die Behauptung, dass Operatoren langsam sind. Ich habe versucht, auf die schwerige(!) Optimierung von Operatoren aufmerksam zu machen. Ich dachte Headerdatei reicht, weil da auch die expression structs und die arithmetic operationen deklariert sind. Es war ein Beispiel...

...und ich behaupte nicht, dass ich Ahnung habe... im Gegenteil, ich habe Frage gestellt, weil ich mehr wissen möchte. Mit Sachliche Diskusion meine ich, dass man über das Thema diskutiert und nicht über meine genervte Ton, über meine Sprachkenntnisse etc...

Kurz:
Es ging in diesem Thread um Optimierungstechniken, um eine Vectorklasse mit optimierte Operationen, wie man am besten arithmetic operationen optimieren kann... Sollte man vielleicht doch operatoren benutzten. Oder lieber so was machen:

http://www.cortstratton.org/articles/OptimizingForSSE.php

So missverständlich war der Anfangspost nun wieder auch nicht...

Meep Meep

orkun schrieb:

Oh man, ohne deine Hilfe hätte ich eine Woche lang auf die Implementierung der Methoden gestart und nicht gewusst
was die Klasse macht, danke dass du mir alles erklärt hast...

solche saetze werden dich auch nicht weiter bringen.

nun zurueck zur thematik.

orkun schrieb:

Kurz:
Es ging in diesem Thread um Optimierungstechniken, um eine Vectorklasse mit optimierte Operationen,
wie man am besten arithmetic operationen optimieren kann... Sollte man vielleicht doch operatoren benutzten.

schreib einfach mal deine verctorklasse oder was auch immer.
messe danach die lauftzeit und benutze einen profiler deines vertrauens.
danach, wenn du weißt an welchen stellen optimiert werden muss,
postest du den code und wir koennen uns das dann mal ansehen und darueber
diskutieren was man machen kann.
einfach pauschal sagen, so und so musst es machen und dann ist es schnell,
wird wahrscheinlich nicht funktionieren.
da ist die ganze sache von zu vielen faktoren abhaengig.

Meep Meep

hustbaer

@orkun:
Ohne auf die anderen Dinge einzugene etwas zu deiner Frage... was ist der Unterschied zwischen intrinsics und inline Assembler...

Der Unterschied ist: mit inline Assembler kommt genau der Code raus den du schreibst, Befehl für Befehl. Dadurch hast du z.B. auch die Kontrolle darüber was zu welchem Zeitpunkt in einem Register gehalten wird, wann du etwas auf den Stack pusht etc.

Bei intrinsics ist zwar sichergestellt dass für die eigentliche Funktion der gewünschte Assembler Befehl verwendet wird, und dass es keinen Funktionsaufruf gibt, allerdings kannst du nicht kontrollieren wie die Parameter genau geladen werden, ob sie bis zum nächsten Aufruf in einem Register stehen bleiben oder neu geladen werden etc. Was das angeht bist du auf den Optimizer vom Compiler angewiesen. Wenn der gut arbeitet ist das nicht schlimm, aber manchmal baut der weniger optimalen Code zusammen als man selbst schreiben könnte.

Der Vorteil von intrinsics ist also dass einem der Compiler/Optimizer viel Arbeit abnehmen kann, man sich also um Register Allocation etc. keine Gedanken machen braucht. Eint weiterer Vorteil ist natürlich dass jeder C++ Programmierer den Code noch lesen kann, vorausgesetzt er hat Zugriff auf die Dokumentation der verwendeten intrinsics.
Meist ist der resultierende Code auch schnell genug, oft genug sogar schneller als wenn man inline Assembler schreibt.

Was Optimierungen im Allgemeinen angeht... das ist ein riesen Thmea. Gewisse Dinge sind noch relativ einfach, und man kann einfach darauf achten keinen Blödsinn zu bauen. z.B. dass Dinge wie Winkelfunktionen, Wurzeln, Logarithmen etc. extrem langsam sind. Früher was auch noch ein enormer Unterschied zwischen floating point und integer, ist heutzutage aber nichtmehr so schlimm. Eine andere Sache die manchmal etwas bringt: mehrere unabhängige Sachen parallel zu machen ist oft besser optimierbar als wenn man sie hintereinander macht. Beispiel:

struct sepp { int x; int y };

void foo(sepp* p, unsigned size)
{
    for (unsigned i = 1; i < size; i++)
        p[i].x = p[i].x * 3 / 6 + p[i-1].y;

    for (unsigned i = 1; i < size; i++)
        p[i].y = p[i].y * 5 / 7 + p[i-1].x;
}

void bar(sepp* p, unsigned size)
{
    for (unsigned i = 0; i < size; i++)
    {
        p[i].x = p[i].x * 3 / 6 + p[i-1].y;
        p[i].y = p[i].y * 5 / 7 + p[i-1].x;
    }
}

Angenommen der Optimizer kann nicht erkennen dass er die beiden Schleifen in foo zusammenziehen kann, dann wird der Code in bar deutlich schneller sein. Nicht unbedingt wegen des Overheads der Schleife, sondern eher deswegen weil in bar 2 unabhängige Rechnungen "parallel" passieren...
In foo muss der Compiler quasi folgenden Code in der Schleife generieren:

0    load reg_1, p[i].x
1    mul reg_1, 3
2    div reg_1, 6
3    add reg_1, p[i-1].y
4    store reg_1, p[i].x

Hier muss Befehl 1 darauf warten dass Befehl 0 fertig ist, Befehl 2 darauf dass Befehl 1 fertig ist etc. Das bremst die CPU aus.
In bar kann der Compiler schon Code generieren der "interleaved" ist, und selbst wenn der Compiler dazu zu dumm ist kann die CPU es meist selbst "reordern" (Im ersten Fall kann die CPU selbst nichts reordern, da sie durch die Schleife daran gehindert wird).
Sieht dann etwa so aus:

0    load reg_1, p[i].x
1    load reg_2, p[i].y
2    mul reg_1, 3
3    mul reg_2, 5
4    div reg_1, 6
5    div reg_2, 7
6    add reg_1, p[i-1].y
7    add reg_2, p[i-1].y
8    store reg_1, p[i].x
9    store reg_2, p[i].y

Befehl 1 ist nun von Befehl 0 unabhängig und muss nicht warten. Befehl 2 ist nur von Befehl 0 abhängig - da dazwischen aber schon Befehl 1 ausgeführt wurde ist die Wartezeit zumindest verkürzt, dasselbe gilt für alle weiteren Befehle.
Das Beispiel ist grob vereinfacht, genauso wie der "pseudo-Assembler" den ich hier verwendet habe, aber ich hoffe du verstehst worum es geht.

Je schneller man also das Ergebnis einer Operation als Quelle/Parameter/Argument für einen neue Operation verwendet, und je weniger "unabhngiger" Code drumherum zu finden ist, desto schlechter ist das. Besonders schlimm ist das bei Operationen wie Dividieren und Multiplizieren. Eine Division gleich gefolgt von einem Befehl der das Ergebnis dieser Division verwendet kann die Ausführung für etliche Zyklen anhalten, weil Divisionen nunmal sehr lange dauern. Macht man nach der Division dagegen erstmal mit anderen Dingen weiter kann diese sozusagen "im Hintergrund" weiterlaufen, und wenn dann etliche Takte später das Ergebnis verwendet wird ist es u.U. schon fertig.

----

Was allerdings auch klar sein sollte: Optimieren ist der grösste Feind der Übersichtlichkeit, Einfachkeit und Wartbarkeit eines Programmes. Optimieren sollte man daher immer nur dort wo es nötig ist bzw. wo es wirklich Sinn macht. Wo es nötig ist bzw. Sinn macht findet man am besten mit einem Profiler heraus. Und das auch nur nachdem man festgestellt hat dass das Programm "zu langsam" ist - wenn das Programm so wie man es ohne Optimierungen geschrieben hat schnell genug ist sollte man einfach glücklich darüber sein und garnixmehr angreifen.