wake-up-neo.com

Warum scheinen Java switch on contiguous ints mit hinzugefügten Fällen schneller zu laufen?

Ich arbeite an etwas Java Code, der stark optimiert werden muss, da er in Hot-Funktionen ausgeführt wird, die an vielen Stellen in meiner Hauptprogrammlogik aufgerufen werden. Ein Teil dieses Codes beinhaltet das Multiplizieren von double Variablen werden durch 10 Angehoben, um beliebige nicht negative intexponent s zu erhalten. Ein schneller Weg (Bearbeiten: aber nicht der schnellste, siehe Update 2 unten) Der multiplizierte Wert lautet auf switch für exponent:

double multiplyByPowerOfTen(final double d, final int exponent) {
   switch (exponent) {
      case 0:
         return d;
      case 1:
         return d*10;
      case 2:
         return d*100;
      // ... same pattern
      case 9:
         return d*1000000000;
      case 10:
         return d*10000000000L;
      // ... same pattern with long literals
      case 18:
         return d*1000000000000000000L;
      default:
         throw new ParseException("Unhandled power of ten " + power, 0);
   }
}

Die kommentierten Auslassungspunkte oben zeigen an, dass die Konstanten caseint weiterhin um 1 inkrementiert werden, sodass der obige Codeausschnitt wirklich 19 case enthält. Da ich nicht sicher war, ob ich tatsächlich alle Potenzen von 10 in case - Anweisungen 10 Bis 18 Benötigen würde, führte ich einige Mikrobenchmarks durch, um die Zeit für 10 Millionen Operationen zu vergleichen mit dieser switch - Anweisung im Vergleich zu einer switch mit nur case s 0 bis 9 (mit der exponent - Beschränkung auf 9 oder weniger, um das Reduzieren zu vermeiden switch). Ich habe das ziemlich überraschende (zumindest für mich!) Ergebnis, dass die längeren switch mit mehr case Anweisungen tatsächlich schneller liefen.

Aus Versehen habe ich versucht, noch mehr case hinzuzufügen, die gerade Dummy-Werte zurückgaben, und festgestellt, dass ich den Switch mit etwa 22-27 deklarierten case noch schneller laufen lassen konnte (obwohl Diese Dummy-Fälle werden niemals getroffen, während der Code ausgeführt wird. (Wiederum wurden case s zusammenhängend hinzugefügt, indem die vorherige case - Konstante um 1 Inkrementiert wurde.) Diese Unterschiede in der Ausführungszeit sind nicht sehr signifikant: für ein zufälliges exponent zwischen 0 Und 10 Beendet die mit Dummy-Pads versehene switch - Anweisung 10 Millionen Ausführungen in 1,49 Sekunden gegenüber 1,54 Sekunden in der ungepolsterten Version 5ns pro Ausführung. Also nicht die Art von Dingen, die es unter Optimierungsgesichtspunkten lohnt, eine switch -Anweisung auszublenden, wenn man davon besessen ist. Aber ich finde es immer noch merkwürdig und kontraintuitiv, dass ein switch nicht langsamer wird (oder bestenfalls konstant bleibt O (1) Zeit), um so mehr auszuführen case s werden hinzugefügt.

switch benchmarking results

Dies sind die Ergebnisse, die ich durch Laufen mit verschiedenen Grenzwerten für die zufällig generierten exponent Werte erhalten habe. Ich habe die Ergebnisse nicht bis auf 1 Für das Limit exponent eingeschlossen, aber die allgemeine Form der Kurve bleibt gleich, mit einem Grat um die 12-17-Fallmarke. und ein Tal zwischen 18-28. Alle Tests wurden in JUnitBenchmarks mit gemeinsam genutzten Containern für die Zufallswerte ausgeführt, um identische Testeingaben sicherzustellen. Ich habe die Tests auch in der Reihenfolge der längsten switch - Anweisung bis zur kürzesten und umgekehrt ausgeführt, um die Möglichkeit von auftragsbezogenen Testproblemen auszuschließen. Ich habe meinen Testcode auf einem Github-Repo abgelegt, wenn jemand versuchen möchte, diese Ergebnisse zu reproduzieren.

Also, was ist hier los? Einige Unklarheiten meiner Architektur oder meiner Micro-Benchmark-Konstruktion? Oder ist die Ausführung von Java switch im Bereich 18 Bis 28case wirklich etwas schneller als sie ist? von 11 bis zu 17?

github test repo "switch-experiment"

UPDATE: Ich habe die Benchmarking-Bibliothek ziemlich aufgeräumt und eine Textdatei in/results mit einigen Ausgaben über einen größeren Bereich von möglichen exponent Werte. Ich habe auch eine Option im Testcode hinzugefügt, die verhindert, dass Exception von default geworfen wird, aber dies scheint die Ergebnisse nicht zu beeinflussen.

UPDATE 2: Wir haben 2009 im xkcd-Forum eine ziemlich gute Diskussion über dieses Problem gefunden: http: //forums.xkcd .com/viewtopic.php? f = 11 & t = 33524 . Die Diskussion des OP über die Verwendung von Array.binarySearch() brachte mich auf die Idee einer einfachen Array-basierten Implementierung des obigen Exponentiationsmusters. Die binäre Suche ist nicht erforderlich, da ich die Einträge in array kenne. Es scheint ungefähr dreimal schneller zu laufen als mit switch, offensichtlich auf Kosten eines Teils des Kontrollflusses, den switch bietet. Dieser Code wurde auch dem Github-Repo hinzugefügt.

273
Andrew Bissell

Wie bereits erwähnt durch die andere Antwort , verwendet der generierte Bytecode für Ihre verschiedenen Tests eine Schaltertabelle (Bytecode-Anweisung tableswitch), da die Fallwerte zusammenhängend sind (im Gegensatz zu spärlich).

Sobald das JIT seinen Job startet und den Bytecode in Assembly kompiliert, führt die Anweisung tableswitch jedoch nicht immer zu einem Array von Zeigern: Manchmal wird die Schaltertabelle in eine Tabelle umgewandelt, die wie eine lookupswitch aussieht. (ähnlich einem if/else if Struktur).

Das Dekompilieren der vom JIT (Hotspot JDK 1.7) generierten Assembly zeigt, dass eine Abfolge von if/else verwendet wird, wenn es 17 Fälle oder weniger gibt, und ein Array von Zeigern, wenn es mehr als 18 gibt (effizienter).

Der Grund, warum diese magische Zahl von 18 verwendet wird, scheint auf den Standardwert des JVM-Flags MinJumpTableSize (um Zeile 352 im Code) zurückzugehen.

Ich habe das Problem auf der Hotspot-Compiler-Liste angesprochen und es scheint ein Erbe vergangener Tests zu sein . Beachten Sie, dass dieser Standardwert wurde in JDK 8 entfernt nach es wurde mehr Benchmarking durchgeführt .

Wenn die Methode zu lang wird (> 25 Fälle in meinen Tests), wird sie schließlich nicht mehr mit den Standard-JVM-Einstellungen eingebunden - dies ist die wahrscheinlichste Ursache für den Leistungsabfall zu diesem Zeitpunkt.


In 5 Fällen sieht der dekompilierte Code folgendermaßen aus (beachten Sie die Anweisungen cmp/je/jg/jmp, die Assembly für if/goto):

[Verified Entry Point]
  # {method} 'multiplyByPowerOfTen' '(DI)D' in 'javaapplication4/Test1'
  # parm0:    xmm0:xmm0   = double
  # parm1:    rdx       = int
  #           [sp+0x20]  (sp of caller)
  0x00000000024f0160: mov    DWORD PTR [rsp-0x6000],eax
                                                ;   {no_reloc}
  0x00000000024f0167: Push   rbp
  0x00000000024f0168: sub    rsp,0x10           ;*synchronization entry
                                                ; - javaapplication4.Test1::[email protected] (line 56)
  0x00000000024f016c: cmp    edx,0x3
  0x00000000024f016f: je     0x00000000024f01c3
  0x00000000024f0171: cmp    edx,0x3
  0x00000000024f0174: jg     0x00000000024f01a5
  0x00000000024f0176: cmp    edx,0x1
  0x00000000024f0179: je     0x00000000024f019b
  0x00000000024f017b: cmp    edx,0x1
  0x00000000024f017e: jg     0x00000000024f0191
  0x00000000024f0180: test   edx,edx
  0x00000000024f0182: je     0x00000000024f01cb
  0x00000000024f0184: mov    ebp,edx
  0x00000000024f0186: mov    edx,0x17
  0x00000000024f018b: call   0x00000000024c90a0  ; OopMap{off=48}
                                                ;*new  ; - javaapplication4.Test1::[email protected] (line 83)
                                                ;   {runtime_call}
  0x00000000024f0190: int3                      ;*new  ; - javaapplication4.Test1::[email protected] (line 83)
  0x00000000024f0191: mulsd  xmm0,QWORD PTR [rip+0xffffffffffffffa7]        # 0x00000000024f0140
                                                ;*dmul
                                                ; - javaapplication4.Test1::[email protected] (line 62)
                                                ;   {section_Word}
  0x00000000024f0199: jmp    0x00000000024f01cb
  0x00000000024f019b: mulsd  xmm0,QWORD PTR [rip+0xffffffffffffff8d]        # 0x00000000024f0130
                                                ;*dmul
                                                ; - javaapplication4.Test1::[email protected] (line 60)
                                                ;   {section_Word}
  0x00000000024f01a3: jmp    0x00000000024f01cb
  0x00000000024f01a5: cmp    edx,0x5
  0x00000000024f01a8: je     0x00000000024f01b9
  0x00000000024f01aa: cmp    edx,0x5
  0x00000000024f01ad: jg     0x00000000024f0184  ;*tableswitch
                                                ; - javaapplication4.Test1::[email protected] (line 56)
  0x00000000024f01af: mulsd  xmm0,QWORD PTR [rip+0xffffffffffffff81]        # 0x00000000024f0138
                                                ;*dmul
                                                ; - javaapplication4.Test1::[email protected] (line 66)
                                                ;   {section_Word}
  0x00000000024f01b7: jmp    0x00000000024f01cb
  0x00000000024f01b9: mulsd  xmm0,QWORD PTR [rip+0xffffffffffffff67]        # 0x00000000024f0128
                                                ;*dmul
                                                ; - javaapplication4.Test1::[email protected] (line 68)
                                                ;   {section_Word}
  0x00000000024f01c1: jmp    0x00000000024f01cb
  0x00000000024f01c3: mulsd  xmm0,QWORD PTR [rip+0xffffffffffffff55]        # 0x00000000024f0120
                                                ;*tableswitch
                                                ; - javaapplication4.Test1::[email protected] (line 56)
                                                ;   {section_Word}
  0x00000000024f01cb: add    rsp,0x10
  0x00000000024f01cf: pop    rbp
  0x00000000024f01d0: test   DWORD PTR [rip+0xfffffffffdf3fe2a],eax        # 0x0000000000430000
                                                ;   {poll_return}
  0x00000000024f01d6: ret    

Mit 18 Fällen sieht die Assembly wie folgt aus (beachten Sie das Array der verwendeten Zeiger und unterdrücken Sie die Notwendigkeit aller Vergleiche: jmp QWORD PTR [r8+r10*1] springt direkt zur richtigen Multiplikation) - das ist der wahrscheinliche Grund für die Leistungssteigerung:

[Verified Entry Point]
  # {method} 'multiplyByPowerOfTen' '(DI)D' in 'javaapplication4/Test1'
  # parm0:    xmm0:xmm0   = double
  # parm1:    rdx       = int
  #           [sp+0x20]  (sp of caller)
  0x000000000287fe20: mov    DWORD PTR [rsp-0x6000],eax
                                                ;   {no_reloc}
  0x000000000287fe27: Push   rbp
  0x000000000287fe28: sub    rsp,0x10           ;*synchronization entry
                                                ; - javaapplication4.Test1::[email protected] (line 56)
  0x000000000287fe2c: cmp    edx,0x13
  0x000000000287fe2f: jae    0x000000000287fe46
  0x000000000287fe31: movsxd r10,edx
  0x000000000287fe34: shl    r10,0x3
  0x000000000287fe38: movabs r8,0x287fd70       ;   {section_Word}
  0x000000000287fe42: jmp    QWORD PTR [r8+r10*1]  ;*tableswitch
                                                ; - javaapplication4.Test1::[email protected] (line 56)
  0x000000000287fe46: mov    ebp,edx
  0x000000000287fe48: mov    edx,0x31
  0x000000000287fe4d: xchg   ax,ax
  0x000000000287fe4f: call   0x00000000028590a0  ; OopMap{off=52}
                                                ;*new  ; - javaapplication4.Test1::[email protected] (line 96)
                                                ;   {runtime_call}
  0x000000000287fe54: int3                      ;*new  ; - javaapplication4.Test1::[email protected] (line 96)
  0x000000000287fe55: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe8b]        # 0x000000000287fce8
                                                ;*dmul
                                                ; - javaapplication4.Test1::[email protected] (line 92)
                                                ;   {section_Word}
  0x000000000287fe5d: jmp    0x000000000287ff16
  0x000000000287fe62: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe86]        # 0x000000000287fcf0
                                                ;*dmul
                                                ; - javaapplication4.Test1::[email protected] (line 90)
                                                ;   {section_Word}
  0x000000000287fe6a: jmp    0x000000000287ff16
  0x000000000287fe6f: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe81]        # 0x000000000287fcf8
                                                ;*dmul
                                                ; - javaapplication4.Test1::[email protected] (line 88)
                                                ;   {section_Word}
  0x000000000287fe77: jmp    0x000000000287ff16
  0x000000000287fe7c: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe7c]        # 0x000000000287fd00
                                                ;*dmul
                                                ; - javaapplication4.Test1::[email protected] (line 86)
                                                ;   {section_Word}
  0x000000000287fe84: jmp    0x000000000287ff16
  0x000000000287fe89: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe77]        # 0x000000000287fd08
                                                ;*dmul
                                                ; - javaapplication4.Test1::[email protected] (line 84)
                                                ;   {section_Word}
  0x000000000287fe91: jmp    0x000000000287ff16
  0x000000000287fe96: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe72]        # 0x000000000287fd10
                                                ;*dmul
                                                ; - javaapplication4.Test1::[email protected] (line 82)
                                                ;   {section_Word}
  0x000000000287fe9e: jmp    0x000000000287ff16
  0x000000000287fea0: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe70]        # 0x000000000287fd18
                                                ;*dmul
                                                ; - javaapplication4.Test1::[email protected] (line 80)
                                                ;   {section_Word}
  0x000000000287fea8: jmp    0x000000000287ff16
  0x000000000287feaa: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe6e]        # 0x000000000287fd20
                                                ;*dmul
                                                ; - javaapplication4.Test1::[email protected] (line 78)
                                                ;   {section_Word}
  0x000000000287feb2: jmp    0x000000000287ff16
  0x000000000287feb4: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe24]        # 0x000000000287fce0
                                                ;*dmul
                                                ; - javaapplication4.Test1::[email protected] (line 76)
                                                ;   {section_Word}
  0x000000000287febc: jmp    0x000000000287ff16
  0x000000000287febe: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe6a]        # 0x000000000287fd30
                                                ;*dmul
                                                ; - javaapplication4.Test1::[email protected] (line 74)
                                                ;   {section_Word}
  0x000000000287fec6: jmp    0x000000000287ff16
  0x000000000287fec8: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe68]        # 0x000000000287fd38
                                                ;*dmul
                                                ; - javaapplication4.Test1::[email protected] (line 72)
                                                ;   {section_Word}
  0x000000000287fed0: jmp    0x000000000287ff16
  0x000000000287fed2: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe66]        # 0x000000000287fd40
                                                ;*dmul
                                                ; - javaapplication4.Test1::[email protected] (line 70)
                                                ;   {section_Word}
  0x000000000287feda: jmp    0x000000000287ff16
  0x000000000287fedc: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe64]        # 0x000000000287fd48
                                                ;*dmul
                                                ; - javaapplication4.Test1::[email protected] (line 68)
                                                ;   {section_Word}
  0x000000000287fee4: jmp    0x000000000287ff16
  0x000000000287fee6: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe62]        # 0x000000000287fd50
                                                ;*dmul
                                                ; - javaapplication4.Test1::[email protected] (line 66)
                                                ;   {section_Word}
  0x000000000287feee: jmp    0x000000000287ff16
  0x000000000287fef0: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe60]        # 0x000000000287fd58
                                                ;*dmul
                                                ; - javaapplication4.Test1::[email protected] (line 64)
                                                ;   {section_Word}
  0x000000000287fef8: jmp    0x000000000287ff16
  0x000000000287fefa: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe5e]        # 0x000000000287fd60
                                                ;*dmul
                                                ; - javaapplication4.Test1::[email protected] (line 62)
                                                ;   {section_Word}
  0x000000000287ff02: jmp    0x000000000287ff16
  0x000000000287ff04: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe5c]        # 0x000000000287fd68
                                                ;*dmul
                                                ; - javaapplication4.Test1::[email protected] (line 60)
                                                ;   {section_Word}
  0x000000000287ff0c: jmp    0x000000000287ff16
  0x000000000287ff0e: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe12]        # 0x000000000287fd28
                                                ;*tableswitch
                                                ; - javaapplication4.Test1::[email protected] (line 56)
                                                ;   {section_Word}
  0x000000000287ff16: add    rsp,0x10
  0x000000000287ff1a: pop    rbp
  0x000000000287ff1b: test   DWORD PTR [rip+0xfffffffffd9b00df],eax        # 0x0000000000230000
                                                ;   {poll_return}
  0x000000000287ff21: ret    

Und schließlich sieht die Versammlung mit 30 Fällen (unten) ähnlich aus wie 18 Fälle, mit Ausnahme der zusätzlichen movapd xmm0,xmm1, das in der Mitte des Codes angezeigt wird, wie von @cHao erkannt - Der wahrscheinlichste Grund für den Leistungsabfall ist jedoch, dass die Methode zu lang ist, um mit den Standardeinstellungen für JVMs inliniert zu werden:

[Verified Entry Point]
  # {method} 'multiplyByPowerOfTen' '(DI)D' in 'javaapplication4/Test1'
  # parm0:    xmm0:xmm0   = double
  # parm1:    rdx       = int
  #           [sp+0x20]  (sp of caller)
  0x0000000002524560: mov    DWORD PTR [rsp-0x6000],eax
                                                ;   {no_reloc}
  0x0000000002524567: Push   rbp
  0x0000000002524568: sub    rsp,0x10           ;*synchronization entry
                                                ; - javaapplication4.Test1::[email protected] (line 56)
  0x000000000252456c: movapd xmm1,xmm0
  0x0000000002524570: cmp    edx,0x1f
  0x0000000002524573: jae    0x0000000002524592  ;*tableswitch
                                                ; - javaapplication4.Test1::[email protected] (line 56)
  0x0000000002524575: movsxd r10,edx
  0x0000000002524578: shl    r10,0x3
  0x000000000252457c: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe3c]        # 0x00000000025243c0
                                                ;*dmul
                                                ; - javaapplication4.Test1::[email protected] (line 118)
                                                ;   {section_Word}
  0x0000000002524584: movabs r8,0x2524450       ;   {section_Word}
  0x000000000252458e: jmp    QWORD PTR [r8+r10*1]  ;*tableswitch
                                                ; - javaapplication4.Test1::[email protected] (line 56)
  0x0000000002524592: mov    ebp,edx
  0x0000000002524594: mov    edx,0x31
  0x0000000002524599: xchg   ax,ax
  0x000000000252459b: call   0x00000000024f90a0  ; OopMap{off=64}
                                                ;*new  ; - javaapplication4.Test1::[email protected] (line 120)
                                                ;   {runtime_call}
  0x00000000025245a0: int3                      ;*new  ; - javaapplication4.Test1::[email protected] (line 120)
  0x00000000025245a1: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe27]        # 0x00000000025243d0
                                                ;*dmul
                                                ; - javaapplication4.Test1::[email protected] (line 116)
                                                ;   {section_Word}
  0x00000000025245a9: jmp    0x0000000002524744
  0x00000000025245ae: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe22]        # 0x00000000025243d8
                                                ;*dmul
                                                ; - javaapplication4.Test1::[email protected] (line 114)
                                                ;   {section_Word}
  0x00000000025245b6: jmp    0x0000000002524744
  0x00000000025245bb: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe1d]        # 0x00000000025243e0
                                                ;*dmul
                                                ; - javaapplication4.Test1::[email protected] (line 112)
                                                ;   {section_Word}
  0x00000000025245c3: jmp    0x0000000002524744
  0x00000000025245c8: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe18]        # 0x00000000025243e8
                                                ;*dmul
                                                ; - javaapplication4.Test1::[email protected] (line 110)
                                                ;   {section_Word}
  0x00000000025245d0: jmp    0x0000000002524744
  0x00000000025245d5: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe13]        # 0x00000000025243f0
                                                ;*dmul
                                                ; - javaapplication4.Test1::[email protected] (line 108)
                                                ;   {section_Word}
  0x00000000025245dd: jmp    0x0000000002524744
  0x00000000025245e2: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe0e]        # 0x00000000025243f8
                                                ;*dmul
                                                ; - javaapplication4.Test1::[email protected] (line 106)
                                                ;   {section_Word}
  0x00000000025245ea: jmp    0x0000000002524744
  0x00000000025245ef: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe09]        # 0x0000000002524400
                                                ;*dmul
                                                ; - javaapplication4.Test1::[email protected] (line 104)
                                                ;   {section_Word}
  0x00000000025245f7: jmp    0x0000000002524744
  0x00000000025245fc: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe04]        # 0x0000000002524408
                                                ;*dmul
                                                ; - javaapplication4.Test1::[email protected] (line 102)
                                                ;   {section_Word}
  0x0000000002524604: jmp    0x0000000002524744
  0x0000000002524609: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffdff]        # 0x0000000002524410
                                                ;*dmul
                                                ; - javaapplication4.Test1::[email protected] (line 100)
                                                ;   {section_Word}
  0x0000000002524611: jmp    0x0000000002524744
  0x0000000002524616: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffdfa]        # 0x0000000002524418
                                                ;*dmul
                                                ; - javaapplication4.Test1::[email protected] (line 98)
                                                ;   {section_Word}
  0x000000000252461e: jmp    0x0000000002524744
  0x0000000002524623: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffd9d]        # 0x00000000025243c8
                                                ;*dmul
                                                ; - javaapplication4.Test1::[email protected] (line 96)
                                                ;   {section_Word}
  0x000000000252462b: jmp    0x0000000002524744
  0x0000000002524630: movapd xmm0,xmm1
  0x0000000002524634: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe0c]        # 0x0000000002524448
                                                ;*dmul
                                                ; - javaapplication4.Test1::[email protected] (line 92)
                                                ;   {section_Word}
  0x000000000252463c: jmp    0x0000000002524744
  0x0000000002524641: movapd xmm0,xmm1
  0x0000000002524645: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffddb]        # 0x0000000002524428
                                                ;*dmul
                                                ; - javaapplication4.Test1::[email protected] (line 90)
                                                ;   {section_Word}
  0x000000000252464d: jmp    0x0000000002524744
  0x0000000002524652: movapd xmm0,xmm1
  0x0000000002524656: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffdd2]        # 0x0000000002524430
                                                ;*dmul
                                                ; - javaapplication4.Test1::[email protected] (line 88)
                                                ;   {section_Word}
  0x000000000252465e: jmp    0x0000000002524744
  0x0000000002524663: movapd xmm0,xmm1
  0x0000000002524667: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffdc9]        # 0x0000000002524438
                                                ;*dmul
                                                ; - javaapplication4.Test1::[email protected] (line 86)
                                                ;   {section_Word}

[etc.]

  0x0000000002524744: add    rsp,0x10
  0x0000000002524748: pop    rbp
  0x0000000002524749: test   DWORD PTR [rip+0xfffffffffde1b8b1],eax        # 0x0000000000340000
                                                ;   {poll_return}
  0x000000000252474f: ret    
227
assylias

Switch-Case ist schneller, wenn die Case-Werte in einem engen Bereich liegen.

case 1:
case 2:
case 3:
..
..
case n:

Denn in diesem Fall kann der Compiler vermeiden, einen Vergleich für jeden Fallabschnitt in der switch-Anweisung durchzuführen. Der Compiler erstellt eine Sprungtabelle, die Adressen der Aktionen enthält, die auf verschiedenen Beinen ausgeführt werden sollen. Der Wert, für den die Umschaltung ausgeführt wird, wird manipuliert, um ihn in einen Index in jump table umzuwandeln. In dieser Implementierung ist die Zeit, die in der switch-Anweisung benötigt wird, viel kürzer als die Zeit, die in einer äquivalenten if-else-if-Anweisungskaskade benötigt wird. Auch die in der switch-Anweisung benötigte Zeit ist unabhängig von der Anzahl der Fallzweige in der switch-Anweisung.

Wie in Wikipedia über switch statement im Abschnitt Compilation angegeben.

Wenn der Bereich der Eingabewerte identifizierbar "klein" ist und nur wenige Lücken aufweist, implementieren einige Compiler, die einen Optimierer enthalten, die switch-Anweisung möglicherweise tatsächlich als Verzweigungstabelle oder als Array indizierter Funktionszeiger anstelle einer langen Reihe von bedingten Anweisungen. Auf diese Weise kann die switch-Anweisung sofort bestimmen, welcher Zweig ausgeführt werden soll, ohne eine Liste von Vergleichen durchlaufen zu müssen.

46
Vishal K

Die Antwort liegt im Bytecode:

SwitchTest10.Java

public class SwitchTest10 {

    public static void main(String[] args) {
        int n = 0;

        switcher(n);
    }

    public static void switcher(int n) {
        switch(n) {
            case 0: System.out.println(0);
                    break;

            case 1: System.out.println(1);
                    break;

            case 2: System.out.println(2);
                    break;

            case 3: System.out.println(3);
                    break;

            case 4: System.out.println(4);
                    break;

            case 5: System.out.println(5);
                    break;

            case 6: System.out.println(6);
                    break;

            case 7: System.out.println(7);
                    break;

            case 8: System.out.println(8);
                    break;

            case 9: System.out.println(9);
                    break;

            case 10: System.out.println(10);
                    break;

            default: System.out.println("test");
        }
    }       
}

Entsprechender Bytecode; Es werden nur relevante Teile angezeigt:

public static void switcher(int);
  Code:
   0:   iload_0
   1:   tableswitch{ //0 to 10
        0: 60;
        1: 70;
        2: 80;
        3: 90;
        4: 100;
        5: 110;
        6: 120;
        7: 131;
        8: 142;
        9: 153;
        10: 164;
        default: 175 }

SwitchTest22.Java:

public class SwitchTest22 {

    public static void main(String[] args) {
        int n = 0;

        switcher(n);
    }

    public static void switcher(int n) {
        switch(n) {
            case 0: System.out.println(0);
                    break;

            case 1: System.out.println(1);
                    break;

            case 2: System.out.println(2);
                    break;

            case 3: System.out.println(3);
                    break;

            case 4: System.out.println(4);
                    break;

            case 5: System.out.println(5);
                    break;

            case 6: System.out.println(6);
                    break;

            case 7: System.out.println(7);
                    break;

            case 8: System.out.println(8);
                    break;

            case 9: System.out.println(9);
                    break;

            case 100: System.out.println(10);
                    break;

            case 110: System.out.println(10);
                    break;
            case 120: System.out.println(10);
                    break;
            case 130: System.out.println(10);
                    break;
            case 140: System.out.println(10);
                    break;
            case 150: System.out.println(10);
                    break;
            case 160: System.out.println(10);
                    break;
            case 170: System.out.println(10);
                    break;
            case 180: System.out.println(10);
                    break;
            case 190: System.out.println(10);
                    break;
            case 200: System.out.println(10);
                    break;
            case 210: System.out.println(10);
                    break;

            case 220: System.out.println(10);
                    break;

            default: System.out.println("test");
        }
    }       
}

Entsprechender Bytecode; Auch hier werden nur relevante Teile angezeigt:

public static void switcher(int);
  Code:
   0:   iload_0
   1:   lookupswitch{ //23
        0: 196;
        1: 206;
        2: 216;
        3: 226;
        4: 236;
        5: 246;
        6: 256;
        7: 267;
        8: 278;
        9: 289;
        100: 300;
        110: 311;
        120: 322;
        130: 333;
        140: 344;
        150: 355;
        160: 366;
        170: 377;
        180: 388;
        190: 399;
        200: 410;
        210: 421;
        220: 432;
        default: 443 }

Im ersten Fall verwendet der kompilierte Bytecode bei engen Bereichen ein tableswitch. Im zweiten Fall verwendet der kompilierte Bytecode ein lookupswitch.

In tableswitch wird der ganzzahlige Wert oben im Stapel verwendet, um in die Tabelle zu indexieren und das Verzweigungs-/Sprungziel zu finden. Dieser Sprung/diese Verzweigung wird dann sofort ausgeführt. Daher ist dies eine O(1) -Operation.

Ein lookupswitch ist komplizierter. In diesem Fall muss der ganzzahlige Wert mit allen Schlüsseln in der Tabelle verglichen werden, bis der richtige Schlüssel gefunden wurde. Nachdem der Schlüssel gefunden wurde, wird das Verzweigungs-/Sprungziel (dem dieser Schlüssel zugeordnet ist) für den Sprung verwendet. Die Tabelle, die in lookupswitch verwendet wird, wird sortiert und ein Binärsuchalgorithmus kann verwendet werden, um den richtigen Schlüssel zu finden. Leistung für eine binäre Suche ist O(log n), und der gesamte Prozess ist auch O(log n), weil der Sprung noch O(1) ist. Der Grund dafür, dass die Leistung bei dünnen Bereichen geringer ist, ist, dass zuerst der richtige Schlüssel gesucht werden muss, da Sie nicht direkt in die Tabelle indizieren können.

Wenn es spärliche Werte gibt und Sie nur ein tableswitch verwenden müssen, enthält die Tabelle im Wesentlichen Dummy-Einträge, die auf die Option default verweisen. Angenommen, der letzte Eintrag in SwitchTest10.Java War 21 Anstelle von 10, Dann erhalten Sie:

public static void switcher(int);
  Code:
   0:   iload_0
   1:   tableswitch{ //0 to 21
        0: 104;
        1: 114;
        2: 124;
        3: 134;
        4: 144;
        5: 154;
        6: 164;
        7: 175;
        8: 186;
        9: 197;
        10: 219;
        11: 219;
        12: 219;
        13: 219;
        14: 219;
        15: 219;
        16: 219;
        17: 219;
        18: 219;
        19: 219;
        20: 219;
        21: 208;
        default: 219 }

Der Compiler erstellt also im Grunde genommen diese riesige Tabelle, die Dummy-Einträge zwischen den Lücken enthält und auf das Verzweigungsziel der Anweisung default verweist. Auch wenn es kein default gibt, enthält es Einträge, die auf die Anweisung after the switch block verweisen. Ich habe einige grundlegende Tests durchgeführt und festgestellt, dass, wenn die Lücke zwischen dem letzten und dem vorherigen Index (9) Größer als 35 Ist, statt ein lookupswitch verwendet wird a tableswitch.

Das Verhalten der switch -Anweisung ist in Java Virtual Machine Specification (§3.10) definiert:

Wenn die Fälle des Schalters spärlich sind, wird die Tabellendarstellung des Tabellenschaltbefehls in Bezug auf den Platz ineffizient. Stattdessen kann der Lookupswitch-Befehl verwendet werden. Der Lookupswitch-Befehl paart int-Schlüssel (die Werte der Fallbezeichnungen) mit Ziel-Offsets in einer Tabelle. Wenn eine Lookupswitch-Anweisung ausgeführt wird, wird der Wert des Ausdrucks des Schalters mit den Schlüsseln in der Tabelle verglichen. Wenn einer der Schlüssel mit dem Wert des Ausdrucks übereinstimmt, wird die Ausführung mit dem zugeordneten Zieloffset fortgesetzt. Wenn kein Schlüssel übereinstimmt, wird die Ausführung am Standardziel fortgesetzt. [...]

30
Vivin Paliath

Da die Frage bereits beantwortet ist (mehr oder weniger), hier ein Tipp. Verwenden

private static final double[] mul={1d, 10d...};
static double multiplyByPowerOfTen(final double d, final int exponent) {
      if (exponent<0 || exponent>=mul.length) throw new ParseException();//or just leave the IOOBE be
      return mul[exponent]*d;
}

Dieser Code benötigt deutlich weniger IC (Instruction Cache) und wird immer inline geschrieben. Das Array befindet sich im L1-Datencache, wenn der Code heiß ist. Die Nachschlagetabelle ist fast immer ein Gewinn. (va auf Mikrobenchmarks: D)

Bearbeiten: Wenn Sie möchten, dass die Methode als Hot-In-Zeile angezeigt wird, müssen Sie die nicht schnellen Pfade wie throw new ParseException() mindestens so kurz wie möglich halten. Das ist throw new ParseException("Unhandled power of ten " + power, 0); ist eine schwache Idee, da es einen Großteil des Inlining-Budgets für Code verbraucht, der nur interpretiert werden kann - die Verkettung von Zeichenfolgen ist im Bytecode ziemlich ausführlich. Weitere Informationen und ein realer Fall mit ArrayList

19
bestsss