Was ist rechnerisch schneller? simple formel

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

Maschi

Ich hasse es einfach wenn man mir Sachen unterstellt die ich so nie gesagt habe und wenn Leute nicht bereit sind selber nachzudenken.

Maschi schrieb:

Seher schrieb:

unsympathisches arrogantes Arschloch

Dir würde eine sympathischere Antwort auf "Bit-Shifter-Assi" einfallen? Lass hören: Ich bin bereit ein besserer Mensch zu werden...

bei dir is hopfen und malz verloren. zum glück bist du mit einer arroganten klugscheisser art ein bedauerlicher einzelfall.

volkard

ich bin hier der, der leute beleidigt.
thread für ein weilchen geschlossen.

Assi == Assistent, du solltest mir deswegen keine böswilligkeit unterstellen
Grafikbereich == ist Anwendungsentwicklung, ausser du programmierst controller für gk, etc

randa

Morgen
Schade das der Thread geschlossen wurde, nur weil sich ein paar nicht benehmen konnten. Ich will die Diskussion mal weiterführen, weil ich das interessant finde...

Also Maschi, folgende Sache:
Wie ich dich verstanden hab, hälst du es für sinnvoll, jeden Takt herauszukitzeln bzw überall Bitshifts zu verwenden, wo es geht.

1)Das hilft dir aber nur, wenn du vorher weißt, das es ein Wert ist, der ein vielfaches von zwei ist. das ist selten der Fall. Wenn doch, wie bestimmst du das zur Laufzeit? Alleine eine if-Abfrage "kostet" dich Takte, also kann man das wieder vergessen.
2)Bei konstanten. Das wars aber auch schon. In einem solchen fall multipliziere ich zum Beispiel immer mit 1/Divisor, was ich vorher ausrechne.
3)Warum bringt Taktezählerei nichts? Wenn du einen 2 Ghz Prozessor hast, hast du 2.000.000.000 (2 Milliarden) Takte in der Sekunde. Wenn du hier um 10, 20, oder 100 Takte optimierst, ist das dem Prozessor wurscht. Das ist, als würdest du in einer Anwendung, die 500 MB RAM belegt, um jeden int (4 Byte) kämpfen, damit nicht zuviel Speicher draufgeht. Also sinnlos.
4)Wieviele Divisionen gibts denn Tatsächlich in einer Grafik-Applikation? Sicher einige, aber nicht so viele, das man das signifikant spüren würde, wenn man stattdessen Bitshifts verwenden könnte und würde. Es geht ja letztendlich darum, das wir mit dem Gesunden Menschenverstand am ende auch was davon merken, aber das tun wir nicht.
5)Die Takte, die du meinst zu gewinnen, verlierst du bei der nächstbesten Funktion, die ein einziges int-Argument mehr nimmt => noch sinnloser.
6)Ich habe mal einen Test gemacht, wieviel Performance ein einzelner Bitshift gegen eine einzelne Multiplikation bw. Division mehr bringt.
Test mit 4 Milliarden Schleifendurchläufen a 10 Schleifendurchläufen a 18 Divisionen und 6 Multiplikationen (edit: natürlich die Zahlen usw. gleich gewählt):

Mit Bitshift: 
159.51 sec
Ohne:
181.72 sec

mit Athlon 64 @ 2 Ghz

Das sind etwa 14% mehr Leistung. Bei den wenigen Anwenungsfällen für Bitshifts also nichts. Meineswissens gibt es kein handelsübliches Programm, das nur annähernd so viele Divisionen und Multiplikationen durchführt. Und wenn ja, die paar Sekunden kann dann auch jeder mehr warten.

Es kann in einer High-Level Programmiersprache nicht Sinn sein, um jede Variable zu kämpfen. Das kannst du mit Assembly machen. Fazit also, durch Bitshifts kannst du in C++ Programmen keine Performance gewinnen. Das mag bei Assembly-Programmen bzw. Programmen, die sehr Low-Level sind, anders sein, aber das ist nicht der Bereich der üblichen Programmierung (wie zum Beispiel Grafikprogramme, Spiele usw.).

Edit:

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

Du solltest dich nicht auf andere Stützen, ich wollte einen Beweis von dir, da du deine Sache so vehement verteidigt hast.

ethereal

randa schrieb:

3)Warum bringt Taktezählerei nichts? Wenn du einen 2 Ghz Prozessor hast, hast du 2.000.000.000 (2 Milliarden) Takte in der Sekunde. Wenn du hier um 10, 20, oder 100 Takte optimierst, ist das dem Prozessor wurscht. Das ist, als würdest du in einer Anwendung, die 500 MB RAM belegt, um jeden int (4 Byte) kämpfen, damit nicht zuviel Speicher draufgeht. Also sinnlos.

Nicht ganz! Nimm' mal wieder das beliebte Beispiel Grafikprogrammierung. Stell dir vor, du musst bestimmte Pixel zeichnen, die nicht unbedingt aufeinander folgen, so dass eine einfache Inkrementierung des Arrays nicht möglich ist, z.B. so eine Media-Player-Visualisierung. Dann bist du darauf angewiesen, jedes Pixel anzusprechen (Formel siehe einen meiner älteren Beiträge in diesem Thread). Gewinnst du da bei einem Pixel, sagen wir mal, 10 Takte (wahrscheinlich sind's wesentlich mehr), kannst du bei einer hohen Auflösung (1600x1200,1024x786) gut und gern gezwungen sein, z.B. 100.000 Pixel zu zeichnen, wenn nicht mehr (1600x1200 hat 1.920.000 Pixel, da sind 100.000 Pixel ziemlich wenig). Macht schonmal 100.000*10 Takte Unterschied, und das ist doch schonmal eine beachtliche Zahl, oder? Dazu addieren sich z.B. noch die Takte der Threads, die im Hintergrund laufen, und dann kann es wirklich mal dazu kommen, dass deine Anwendung ein Frame (du bist ja immer auf Frames aus) oder mehr langsamer wird. Analoges gilt für Schleifen, bei denen du jeden Durchlauf neu berechnen musst und nicht einfacher aus vorherigen Werten ableiten kannst.

randa

100.000*10=1.000.000 Takte => 0.05% Performance gewonnen, = bei 25 Bilder/s einen Frame gewonnen, geht man davon aus, dass die gesamte Leistung dem Programm zur Verfügung steht (insgesamt wärens mehr).
Dein Beispiel zieht, wenn du mir die Formel zeigst und sichergehen kannst, das alle entsprechenden Operationen durch Bitshifts ersetzt werden können. Wieviel Takte gewonnen werden können, ist außerdem (denke ich mal) Prozessorabhängig, von daher würde ich mit Takten etwas vorsichtig umgehen. Hat der Prozessor ein (oder zwei oder drei...) Megahertz mehr, ist dein Rechenbeispiel wieder nichtig. Du bewegst dich einfach auf zu Prozessornahem Nieveau, um mit einer solchen Rechnung was zu gewinnen.

Außerdem trifft dies nur einen Spezialfall, in der 3D-Grafikprogrammierung indizierst du den Array inkrementell (oder wie auch immer, aber nicht durch divisionen ). Außerdem ist die ganze Bitshift-Sache hauptsächlich für Divisionen gültig, denn bei Mutliplikationen ist der Performanceunterschied viel geringer.

(du bist ja immer auf Frames aus)

Du kannst auch mit Nanosekunden rechnen.