Warum ist (a * b! = 0) in Java schneller als (a! = 0 && b! = 0)?

412

Ich schreibe einen Code in Java, bei dem der Programmfluss irgendwann dadurch bestimmt wird, ob zwei int-Variablen "a" und "b" ungleich Null sind (Anmerkung: a und b sind niemals negativ, und niemals innerhalb eines ganzzahligen Überlaufbereichs).

Ich kann es mit bewerten

if (a != 0 && b != 0) { /* Some code */ }

Oder alternativ

if (a*b != 0) { /* Some code */ }

Da ich davon ausgehe, dass dieser Code pro Lauf millionenfach ausgeführt wird, habe ich mich gefragt, welcher Code schneller sein würde. Ich habe das Experiment durchgeführt, indem ich sie auf einem riesigen zufällig generierten Array verglichen habe, und ich war auch gespannt, wie sich die Sparsity des Arrays (Bruchteil der Daten = 0) auf die Ergebnisse auswirken würde:

long time;
final int len = 50000000;
int arbitrary = 0;
int[][] nums = new int[2][len];

for (double fraction = 0 ; fraction <= 0.9 ; fraction += 0.0078125) {
    for(int i = 0 ; i < 2 ; i++) {
        for(int j = 0 ; j < len ; j++) {
            double random = Math.random();

            if(random < fraction) nums[i][j] = 0;
            else nums[i][j] = (int) (random*15 + 1);
        }
    }

    time = System.currentTimeMillis();

    for(int i = 0 ; i < len ; i++) {
        if( /*insert nums[0][i]*nums[1][i]!=0 or nums[0][i]!=0 && nums[1][i]!=0*/ ) arbitrary++;
    }
    System.out.println(System.currentTimeMillis() - time);
}

Und die Ergebnisse zeigen, dass, wenn Sie erwarten, dass "a" oder "b" in mehr als ~ 3% der Fälle gleich 0 a*b != 0ist, dies schneller ist als a!=0 && b!=0:

Grafische Darstellung der Ergebnisse von a UND b ungleich Null

Ich bin gespannt warum. Könnte jemand etwas Licht ins Dunkel bringen? Ist es der Compiler oder auf Hardwareebene?

Bearbeiten: Aus Neugier ... jetzt, wo ich etwas über die Verzweigungsvorhersage gelernt habe, habe ich mich gefragt, was der analoge Vergleich für einen OR b ungleich Null zeigen würde:

Graph von a oder b ungleich Null

Wir sehen den gleichen Effekt der Verzweigungsvorhersage wie erwartet, interessanterweise ist der Graph entlang der X-Achse etwas gespiegelt.

Aktualisieren

1- Ich !(a==0 || b==0)habe der Analyse hinzugefügt, um zu sehen, was passiert.

2- ich ebenfalls enthalten a != 0 || b != 0, (a+b) != 0und (a|b) != 0aus Neugier, nach etwa Verzweigungsvorhersage zu lernen. Sie sind jedoch nicht logisch äquivalent zu den anderen Ausdrücken, da nur ein ODER b ungleich Null sein muss, um true zurückzugeben, sodass sie nicht für die Verarbeitungseffizienz verglichen werden sollen.

3- Ich habe auch den tatsächlichen Benchmark hinzugefügt, den ich für die Analyse verwendet habe, bei dem nur eine beliebige int-Variable iteriert wird.

4- Einige Leute schlugen vor, a != 0 & b != 0im Gegensatz zu einzubeziehen a != 0 && b != 0, mit der Vorhersage, dass es sich enger verhalten würde, a*b != 0weil wir den Verzweigungsvorhersageeffekt entfernen würden. Ich wusste nicht, dass &dies mit booleschen Variablen verwendet werden kann. Ich dachte, es wird nur für binäre Operationen mit ganzen Zahlen verwendet.

Hinweis: In dem Kontext, in dem ich all dies in Betracht gezogen habe, ist int overflow kein Problem, aber das ist definitiv eine wichtige Überlegung in allgemeinen Kontexten.

CPU: Intel Core i7-3610QM bei 2,3 GHz

Java-Version: 1.8.0_45
Java (TM) SE-Laufzeitumgebung (Build 1.8.0_45-b14)
Java HotSpot (TM) 64-Bit-Server-VM (Build 25.45-b02, gemischter Modus)

Maljam
quelle
11
Was ist mit if (!(a == 0 || b == 0))? Mikrobenchmarks sind notorisch unzuverlässig, es ist unwahrscheinlich, dass dies wirklich messbar ist (~ 3% klingt für mich nach einer Fehlerquote).
Elliott Frisch
9
Oder a != 0 & b != 0.
Louis Wasserman
16
Die Verzweigung ist langsam, wenn die vorhergesagte Verzweigung falsch ist. a*b!=0hat einen Zweig weniger
Erwin Bolwidt
19
(1<<16) * (1<<16) == 0dennoch unterscheiden sich beide von Null.
CodesInChaos
13
@Gene: Ihre vorgeschlagene Optimierung ist ungültig. Selbst a*bwenn der Überlauf ignoriert wird, ist er Null, wenn einer von aund bNull ist. a|bist nur dann Null, wenn beide sind.
Hmakholm verließ Monica

Antworten:

240

Ich ignoriere das Problem, dass Ihr Benchmarking möglicherweise fehlerhaft ist, und nehme das Ergebnis zum Nennwert.

Ist es der Compiler oder auf Hardwareebene?

Letzteres denke ich:

  if (a != 0 && b != 0)

Kompiliert zu 2 Speicherlasten und zwei bedingten Zweigen

  if (a * b != 0)

Kompiliert zu 2 Speicherlasten, einem Multiplikations- und einem bedingten Zweig.

Die Multiplikation ist wahrscheinlich schneller als die zweite bedingte Verzweigung, wenn die Verzweigungsvorhersage auf Hardwareebene unwirksam ist. Wenn Sie das Verhältnis erhöhen, wird die Verzweigungsvorhersage weniger effektiv.

Der Grund dafür, dass bedingte Verzweigungen langsamer sind, besteht darin, dass sie die Befehlsausführungspipeline zum Stillstand bringen. Bei der Verzweigungsvorhersage geht es darum, den Stillstand zu vermeiden, indem vorhergesagt wird, in welche Richtung die Verzweigung gehen wird, und spekulativ die nächste Anweisung basierend darauf ausgewählt wird. Wenn die Vorhersage fehlschlägt, gibt es eine Verzögerung, während der Befehl für die andere Richtung geladen wird.

(Hinweis: Die obige Erklärung ist zu stark vereinfacht. Für eine genauere Erklärung müssen Sie die vom CPU-Hersteller bereitgestellte Literatur für Assembler-Codierer und Compiler-Autoren lesen. Die Wikipedia-Seite zu Branch Predictors bietet einen guten Hintergrund.)


Es gibt jedoch eine Sache, bei der Sie bei dieser Optimierung vorsichtig sein müssen. Gibt es Werte, bei denen a * b != 0die falsche Antwort gegeben wird? Betrachten Sie Fälle, in denen die Berechnung des Produkts zu einem ganzzahligen Überlauf führt.


AKTUALISIEREN

Ihre Grafiken bestätigen in der Regel, was ich gesagt habe.

  • Es gibt auch einen "Verzweigungsvorhersage" -Effekt im a * b != 0Fall der bedingten Verzweigung , und dies wird in den Diagrammen deutlich.

  • Wenn Sie die Kurven über 0,9 hinaus auf die X-Achse projizieren, sieht es so aus, als ob 1) sie sich bei ungefähr 1,0 treffen und 2) der Treffpunkt ungefähr den gleichen Y-Wert wie für X = 0,0 hat.


UPDATE 2

Ich verstehe nicht, warum die Kurven für die a + b != 0und die a | b != 0Fälle unterschiedlich sind. Die Logik der Zweigprädiktoren könnte etwas Kluges enthalten. Oder es könnte auf etwas anderes hinweisen.

(Beachten Sie, dass diese Art von Dingen für eine bestimmte Chipmodellnummer oder sogar Version spezifisch sein kann. Die Ergebnisse Ihrer Benchmarks können auf anderen Systemen unterschiedlich sein.)

Beide haben jedoch den Vorteil, für alle nicht negativen Werte von aund zu arbeiten b.

Stephen C.
quelle
1
@DebosmitRay - 1) Es sollten keine SWs vorhanden sein. Die Zwischenergebnisse werden in einem Register geführt. 2) Im zweiten Fall stehen zwei Zweige zur Verfügung: einer zum Ausführen von "etwas Code" und der andere zum Springen zur nächsten Anweisung nach dem if.
Stephen C
1
@StephenC Sie sind zu Recht verwirrt über a + b und a | b, weil die Kurven gleich sind , ich denke, es sind die Farben, die wirklich nah sind. Entschuldigung für farbenblinde Menschen!
Maljam
3
@ njzk2 aus Wahrscheinlichkeitssicht sollten diese Fälle gemäß der Achse auf 50% symmetrisch sein (Wahrscheinlichkeit Null von a&bund a|b). Sie sind, aber nicht perfekt, das ist das Rätsel.
Antonín Lejsek
3
@StephenC Der Grund, warum a*b != 0und a+b != 0Benchmark anders ist, ist, dass a+b != 0es überhaupt nicht gleichwertig ist und niemals hätte bewertet werden dürfen. Beispiel: Mit a = 1, b = 0wird der erste Ausdruck als falsch ausgewertet, der zweite als wahr. Die Multiplikation verhält sich wie ein und -Operator, während sich die Addition wie ein oder -Operator verhält.
JS1
2
@ AntonínLejsek Ich denke, die Wahrscheinlichkeiten würden sich unterscheiden. Wenn Sie nNullen dann die Wahrscheinlichkeit , dass beide aund bist Null steigt mit n. Bei einer ANDOperation mit höherer nWahrscheinlichkeit steigt die Wahrscheinlichkeit, dass einer von ihnen nicht Null ist , und die Bedingung ist erfüllt. Dies ist für eine OROperation umgekehrt (die Wahrscheinlichkeit, dass einer von ihnen Null ist, steigt mit n). Dies basiert auf einer mathematischen Perspektive. Ich bin mir nicht sicher, ob die Hardware so funktioniert.
WYSIWYG
70

Ich denke, Ihr Benchmark weist einige Mängel auf und ist möglicherweise nicht hilfreich, um auf echte Programme zu schließen. Hier sind meine Gedanken:

  • (a|b)!=0und (a+b)!=0testen Sie, ob einer der Werte nicht Null ist, während a != 0 && b != 0und (a*b)!=0testen Sie, ob beide Werte nicht Null sind. Sie vergleichen also nicht nur das Timing der Arithmetik: Wenn die Bedingung häufiger zutrifft, führt dies zu mehr Ausführungen des ifKörpers, was ebenfalls mehr Zeit in Anspruch nimmt.

  • (a+b)!=0 wird das Falsche für positive und negative Werte tun, die sich zu Null summieren, so dass Sie es im allgemeinen Fall nicht verwenden können, selbst wenn es hier funktioniert.

  • In ähnlicher Weise (a*b)!=0wird das Falsche für Werte getan, die überlaufen. (Zufälliges Beispiel: 196608 * 327680 ist 0, da das wahre Ergebnis zufällig durch 2 32 teilbar ist. Die niedrigen 32 Bits sind also 0, und diese Bits sind alles, was Sie erhalten, wenn es sich um eine intOperation handelt.)

  • Die VM optimiert den Ausdruck während der ersten Durchläufe der Outer ( fraction) - Schleife, wenn fraction0 ist, wenn die Zweige fast nie genommen werden. Das Optimierungsprogramm kann verschiedene Aktionen ausführen, wenn Sie fractionbei 0,5 beginnen.

  • Sofern die VM nicht in der Lage ist, einige der Array-Begrenzungsprüfungen hier zu eliminieren, enthält der Ausdruck nur aufgrund der Begrenzungsprüfungen vier weitere Zweige. Dies ist ein komplizierter Faktor, wenn Sie herausfinden möchten, was auf niedriger Ebene geschieht. Sie erhalten möglicherweise unterschiedliche Ergebnisse, wenn Sie das zweidimensionale Array in zwei flache Arrays aufteilen, indem Sie nums[0][i]und nums[1][i]zu nums0[i]und ändern nums1[i].

  • CPU-Zweigprädiktoren erkennen kurze Muster in den Daten oder Läufe aller Zweige, die genommen oder nicht genommen werden. Ihre zufällig generierten Benchmark-Daten sind das Worst-Case-Szenario für einen Branch Predictor . Wenn reale Daten ein vorhersehbares Muster aufweisen oder lange Zeiträume mit Werten von Null und Null haben, können die Verzweigungen viel weniger kosten .

  • Der bestimmte Code, der ausgeführt wird, nachdem die Bedingung erfüllt ist, kann sich auf die Leistung der Auswertung der Bedingung selbst auswirken, da er sich beispielsweise darauf auswirkt, ob die Schleife abgewickelt werden kann oder nicht, welche CPU-Register verfügbar sind und ob einer der abgerufenen numsWerte erforderlich ist nach Bewertung des Zustands wiederverwendet werden. Das bloße Inkrementieren eines Zählers im Benchmark ist kein perfekter Platzhalter für das, was echter Code tun würde.

  • System.currentTimeMillis()ist auf den meisten Systemen nicht genauer als +/- 10 ms. System.nanoTime()ist in der Regel genauer.

Es gibt viele Unsicherheiten, und bei solchen Mikrooptimierungen ist es immer schwierig, etwas Bestimmtes zu sagen, da ein Trick, der auf einer VM oder CPU schneller ist, auf einer anderen langsamer sein kann. Wenn Sie die 32-Bit-HotSpot-JVM anstelle der 64-Bit-Version ausführen, beachten Sie, dass es zwei Varianten gibt: Die "Client" -VM weist im Vergleich zur "Server" -VM andere (schwächere) Optimierungen auf.

Wenn Sie den von der VM generierten Maschinencode zerlegen können , tun Sie dies, anstatt zu erraten, was er tut!

Boann
quelle
24

Die Antworten hier sind gut, obwohl ich eine Idee hatte, die die Dinge verbessern könnte.

Da die beiden Zweige und die damit verbundene Verzweigungsvorhersage der wahrscheinliche Schuldige sind, können wir die Verzweigung möglicherweise auf einen einzelnen Zweig reduzieren, ohne die Logik überhaupt zu ändern.

bool aNotZero = (nums[0][i] != 0);
bool bNotZero = (nums[1][i] != 0);
if (aNotZero && bNotZero) { /* Some code */ }

Es kann auch funktionieren

int a = nums[0][i];
int b = nums[1][i];
if (a != 0 && b != 0) { /* Some code */ }

Der Grund dafür ist, dass nach den Regeln des Kurzschlusses, wenn der erste Boolesche Wert falsch ist, der zweite nicht bewertet werden sollte. Es muss eine zusätzliche Verzweigung durchgeführt werden, um zu vermeiden, dass bewertet wird, nums[1][i]ob dies nums[0][i]falsch war. Nun ist es Ihnen vielleicht egal, dass dies nums[1][i]ausgewertet wird, aber der Compiler kann nicht sicher sein, dass er dabei keine außerhalb des Bereichs oder Null-Refs auslöst. Durch Reduzieren des if-Blocks auf einfache Bools kann der Compiler klug genug sein, um zu erkennen, dass das unnötige Auswerten des zweiten Booleschen Werts keine negativen Nebenwirkungen hat.

Seitenfehler
quelle
3
Upvoted, obwohl ich das Gefühl habe, dass dies die Frage nicht ganz beantwortet.
Pierre Arlaud
3
Auf diese Weise können Sie einen Zweig einführen, ohne die Logik von Nicht-Verzweigung zu ändern (wenn Sie die Art aund Weise erhalten und bNebenwirkungen gehabt hätten, hätten Sie sie beibehalten). Sie haben noch, also haben &&Sie noch eine Niederlassung.
Jon Hanna
11

Wenn wir die Multiplikation nehmen, ist das Produkt 0, auch wenn eine Zahl 0 ist. Beim Schreiben

    (a*b != 0)

Es wertet das Ergebnis des Produkts aus, wodurch die ersten paar Vorkommen der Iteration ab 0 eliminiert werden. Infolgedessen sind die Vergleiche geringer als bei der Bedingung

   (a != 0 && b != 0)

Dabei wird jedes Element mit 0 verglichen und ausgewertet. Daher ist der Zeitaufwand geringer. Aber ich glaube, dass die zweite Bedingung Ihnen eine genauere Lösung geben könnte.

Sanket Gupte
quelle
4
Wenn im zweiten Ausdruck aNull ist, bmuss dies nicht ausgewertet werden, da der gesamte Ausdruck bereits falsch ist. Also ist jedes Element, das verglichen wird, nicht wahr.
Kuba Wyrostek
9

Sie verwenden zufällige Eingabedaten, wodurch die Zweige unvorhersehbar werden. In der Praxis sind Verzweigungen häufig (~ 90%) vorhersehbar, sodass der Verzweigungscode im realen Code wahrscheinlich schneller ist.

Das gesagt. Ich sehe nicht, wie a*b != 0schneller sein kann als (a|b) != 0. Im Allgemeinen ist die ganzzahlige Multiplikation teurer als ein bitweises ODER. Aber solche Dinge werden gelegentlich komisch. Siehe zum Beispiel das Beispiel "Beispiel 7: Hardwarekomplexität" aus der Galerie der Prozessor-Cache-Effekte .

StackedCrooked
quelle
2
&ist kein "bitweises ODER", sondern (in diesem Fall) ein "logisches UND", da beide Operanden Boolesche Werte sind und es nicht ist |;-)
siegi
1
@siegi TIL Java '&' ist eigentlich ein logisches UND ohne Kurzschluss.
StackedCrooked