Was ist rechnerisch schneller? simple formel

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.

*lol*

Ich würd dich gern später als mein Bit-Shifter-Assi oder so ähnlich einstellen. Bezahlung könnte gut sein. Kommt darauf an wie gut du bist, also ab ran an die Demo.

mfg marcel

Es scheint aber nicht nur meine Erfahrung zu sein, dass Bitshifting Performance bringen kann.

Hast es schon richtig erkannt, trotzdem sollte man nicht auf nicht allg-gültige Aussagen zurückschliessen. Entweder du benutzt Bit-Operatoren (von Anfang an wo es geht) oder du lässt es, da am Ende eines Projekts, ein Quellcode mehrere tausend Zeilen Quellcode enthalten kann und du mit deiner Kinderspielereioptimierung vielleicht 0.00001% Geschwindigkeit herausholen kannst. Was wiederum Zeit in Anspruch nimmt und die Kosten deines Produkts in die höhe treibt. Und ohne vernünftige UNIT-Tests hast du erst recht die Arschkarte.

Cu

Maschi

Wen man keine Ahnung hat ... einfach mal Fresse halten! Ich sprach nie von Anwendungsentwicklung, sondern ausschließlich vom Grafikbereich und da auch nur von Flaschenhälsen. Wenn du mal den Thread lesen würdest, dann würdest du auch erkennen, dass ich irgendwo auch mal gesagt habe, dass Allgemeinaussagen in puncto Optimierung Mist sind.

Maschi schrieb:

Wen man keine Ahnung hat ... einfach mal Fresse halten! Ich sprach nie von Anwendungsentwicklung, sondern ausschließlich vom Grafikbereich und da auch nur von Flaschenhälsen. Wenn du mal den Thread lesen würdest, dann würdest du auch erkennen, dass ich irgendwo auch mal gesagt habe, dass Allgemeinaussagen in puncto Optimierung Mist sind.

unsympathisches arrogantes Arschloch