Was ist rechnerisch schneller? simple formel

interpreter

Maschi schrieb:

i++; // Effekt: i wird inkrementiert (hier optimiert der Compiler zu ++i)

Könntest du mir bitte erklären, WIE der Compiler hier optimiert?

Bashar

interpreter schrieb:

Maschi schrieb:
i++; // Effekt: i wird inkrementiert (hier optimiert der Compiler zu ++i)
Könntest du mir bitte erklären, WIE der Compiler hier optimiert?

Er stellt während der Abhängigkeitsanalyse fest, dass das Ergebnis des Ausdruckes verworfen wird, also läßt er den Teil des Codes, der dafür zuständig ist, weg. Würd ich mal sagen.

Ringding

randa schrieb:

@etheral: Ich weiß nicht wie du Grafik Programmierst, aber wenn du auch nur einen müden Frame mit der Benutzung von Bitshifts in einem Programm gewinnst, dann würde mich das echt wundern.

Jeder Compiler macht das automatisch (bei Multiplikation mit Konstanten).

randa schrieb:

@etheral: Ich weiß nicht wie du Grafik Programmierst, aber wenn du auch nur einen müden Frame mit der Benutzung von Bitshifts in einem Programm gewinnst, dann würde mich das echt wundern.

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.

Es lassen sich unendlich viele weitere Beispiele finden. Mehrdimensionale Arrays, die intern als eindimensionales Array abgebildet werden, multiplizieren sich nicht die Indizes zusammen sondern shiften sie sich zusammen...

KPC

@Optimizer
Und das muss ich wirklich alles selbermachen und nicht den Compiler übernehmen lassen? Ich versteh nicht so ganz wo man da optimieren kann, weil bei Konstanten berechnungen optimiert sowas doch wirklich der Compiler oder etwa nicht?

Jo, ich rede auch nicht Ausdrücken mit Konstanten. Aber wenn man irgendwas entwickelt (ein mehrdimensionales Array), dann muss man sich da schon Gedanken machen.
Ging mir nur darum, zu sagen, dass das shiften nicht generell uninteressant ist.

ethereal

randa schrieb:

@etheral: Ich weiß nicht wie du Grafik Programmierst, aber wenn du auch nur einen müden Frame mit der Benutzung von Bitshifts in einem Programm gewinnst, dann würde mich das echt wundern.

Oft genug kommst du in Situationen, in denen du deine x/y-Koordinate als lineares Array betrachten musst. Dann gibt's kein x/y mehr, sondern nur noch einen Wert im Array, der die entsprechende Position repräsentiert. Ergo berechnest du den Wert mit

pos=y*Zeilenbreite+x

Deine Auflösung am PC ist aber leider sehr selten 512 oder 256. Sondern eben 640,800,1600. Da musst du dann selbst ran.
Hier mal ein paar Daten zum einfachen Assembler-Mul:

Clocks Size
Operands 808x 286 386 486 Bytes
reg32 - - 9-38 13-42 2-4

Brauch auf nem 486 bei 32bit-Registern bis zu 42 Takte.
Dagegen ein SHL:

Clocks Size
Operands 808x 286 386 486 Bytes
reg,CL 8+4n 5+n 3 3 2

Brauch 3 Takte...Nehmen wir an, du splittest die Bildschirmbreite in zwei Summanden, die Zweierpotenzen sind.
Hast du also 2*3 Takte + 1*1Takt, um beide zu addieren = ~7 Takte at all.
Im Vergleich zu den 13-42 Takte ist das doch schon mal ein kleiner Fortschritt, oder? Und auch, wenn deine GUI noch so ausgefeilt ist, wird's im Endeffekt wohl immer auf ähnliche Art gelöst werden.

LaMothe schreibt dazu im "Tricks of the..." auch interessante Kommentare. Shifts sind mächtiger, als man denkt

edit:Sry für die Formatierungsfehler in den Tabellen...

volkard

KPC schrieb:

@Optimizer
Und das muss ich wirklich alles selbermachen und nicht den Compiler übernehmen lassen? Ich versteh nicht so ganz wo man da optimieren kann, weil bei Konstanten berechnungen optimiert sowas doch wirklich der Compiler oder etwa nicht?

man muss wissen, daß der compiler so sachen optimiert.
das führt zu schnellerem code.

bool operator<(Zeit const& a,Zeit const& b){
   return a.stunde*60+a.minute < b.stunde*60+b.minute;
}

ist in diesem sinne kacke, denn mit dem wissen um den trick mit dem shiften muß es heißen:

bool operator<(Zeit const& a,Zeit const& b){
   return a.stunde*64+a.minute < b.stunde*64+b.minute;
}

es ist gut, wenn man weiß, was in den unteren stockwerken des computers passiert. natürlich soll keiner mehr mit der hand shiften, es reicht, dem compiler auf die sprünge zu helfen.

interpreter

Bashar schrieb:

interpreter schrieb:
Maschi schrieb:
i++; // Effekt: i wird inkrementiert (hier optimiert der Compiler zu ++i)
Könntest du mir bitte erklären, WIE der Compiler hier optimiert?
Er stellt während der Abhängigkeitsanalyse fest, dass das Ergebnis des Ausdruckes verworfen wird, also läßt er den Teil des Codes, der dafür zuständig ist, weg. Würd ich mal sagen.

Richtig, das wird er auch machen. Aber er wird nicht das machen, was im Kommentar steht, denn bei einem int ist ++i nicht effizienter als i++. (Wenn der Compiler die Zeile nicht einfach streichen würde, WÜRDE es zu einem add eax, 1 oder inc werden)

Maschi

Schlaumeier, aber dann ist es auch kein "mov + inc" mehr, sondern nur ein "inc" und ein einzelnes "inc" erzeugt auf den mir bekannten Plattformen keine Kopie! Hat da der Compiler etwa nicht optimiert wenn er eine redundante Kopie einspart?

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...