Die folgenden drei Codeteile erzielen genau den gleichen Effekt. Bei der Kompilierung mit -O3 auf GCC 4.5.2 variieren die Zeiten für viele Iterationen jedoch ziemlich stark.
Die obigen Zeiten sind die besten für jede Methode, wenn sie als innere Schleife eines Benchmark-Programms ausgeführt werden. Der random() wird vor jedem Lauf auf dieselbe Weise gesetzt.
Bevor ich diesen Benchmark machte, nahm ich an, dass GCC die Unterschiede optimieren würde. Vor allem das zweite Beispiel lässt mich den Kopf kratzen. Kann irgendjemand erklären, warum GCC diesen Code nicht in gleichwertigen Code umwandelt?
BEARBEITEN: Einige Fehler wurden behoben, und es wurde auch klargestellt, dass die Zufallszahlen unabhängig davon erstellt und verwendet werden, um nicht weg optimiert zu werden. Sie waren immer im Original-Benchmark, ich habe nur den Code verpfuscht, den ich hier angelegt habe.
Hier ist ein Beispiel für eine tatsächliche Benchmark-Funktion:
%Vor%Das OP hat sich seit meiner ursprünglichen Antwort ein wenig verändert. Lassen Sie mich versuchen, hier noch einmal zu sehen.
Im Fall 1 würde ich wegen des Kurzschließens von or erwarten, dass der Compiler vier Compare-two-Branch-Code-Abschnitte erzeugt. Verzweigungen können offensichtlich ziemlich teuer sein, besonders wenn sie nicht den vorhergesagten Weg gehen.
Im Fall 2 kann der Compiler entscheiden, alle vier Vergleiche durchzuführen, sie in Bool 0/1 Ergebnisse umwandeln und dann bitweise or alle vier Teile zusammen und dann einen einzelnen (zusätzlichen) Zweig machen. Dies handelt möglicherweise mehr Vergleiche für möglicherweise weniger Filialen. Es sieht so aus, als würde die Reduzierung der Anzahl der Zweige die Leistung verbessern.
Im Fall 3 funktionieren die Dinge ziemlich genau wie 2, außer ganz am Ende kann ein weiterer Zweig eliminiert werden, indem dem Compiler explizit gesagt wird: "Ich weiß, dass das Ergebnis null oder eins ist. Multiplizieren Sie einfach das Ding auf der linken Seite um diesen Wert ". Die Multiplikation kommt anscheinend schneller als der entsprechende Zweig auf Ihrer Hardware heraus. Dies steht im Gegensatz zu dem zweiten Beispiel, in dem der Compiler den Bereich der möglichen Ausgaben aus dem bitweisen or nicht kennt, so dass er annehmen muss, dass er irgendeine ganze Zahl sein könnte und stattdessen einen Vergleich und Sprung durchführen muss.
Ursprüngliche Antwort für Geschichte:
Der erste Fall unterscheidet sich funktional von dem zweiten und dritten, wenn random Nebenwirkungen hat (was ein normaler PRNG wäre), also liegt es nahe, dass der Compiler sie anders optimieren kann. Insbesondere ruft der erste Fall random nur so oft auf wie nötig, um die Prüfung zu bestehen, während in den anderen beiden Fällen random immer viermal aufgerufen wird. Dies wird (unter der Annahme, dass random wirklich Stateful ist) dazu führen, dass die zukünftigen Zufallszahlen anders sind.
Der Unterschied zwischen dem zweiten und dritten liegt darin, dass der Compiler wahrscheinlich aus irgendeinem Grund nicht herausfinden kann, ob das Ergebnis der bitweisen oder immer 0 oder 1 ist. Wenn Sie einen Hinweis geben, die Multiplikation statt Verzweigung zu machen die Multiplikation kommt wahrscheinlich schneller durch Pipelining.
Bei logischen Operatoren wird der Code verzweigt und vorgezogen. Bitweise Operatoren machen immer die volle Arbeit.
Die Verzweigungsvorhersage wird im ersten Fall schlechter sein, obwohl sie für größere Beispiele den bitweisen Fall übertrifft.
Es kann random() nicht optimieren, weil diese Funktion nicht rein (idempotent) ist.
Sie können immer versuchen, die Verzweigung zu optimieren und zu multiplizieren. Statt:
%Vor%oder
%Vor%Sie können:
%Vor% Wenn test falsch ist, -false==0 und (blah&0)==0 . Wenn test wahr ist, -true==~0 und (blah&~0)==blah . Sie müssen möglicherweise mit test als !!test herumspielen, um true==1 zu gewährleisten.
Auf meinem Rechner (Intel E5503) mit gcc 4.5.3 finde ich, dass Version 1 im Allgemeinen die schnellste ist, obwohl der Unterschied innerhalb des Messrauschens liegt (f3 ist am langsamsten, obwohl nur etwa 2% langsamer als f1) .
Wie messen Sie Ihre Zeitmessung? Sie stellen möglicherweise fest, dass die Unterschiede, die Sie sehen, mehr darauf zurückzuführen sind als der tatsächliche Unterschied im erzeugten Code.
Tags und Links optimization c++ gcc