282

メインプログラムロジックの多くのポイントで呼び出されるホット関数で実行されるため、高度に最適化する必要のあるJavaコードに取り組んでいます。doubleこのコードの一部には、変数10を任意の非負int exponentのsに上げて乗算することが含まれます。乗算された値を取得するための1つの高速な方法（編集：ただし、可能な限り最速ではありません。以下の更新2を参照）はswitch、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);
   }
}

上記のコメント付き省略記号は、case int定数が1ずつ増加し続けることを示しているためcase、上記のコードスニペットには実際には19秒あります。caseステートメント10スルーで実際に10の累乗がすべて必要かどうかわからなかったため、このステートメント18で1,000万回の操作を完了する時間と、sスルーのみのa （9以下に制限）を比較するマイクロベンチマークを実行しました。簡素化されたものを壊さないでください）。かなり驚くべき結果が得られました（少なくとも私にとっては！）。ステートメントが多いほど長くなるほど、実際には速く実行されます。switchswitchcase09exponentswitchswitchcase

ひばりで、ダミー値を返すだけのsをさらに追加してcaseみたところ、22〜27個の宣言されたsを使用すると、スイッチをさらに高速に実行できることがわかりましたcase（コードの実行中にこれらのダミーケースが実際にヒットすることはありませんが） ）。（ここでも、 sは前の定数をcaseインクリメントすることにより、連続して追加されました。）これらの実行時間の違いはそれほど重要ではありません。との間のランダムな場合、ダミーの埋め込みステートメントは1.49秒で1,000万回の実行を終了しますが、埋め込みなしの場合は1.54秒です。バージョン、実行ごとに5nsの総節約。だから、パディングアウトに執着するようなものではありませんcase1exponent010switchswitch最適化の観点から努力する価値のあるステートメント。しかし、 sが追加されても 、実行switchが遅くならない（または、せいぜい一定のO（1）時間を維持する）ことが不思議で直感に反していることに気づきました。case

ベンチマーク結果を切り替える

これらは、ランダムに生成されたexponent値にさまざまな制限を加えて実行した結果です。1結果を限界まで含めませんでしたexponentが、曲線の一般的な形状は同じままで、12-17のケースマークの周りに隆起があり、18-28の間に谷があります。すべてのテストは、ランダムな値に共有コンテナーを使用してJUnitBenchmarksで実行され、同一のテスト入力を保証しました。また、注文に関連するテストの問題の可能性を排除するために、ステートメントが長いものswitchから短いものへ、またはその逆の順序でテストを実行しました。誰かがこれらの結果を再現しようとする場合は、テストコードをgithubリポジトリに配置しました。

それで、ここで何が起こっているのですか？私のアーキテクチャまたはマイクロベンチマーク構造のいくつかの気まぐれ？または、Javaは、最大から範囲までの範囲よりも、範囲内switchで実行する方が実際に少し高速ですか？1828 case1117

githubテストリポジトリ「switch-experiment」

更新：ベンチマークライブラリをかなりクリーンアップし、/ resultsにテキストファイルを追加して、可能なexponent値のより広い範囲にわたる出力を追加しました。Exceptionまた、テストコードにfromをスローしないオプションを追加しましたdefaultが、これは結果に影響を与えないようです。

更新2： 2009年にxkcdフォーラムでこの問題に関するかなり良い議論を見つけました：http ：//forums.xkcd.com/viewtopic.php？f = 11＆t=33524 。OPの使用に関する議論はArray.binarySearch()、上記のべき乗パターンの単純な配列ベースの実装のアイデアを私に与えました。のエントリが何であるかを知っているので、バイナリ検索の必要はありませんarray。を使用するよりも約3倍速く実行されるように見えますがswitch、明らかに、余裕のある制御フローの一部が犠牲になっていswitchます。そのコードはgithubリポジトリにも追加されています。

4

5 に答える 5

236

他の回答で指摘されているように、ケース値は（スパースではなく）連続しているため、さまざまなテスト用に生成されたバイトコードはスイッチテーブル（バイトコード命令tableswitch）を使用します。

ただし、JITがジョブを開始し、バイトコードをアセンブリにコンパイルすると、命令によって常にポインタの配列が生成されるとは限りません。スイッチテーブルが（ /構造体に似た）tableswitchものに変換される場合があります。lookupswitchifelse if

JIT（hotspot JDK 1.7）によって生成されたアセンブリを逆コンパイルすると、17個以下の場合はif / elseの連続を使用し、18個を超える場合（より効率的）のポインターの配列を使用することがわかります。

このマジックナンバー18が使用される理由は、MinJumpTableSizeJVMフラグのデフォルト値（コードの352行目あたり）に帰着するようです。

ホットスポットコンパイラリストで問題を提起しましたが、これは過去のテストの遺産のようです。このデフォルト値は、さらにベンチマークが実行された後、JDK8で削除されていることに注意してください。

最後に、メソッドが長くなりすぎると（私のテストでは> 25ケース）、デフォルトのJVM設定でインライン化されなくなります。これがその時点でのパフォーマンス低下の最も可能性の高い原因です。

5つのケースでは、逆コンパイルされたコードは次のようになります（cmp / je / jg / jmp命令、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

18の場合、アセンブリは次のようになります（使用されるポインターの配列に注意して、すべての比較の必要性を抑制します。jmp QWORD PTR [r8+r10*1]正しい乗算に直接ジャンプします）-これがパフォーマンス向上の理由である可能性があります。

[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

そして最後に、30ケース（以下）のアセンブリは18ケースに似ていますが、@ cHaoによって検出されたようmovapd xmm0,xmm1に、コードの中央に表示される追加を除いて-ただし、パフォーマンスが低下する最も可能性の高い理由は、メソッドもデフォルトのJVM設定とインライン化するのが待ち遠しい：

[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
于 2013-03-25T17:59:57.843 に答える
46

Switch-case値が狭い範囲に配置されている場合、caseはより高速です。

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

なぜなら、この場合、コンパイラはswitchステートメントのすべてのcaseレッグの比較を回避できるからです。コンパイラは、さまざまなレッグで実行されるアクションのアドレスを含むジャンプテーブルを作成します。切り替えが実行されている値は、へのインデックスに変換するために操作されjump tableます。この実装では、switchステートメントにかかる時間は、同等のif-else-ifステートメントカスケードにかかる時間よりもはるかに短くなります。また、switchステートメントにかかる時間は、switchステートメントのcaseレッグの数とは無関係です。

ウィキペディアでコンパイルセクションのswitchステートメントについて述べられているように。

入力値の範囲が識別可能に「小さく」、ギャップがわずかしかない場合、オプティマイザーを組み込んだ一部のコンパイラーは、長い一連の条件付き命令ではなく、実際にswitchステートメントを分岐テーブルまたはインデックス付き関数ポインターの配列として実装する場合があります。これにより、switchステートメントは、比較のリストを調べなくても、実行するブランチを即座に決定できます。

于 2013-03-25T17:34:32.183 に答える
31

答えはバイトコードにあります：

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");
        }
    }       
}

対応するバイトコード。示されている関連部品のみ：

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");
        }
    }       
}

対応するバイトコード。ここでも、関連する部分のみが示されています。

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 }

最初のケースでは、範囲が狭く、コンパイルされたバイトコードは。を使用しtableswitchます。2番目のケースでは、コンパイルされたバイトコードはを使用しlookupswitchます。

ではtableswitch、スタックの最上位にある整数値を使用してテーブルにインデックスを付け、分岐/ジャンプターゲットを見つけます。このジャンプ/ブランチはすぐに実行されます。したがって、これはO(1)操作です。

Alookupswitchはもっと複雑です。この場合、正しいキーが見つかるまで、整数値をテーブル内のすべてのキーと比較する必要があります。キーが見つかった後、（このキーがマップされている）ブランチ/ジャンプターゲットがジャンプに使用されます。で使用されるテーブルlookupswitchは並べ替えられ、バイナリ検索アルゴリズムを使用して正しいキーを見つけることができます。二分探索のパフォーマンスはであり、ジャンプがまだであるため、O(log n)プロセス全体もです。したがって、スパース範囲の場合にパフォーマンスが低下する理由は、テーブルに直接インデックスを付けることができないため、最初に正しいキーを検索する必要があるためです。O(log n)O(1)

スパース値があり、tableswitchを使用するだけの場合、テーブルには基本的にdefaultオプションを指すダミーエントリが含まれます。たとえば、の最後のエントリがでSwitchTest10.javaは21なくだったとすると10、次のようになります。

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 }

したがって、コンパイラは基本的に、ギャップ間のダミーエントリを含むこの巨大なテーブルを作成し、命令の分岐ターゲットを指しdefaultます。がない場合でも、スイッチブロックの後defaultの命令を指すエントリが含まれます。いくつかの基本的なテストを行いましたが、最後のインデックスと前のインデックス（ ）の間のギャップがより大きい場合、の代わりにを使用することがわかりました。935lookupswitchtableswitch

switchステートメントの動作は、Java仮想マシン仕様（§3.10）で定義されています。

スイッチのケースがまばらである場合、tableswitch命令のテーブル表現はスペースの点で非効率になります。代わりにlookupswitch命令を使用できます。lookupswitch命令は、intキー（ケースラベルの値）とテーブル内のターゲットオフセットをペアにします。lookupswitch命令が実行されると、スイッチの式の値がテーブル内のキーと比較されます。キーの1つが式の値と一致する場合、実行は関連するターゲットオフセットで続行されます。一致するキーがない場合、実行はデフォルトのターゲットで続行されます。[...]

于 2013-03-25T18:14:55.777 に答える
19

質問はすでに（多かれ少なかれ）答えられているので、ここにいくつかのヒントがあります。使用する

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;
}

そのコードは大幅に少ないIC（命令キャッシュ）を使用し、常にインライン化されます。コードがホットな場合、配列はL1データキャッシュにあります。ルックアップテーブルは、ほとんどの場合、勝利です。（特にマイクロベンチマーク：D）

編集：メソッドをホットインライン化する場合は、非高速パスthrow new ParseException()を最小に短くするか、別の静的メソッドに移動する（したがって、最小に短くする）ようにします。これはthrow new ParseException("Unhandled power of ten " + power, 0);、解釈できるコードのインライン化予算の多くを消費するという弱い考えです。文字列の連結は、バイトコードでは非常に冗長です。詳細とArrayListを使用した実際のケース

于 2013-03-27T21:58:52.090 に答える
0

javacソースに基づいて、を使用する方法でスイッチを記述できますtableswitch。

javacソースからの計算を使用して、2番目の例のコストを計算できます。

lo = 0
hi = 220
nlabels = 24

table_space_cost = 4 + hi - lo + 1
table_time_cost = 3
lookup_space_cost = 3 + 2 * nlabels
lookup_time_cost = nlabels

table_cost = table_space_cost + 3 * table_time_cost // 234
lookup_cost = lookup_space_cost + 3 * lookup_time_cos // 123

ここで、テーブルスイッチのコストはルックアップスイッチ（123）よりも高い（234）ため、ルックアップスイッチがこのswitchステートメントのオペコードとして選択されます。

于 2021-04-20T15:56:12.217 に答える