java JVM 的 LookupSwitch 和 TableSwitch 的区别？

Difference between JVM's LookupSwitch and TableSwitch?

提问by zell

I have some difficulty to understand LookUpSwitch and TableSwitch in Java bytecode.

我在理解 Java 字节码中的 LookUpSwitch 和 TableSwitch 时有些困难。

If I understand well, both LookUpSwitch and TableSwitch correspond to the switchstatement of Java source? Why one JAVA statement generates 2 different bytecodes?

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

Jasmin documentation of each:

每个 Jasmin 文档：

• LookupSwitch
• tableswitch
• both

• 查找开关
• 表开关
• 两个都

回答by Mecki

The difference is that

不同之处在于

• lookupswitchuses a table with keys and labels
• tableswitchuses a table with labels only.

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

When performing a tableswitch, the int value on top of stack is directly used as an index into the table to grab the jump destination and perform the jump immediately. The whole lookup+jump process is an O(1) operation, that means it's blazing fast.

执行tableswitch 时，堆栈顶部的 int 值直接用作表中的索引，以获取跳转目标并立即执行跳转。整个查找+跳转过程是一个O(1) 操作，这意味着它非常快。

When performing a lookupswitch, the int value on top of the stack is compared against the keys in the table until a match is found and then the jump destination next to this key is used to perform the jump. Since a lookupswitch table always must be sortedso that keyX < keyY for every X < Y, the whole lookup+jump process is a O(log n) operationas the key will be searched using a binary search algorithm (it's not necessary to compare the int value against all possible keys to find a match or to determine that none of the keys matches). O(log n) is somewhat slower than O(1), yet it is still okay since many well known algorithms are O(log n) and these are usually considered fast; even O(n) or O(n * log n) is still considered a pretty good algorithm (slow/bad algorithms have O(n^2), O(n^3), or even worse).

执行lookupswitch 时，将堆栈顶部的 int 值与表中的键进行比较，直到找到匹配项，然后使用此键旁边的跳转目标来执行跳转。由于一个lookupswitch表总是必须排序，使得keyX < keyY for each X < Y，整个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)，甚至更糟）。

The decision which instruction to use is made by the compiler based upon the fact how compactthe switch statement is, e.g.

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

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

The switch above is perfectly compact, it has no numeric "holes". The compiler will create a tableswitch like this:

上面的开关非常紧凑，没有数字“孔”。编译器会像这样创建一个 tableswitch：

 tableswitch 1 3
    OneLabel
    TwoLabel
    ThreeLabel
  default: DefaultLabel

The pseudo code from the Jasmin page explains this pretty well:

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
}

This code is pretty clear on how such a tableswitch works. valis inputValue, lowwould be 1 (the lowest case value in the switch) and highwould be 3 (the highest case value in the switch).

这段代码非常清楚地说明了这种 tableswitch 是如何工作的。valis inputValue,low将是 1（开关中的最低值）并且high将是 3（开关中的最高值）。

Even with some holes a switch can be compact, e.g.

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

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

The switch above is "almost compact", it only has a single hole. A compiler could generate the following instruction:

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

 tableswitch 1 6
    OneLabel
    FakeTwoLabel
    ThreeLabel
    FourLabel
    FiveLabel
  default: DefaultLabel

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

  FakeTwoLabel:
  DefaultLabel:
    ; default code

As you can see, the compiler has to add a fake case for 2, FakeTwoLabel. Since 2 is no real value of the switch, FakeTwoLabel is in fact a label that changes code flow exactly where the default case is located, since a value of 2 should in fact execute the default case.

如您所见，编译器必须为 2、FakeTwoLabel. 由于 2 不是开关的实际值，因此 FakeTwoLabel 实际上是一个标签，可以准确地更改默认情况所在的代码流，因为值 2 实际上应该执行默认情况。

So a switch doesn't have to be perfectly compact for the compiler to create a tableswitch, yet it should at least be pretty close to compactness. Now consider the following switch:

因此，编译器创建 tableswitch 时，开关不必非常紧凑，但它至少应该非常接近紧凑。现在考虑以下开关：

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

This switch is nowhere near compactness, it has more than hundred times more holes than values. One would call this a spare switch. The compiler would have to generate almost thousand fake casesto express this switch as a tableswitch. The result would be a huge table, blowing up the size of the class file dramatically. This is not practical. Instead it will generate a lookupswitch:

这个开关远非紧凑，它的孔比 values多一百倍。人们将其称为备用开关。编译器将不得不生成近千个假案例来将此开关表示为 tableswitch。结果将是一个巨大的表，极大地增加了类文件的大小。这不实用。相反，它会生成一个查找开关：

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

This table has only 5 entries, instead of over thousand ones. The table has 4 real values, O(log 4) is 2 (log is here log to the base of 2 BTW, not to the base of 10, since computer operate on binary numbers). That means it takes the VM at most two comparisons to find the label for the inputValue or to come to the conclusion, that the value is not in the table and thus the default value must be executed. Even if the table had 100 entries, it would take the VM at most 7 comparisons to find the correct label or decide to jump to the default label (and 7 comparisons is a lot less than 100 comparisons, don't you think?).

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

So it's nonsense that these two instructions are interchangeable or that the reason for two instructions has historical reasons. There are two instructions for two different kind of situations, one for switches with compact values (for maximum speed) and one for switches with spare values (not maximum speed, yet still good speed and very compact table representation regardless all the numeric holes).

所以说这两条指令可以互换或者说两条指令的原因有历史原因都是无稽之谈。对于两种不同的情况有两种指令，一种用于具有紧凑值的开关（用于最大速度），另一种用于具有备用值的开关（不是最大速度，但仍然具有良好的速度和非常紧凑的表格表示，无论所有数字孔如何）。

回答by zsxwing

Java Virtual Machine Specificationdescribe the difference. "The tableswitch instruction is used when the cases of the switch can be efficiently represented as indices into a table of target offsets." The specification describes the more details.

Java 虚拟机规范描述了差异。“当切换的情况可以有效地表示为目标偏移表的索引时，将使用 tableswitch 指令。” 规范描述了更多细节。

回答by Eugene Kuleshov

I suspect it is mostly historical, due to some specific binding of Java bytecode to underline machine code (e.g. Sun's own CPU).

我怀疑这主要是历史性的，因为 Java 字节码的某些特定绑定到机器代码下划线（例如 Sun 自己的 CPU）。

The tableswitch is essentially a computed jump, where destination is taken from a lookup table. On a contrary lookupswitch requires comparison of each value, basically an iteration trough table elements until matching value is found.

tableswitch 本质上是一个计算跳转，其中目标是从查找表中获取的。相反，lookupswitch 需要比较每个值，基本上是一个迭代槽表元素，直到找到匹配值。

Obviously those opcodes are interchangeable, but based on values, one or the other could be faster or more compact (e.g. compare set of keys with large gaps in between and a sequential set of keys).

显然，这些操作码是可互换的，但基于值，一个或另一个可能更快或更紧凑（例如比较一组键之间有很大差距和一组连续键）。