wake-up-neo.com

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, wie boolean 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?

69
SusanW

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:

  1. Es lädt value und x auf den Stapel und springt zu L1, wenn value niedriger ist. Ansonsten läuft es in den nächsten Zeilen weiter.
  2. Es lädt value und y auf den Stapel und springt auch zu L1, wenn value größer ist. Ansonsten läuft es in den nächsten Zeilen weiter.
  3. Was zufällig ein _return true_ ist, falls keiner der beiden Sprünge gemacht wurde.
  4. Und dann haben wir die als L1 markierten Zeilen, die ein _return false_ sind.

Die Methode AndNonSC (_&_) erzeugt jedoch drei bedingte Sprünge!

  1. Es lädt value und x auf den Stapel und springt zu L1, wenn value niedriger ist. Da das Ergebnis jetzt gespeichert werden muss, um es mit dem anderen Teil des AND zu vergleichen, muss es entweder "save true" oder "save false" ausführen, was nicht möglich ist beide mit der gleichen Anweisung.
  2. Es lädt value und y auf den Stapel und springt zu L1, wenn value größer ist. Wieder muss es true oder false speichern und das sind zwei verschiedene Zeilen, abhängig vom Vergleichsergebnis.
  3. 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.
  • Mit Intel-Syntax:
    • Der ASM-Code für AndSC ist mit nur 2 bedingten Sprüngen kürzer (ohne den nicht bedingten jmp am Ende). Tatsächlich sind es nur zwei CMP, zwei JL/E und ein XOR/MOV, abhängig vom Ergebnis.
    • Der ASM-Code für AndNonSC ist jetzt länger als der für AndSC! 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.

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ällige values) 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.

72
walen

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

23
SubOptimal

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.

12
Stephen C

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:

The first profiling test

Zweiter Test:

The second profiling test

Dritter Test:

The third profiling 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:

enter image description here

Test 2:

enter image description here

Test 3:

enter image description here

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.

6
Luke Melaia

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.

3
Joop Eggen

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.

0
milkman

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.

0
Oromë