JVM的LookupSwitch和TableSwitch之间的区别？

Question

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

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

每个Jasmin文档:

• LookupSwitch
• tableswitch

Answer 1

不同之处在于lookupswitch使用带有键和标签的表,而tableswitch只使用带有标签的表.

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

执行lookupswitch时,堆栈顶部的int值将与表中的键进行比较,直到找到匹配项,然后使用此键旁边的跳转目标执行跳转.由于lookupswitch表总是必须进行排序,使keyX <keyY每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),甚至更糟).

决定使用哪条指令是由编译器根据switch语句的紧凑程度做出的,例如

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

上面的开关非常紧凑,没有数字"孔".编译器将创建一个这样的tableswitch:

 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
}

这段代码很清楚如何使用这样的tableswitch.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实际上应该执行默认情况.

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

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

这个开关远不够紧凑,它的孔数比数值多一百多倍.人们会称之为备用开关.编译器必须生成近千个假案例,以将此开关表示为表格开关.结果将是一个巨大的表,大大夸大了类文件的大小.这不切实际.相反它会生成一个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点的比较少了很多,你不觉得吗？).

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

Answer 2

什么时候javac 1.8.0_45编译切换到任何一个？

要决定何时使用哪个,您可以使用javac选择算法作为基础.

我们知道的来源switch是在javac回购协议.

然后我们grep:

hg grep -i tableswitch

第一个结果是langtools/src/share/classes/com/sun/tools/javac/jvm/Gen.java:

// Determine whether to issue a tableswitch or a lookupswitch
// instruction.
long table_space_cost = 4 + ((long) hi - lo + 1); // words
long table_time_cost = 3; // comparisons
long lookup_space_cost = 3 + 2 * (long) nlabels;
long lookup_time_cost = nlabels;
int opcode =
    nlabels > 0 &&
    table_space_cost + 3 * table_time_cost <=
    lookup_space_cost + 3 * lookup_time_cost
    ?
    tableswitch : lookupswitch;

哪里:

• javac:最大案例值
• langtools:最小案例值

因此我们得出结论,它考虑了时间和空间的复杂性,时间复杂度的权重为3.

TODO我不明白为什么hi和不lo,因为lookup_time_cost = nlabels可以在O(log(n))中使用二进制搜索完成.

额外:C++实现也在O(1)跳转表和O(long(n))二进制搜索之间做出类似的选择:切换if-else语句的优点

Answer 3

Java虚拟机规范描述了差异."当开关的情况可以有效地表示为目标偏移表中的索引时,使用tableswitch指令." 规范描述了更多细节.