Was ist rechnerisch schneller? simple formel

msp

hi,
schaut mal hier das koennte euch vielleicht auch helfen:
http://library.simugraph.com/articles/opti/optimizing.html

Maschi

msp schrieb:

http://library.simugraph.com/articles/opti/optimizing.html

Die meisten von den Optimierungen nimmt ein moderner Compiler sowieso vor, ich sehe also in den meisten Fällen keinen grund für manuelles loop-unrolling wie es dort beschrieben wird etc. Zum Thema Optimierung würde ich mir heutzutage eher blitz++ (The library that thinks it is a compiler) anschauen .

randa

Optimizer schrieb:

Unterschätze die Bedeutung nicht. Für dich als Anwendungsprogrammierer ist das wahrscheinlich nur selten interessant.
Aber Zahlen wie 16, 256 sind keine Hirngespinnste von irgendwelchen Freaks. Texturen werden z.B. meistens in einer 2er-Potenz Größe im Grafikspeicher abgelegt.

Ich entwickle selbst einen Software Renderer, kann mir aber nicht vorstellen, wo ihr so oft eine Texturgröße (256*256) oder die Auflösung durch irgendetwas dividieren wollt. Bei den Divisionen, die stattfinden, ist es gleich, ob sie mit Bistshifts realisiert werden oder sonstwie, denn sie fallen nicht im geringsten ins Gewicht im Gegensatz zum Gesamten Berechnungsaufwand für einen Frame.
Und wenn das automtisch "optimiert" wird, dann ist es eh egal. Und erinnern wir uns: Der Algotithmus macht etwas schnell, nicht der Compiler.

~7 Takte at all.

Wenn du schon mit Takten und Nanosekunden kämpfst, dann bist du nicht mehr zu retten.

volkard

randa schrieb:

Ich entwickle selbst einen Software Renderer,

ist kein beweis, daß du ahnung hast.

kann mir aber nicht vorstellen, wo ihr so oft eine Texturgröße (256*256) oder die Auflösung durch irgendetwas dividieren wollt.

aber multiplizieren? spätestens innerhalb der graka wird es spannend.

Und erinnern wir uns: Der Algotithmus macht etwas schnell, nicht der Compiler.

das erinnert mich an sledge hammer: "nicht die pistolen töten menschen, die kugeln tun es".

~7 Takte at all.

Wenn du schon mit Takten und Nanosekunden kämpfst, dann bist du nicht mehr zu retten.[/quote]
meine fachliche meinung dazu ist aber, daß aus optimizer mal ein ganz großer wird.

Maschi

@randa: Ok, der Algorithmus macht etwas schnell. Ein Algorithmus mit O(n*log(n)) ist sicher einem O(n^2) vorzuziehen. Ja, aber was bedeutet eigentlich das O? Die Definition der Landau-Symbole kann man in jedem besseren Algo-Buch nachlesen... Es kann über Ruckeln oder flüssiges Bild entscheiden, wenn ein Algo 2*n*log(n) braucht statt 10*n*log(n). Da ist immerhin ein Faktor 5 drin. Auch kann ein Algorithmus mit Laufzeit 42*n*log(n) für kleine Inputs langsamer sein als einer mit n^3.
Selbst wenn man tolle Algorithmen kennt macht es Sinn Takte zu sparen an Stellen wo sie unnötig sind. Diese Stellen findet man am besten mit einem Profiler und optimiert sie mit gesundem Menschenverstand. Verallgemeinern lässt sich so etwas nie...

Maschi

volkard schrieb:

Und erinnern wir uns: Der Algotithmus macht etwas schnell, nicht der Compiler.

das erinnert mich an sledge hammer: "nicht die pistolen töten menschen, die kugeln tun es".

Hehe, ja der gute alte Sledge hat auf alles eine Antwort...

randa

volkard schrieb:

ist kein beweis, daß du ahnung hast.

Das hab ich ja nicht behauptet, nur ich bin kein Anwendungsprogrammierer.

aber multiplizieren?

Sicher doch.

das erinnert mich an sledge hammer: "nicht die pistolen töten menschen, die kugeln tun es".

Ist daran etwas auszusetzen?

meine fachliche meinung dazu ist aber, daß aus optimizer mal ein ganz großer wird.

Aber nicht mit Taktezählerei.

Wer an den falschen Stellen optimiert, gewinnt nix und ist selber schuld.

Edit: Ich bleibe dabei: Optimieren von Divisionen bringt im Gegensatz zum restlichen Arbeitsaufwand pro Frame imho nichts. Wer trotzdem optimieren will, der kann machen was er will. Und wenn der Compiler sowieso selber shiftet, dann ist diese Diskussion überflüssig.

Maschi

randa schrieb:

meine fachliche meinung dazu ist aber, daß aus optimizer mal ein ganz großer wird.

Aber nicht mit Taktezählerei.

Doch, denn die kann auch an den richtigen Stellen geschehen... Müsstest du als toller "Software Renderer-Entwickler" aber eigentlich wissen .

randa

Maschi schrieb:

Müsstest du als toller "Software Renderer-Entwickler" aber eigentlich wissen .

Was muckiert ihr euch eigentlich darüber, das ich das erwähnt habe? Habt ihr ein Problem? Ich habe nicht im geringsten damit geprahlt, und wenn das bei euch so angekommen ist, dann hab ich nichts damit zu schaffen.

Maschi

Du verkündest hier nach so einer Aussage deine Halbweisheiten über Optimierung. Dann musst du dich nicht wundern...

randa

Maschi schrieb:

Du verkündest hier nach so einer Aussage deine Halbweisheiten über Optimierung. Dann musst du dich nicht wundern...

Zeig mir deine Bistshift Performance Demo, Meister, und dann sehen wir weiter. Ich kapituliere, sobald du mehr als einen Frame gewonnen hast.

Maschi

Du hast dich schon selber disqualifiziert, tut mir leid!

Um mal zum eigentlichen Thema zurückzukommen, für Schleifen gibt es eine (zugegeben recht wilde) Möglichkeit der Optimierung, das so genannte "Duff's Device" - im Grunde so ne Art manuelles partial-loop-unroll. Statt

do something() while(--n > 0);

schreibt man da

int m = n / 8;
switch(n % 8){
  do {    something();
  case 7: something();
  case 6: something();
  case 5: something();
  case 4: something();
  case 3: something();
  case 2: something();
  case 1: something();
  case 0:
 } while(--m >= 0);
}

Die Idee ist im Grunde, in die Schleife reinzuswitchen und so die Anzahl der Vergleiche auf ein Achtel zu reduzieren. Funktioniert natürlich nicht bei komplexeren Bedingungen. Ansonsten - wenn schon zur Compilezeit feststeht, wie oft die Schleife durchlaufen werden soll, gibts templates:

template<int i> struct do_loop() { static void run(); };
template<int i> void do_loop< i>::run() { 
  do_loop<i-1>::run();
  something();
}
template<>      void do_loop<-1>::run() {}

//...

do_loop<23>::run(); // führt den Schleifeninhalt 23 mal aus

Da wird der Kram zur Compilezeit aufgelöst, so dass effektiv 23 mal hintereinander something(); da steht.

ethereal

randa schrieb:

ethereal schrieb:

~7 Takte at all.

Wenn du schon mit Takten und Nanosekunden kämpfst, dann bist du nicht mehr zu retten.

Darf ich fragen, was du unter Optimierung bzgl. Geschwindigkeit verstehst?
Vielleicht missverstehen wir uns ja da...

randa

Darf ich fragen, was du unter Optimierung bzgl. Geschwindigkeit verstehst?
Vielleicht missverstehen wir uns ja da...

Erhöhung der Ausführungsgeschwindigkeit *g*.
Wenn man an jeder Variable rumwerkelt, hat man am ende nichts gewonnen. Wenn man den Algorithmus verbessert, kann man viel gewinnen.

Maschi schrieb:

Du hast dich schon selber disqualifiziert, tut mir leid!

Du bist mir immernoch einen simplen Beweis schuldig. Es ist erstmal eine Behauptung, zu sagen, mit Bitshifts gewinne ich Performance in einem Programm, und dann nichts zur Untermauerung der Aussage hinzuzufügen. Ich will ein Programm sehen, in dem ich einen Frame mit Bitsthifts hinzugewinne. Alles andere disqualifiziert dich selbst.

net 0

Alithecoaster schrieb:

und ob es eine funktion zum potentieren gibt die schneller ist als wenn ich jetzt y * y * y schreibe?

kann sein dass man das mit einer folge von verschiebeoperationen und additionen schneller kriegt.
beispiel: x*33 = x<<5+x

btw:
hab jetzt den ganzen thread nicht gelesen, also sorry wenn einer schon sowas ähnliches geschrieben hat.

Bashar

net schrieb:

Alithecoaster schrieb:

und ob es eine funktion zum potentieren gibt die schneller ist als wenn ich jetzt y * y * y schreibe?

kann sein dass man das mit einer folge von verschiebeoperationen und additionen schneller kriegt.
beispiel: x*33 = x<<5+x

Du verwechselst potenzieren und multiplizieren.

net 0

Bashar schrieb:

Du verwechselst potenzieren und multiplizieren.

potenzieren kann man bestimmt auch so ähnlich. ist nur die frage ob's schneller ist. wahrscheinlich eher nicht.

volkard

net schrieb:

potenzieren kann man bestimmt auch so ähnlich. ist nur die frage ob's schneller ist. wahrscheinlich eher nicht.

für x^3 noch nicht, genauso wie für x*3 der trick x+x<<1 noch nicht schneller als x+x+x ist.

Maschi

randa schrieb:

Du bist mir immernoch einen simplen Beweis schuldig. Es ist erstmal eine Behauptung, zu sagen, mit Bitshifts gewinne ich Performance in einem Programm, und dann nichts zur Untermauerung der Aussage hinzuzufügen. Ich will ein Programm sehen, in dem ich einen Frame mit Bitsthifts hinzugewinne. Alles andere disqualifiziert dich selbst.

Witzig, ich programmiere jetzt bestimmt mal eben ein komplettes Demo (besser gesagt 2, sonst fehlt der Vergleich) um dir zu demonstrieren, dass ich Recht habe. So wichtig ist es mir auch nicht. Wenn du lernresistent bist dann ist das deine Sache... Es scheint aber nicht nur meine Erfahrung zu sein, dass Bitshifting Performance bringen kann.

Wenn du den Thread aufmerksam gelesen hättest dann wüsstest du, dass es nur in manchen Fällen Sinn macht. So einen Fall kann man nicht mal eben konstruieren. Man muss Schwachstellen aufdecken, den Profiler befragen wo es hapert und dann überlegen ob man mit geschickten Alternativoperationen Takte sparen kann.