用ChatGPT解决这个技术问题 Extra ChatGPT

为什么 Java switch on contiguous ints 似乎在添加案例时运行得更快？

我正在处理一些需要高度优化的 Java 代码，因为它将在热函数中运行，这些函数在我的主程序逻辑中的许多点被调用。此代码的一部分涉及将 double 变量乘以 10，得到任意非负 int exponent。获得相乘值的一种快速方法（编辑：但不是最快的方法，请参见下面的更新 2）是在 exponent 上的 switch： 

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，因此在上面的代码片段中确实有 19 个 case。由于我不确定在 case 语句 10 到 18 中是否真的需要 10 的所有幂，因此我运行了一些微基准测试，比较了使用此 switch 语句与 { 7} 只有 case 到 0 到 9（exponent 限制为 9 或更少，以避免破坏缩减的 switch）。我得到了一个相当令人惊讶的结果（至少对我来说！），越长的 switch 和更多的 case 语句实际上运行得更快。

在云雀中，我尝试添加更多只返回虚拟值的 case，并发现我可以使用大约 22-27 个声明的 case 让开关运行得更快（即使这些虚拟案例实际上从未在代码运行时点击）。 （同样，通过将先前的 case 常数增加 1 以连续方式添加 case。）这些执行时间差异不是很显着：对于 0 和 10 之间的随机 exponent ，虚拟填充 switch 语句在 1.49 秒内完成 1000 万次执行，而未填充版本为 1.54 秒，每次执行总共节省 5ns。因此，从优化的角度来看，不是那种让痴迷于填充 switch 语句的事情值得付出努力。但我仍然觉得奇怪和违反直觉的是，switch 不会随着更多 case 的执行而变得更慢（或者可能充其量保持恒定的 O(1) 时间）执行添加到它。

https://i.stack.imgur.com/kbnan.png

这些是我通过对随机生成的 exponent 值进行各种限制运行而获得的结果。对于 exponent 限制，我没有将结果一直包括到 1，但曲线的一般形状保持不变，在 12-17 案例标记周围有一个脊，在 18- 之间有一个谷28.所有测试都在 JUnitBenchmarks 中运行，使用共享容器获取随机值，以确保相同的测试输入。我还按照从最长的 switch 语句到最短的顺序运行了测试，反之亦然，以尝试消除与排序相关的测试问题的可能性。如果有人想尝试重现这些结果，我已经将我的测试代码放在了 github repo 上。

那么，这里发生了什么？我的架构或微基准构建的一些变幻莫测？或者，Java switch 在 18 到 28 case 范围内的执行速度真的比在 11 到 17 范围内要快一点吗？

github test repo "switch-experiment"

更新：我对基准测试库进行了相当多的清理，并在 /results 中添加了一个文本文件，其中包含更广泛的可能 exponent 值的一些输出。我还在测试代码中添加了一个选项，不从 default 抛出 Exception，但这似乎不会影响结果。

更新 2： 早在 2009 年就在此处的 xkcd 论坛上找到了一些关于此问题的很好的讨论：http://forums.xkcd.com/viewtopic.php?f=11&t=33524。 OP 对使用 Array.binarySearch() 的讨论让我想到了上面求幂模式的简单的基于数组的实现。因为我知道 array 中的条目是什么，所以不需要二进制搜索。它的运行速度似乎比使用 switch 快大约 3 倍，显然是以牺牲 switch 提供的一些控制流为代价的。该代码也已添加到 github 存储库中。

现在，世界各地的所有 Google 员工在所有 switch 语句中都恰好有 22 个案例，因为这显然是最优化的解决方案。 ：D（请不要向我的领导展示这个。）
你有更简单的SSCCE吗？这个不适合我。尽管我的 Java 性能很弱，但我想试一试。
您可能会发现有关基于字符串的案例的第 "Switches in the JVM" in my answer 部分很有帮助。我认为这里发生的事情是您正在从 lookupswitch 切换到 tableswitch。用 javap 反汇编你的代码肯定会告诉你。
我将依赖项 jar 添加到 repo 中的 /lib 文件夹中。 @Mysticial对不起，我已经花了太多时间去这个兔子洞了！如果你从测试类中去掉“extends AbstractBenchmark”并去掉“com.carrotsearch”导入，你可以只使用JUnit依赖项运行，但是carrotsearch的东西对于过滤掉来自JIT的一些噪音非常好和热身期。不幸的是，我不知道如何在 IntelliJ 之外运行这些 JUnit 测试。
@AndrewBissell 我设法用一个更简单的基准来重现您的结果。小型与中型性能的分支与表是一个有点明显的猜测。但对于 30 起案件的下跌，我没有比其他人更好的洞察力……

C
Community

正如 by the other answer 所指出的，因为 case 值是连续的（而不是稀疏的），为您的各种测试生成的字节码使用一个开关表（字节码指令 tableswitch）。

然而，一旦 JIT 开始其工作并将字节码编译成汇编，tableswitch 指令并不总是产生一个指针数组：有时开关表会转换为看起来像 lookupswitch 的东西（类似于 {3 }/else if 结构）。

反编译由 JIT（热点 JDK 1.7）生成的程序集表明，当有 17 个或更少的情况时，它使用连续的 if/else if/else，当有超过 18 个时使用指针数组（更有效）。

使用 18 这个幻数的原因似乎归结为 MinJumpTableSize JVM 标志的默认值（代码中的第 352 行附近）。

我在热点编译器列表和 it seems to be a legacy of past testing 上提出了这个问题。请注意，此默认值 has been removed in JDK 8 在 more benchmarking was performed 之后。

最后，当方法变得太长时（在我的测试中 > 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 个案例，除了出现在代码中间的附加 movapd xmm0,xmm1 as spotted by @cHao - 但是性能下降的最可能原因是该方法是太长而无法与默认 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
@syb0rg 老实说，我也不了解细节;-)
+1 很好的答案！你能用 30 多个案例拆开一些东西来比较性能何时退出 OP 图表中的“下降”吗？
@VivinPaliath stackoverflow.com/questions/1503479/…
@AndrewBissell我的猜测是，不同的行为基于（i）跨架构性能测试，这些测试表明指针数组仅在案例数量大于18时才有效，或者（ii）代码被描述为它运行并且分析器确定在运行时哪种方法更好。我找不到答案。
30 箱拆装和 18 箱拆机看起来大同小异。在大约第 11 种情况之后，差异似乎主要限于额外的寄存器改组。不能说为什么 JITter 会这样做；似乎没有必要。
V
Vishal K

如果将 case 值放在一个狭窄的范围内，则 Switch - case 会更快。 

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

因为，在这种情况下，编译器可以避免对 switch 语句中的每个 case 分支执行比较。编译器制作一个跳转表，其中包含要在不同腿上采取的动作的地址。操作正在执行切换的值以将其转换为 jump table 中的索引。在此实现中，switch 语句所用的时间远少于等效 if-else-if 语句级联所用的时间。此外，switch 语句所用的时间与 switch 语句中的 case 分支数无关。

如 wikipedia 关于编译部分中的 switch statement 所述。

如果输入值的范围可以识别为“小”并且只有几个间隙，则某些包含优化器的编译器实际上可能将 switch 语句实现为分支表或索引函数指针数组，而不是冗长的一系列条件指令。这允许 switch 语句立即确定要执行的分支，而无需通过比较列表。

这是不正确的。无论 case 值的范围是窄还是宽，它都会更快。它是 O(1) - 大小写值之间的差异无关紧要。
@Aniket：阅读这篇维基百科的文章。 en.wikipedia.org/wiki/Branch_table
@Aniket：如果范围宽且稀疏，则不是 O(1)。有两种开关，如果范围过于分散，Java 会将其编译为“lookupswitch”而不是“tableswitch”。前者需要对每个分支进行比较，直到找到，而后者不需要。
维基百科是查找参考资料的好地方，但不应被视为权威来源。你在那里读到的任何东西充其量都是二手信息。
@Aniket：平心而论，反汇编特定于特定平台上的给定JVM。其他人可能会以不同的方式翻译它。有些人实际上可能使用哈希表进行查找切换。它的性能仍然不如 tableswitch，但至少可以接近。 JIT 只需要更长的时间，并且涉及对输入应用散列算法。因此，尽管生成的汇编代码可能具有启发性，但它也不具有权威性，除非您专门讨论的是 Windows x86_64 上的 Hotspot v1.7.whatever。
V
Vivin Paliath

答案在于字节码：

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。在第二种情况下，编译后的字节码使用 lookupswitch。

在 tableswitch 中，堆栈顶部的整数值用于索引到表中，以找到分支/跳转目标。然后立即执行此跳转/分支。因此，这是一个 O(1) 操作。

lookupswitch 更复杂。在这种情况下，需要将整数值与表中的所有键进行比较，直到找到正确的键。找到键后，将使用分支/跳转目标（该键映射到的）进行跳转。 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，它也会包含指向 switch 块之后指令的条目。我做了一些基本的测试，我发现如果最后一个索引和前一个索引（9）之间的差距大于35，它使用lookupswitch而不是tableswitch。

switch 语句的行为在 Java Virtual Machine Specification (§3.10) 中定义：

在 switch 的情况很少的情况下，tableswitch 指令的表表示在空间方面变得低效。可以改为使用 lookupswitch 指令。 lookupswitch 指令将 int 键（案例标签的值）与表中的目标偏移量配对。当执行lookupswitch 指令时，将switch 表达式的值与表中的键进行比较。如果其中一个键与表达式的值匹配，则在关联的目标偏移处继续执行。如果没有键匹配，则在默认目标处继续执行。 [...]

我从这个问题中了解到，数字总是连续的，但范围或多或少是长的——即在一个例子中，案例从 0 到 5，而在另一个例子中，它们从 0 到 30——并且没有一个例子使用稀疏值
@assylias 嗯，很有趣。我想我误解了这个问题。让我再做一些实验。所以您是说即使 连续 范围是 0-30，编译器也会使用 lookupswitch？
@VivinPaliath：是的，在我的测试中，大小写常量总是连续的，所以我基本上是在测试 [0, 1]、[0, 1, 2]、[0, 1, 2, 3] ... 等上的开关
@VivinPaliath 不，字节码总是使用 tableswitch - 但是 JIT 编译器似乎不会编译 tableswitch 以根据它包含的项目数量以相同的方式组装。
@VivinPaliath 我可以肯定地更清楚地表达这个问题。在评估涉及这种低级字节码和汇编内容的答案时，我有点不知所措。在我看来，tableswitch/lookupswitch 的区别在这里仍然很重要，而你的答案是迄今为止唯一使用这些术语的答案（尽管其他人可能用不同的术语提出了相同的概念）。另外，我也喜欢 JVM Spec 链接。
b
bestsss

由于问题已经得到解答（或多或少），这里有一些提示。利用 

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); 是一个弱想法 b/c 它消耗了大量可以解释的代码的内联预算 - 字符串连接在字节码中非常冗长。更多信息和real case w/ ArrayList

S
SMUsamaShah

基于 javac source，您可以使用 tableswitch 的方式编写 switch。

我们可以使用 javac 源中的计算来计算您的第二个示例的成本。 

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

这里 tableswitch 的成本 (234) 比 lookupswitch (123) 高，因此 lookupswitch 将被选为这个 switch 语句的操作码。

这些“成本”数字当然只是在代码大小和最佳与最坏情况下权衡 cmp/分支指令链的启发式方法。即使在间接分支预测器较弱的 CPU 上，重复选择相同的情况也可以很好地预测间接分支，并且表指针将在数据缓存中保持热状态，因此查找表在这个特定的微基准上表现非常好。
哦，这只是在javac控制字节码的选择。如其他答案中所述，JIT 将有自己的启发式方法来了解如何在本机机器代码中实现 tableswitch。

关注公众号,不定期副业成功案例分享
关注公众号

不定期副业成功案例分享

想领先一步获取最新的外包任务吗？

立即订阅

HuntsBot(狩猎机器人)，一站式外包任务、远程工作、产品创意分享与订阅平台，支持钉钉、飞书、企业微信、邮箱、Telegram机器人订阅。平台会以及时、稳定、可靠的技术把外包任务需求、远程工作机会、产品创意等推送给每一位订阅的用户。

简体中文 English

平台

支持

联系我们

在使用过程中有任何问题或建议，可以通过以下方式联系我们：

微信公众号: 火星来客

Email: huntsbot@xinbeitime.com

Copyright© 2022-2023 www.huntsbot.com 浙ICP备2022000860号-4 All Rights Reserved.