Warum scheint Java beim Einschalten zusammenhängender Ints mit hinzugefügten Fällen schneller zu laufen?

276

Ich arbeite an Java-Code, der stark optimiert werden muss, da er in heißen Funktionen ausgeführt wird, die an vielen Stellen in meiner Hauptprogrammlogik aufgerufen werden. Ein Teil dieses Codes beinhaltet das Multiplizieren von doubleVariablen durch 10Erhöhen auf beliebige nicht negative int exponents. Eine schnelle Art und Weise (edit: aber nicht die schnellsten möglich, siehe Update 2 unten) zu bekommen den multiplizierte Wert ist switchauf dem 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 oben kommentierten Ellipsen zeigen an, dass die case intKonstanten weiterhin um 1 erhöht werden, sodass casedas obige Codefragment tatsächlich 19 Sekunden enthält. Da ich nicht sicher war, ob ich tatsächlich alle Potenzen von 10 in caseAnweisungen 10durch benötigen würde 18, habe ich einige Mikrobenchmarks ausgeführt, in denen die Zeit für die switchAusführung von 10 Millionen Operationen mit dieser Anweisung mit einer switchmit nur cases 0bis verglichen wurde 9(wobei die exponentauf 9 oder weniger begrenzt ist) Vermeiden Sie es, das reduzierte zu brechen switch. Ich habe das ziemlich überraschende (zumindest für mich!) Ergebnis erhalten, dass das längere switchmit mehr caseAussagen tatsächlich schneller lief.

Aus Versehen habe ich versucht, noch mehr cases hinzuzufügen, die nur Dummy-Werte zurückgegeben haben, und festgestellt, dass ich den Switch mit etwa 22 bis 27 deklarierten cases noch schneller ausführen kann (obwohl diese Dummy-Fälle während der Ausführung des Codes nie tatsächlich getroffen werden ). (Wiederum wurden cases in zusammenhängender Weise hinzugefügt, indem die vorherige caseKonstante um erhöht wurde 1.) Diese Unterschiede in der Ausführungszeit sind nicht sehr signifikant: für eine zufällige exponentZwischen- 0und10 die mit Dummy gepolsterte switchAnweisung 10 Millionen Ausführungen in 1,49 Sekunden gegenüber 1,54 Sekunden für die ungepolsterte Version, für eine Gesamteinsparung von 5 ns pro Ausführung. Also nicht die Art von Dingen, die dazu führen, dass man besessen davon ist, aswitchAussage, die sich vom Standpunkt der Optimierung aus lohnt. Aber ich finde es immer noch merkwürdig und kontraintuitiv, dass a switchnicht langsamer wird (oder bestenfalls die konstante O (1) -Zeit beibehält ), wenn mehr cases hinzugefügt werden.

Benchmarking-Ergebnisse wechseln

Dies sind die Ergebnisse, die ich beim Laufen mit verschiedenen Grenzen für die zufällig generierten exponentWerte erhalten habe. Ich habe die Ergebnisse nicht bis 1zum exponentLimit berücksichtigt, aber die allgemeine Form der Kurve bleibt gleich, mit einem Kamm um die 12-17-Fallmarke und einem Tal zwischen 18-28. Alle Tests wurden in JUnitBenchmarks unter Verwendung gemeinsam genutzter Container für die Zufallswerte ausgeführt, um identische Testeingaben sicherzustellen. Ich habe die Tests auch sowohl in der Reihenfolge von der längsten switchbis zur kürzesten Aussage als auch umgekehrt durchgeführt, um zu versuchen, 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 Java switchim Bereich 18to wirklich etwas schneller auszuführen 28 caseals 11bis 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 möglicher exponentWerte hinzugefügt . Ich habe auch eine Option im Testcode nicht zu werfen ein zusätzlicher Exceptionaus default, aber dies scheint nicht um die Ergebnisse zu beeinflussen.

UPDATE 2: Eine ziemlich gute Diskussion zu diesem Thema aus dem Jahr 2009 im xkcd-Forum finden Sie hier: http://forums.xkcd.com/viewtopic.php?f=11&t=33524 . Die Diskussion des OP über die Verwendung Array.binarySearch()brachte mich auf die Idee einer einfachen Array-basierten Implementierung des oben genannten Exponentiationsmusters. Die binäre Suche ist nicht erforderlich, da ich die Einträge in der Liste kenne array. Es scheint ungefähr dreimal schneller zu laufen als die Verwendung switch, offensichtlich auf Kosten eines Teils des Kontrollflusses, der sich switchergibt. Dieser Code wurde auch dem Github-Repo hinzugefügt.

Andrew Bissell
quelle
64
Jetzt haben alle Googler überall genau 22 Fälle in allen switchAussagen, da dies eindeutig die optimalste Lösung ist. : D (Zeigen Sie dies bitte nicht meiner Führung.)
asteri
2
Haben Sie eine einfachere SSCCE? Dieser kompiliert nicht für mich. So schwach ich auch mit der Java-Leistung bin, ich möchte es versuchen.
Mysticial
5
Vielleicht finden Sie den Abschnitt "Switches in the JVM" in meiner Antwort zu stringbasierten Fällen hilfreich. Ich denke, was hier passiert, ist, dass Sie von a lookupswitchzu a wechseln tableswitch. Das Zerlegen Ihres Codes mit javapwürde Ihnen sicher zeigen.
Erickson
2
Ich habe die Abhängigkeitsgläser zum Ordner / lib im Repo hinzugefügt. @Mysticial Sorry, ich habe schon zu viel Zeit damit verbracht, dieses Kaninchenloch hinunterzugehen! Wenn Sie das "Extended AbstractBenchmark" aus den Testklassen entfernen und die "com.carrotsearch" -Importe entfernen, können Sie nur mit der JUnit-Abhängigkeit ausführen, aber das Carrotsearch-Zeug ist ziemlich gut, um einen Teil des Rauschens aus der JIT herauszufiltern und Aufwärmzeiten. Leider weiß ich nicht, wie ich diese JUnit-Tests außerhalb von IntelliJ ausführen soll.
Andrew Bissell
2
@ AndrewBissell Ich habe es geschafft, Ihre Ergebnisse mit einem viel einfacheren Benchmark zu reproduzieren. Die Verzweigung gegen Tabelle für die Leistung mit kleiner oder mittlerer Größe war eine ziemlich offensichtliche Vermutung. Aber ich habe keinen besseren Einblick als jeder andere über das Eintauchen in 30 Fälle ...
Mysticial

Antworten:

228

Wie in der anderen Antwort hervorgehoben , verwendet der für Ihre verschiedenen Tests generierte Bytecode eine Switch-Tabelle (Bytecode-Anweisung tableswitch) , da die Fallwerte zusammenhängend sind (im Gegensatz zu Sparse ).

Sobald die JIT ihren Job startet und den Bytecode in Assembly kompiliert, führt die tableswitchAnweisung jedoch nicht immer zu einem Array von Zeigern: Manchmal wird die Switch-Tabelle in eine lookupswitch(ähnlich einer if/ else ifStruktur) aussehende Tabelle umgewandelt .

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

Der Grund, warum diese magische Zahl von 18 verwendet wird, scheint auf den Standardwert des MinJumpTableSizeJVM-Flags (um Zeile 352 im Code) zurückzuführen zu sein.

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

Wenn die Methode zu lang wird (> 25 Fälle in meinen Tests), werden die Standard-JVM-Einstellungen nicht mehr verwendet - 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::multiplyByPowerOfTen@-1 (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::multiplyByPowerOfTen@72 (line 83)
                                                ;   {runtime_call}
  0x00000000024f0190: int3                      ;*new  ; - javaapplication4.Test1::multiplyByPowerOfTen@72 (line 83)
  0x00000000024f0191: mulsd  xmm0,QWORD PTR [rip+0xffffffffffffffa7]        # 0x00000000024f0140
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@52 (line 62)
                                                ;   {section_word}
  0x00000000024f0199: jmp    0x00000000024f01cb
  0x00000000024f019b: mulsd  xmm0,QWORD PTR [rip+0xffffffffffffff8d]        # 0x00000000024f0130
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@46 (line 60)
                                                ;   {section_word}
  0x00000000024f01a3: jmp    0x00000000024f01cb
  0x00000000024f01a5: cmp    edx,0x5
  0x00000000024f01a8: je     0x00000000024f01b9
  0x00000000024f01aa: cmp    edx,0x5
  0x00000000024f01ad: jg     0x00000000024f0184  ;*tableswitch
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@1 (line 56)
  0x00000000024f01af: mulsd  xmm0,QWORD PTR [rip+0xffffffffffffff81]        # 0x00000000024f0138
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@64 (line 66)
                                                ;   {section_word}
  0x00000000024f01b7: jmp    0x00000000024f01cb
  0x00000000024f01b9: mulsd  xmm0,QWORD PTR [rip+0xffffffffffffff67]        # 0x00000000024f0128
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@70 (line 68)
                                                ;   {section_word}
  0x00000000024f01c1: jmp    0x00000000024f01cb
  0x00000000024f01c3: mulsd  xmm0,QWORD PTR [rip+0xffffffffffffff55]        # 0x00000000024f0120
                                                ;*tableswitch
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@1 (line 56)
                                                ;   {section_word}
  0x00000000024f01cb: add    rsp,0x10
  0x00000000024f01cf: pop    rbp
  0x00000000024f01d0: test   DWORD PTR [rip+0xfffffffffdf3fe2a],eax        # 0x0000000000430000
                                                ;   {poll_return}
  0x00000000024f01d6: ret    

In 18 Fällen sieht die Assembly folgendermaßen aus (beachten Sie das verwendete Zeigerarray, das die Notwendigkeit aller Vergleiche unterdrückt: jmp QWORD PTR [r8+r10*1]Springt direkt zur richtigen Multiplikation) - das ist der wahrscheinliche Grund für die Leistungsverbesserung:

[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::multiplyByPowerOfTen@-1 (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::multiplyByPowerOfTen@1 (line 56)
  0x000000000287fe46: mov    ebp,edx
  0x000000000287fe48: mov    edx,0x31
  0x000000000287fe4d: xchg   ax,ax
  0x000000000287fe4f: call   0x00000000028590a0  ; OopMap{off=52}
                                                ;*new  ; - javaapplication4.Test1::multiplyByPowerOfTen@202 (line 96)
                                                ;   {runtime_call}
  0x000000000287fe54: int3                      ;*new  ; - javaapplication4.Test1::multiplyByPowerOfTen@202 (line 96)
  0x000000000287fe55: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe8b]        # 0x000000000287fce8
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@194 (line 92)
                                                ;   {section_word}
  0x000000000287fe5d: jmp    0x000000000287ff16
  0x000000000287fe62: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe86]        # 0x000000000287fcf0
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@188 (line 90)
                                                ;   {section_word}
  0x000000000287fe6a: jmp    0x000000000287ff16
  0x000000000287fe6f: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe81]        # 0x000000000287fcf8
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@182 (line 88)
                                                ;   {section_word}
  0x000000000287fe77: jmp    0x000000000287ff16
  0x000000000287fe7c: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe7c]        # 0x000000000287fd00
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@176 (line 86)
                                                ;   {section_word}
  0x000000000287fe84: jmp    0x000000000287ff16
  0x000000000287fe89: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe77]        # 0x000000000287fd08
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@170 (line 84)
                                                ;   {section_word}
  0x000000000287fe91: jmp    0x000000000287ff16
  0x000000000287fe96: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe72]        # 0x000000000287fd10
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@164 (line 82)
                                                ;   {section_word}
  0x000000000287fe9e: jmp    0x000000000287ff16
  0x000000000287fea0: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe70]        # 0x000000000287fd18
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@158 (line 80)
                                                ;   {section_word}
  0x000000000287fea8: jmp    0x000000000287ff16
  0x000000000287feaa: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe6e]        # 0x000000000287fd20
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@152 (line 78)
                                                ;   {section_word}
  0x000000000287feb2: jmp    0x000000000287ff16
  0x000000000287feb4: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe24]        # 0x000000000287fce0
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@146 (line 76)
                                                ;   {section_word}
  0x000000000287febc: jmp    0x000000000287ff16
  0x000000000287febe: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe6a]        # 0x000000000287fd30
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@140 (line 74)
                                                ;   {section_word}
  0x000000000287fec6: jmp    0x000000000287ff16
  0x000000000287fec8: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe68]        # 0x000000000287fd38
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@134 (line 72)
                                                ;   {section_word}
  0x000000000287fed0: jmp    0x000000000287ff16
  0x000000000287fed2: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe66]        # 0x000000000287fd40
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@128 (line 70)
                                                ;   {section_word}
  0x000000000287feda: jmp    0x000000000287ff16
  0x000000000287fedc: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe64]        # 0x000000000287fd48
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@122 (line 68)
                                                ;   {section_word}
  0x000000000287fee4: jmp    0x000000000287ff16
  0x000000000287fee6: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe62]        # 0x000000000287fd50
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@116 (line 66)
                                                ;   {section_word}
  0x000000000287feee: jmp    0x000000000287ff16
  0x000000000287fef0: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe60]        # 0x000000000287fd58
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@110 (line 64)
                                                ;   {section_word}
  0x000000000287fef8: jmp    0x000000000287ff16
  0x000000000287fefa: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe5e]        # 0x000000000287fd60
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@104 (line 62)
                                                ;   {section_word}
  0x000000000287ff02: jmp    0x000000000287ff16
  0x000000000287ff04: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe5c]        # 0x000000000287fd68
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@98 (line 60)
                                                ;   {section_word}
  0x000000000287ff0c: jmp    0x000000000287ff16
  0x000000000287ff0e: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe12]        # 0x000000000287fd28
                                                ;*tableswitch
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@1 (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 ähnelt die Baugruppe mit 30 Fällen (unten) 18 Fällen, mit Ausnahme der zusätzlichen Fälle, die movapd xmm0,xmm1in der Mitte des Codes angezeigt werden, wie von @cHao festgestellt. Der wahrscheinlichste Grund für den Leistungsabfall ist jedoch, dass die Methode ebenfalls vorhanden ist lange, um mit den Standard-JVM-Einstellungen eingebunden 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::multiplyByPowerOfTen@-1 (line 56)
  0x000000000252456c: movapd xmm1,xmm0
  0x0000000002524570: cmp    edx,0x1f
  0x0000000002524573: jae    0x0000000002524592  ;*tableswitch
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@1 (line 56)
  0x0000000002524575: movsxd r10,edx
  0x0000000002524578: shl    r10,0x3
  0x000000000252457c: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe3c]        # 0x00000000025243c0
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@364 (line 118)
                                                ;   {section_word}
  0x0000000002524584: movabs r8,0x2524450       ;   {section_word}
  0x000000000252458e: jmp    QWORD PTR [r8+r10*1]  ;*tableswitch
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@1 (line 56)
  0x0000000002524592: mov    ebp,edx
  0x0000000002524594: mov    edx,0x31
  0x0000000002524599: xchg   ax,ax
  0x000000000252459b: call   0x00000000024f90a0  ; OopMap{off=64}
                                                ;*new  ; - javaapplication4.Test1::multiplyByPowerOfTen@370 (line 120)
                                                ;   {runtime_call}
  0x00000000025245a0: int3                      ;*new  ; - javaapplication4.Test1::multiplyByPowerOfTen@370 (line 120)
  0x00000000025245a1: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe27]        # 0x00000000025243d0
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@358 (line 116)
                                                ;   {section_word}
  0x00000000025245a9: jmp    0x0000000002524744
  0x00000000025245ae: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe22]        # 0x00000000025243d8
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@348 (line 114)
                                                ;   {section_word}
  0x00000000025245b6: jmp    0x0000000002524744
  0x00000000025245bb: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe1d]        # 0x00000000025243e0
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@338 (line 112)
                                                ;   {section_word}
  0x00000000025245c3: jmp    0x0000000002524744
  0x00000000025245c8: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe18]        # 0x00000000025243e8
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@328 (line 110)
                                                ;   {section_word}
  0x00000000025245d0: jmp    0x0000000002524744
  0x00000000025245d5: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe13]        # 0x00000000025243f0
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@318 (line 108)
                                                ;   {section_word}
  0x00000000025245dd: jmp    0x0000000002524744
  0x00000000025245e2: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe0e]        # 0x00000000025243f8
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@308 (line 106)
                                                ;   {section_word}
  0x00000000025245ea: jmp    0x0000000002524744
  0x00000000025245ef: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe09]        # 0x0000000002524400
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@298 (line 104)
                                                ;   {section_word}
  0x00000000025245f7: jmp    0x0000000002524744
  0x00000000025245fc: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe04]        # 0x0000000002524408
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@288 (line 102)
                                                ;   {section_word}
  0x0000000002524604: jmp    0x0000000002524744
  0x0000000002524609: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffdff]        # 0x0000000002524410
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@278 (line 100)
                                                ;   {section_word}
  0x0000000002524611: jmp    0x0000000002524744
  0x0000000002524616: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffdfa]        # 0x0000000002524418
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@268 (line 98)
                                                ;   {section_word}
  0x000000000252461e: jmp    0x0000000002524744
  0x0000000002524623: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffd9d]        # 0x00000000025243c8
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@258 (line 96)
                                                ;   {section_word}
  0x000000000252462b: jmp    0x0000000002524744
  0x0000000002524630: movapd xmm0,xmm1
  0x0000000002524634: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffe0c]        # 0x0000000002524448
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@242 (line 92)
                                                ;   {section_word}
  0x000000000252463c: jmp    0x0000000002524744
  0x0000000002524641: movapd xmm0,xmm1
  0x0000000002524645: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffddb]        # 0x0000000002524428
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@236 (line 90)
                                                ;   {section_word}
  0x000000000252464d: jmp    0x0000000002524744
  0x0000000002524652: movapd xmm0,xmm1
  0x0000000002524656: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffdd2]        # 0x0000000002524430
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@230 (line 88)
                                                ;   {section_word}
  0x000000000252465e: jmp    0x0000000002524744
  0x0000000002524663: movapd xmm0,xmm1
  0x0000000002524667: mulsd  xmm0,QWORD PTR [rip+0xfffffffffffffdc9]        # 0x0000000002524438
                                                ;*dmul
                                                ; - javaapplication4.Test1::multiplyByPowerOfTen@224 (line 86)
                                                ;   {section_word}

[etc.]

  0x0000000002524744: add    rsp,0x10
  0x0000000002524748: pop    rbp
  0x0000000002524749: test   DWORD PTR [rip+0xfffffffffde1b8b1],eax        # 0x0000000000340000
                                                ;   {poll_return}
  0x000000000252474f: ret    
Assylien
quelle
7
@ Syb0rg Um ehrlich zu sein, verstehe ich auch die feinen Details nicht ;-)
Assylias
4
+1 für eine gute Antwort! Könnten Sie etwas mit mehr als 30 Fällen zerlegen, um zu vergleichen, wann die Leistung den "Einbruch" in der OP-Tabelle verlässt?
Asteri
4
@ VivinPaliath stackoverflow.com/questions/1503479/…
Assylias
2
@AndrewBissell Ich vermute, dass das unterschiedliche Verhalten entweder auf (i) architekturübergreifenden Leistungstests basiert, die gezeigt haben, dass das Array von Zeigern nur dann effizient ist, wenn die Anzahl der Fälle größer als 18 ist, oder (ii) der Code als Profil erstellt wird Es wird ausgeführt und der Profiler bestimmt, welcher Ansatz zur Laufzeit besser ist. Ich kann die Antwort nicht finden.
Assylias
3
Die 30-Gehäuse-Demontage und die 18-Gehäuse-Demontage sehen größtenteils gleich aus. Die Unterschiede scheinen größtenteils auf ein zusätzliches bisschen zusätzliches Mischen der Register nach etwa dem 11. Fall beschränkt zu sein. Ich kann nicht sagen, warum der JITter das tut. es erscheint unnötig.
CHao
46

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

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

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 der Wechsel ausgeführt wird, wird manipuliert, um ihn in einen Index in den zu konvertieren jump table. In dieser Implementierung ist die in der switch-Anweisung benötigte Zeit viel kürzer als die in einer äquivalenten if-else-if-Anweisungskaskade benötigte Zeit. Auch die in der switch-Anweisung benötigte Zeit ist unabhängig von der Anzahl der Fallbeine in der switch-Anweisung.

Wie in Wikipedia über die switch-Anweisung im Abschnitt "Kompilierung" 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.

Vishal K.
quelle
4
das ist nicht richtig Es ist schneller, unabhängig davon, ob die Fallwerte eng oder breit sind. Es ist O (1) - sollte keine Rolle spielen, wie weit die Fallwerte voneinander entfernt sind.
Aniket Inge
6
@ Aniket: Lesen Sie diesen Artikel von Wikipedia. en.wikipedia.org/wiki/Branch_table
Vishal K
14
@ Aniket: Es ist nicht O (1), wenn der Bereich breit und dünn ist. Es gibt zwei Arten von Schaltern. Wenn der Bereich zu weit verteilt ist, kompiliert Java ihn zu einem "Lookupswitch" und nicht zu einem "Tableswitch". Ersteres erfordert einen Vergleich pro Zweig, bis einer gefunden wurde, während letzterer dies nicht tut.
CHao
4
Wikipedia ist ein anständiger Ort, um Referenzen zu finden, sollte aber nicht als maßgebliche Quelle angesehen werden. Alles, was Sie dort lesen, ist bestenfalls aus zweiter Hand.
CHao
6
@Aniket: Fairerweise ist die Demontage spezifisch für eine bestimmte JVM auf einer bestimmten Plattform. Andere übersetzen es möglicherweise anders. Einige könnten tatsächlich eine Hash-Tabelle für einen Suchschalter verwenden. Es funktioniert immer noch nicht so gut wie ein Tischschalter, aber es könnte zumindest nahe sein. JIT würde nur länger dauern und einen Hashing-Algorithmus auf die Eingabe anwenden. Obwohl der resultierende Assemblycode aufschlussreich sein kann, ist er auch nicht maßgebend, es sei denn, Sie sprechen speziell über Hotspot v1.7. Was auch immer unter Windows x86_64.
CHao
30

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; nur relevante Teile gezeigt:

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 a tableswitch. Im zweiten Fall verwendet der kompilierte Bytecode a lookupswitch.

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

A lookupswitchist 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, in der verwendet wird, lookupswitchist sortiert und ein binärer Suchalgorithmus 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 ist O(1). Der Grund für die geringere Leistung bei Bereichen mit geringer Dichte 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 einen tableswitchverwenden müssen, enthält die Tabelle im Wesentlichen Dummy-Einträge, die auf die defaultOption verweisen . Angenommen, der letzte Eintrag in SwitchTest10.javawar 21anstelle von 10, 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 mit Dummy-Einträgen zwischen den Lücken, die auf das Verzweigungsziel der defaultAnweisung zeigen. Auch wenn es keine gibt default, enthält es Einträge, die auf die Anweisung nach dem Schalterblock verweisen . Ich habe einige grundlegende Tests durchgeführt und festgestellt, dass, wenn die Lücke zwischen dem letzten Index und dem vorherigen ( 9) größer als ist 35, a lookupswitchanstelle von a verwendet wird tableswitch.

Das Verhalten der switchAnweisung ist in der Java Virtual Machine Specification (§3.10) definiert :

Wenn die Fälle des Schalters spärlich sind, wird die Tabellendarstellung des Tabellenschalterbefehls räumlich ineffizient. Stattdessen kann der Lookupswitch-Befehl verwendet werden. Der Befehl lookupswitch paart int-Schlüssel (die Werte der Fallbezeichnungen) mit Zielversätzen in einer Tabelle. Wenn ein Lookupswitch-Befehl 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 zugehörigen Zielversatz fortgesetzt. Wenn kein Schlüssel übereinstimmt, wird die Ausführung am Standardziel fortgesetzt. [...]

Vivin Paliath
quelle
1
Ich habe aus der Frage verstanden, dass die Zahlen immer zusammenhängend sind, aber der Bereich mehr oder weniger lang ist - dh in einem Beispiel gehen die Fälle von 0 bis 5, während sie in einem anderen Beispiel von 0 bis 30 gehen - und keines der Beispiele verwendet spärliche Werte
Assylias
@assylias Hmm, interessant. Ich glaube, ich habe die Frage falsch verstanden. Lassen Sie mich noch etwas experimentieren. Sie sagen also, dass der Compiler selbst bei einem zusammenhängenden Bereich von 0 bis 30 ein lookupswitch?
Vivin Paliath
@ VivinPaliath: Ja, in meinen Tests sind die Fallkonstanten immer zusammenhängend, also teste ich im Grunde die Schalter auf [0, 1], [0, 1, 2], [0, 1, 2, 3] ... usw.
Andrew Bissell
@VivinPaliath Nein, der Bytecode verwendet immer einen Tabellenschalter. Der JIT-Compiler scheint den Tabellenschalter jedoch nicht auf die gleiche Weise zu kompilieren, je nachdem, wie viele Elemente er enthält.
Assylias
6
@ VivinPaliath Ich hätte die Frage mit Sicherheit klarer formulieren können. Ich bin ziemlich überfordert, wenn es darum geht, Antworten zu bewerten, die dieses einfache Bytecode- und Assembly-Zeug betreffen. Es scheint mir immer noch so, als ob die Unterscheidung zwischen Tableswitch und Lookupswitch hier tatsächlich wichtig ist, und Ihre ist die einzige Antwort, die diese Begriffe bisher verwendet (obwohl die anderen wahrscheinlich dasselbe Konzept mit unterschiedlicher Terminologie darlegen). Außerdem mag ich auch den JVM Spec-Link.
Andrew Bissell
19

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 verwendet deutlich weniger IC (Anweisungscache) und wird immer inline gesetzt. Das Array befindet sich im L1-Datencache, wenn der Code heiß ist. Die Nachschlagetabelle ist fast immer ein Gewinn. (insbesondere auf Mikrobenchmarks: D)

Bearbeiten: Wenn Sie möchten, dass die Methode Hot-Inlined ist, sollten Sie die nicht schnellen Pfade throw new ParseException()als so kurz wie möglich betrachten oder sie in eine separate statische Methode verschieben (wodurch sie so kurz wie möglich sind). Das ist throw new ParseException("Unhandled power of ten " + power, 0);eine schwache Idee, da sie 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 Infos und ein realer Fall mit ArrayList

bestsss
quelle