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

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:

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:

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)

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.

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 ³² 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!

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.

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.

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 .