java - JVM的LookupSwitch和TableSwitch之间的区别？

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

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

每个Jasmin文档:

LookupSwitch

tableswitch

both

最佳答案

区别在于

lookupswitch使用一个带有键和标签的表

tableswitch使用一个仅带有标签的表。

当执行表开关时，堆栈顶部的int值直接用作表的索引，以获取跳转目标并立即执行跳转。整个查找和跳转过程是一个 O(1)操作，这意味着它运行起来很快。
当执行 lookupswitch 时，将堆栈顶部的int值与表中的键进行比较，直到找到匹配项为止，然后使用该键旁边的跳转目标执行跳转。由于必须始终将looktswitch表排序为，以便每个X O(log n)操作，因为将使用二进制搜索算法来搜索 key (不必将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

如您所见，编译器必须为FakeTwoLabel 2添加一个假包。由于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次比较，您不觉得吗？)。
因此，这两个指令是可互换的，或者两个指令的原因具有历史原因是胡说八道。有两种针对两种不同情况的指令，一种用于具有紧凑值的开关(用于最大速度)，另一种用于具有稀疏值的开关(不是最大速度，但仍具有良好的速度和非常紧凑的表表示方式，而与数字孔无关)。