JVM的LookupSwitch和TableSwitch之间的区别？ [英] Difference between JVM's LookupSwitch and TableSwitch?

问题描述

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

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

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

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

每个的Jasmin文档：

Jasmin documentation of each:

• LookupSwitch


• tableswitch

• LookupSwitch
• tableswitch

推荐答案

不同之处在于，lookupswitch使用带有键和标签的表，但是tableswitch使用仅带标签的表。

The difference is that a lookupswitch uses a table with keys and labels, yet a tableswitch uses a table with labels only.

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

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.

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

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 sorted so that keyX < keyY for every X < Y, the whole lookup+jump process is a O(log n) operation as 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).

决定使用哪条指令是由编译器基于 compact switch语句的事实，例如

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

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 1 3
    OneLabel
    TwoLabel
    ThreeLabel
  default: DefaultLabel

来自Jasmin页面的伪代码解释得非常好：

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

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
}

这段代码非常清楚如何tableswitch的工作原理。 val inputValue ， low 将为1（最低）交换机中的案例值）和高将为3（交换机中的最高案例值）。

This code is pretty clear on how such a tableswitch works. val is inputValue, low would be 1 (the lowest case value in the switch) and high would be 3 (the highest case value in the switch).

均匀有一些洞，开关可以是紧凑的，例如

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

正如您所看到的，编译器必须为2 <添加假案例/ em>， FakeTwoLabel 。由于2不是交换机的实际值，因此FakeTwoLabel实际上是一个标签，可以在默认情况下确切地改变代码流，因为值2实际上应该执行默认情况。

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.

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

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:

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

这个开关远不是紧凑的，它的值比数值孔多了一百多倍。人们会称之为备用开关。编译器必须生成几千个假案例，以将此开关表示为tableswitch。结果将是一个巨大的表，大大夸大了类文件的大小。这不切实际。相反它会生成一个lookupswitch：

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 cases to 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:

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

此表仅包含5个条目，而不是超过一千个。该表有4个实数值，O（log 4）为2（log这里记录到2 BTW的基数，而不是10的基数，因为计算机操作二进制数）。这意味着VM最多需要两次比较才能找到inputValue的标签或得出结论，该值不在表中，因此必须执行默认值。即使表有100个条目，VM最多需要7次比较才能找到正确的标签或决定跳转到默认标签（7次比较远不及100次比较，你不觉得吗？）。

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?).

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

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).

这篇关于JVM的LookupSwitch和TableSwitch之间的区别？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！