JVM的LookupSwitch和TableSwitch之间的区别？

Question

我很难理解Java字节码中的LookUpSwitch和TableSwitch。

如果我很好理解，LookUpSwitch和TableSwitch都对应于switchJava源代码的声明？为什么一个JAVA语句会生成2个不同的字节码？

每个Jasmin文档：

• 查找开关
• tableswi
• instructions

Answer 1

区别在于

• lookupswitch 使用 带有键和标签的表
• tableswitch 使用 仅带有标签的表 。

当执行 tableswitch ，堆栈顶部的int值被直接用作索引到表抢跳转目的地和立即执行跳转。整个查找+跳转过程是一个 O（1）操作
，这意味着它 运行 起来很快。

当执行 lookupswitch时 ，将堆栈顶部的int值与表中的键进行比较，直到找到匹配项为止，然后使用该键旁边的跳转目标执行跳转。由于
必须 始终对lookupswitch 表 进行排序， 以便每个X <Y的keyX <keyY，因此整个lookup + jump过程是
O（log n）操作 因为该键将使用二进制搜索算法进行搜索（不必将int值与所有可能的键进行比较以找到匹配项或确定所有键都不匹配）。O（log
n）比O（1）慢一些，但是它仍然可以，因为许多众所周知的算法都是O（log n），通常被认为是快速算法。甚至O（n）或O（n * log
n）仍被认为是一种相当不错的算法（慢速/差速算法具有O（n ^ 2），O（n ^ 3），甚至更差）。

编译器根据switch语句的 紧凑程度 来决定使用哪条指令，例如

switch (inputValue) {
  case 1:  // ...
  case 2:  // ...
  case 3:  // ...
  default: // ...
}

上面的开关非常紧凑，没有数字“孔”。编译器将创建一个表开关，如下所示：

 tableswitch 1 3
    OneLabel
    TwoLabel
    ThreeLabel
  default: DefaultLabel

Jasmin页面上的伪代码很好地解释了这一点：

int val = pop();                // pop an int from the stack
if (val < low || val > high) {  // if its less than <low> or greater than <high>,
    pc += default;              // branch to default 
} else {                        // otherwise
    pc += table[val - low];     // branch to entry in table
}

关于这样的表开关如何工作，这段代码非常清楚。val是inputValue，low将为1（开关中的最小大小写值），high将为3（开关中的最大大小写值）。

即使有一些孔，开关也可以紧凑，例如

switch (inputValue) {
  case 1:  // ...
  case 3:  // ...
  case 4:  // ...
  case 5:  // ...
  default: // ...
}

上面的开关“几乎紧凑”，只有一个孔。编译器可以生成以下指令：

 tableswitch 1 6
    OneLabel
    FakeTwoLabel
    ThreeLabel
    FourLabel
    FiveLabel
  default: DefaultLabel

  ; <...code left out...>

  FakeTwoLabel:
  DefaultLabel:
    ; default code

正如你所看到的，编译器必须添加一个 假的情况下2
，FakeTwoLabel。由于2不是开关的实际值，因此FakeTwoLabel实际上是一个标签，它可以精确地更改代码流的默认大小写所在的位置，因为值2实际上应该执行默认大小写。

因此，对于编译器创建表开关而言，开关并不一定要完全紧凑，但它至少应该非常接近紧凑性。现在考虑以下开关：

switch (inputValue) {
  case 1:    // ...
  case 10:   // ...
  case 100:  // ...
  case 1000: // ...
  default:   // ...
}

这个开关远不紧凑，它的 孔比值 多一百倍。有人将其称为备用开关。编译器必须生成 近千个伪造案例，
才能将此开关表示为tableswitch。结果将是一个巨大的表，极大地炸毁了类文件的大小。这是不切实际的。相反，它将生成一个lookupswitch：

lookupswitch
    1       : Label1
    10      : Label10
    100     : Label100
    1000    : Label1000
    default : DefaultLabel

该表只有5个条目，而不是上千个条目。该表具有4个实数值，O（log 4）为2（此处的日志以2
BTW的底数而不是10的底数为对数，因为计算机使用二进制数进行操作）。这意味着VM最多需要两次比较才能找到inputValue的标签或得出结论，即该值不在表中，因此必须执行默认值。即使表中有100个条目，VM最多也要进行7次比较才能找到正确的标签或决定跳转到默认标签（而7次比较远少于100次比较，您不觉得吗？）。

因此，这两个指令是可互换的，或者两个指令的原因具有历史原因是胡说八道。有两种针对两种不同情况的指令，一种用于具有紧凑值的开关（用于最大速度），另一种用于具有备用值的开关（不是最大速度，但仍具有良好的速度和非常紧凑的表表示形式，无论所有数字孔如何）。