Kann & in Java schneller sein als &&?
In diesem Code:
if (value >= x && value <= y) {
wenn value >= x und value <= y ohne bestimmtes Muster so wahrscheinlich wahr wie falsch sind, ist die Verwendung des Operators & schneller als die Verwendung von &&?
Insbesondere denke ich darüber nach, wie && Den Ausdruck auf der rechten Seite träge auswertet (dh nur wenn die LHS wahr ist), was eine Bedingung impliziert, während in Java & Garantiert in diesem Zusammenhang die strikte Auswertung beider (boolescher) Unterausdrücke. Das Wertergebnis ist in beiden Fällen dasselbe.
Während ein Operator >= Oder <= Eine einfache Vergleichsanweisung verwendet, muss der Operator && Eine Verzweigung enthalten, und diese Verzweigung kann verzweigt werden Vorhersagefehler - gemäß dieser sehr berühmten Frage: Warum ist es schneller, ein sortiertes Array zu verarbeiten als ein unsortiertes Array?
Das Erzwingen, dass der Ausdruck keine faulen Komponenten enthält, ist sicherlich deterministischer und nicht anfällig für Vorhersagefehler. Richtig?
Anmerkungen:
- offensichtlich wäre die Antwort auf meine Frage Nein , wenn der Code so aussähe:
if(value >= x && verySlowFunction()). Ich konzentriere mich auf "ausreichend einfache" RHS-Ausdrücke. - es gibt dort sowieso einen bedingten Zweig (die
if-Anweisung). Ich kann mir nicht recht beweisen, dass das irrelevant ist und dass alternative Formulierungen bessere Beispiele sein könnten, wieboolean b = value >= x && value <= y; - das alles fällt in die Welt der schrecklichen Mikrooptimierungen. Ja, ich weiß :-) ... aber interessant?
Update Nur um zu erklären, warum ich interessiert bin: Ich habe auf die Systeme gestarrt, über die Martin Thompson auf seinem Mechanical) geschrieben hat Sympathie-Blog , nachdem er gekommen ist und hat ein Gespräch geführt über Aeron. Eine der Schlüsselbotschaften ist, dass unsere Hardware all dieses magische Zeug enthält und wir Softwareentwickler es auf tragische Weise nicht ausnutzen. Keine Sorge, ich werde nicht mit meinem gesamten Code loslegen :-) ... aber auf dieser Website gibt es eine Reihe von Fragen zur Verbesserung der Vorhersage von Zweigen durch Entfernen von Zweigen Für mich sind die bedingten Booleschen Operatoren der Kern der Testbedingungen.
Natürlich macht @StephenC den fantastischen Punkt, dass das Biegen Ihres Codes in seltsame Formen für JITs das Erkennen allgemeiner Optimierungen erschweren kann - wenn nicht jetzt, dann in Zukunft. Und dass die oben erwähnte sehr berühmte Frage besonders ist, weil sie die Vorhersagekomplexität weit über die praktische Optimierung hinaus treibt.
Mir ist ziemlich genau bewusst, dass in den meisten (oder fast allen ) Situationen && Das klarste, einfachste, schnellste und beste ist, obwohl ich Ich bin den Leuten sehr dankbar, die Antworten gepostet haben, die dies demonstrieren! Ich bin wirklich interessiert zu sehen, ob es tatsächlich Fälle gibt, in denen die Antwort auf "Kann & Schneller sein?" könnte sein Ja ...
Update 2 : (Hinweis, dass die Frage zu weit gefasst ist. Ich möchte keine größeren Änderungen an dieser Frage vornehmen weil es einige der folgenden Antworten, die von außergewöhnlicher Qualität sind, gefährden könnte!) Vielleicht ist ein Beispiel in freier Wildbahn gefragt; Dies ist aus der Klasse Guava LongMath (Vielen Dank an @maaartinus, der dies gefunden hat):
public static boolean isPowerOfTwo(long x) {
return x > 0 & (x & (x - 1)) == 0;
}
Siehst du das zuerst &? Und wenn Sie den Link überprüfen, heißt die next -Methode lessThanBranchFree(...), was darauf hindeutet, dass wir uns im Gebiet der Zweigumgehung befinden - und Guava ist wirklich weit verbreitet: Jeder gespeicherte Zyklus führt zu einem sichtbaren Abfall des Meeresspiegels. Stellen wir die Frage also so: Ist diese Verwendung von & (Wobei && Normaler wäre) eine echte Optimierung?
Ok, also wollen Sie wissen, wie es sich auf der unteren Ebene verhält ... Schauen wir uns dann den Bytecode an!
BEARBEITEN: Der generierte Assembly-Code für AMD64 wurde am Ende hinzugefügt. Schauen Sie sich einige interessante Hinweise an.
EDIT 2 (re: OPs "Update 2"): asm-Code für Guavas isPowerOfTwo -Methode hinzugefügt.
Java-Quelle
Ich habe diese zwei schnellen Methoden geschrieben:
_public boolean AndSC(int x, int value, int y) {
return value >= x && value <= y;
}
public boolean AndNonSC(int x, int value, int y) {
return value >= x & value <= y;
}
_Wie Sie sehen, sind sie bis auf den Typ des AND-Operators genau gleich.
Java-Bytecode
Und das ist der generierte Bytecode:
_ public AndSC(III)Z
L0
LINENUMBER 8 L0
ILOAD 2
ILOAD 1
IF_ICMPLT L1
ILOAD 2
ILOAD 3
IF_ICMPGT L1
L2
LINENUMBER 9 L2
ICONST_1
IRETURN
L1
LINENUMBER 11 L1
FRAME SAME
ICONST_0
IRETURN
L3
LOCALVARIABLE this Ltest/lsoto/AndTest; L0 L3 0
LOCALVARIABLE x I L0 L3 1
LOCALVARIABLE value I L0 L3 2
LOCALVARIABLE y I L0 L3 3
MAXSTACK = 2
MAXLOCALS = 4
// access flags 0x1
public AndNonSC(III)Z
L0
LINENUMBER 15 L0
ILOAD 2
ILOAD 1
IF_ICMPLT L1
ICONST_1
GOTO L2
L1
FRAME SAME
ICONST_0
L2
FRAME SAME1 I
ILOAD 2
ILOAD 3
IF_ICMPGT L3
ICONST_1
GOTO L4
L3
FRAME SAME1 I
ICONST_0
L4
FRAME FULL [test/lsoto/AndTest I I I] [I I]
IAND
IFEQ L5
L6
LINENUMBER 16 L6
ICONST_1
IRETURN
L5
LINENUMBER 18 L5
FRAME SAME
ICONST_0
IRETURN
L7
LOCALVARIABLE this Ltest/lsoto/AndTest; L0 L7 0
LOCALVARIABLE x I L0 L7 1
LOCALVARIABLE value I L0 L7 2
LOCALVARIABLE y I L0 L7 3
MAXSTACK = 3
MAXLOCALS = 4
_Die Methode AndSC (_&&_) generiert erwartungsgemäß zwei bedingte Sprünge:
- Es lädt
valueundxauf den Stapel und springt zu L1, wennvalueniedriger ist. Ansonsten läuft es in den nächsten Zeilen weiter. - Es lädt
valueundyauf den Stapel und springt auch zu L1, wennvaluegrößer ist. Ansonsten läuft es in den nächsten Zeilen weiter. - Was zufällig ein _
return true_ ist, falls keiner der beiden Sprünge gemacht wurde. - Und dann haben wir die als L1 markierten Zeilen, die ein _
return false_ sind.
Die Methode AndNonSC (_&_) erzeugt jedoch drei bedingte Sprünge!
- Es lädt
valueundxauf den Stapel und springt zu L1, wennvalueniedriger ist. Da das Ergebnis jetzt gespeichert werden muss, um es mit dem anderen Teil des AND zu vergleichen, muss es entweder "savetrue" oder "savefalse" ausführen, was nicht möglich ist beide mit der gleichen Anweisung. - Es lädt
valueundyauf den Stapel und springt zu L1, wennvaluegrößer ist. Wieder muss estrueoderfalsespeichern und das sind zwei verschiedene Zeilen, abhängig vom Vergleichsergebnis. - Nachdem beide Vergleiche durchgeführt wurden, führt der Code die AND-Operation tatsächlich aus - und wenn beide wahr sind, springt er (zum dritten Mal), um wahr zurückzugeben. Andernfalls wird die Ausführung in der nächsten Zeile fortgesetzt, um false zurückzugeben.
(Vorläufige) Schlussfolgerung
Obwohl ich nicht so viel Erfahrung mit Java bytecode habe und vielleicht etwas übersehen habe, scheint es mir, dass _&_ tatsächlich eine schlechtere Leistung erbringt in jedem Fall als _&&_: Es werden mehr auszuführende Anweisungen generiert, einschließlich mehr bedingter Sprünge, die vorhergesagt werden müssen und bei denen möglicherweise ein Fehler auftritt.
Ein Umschreiben des Codes, um Vergleiche mit arithmetischen Operationen zu ersetzen, wie es von einer anderen Person vorgeschlagen wurde, könnte eine bessere Möglichkeit sein, _&_ zu machen, allerdings auf Kosten einer weitaus geringeren Klarheit des Codes.
IMHO lohnt es sich nicht für 99% der Szenarien (es lohnt sich möglicherweise für die 1% -Schleifen, die jedoch extrem optimiert werden müssen).
EDIT: AMD64 Assembly
Wie in den Kommentaren erwähnt, kann derselbe Java bytecode in verschiedenen Systemen zu unterschiedlichem Maschinencode führen, während der Java bytecode uns einen Hinweis darauf geben kann, welcher Die AND-Version bietet eine bessere Leistung. Nur wenn Sie den vom Compiler generierten ASM-Code erhalten, können Sie das herausfinden.
Ich habe die AMD64-ASM-Anweisungen für beide Methoden gedruckt. Im Folgenden sind die relevanten Linien (abgespeckte Einstiegspunkte usw.) aufgeführt.
HINWEIS: Alle Methoden wurden mit Java 1.8.0_91 kompiliert, sofern nicht anders angegeben.
Methode AndSC mit Standardoptionen
_ # {method} {0x0000000016da0810} 'AndSC' '(III)Z' in 'AndTest'
...
0x0000000002923e3e: cmp %r8d,%r9d
0x0000000002923e41: movabs $0x16da0a08,%rax ; {metadata(method data for {method} {0x0000000016da0810} 'AndSC' '(III)Z' in 'AndTest')}
0x0000000002923e4b: movabs $0x108,%rsi
0x0000000002923e55: jl 0x0000000002923e65
0x0000000002923e5b: movabs $0x118,%rsi
0x0000000002923e65: mov (%rax,%rsi,1),%rbx
0x0000000002923e69: lea 0x1(%rbx),%rbx
0x0000000002923e6d: mov %rbx,(%rax,%rsi,1)
0x0000000002923e71: jl 0x0000000002923eb0 ;*if_icmplt
; - AndTest::[email protected] (line 22)
0x0000000002923e77: cmp %edi,%r9d
0x0000000002923e7a: movabs $0x16da0a08,%rax ; {metadata(method data for {method} {0x0000000016da0810} 'AndSC' '(III)Z' in 'AndTest')}
0x0000000002923e84: movabs $0x128,%rsi
0x0000000002923e8e: jg 0x0000000002923e9e
0x0000000002923e94: movabs $0x138,%rsi
0x0000000002923e9e: mov (%rax,%rsi,1),%rdi
0x0000000002923ea2: lea 0x1(%rdi),%rdi
0x0000000002923ea6: mov %rdi,(%rax,%rsi,1)
0x0000000002923eaa: jle 0x0000000002923ec1 ;*if_icmpgt
; - AndTest::[email protected] (line 22)
0x0000000002923eb0: mov $0x0,%eax
0x0000000002923eb5: add $0x30,%rsp
0x0000000002923eb9: pop %rbp
0x0000000002923eba: test %eax,-0x1c73dc0(%rip) # 0x0000000000cb0100
; {poll_return}
0x0000000002923ec0: retq ;*ireturn
; - AndTest::[email protected] (line 25)
0x0000000002923ec1: mov $0x1,%eax
0x0000000002923ec6: add $0x30,%rsp
0x0000000002923eca: pop %rbp
0x0000000002923ecb: test %eax,-0x1c73dd1(%rip) # 0x0000000000cb0100
; {poll_return}
0x0000000002923ed1: retq
_Methode AndSC mit _-XX:PrintAssemblyOptions=intel_ Option
_ # {method} {0x00000000170a0810} 'AndSC' '(III)Z' in 'AndTest'
...
0x0000000002c26e2c: cmp r9d,r8d
0x0000000002c26e2f: jl 0x0000000002c26e36 ;*if_icmplt
0x0000000002c26e31: cmp r9d,edi
0x0000000002c26e34: jle 0x0000000002c26e44 ;*iconst_0
0x0000000002c26e36: xor eax,eax ;*synchronization entry
0x0000000002c26e38: add rsp,0x10
0x0000000002c26e3c: pop rbp
0x0000000002c26e3d: test DWORD PTR [rip+0xffffffffffce91bd],eax # 0x0000000002910000
0x0000000002c26e43: ret
0x0000000002c26e44: mov eax,0x1
0x0000000002c26e49: jmp 0x0000000002c26e38
_Methode AndNonSC mit Standardoptionen
_ # {method} {0x0000000016da0908} 'AndNonSC' '(III)Z' in 'AndTest'
...
0x0000000002923a78: cmp %r8d,%r9d
0x0000000002923a7b: mov $0x0,%eax
0x0000000002923a80: jl 0x0000000002923a8b
0x0000000002923a86: mov $0x1,%eax
0x0000000002923a8b: cmp %edi,%r9d
0x0000000002923a8e: mov $0x0,%esi
0x0000000002923a93: jg 0x0000000002923a9e
0x0000000002923a99: mov $0x1,%esi
0x0000000002923a9e: and %rsi,%rax
0x0000000002923aa1: cmp $0x0,%eax
0x0000000002923aa4: je 0x0000000002923abb ;*ifeq
; - AndTest::[email protected] (line 29)
0x0000000002923aaa: mov $0x1,%eax
0x0000000002923aaf: add $0x30,%rsp
0x0000000002923ab3: pop %rbp
0x0000000002923ab4: test %eax,-0x1c739ba(%rip) # 0x0000000000cb0100
; {poll_return}
0x0000000002923aba: retq ;*ireturn
; - AndTest::[email protected] (line 30)
0x0000000002923abb: mov $0x0,%eax
0x0000000002923ac0: add $0x30,%rsp
0x0000000002923ac4: pop %rbp
0x0000000002923ac5: test %eax,-0x1c739cb(%rip) # 0x0000000000cb0100
; {poll_return}
0x0000000002923acb: retq
_Methode AndNonSC mit _-XX:PrintAssemblyOptions=intel_ Option
_ # {method} {0x00000000170a0908} 'AndNonSC' '(III)Z' in 'AndTest'
...
0x0000000002c270b5: cmp r9d,r8d
0x0000000002c270b8: jl 0x0000000002c270df ;*if_icmplt
0x0000000002c270ba: mov r8d,0x1 ;*iload_2
0x0000000002c270c0: cmp r9d,edi
0x0000000002c270c3: cmovg r11d,r10d
0x0000000002c270c7: and r8d,r11d
0x0000000002c270ca: test r8d,r8d
0x0000000002c270cd: setne al
0x0000000002c270d0: movzx eax,al
0x0000000002c270d3: add rsp,0x10
0x0000000002c270d7: pop rbp
0x0000000002c270d8: test DWORD PTR [rip+0xffffffffffce8f22],eax # 0x0000000002910000
0x0000000002c270de: ret
0x0000000002c270df: xor r8d,r8d
0x0000000002c270e2: jmp 0x0000000002c270c0
_- Erstens unterscheidet sich der generierte ASM-Code je nachdem, ob wir die Standard-AT & T-Syntax oder die Intel-Syntax wählen.
- Mit AT & T-Syntax:
- Der ASM-Code ist tatsächlich länger für die Methode
AndSC, wobei jeder Bytecode _IF_ICMP*_ in zwei Assembly-Sprunganweisungen übersetzt wird, was insgesamt 4 bedingte Sprünge ergibt . - In der Zwischenzeit generiert der Compiler für die
AndNonSC-Methode einen einfacheren Code, bei dem jeder Bytecode _IF_ICMP*_ in nur eine Assembly-Sprunganweisung übersetzt wird, wobei die ursprüngliche Anzahl von 3 bedingten Sprüngen beibehalten wird.
- Der ASM-Code ist tatsächlich länger für die Methode
- Mit Intel-Syntax:
- Der ASM-Code für
AndSCist mit nur 2 bedingten Sprüngen kürzer (ohne den nicht bedingtenjmpam Ende). Tatsächlich sind es nur zwei CMP, zwei JL/E und ein XOR/MOV, abhängig vom Ergebnis. - Der ASM-Code für
AndNonSCist jetzt länger als der fürAndSC! Allerdings hat es nur 1 bedingten Sprung (für den ersten Vergleich), wobei die Register verwendet werden, um das erste Ergebnis direkt mit dem zweiten zu vergleichen, ohne dass weitere Sprünge erforderlich sind.
- Der ASM-Code für
Fazit nach ASM-Code-Analyse
- Auf AMD64-Maschinensprachenebene scheint der Operator _
&_ ASM-Code mit weniger bedingten Sprüngen zu generieren, was für hohe Vorhersagefehlerraten (z. B. zufälligevalues) besser sein könnte. - Andererseits scheint der Operator _
&&_ ASM-Code mit weniger Anweisungen zu generieren (mit der Option _-XX:PrintAssemblyOptions=intel_), was für wirklich lange Schleifen mit vorhersagefreundlichen Eingaben, bei denen die geringere Anzahl von CPU-Zyklen für jeden Vergleich auf lange Sicht einen Unterschied ausmachen kann.
Wie ich in einigen Kommentaren ausgeführt habe, wird dies zwischen den Systemen sehr unterschiedlich sein. Wenn es sich also um die Optimierung der Verzweigungsvorhersage handelt, lautet die einzig richtige Antwort: Dies hängt von Ihrer JVM-Implementierung und Ihrem Compiler ab , Ihre CPU und Ihre Eingabedaten.
Nachtrag: Guavas isPowerOfTwo Methode
Hier haben sich die Entwickler von Guava eine einfache Methode ausgedacht, um zu berechnen, ob eine bestimmte Zahl eine Potenz von 2 ist:
_public static boolean isPowerOfTwo(long x) {
return x > 0 & (x & (x - 1)) == 0;
}
_Zitat von OP:
Ist diese Verwendung von _
&_ (wobei _&&_ normaler wäre) eine echte Optimierung?
Um herauszufinden, ob dies der Fall ist, habe ich meiner Testklasse zwei ähnliche Methoden hinzugefügt:
_public boolean isPowerOfTwoAND(long x) {
return x > 0 & (x & (x - 1)) == 0;
}
public boolean isPowerOfTwoANDAND(long x) {
return x > 0 && (x & (x - 1)) == 0;
}
_Intels ASM-Code für Guavas Version
_ # {method} {0x0000000017580af0} 'isPowerOfTwoAND' '(J)Z' in 'AndTest'
# this: rdx:rdx = 'AndTest'
# parm0: r8:r8 = long
...
0x0000000003103bbe: movabs rax,0x0
0x0000000003103bc8: cmp rax,r8
0x0000000003103bcb: movabs rax,0x175811f0 ; {metadata(method data for {method} {0x0000000017580af0} 'isPowerOfTwoAND' '(J)Z' in 'AndTest')}
0x0000000003103bd5: movabs rsi,0x108
0x0000000003103bdf: jge 0x0000000003103bef
0x0000000003103be5: movabs rsi,0x118
0x0000000003103bef: mov rdi,QWORD PTR [rax+rsi*1]
0x0000000003103bf3: lea rdi,[rdi+0x1]
0x0000000003103bf7: mov QWORD PTR [rax+rsi*1],rdi
0x0000000003103bfb: jge 0x0000000003103c1b ;*lcmp
0x0000000003103c01: movabs rax,0x175811f0 ; {metadata(method data for {method} {0x0000000017580af0} 'isPowerOfTwoAND' '(J)Z' in 'AndTest')}
0x0000000003103c0b: inc DWORD PTR [rax+0x128]
0x0000000003103c11: mov eax,0x1
0x0000000003103c16: jmp 0x0000000003103c20 ;*goto
0x0000000003103c1b: mov eax,0x0 ;*lload_1
0x0000000003103c20: mov rsi,r8
0x0000000003103c23: movabs r10,0x1
0x0000000003103c2d: sub rsi,r10
0x0000000003103c30: and rsi,r8
0x0000000003103c33: movabs rdi,0x0
0x0000000003103c3d: cmp rsi,rdi
0x0000000003103c40: movabs rsi,0x175811f0 ; {metadata(method data for {method} {0x0000000017580af0} 'isPowerOfTwoAND' '(J)Z' in 'AndTest')}
0x0000000003103c4a: movabs rdi,0x140
0x0000000003103c54: jne 0x0000000003103c64
0x0000000003103c5a: movabs rdi,0x150
0x0000000003103c64: mov rbx,QWORD PTR [rsi+rdi*1]
0x0000000003103c68: lea rbx,[rbx+0x1]
0x0000000003103c6c: mov QWORD PTR [rsi+rdi*1],rbx
0x0000000003103c70: jne 0x0000000003103c90 ;*lcmp
0x0000000003103c76: movabs rsi,0x175811f0 ; {metadata(method data for {method} {0x0000000017580af0} 'isPowerOfTwoAND' '(J)Z' in 'AndTest')}
0x0000000003103c80: inc DWORD PTR [rsi+0x160]
0x0000000003103c86: mov esi,0x1
0x0000000003103c8b: jmp 0x0000000003103c95 ;*goto
0x0000000003103c90: mov esi,0x0 ;*iand
0x0000000003103c95: and rsi,rax
0x0000000003103c98: and esi,0x1
0x0000000003103c9b: mov rax,rsi
0x0000000003103c9e: add rsp,0x50
0x0000000003103ca2: pop rbp
0x0000000003103ca3: test DWORD PTR [rip+0xfffffffffe44c457],eax # 0x0000000001550100
0x0000000003103ca9: ret
_Intel asm code für _&&_ version
_ # {method} {0x0000000017580bd0} 'isPowerOfTwoANDAND' '(J)Z' in 'AndTest'
# this: rdx:rdx = 'AndTest'
# parm0: r8:r8 = long
...
0x0000000003103438: movabs rax,0x0
0x0000000003103442: cmp rax,r8
0x0000000003103445: jge 0x0000000003103471 ;*lcmp
0x000000000310344b: mov rax,r8
0x000000000310344e: movabs r10,0x1
0x0000000003103458: sub rax,r10
0x000000000310345b: and rax,r8
0x000000000310345e: movabs rsi,0x0
0x0000000003103468: cmp rax,rsi
0x000000000310346b: je 0x000000000310347b ;*lcmp
0x0000000003103471: mov eax,0x0
0x0000000003103476: jmp 0x0000000003103480 ;*ireturn
0x000000000310347b: mov eax,0x1 ;*goto
0x0000000003103480: and eax,0x1
0x0000000003103483: add rsp,0x40
0x0000000003103487: pop rbp
0x0000000003103488: test DWORD PTR [rip+0xfffffffffe44cc72],eax # 0x0000000001550100
0x000000000310348e: ret
_In diesem speziellen Beispiel generiert der JIT-Compiler weit weniger Assemblycode für die Version _&&_ als für die Version _&_ von Guava (und nach den Ergebnissen von gestern I) war ehrlich überrascht).
Im Vergleich zu Guava bedeutet die Version _&&_ 25% weniger zu kompilierenden Bytecode für JIT, 50% weniger Assembly-Anweisungen und nur zwei bedingte Sprünge (die Version _&_ enthält vier davon ).
Alles deutet darauf hin, dass Guavas _&_ -Verfahren weniger effizient ist als die "natürlichere" _&&_ -Version.
... Oder ist es?
Wie bereits erwähnt, führe ich die obigen Beispiele mit Java 8:
_C:\....>Java -version
Java version "1.8.0_91"
Java(TM) SE Runtime Environment (build 1.8.0_91-b14)
Java HotSpot(TM) 64-Bit Server VM (build 25.91-b14, mixed mode)
_Aber was ist, wenn ich zu Java 7 wechsle?
_C:\....>c:\jdk1.7.0_79\bin\Java -version
Java version "1.7.0_79"
Java(TM) SE Runtime Environment (build 1.7.0_79-b15)
Java HotSpot(TM) 64-Bit Server VM (build 24.79-b02, mixed mode)
C:\....>c:\jdk1.7.0_79\bin\Java -XX:+UnlockDiagnosticVMOptions -XX:CompileCommand=print,*AndTest.isPowerOfTwoAND -XX:PrintAssemblyOptions=intel AndTestMain
.....
0x0000000002512bac: xor r10d,r10d
0x0000000002512baf: mov r11d,0x1
0x0000000002512bb5: test r8,r8
0x0000000002512bb8: jle 0x0000000002512bde ;*ifle
0x0000000002512bba: mov eax,0x1 ;*lload_1
0x0000000002512bbf: mov r9,r8
0x0000000002512bc2: dec r9
0x0000000002512bc5: and r9,r8
0x0000000002512bc8: test r9,r9
0x0000000002512bcb: cmovne r11d,r10d
0x0000000002512bcf: and eax,r11d ;*iand
0x0000000002512bd2: add rsp,0x10
0x0000000002512bd6: pop rbp
0x0000000002512bd7: test DWORD PTR [rip+0xffffffffffc0d423],eax # 0x0000000002120000
0x0000000002512bdd: ret
0x0000000002512bde: xor eax,eax
0x0000000002512be0: jmp 0x0000000002512bbf
.....
_Überraschung! Der vom JIT-Compiler in Java 7) für die Methode _&_ generierte Assemblycode hat jetzt nur einen bedingten Sprung und ist viel kürzer! Während die _&&_ -Methode (Sie müssen mir auf diese vertrauen, ich möchte das Ende nicht überladen!) mit ihren zwei bedingten Sprüngen und ein paar Anweisungen weniger in etwa gleich bleibt, Oberteile.
Sieht so aus, als ob Guavas Ingenieure doch wussten, was sie taten! (Wenn sie versuchten, Java 7 Ausführungszeit zu optimieren, das ist ;-)
Also zurück zur letzten Frage von OP:
Ist diese Verwendung von _
&_ (wobei _&&_ normaler wäre) eine echte Optimierung?
Und IMHO die Antwort ist die gleiche, auch für dieses (sehr!) Spezifische Szenario: es hängt von Ihrer JVM-Implementierung, Ihrem Compiler, Ihrer CPU und Ihren Eingabedaten ab.
Für diese Art von Fragen sollten Sie ein Mikrobenchmark verwenden. Ich habe JMH für diesen Test verwendet.
Die Benchmarks sind implementiert als
// boolean logical AND
bh.consume(value >= x & y <= value);
und
// conditional AND
bh.consume(value >= x && y <= value);
und
// bitwise OR, as suggested by Joop Eggen
bh.consume(((value - x) | (y - value)) >= 0)
Mit Werten für value, x and y entsprechend dem Benchmarknamen.
Das Ergebnis (fünf Aufwärm- und zehn Messungsiterationen) für das Durchsatz-Benchmarking ist:
Benchmark Mode Cnt Score Error Units
Benchmark.isBooleanANDBelowRange thrpt 10 386.086 ▒ 17.383 ops/us
Benchmark.isBooleanANDInRange thrpt 10 387.240 ▒ 7.657 ops/us
Benchmark.isBooleanANDOverRange thrpt 10 381.847 ▒ 15.295 ops/us
Benchmark.isBitwiseORBelowRange thrpt 10 384.877 ▒ 11.766 ops/us
Benchmark.isBitwiseORInRange thrpt 10 380.743 ▒ 15.042 ops/us
Benchmark.isBitwiseOROverRange thrpt 10 383.524 ▒ 16.911 ops/us
Benchmark.isConditionalANDBelowRange thrpt 10 385.190 ▒ 19.600 ops/us
Benchmark.isConditionalANDInRange thrpt 10 384.094 ▒ 15.417 ops/us
Benchmark.isConditionalANDOverRange thrpt 10 380.913 ▒ 5.537 ops/us
Das Ergebnis ist für die Auswertung selbst nicht so unterschiedlich. Solange dieser Code keine Auswirkungen auf die Leistung hat, würde ich nicht versuchen, ihn zu optimieren. Abhängig von der Stelle im Code kann sich der Hotspot-Compiler für eine Optimierung entscheiden. Welche wahrscheinlich nicht durch die oben genannten Benchmarks abgedeckt ist.
einige Referenzen:
Boolesches logisches UND - der Ergebniswert ist true, wenn beide Operandenwerte true sind; ansonsten ist das Ergebnis false
Bedingtes UND - ist wie &, wertet aber seinen rechten Operanden nur aus, wenn der Wert seines linken Operanden true ist
bitweises ODER - Der Ergebniswert ist der bitweise einschließlich OR der Operandenwerte
Ich werde das aus einem anderen Blickwinkel betrachten.
Betrachten Sie diese beiden Codefragmente,
if (value >= x && value <= y) {
und
if (value >= x & value <= y) {
Wenn wir annehmen, dass value, x, y einen primitiven Typ haben, geben diese beiden (Teil-) Anweisungen für alle möglichen Eingabewerte das gleiche Ergebnis. (Wenn Wrapper-Typen beteiligt sind, sind sie aufgrund eines impliziten null-Tests für y, der in der Version & Und nicht in der Version && Ausführung.)
Wenn der JIT-Compiler gute Arbeit leistet, kann der Optimierer daraus schließen, dass diese beiden Anweisungen dasselbe tun:
Wenn einer vorhersehbar schneller ist als der andere, sollte er die schnellere Version verwenden können ... im JIT-kompilierten Code.
Wenn nicht, spielt es keine Rolle, welche Version auf Quellcodeebene verwendet wird.
Da der JIT-Compiler vor dem Kompilieren Pfadstatistiken sammelt, kann er möglicherweise mehr Informationen über die Ausführungseigenschaften haben, die der Programmierer (!) Hat.
Wenn der JIT-Compiler der aktuellen Generation (auf einer bestimmten Plattform) nicht gut genug dafür optimiert ist, könnte die nächste Generation dies tun ... abhängig davon, ob empirische Beweise darauf hindeuten, dass dies ein lohnenswert ist oder nicht = zu optimierendes Muster.
In der Tat, wenn Sie Java Code in einer Weise schreiben, die dies optimiert, gibt es eine Chance dass Sie die "obskurere" Version des Codes auswählen might inhibit die Fähigkeit des aktuellen oder zukünftigen JIT-Compilers zur Optimierung.
Kurz gesagt, ich denke nicht, dass Sie diese Art der Mikrooptimierung auf Quellcode-Ebene durchführen sollten. Und wenn Sie dieses Argument akzeptieren1, und folgen Sie ihm zu seiner logischen Schlussfolgerung, die Frage, welche Version schneller ist, ist ... strittig2.
1 - Ich behaupte nicht, dass dies beinahe ein Beweis ist.
2 - Es sei denn, Sie gehören zu der kleinen Gemeinschaft von Leuten, die tatsächlich Java JIT-Compiler schreiben ...
Die "sehr berühmte Frage" ist in zweierlei Hinsicht interessant:
Einerseits ist dies ein Beispiel, bei dem die Art der Optimierung, die erforderlich ist, um einen Unterschied zu machen, weit über die Fähigkeiten eines JIT-Compilers hinausgeht.
Andererseits wäre es nicht unbedingt das Richtige, das Array zu sortieren ... nur weil ein sortiertes Array schneller verarbeitet werden kann. Die Kosten für das Sortieren des Arrays könnten (viel) höher sein als die Einsparung.
Wenn Sie entweder & Oder && Verwenden, muss eine Bedingung noch ausgewertet werden. Es ist daher unwahrscheinlich, dass dadurch Verarbeitungszeit gespart wird. Möglicherweise können Sie sogar zusätzliche Ausdrücke hinzufügen, wenn Sie beide Ausdrücke nur auswerten müssen bewerte einen.
Verwenden Sie & Über &&, Um eine Nanosekunde zu speichern. Wenn dies in einigen sehr seltenen Situationen sinnlos ist, haben Sie bereits mehr Zeit damit verbracht, über den Unterschied nachzudenken, als Sie mit & Gespart hätten. ] über &&.
Bearbeiten
Ich wurde neugierig und beschloss, einige Benchmarks zu laufen.
Ich habe diese Klasse gemacht:
public class Main {
static int x = 22, y = 48;
public static void main(String[] args) {
runWithOneAnd(30);
runWithTwoAnds(30);
}
static void runWithOneAnd(int value){
if(value >= x & value <= y){
}
}
static void runWithTwoAnds(int value){
if(value >= x && value <= y){
}
}
}
und führte einige Profilingtests mit NetBeans durch. Ich habe keine print-Anweisungen verwendet, um Verarbeitungszeit zu sparen. Ich weiß nur, dass beide zu true ausgewertet werden.
Erster Test:
Zweiter Test:
Dritter Test:
Wie Sie anhand der Profilerstellungstests sehen können, dauert die Ausführung von nur einem & 2-3-mal länger als bei zwei &&. Dies scheint etwas seltsam zu sein, da ich von nur einem & Eine bessere Leistung erwartet habe.
Ich bin mir nicht 100% sicher warum. In beiden Fällen müssen beide Ausdrücke ausgewertet werden, da beide wahr sind. Ich vermute, dass die JVM hinter den Kulissen einige spezielle Optimierungen vornimmt, um sie zu beschleunigen.
Moral der Geschichte: Konvention ist gut und vorzeitige Optimierung ist schlecht.
Edit 2
Ich habe den Benchmark-Code unter Berücksichtigung der Kommentare von @ SvetlinZarev und einiger weiterer Verbesserungen überarbeitet. Hier ist der geänderte Benchmark-Code:
public class Main {
static int x = 22, y = 48;
public static void main(String[] args) {
oneAndBothTrue();
oneAndOneTrue();
oneAndBothFalse();
twoAndsBothTrue();
twoAndsOneTrue();
twoAndsBothFalse();
System.out.println(b);
}
static void oneAndBothTrue() {
int value = 30;
for (int i = 0; i < 2000; i++) {
if (value >= x & value <= y) {
doSomething();
}
}
}
static void oneAndOneTrue() {
int value = 60;
for (int i = 0; i < 4000; i++) {
if (value >= x & value <= y) {
doSomething();
}
}
}
static void oneAndBothFalse() {
int value = 100;
for (int i = 0; i < 4000; i++) {
if (value >= x & value <= y) {
doSomething();
}
}
}
static void twoAndsBothTrue() {
int value = 30;
for (int i = 0; i < 4000; i++) {
if (value >= x & value <= y) {
doSomething();
}
}
}
static void twoAndsOneTrue() {
int value = 60;
for (int i = 0; i < 4000; i++) {
if (value >= x & value <= y) {
doSomething();
}
}
}
static void twoAndsBothFalse() {
int value = 100;
for (int i = 0; i < 4000; i++) {
if (value >= x & value <= y) {
doSomething();
}
}
}
//I wanted to avoid print statements here as they can
//affect the benchmark results.
static StringBuilder b = new StringBuilder();
static int times = 0;
static void doSomething(){
times++;
b.append("I have run ").append(times).append(" times \n");
}
}
Und hier sind die Leistungstests:
Test 1:
Test 2:
Test 3:
Dies berücksichtigt auch unterschiedliche Werte und unterschiedliche Bedingungen.
Die Verwendung von einem & Dauert länger, wenn beide Bedingungen erfüllt sind, etwa 60% oder 2 Millisekunden länger. Wenn eine oder beide Bedingungen falsch sind, läuft eine & Schneller, aber nur ca. 0,30-0,50 Millisekunden schneller. Daher läuft & In den meisten Fällen schneller als &&, Aber der Leistungsunterschied ist immer noch vernachlässigbar.
Was Sie suchen, ist ungefähr so:
x <= value & value <= y
value - x >= 0 & y - value >= 0
((value - x) | (y - value)) >= 0 // integer bit-or
Interessant, man möchte sich fast den Bytecode anschauen. Aber schwer zu sagen. Ich wünschte, dies wäre eine C-Frage.
Die Art und Weise, wie mir dies erklärt wurde, ist, dass && false zurückgibt, wenn die erste Prüfung in einer Reihe false ist, während & alle Elemente in einer Reihe prüft, unabhängig davon, wie viele false sind. I.E.
if (x> 0 && x <= 10 && x
Läuft schneller als
if (x> 0 & x <= 10 & x
Wenn x größer als 10 ist, werden die restlichen Bedingungen weiterhin durch einfache und-Zeichen überprüft, während doppelte und-Zeichen nach der ersten nicht zutreffenden Bedingung unterbrochen werden.
Ich war auch neugierig auf die Antwort und schrieb dazu den folgenden (einfachen) Test:
private static final int max = 80000;
private static final int size = 100000;
private static final int x = 1500;
private static final int y = 15000;
private Random random;
@Before
public void setUp() {
this.random = new Random();
}
@After
public void tearDown() {
random = null;
}
@Test
public void testSingleOperand() {
int counter = 0;
int[] numbers = new int[size];
for (int j = 0; j < size; j++) {
numbers[j] = random.nextInt(max);
}
long start = System.nanoTime(); //start measuring after an array has been filled
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] >= x & numbers[i] <= y) {
counter++;
}
}
long end = System.nanoTime();
System.out.println("Duration of single operand: " + (end - start));
}
@Test
public void testDoubleOperand() {
int counter = 0;
int[] numbers = new int[size];
for (int j = 0; j < size; j++) {
numbers[j] = random.nextInt(max);
}
long start = System.nanoTime(); //start measuring after an array has been filled
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] >= x & numbers[i] <= y) {
counter++;
}
}
long end = System.nanoTime();
System.out.println("Duration of double operand: " + (end - start));
}
Das Endergebnis ist, dass der Vergleich mit && immer in Bezug auf die Geschwindigkeit gewinnt und ungefähr 1,5/2 Millisekunden schneller ist als &.
EDIT: Wie @SvetlinZarev betonte, maß ich auch die Zeit, die Random brauchte, um eine Ganzzahl zu erhalten. Es wurde geändert, um ein vorab gefülltes Array von Zufallszahlen zu verwenden, wodurch die Dauer des Einzeloperandentests stark schwankte. Die Unterschiede zwischen mehreren Läufen betrugen bis zu 6-7 ms.