JVM 的 LookupSwitch 和 TableSwitch 之间的区别？

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

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

每个茉莉文件:

15099 次浏览
小开

我怀疑它大部分是历史性的，因为 Java 字节码与底层机器代码(例如 Sun 自己的 CPU)之间存在某种特定的绑定。

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

显然，这些操作码是可以互换的，但是基于值，其中一个可以更快或更紧凑(例如，比较一组中间有较大间隔的键和一组连续的键)。

小开

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

小开
最佳答案

区别在于

  • Lookupswitch use < strong > a table with key and label
  • Tablesswitch 使用 只有标签的桌子。

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

执行 查找开关时，将将堆栈顶部的 int 值与表中的键进行比较，直到找到匹配项，然后使用该键旁边的跳转目标执行跳转。因为查找开关表总是 必须解决，所以每个 X < Y 的 keyX < keyY，整个查找 + 跳转过程是一个 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

如您所见，编译器必须添加 两个人的假箱子、 FakeTwoLabel。因为2不是开关的实际值，所以 FakeTwoLabel实际上是一个标签，它可以精确地改变缺省大小写所在的代码流，因为值2实际上应该执行缺省大小写。

因此，编译器创建表开关时，开关不必非常紧凑，但至少应该非常接近紧凑。现在考虑下面的转换:

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

这个开关没有接近紧凑，它有超过百倍的 漏洞多于价值。有人会称之为稀疏开关。编译器必须生成 差不多一千个假案子才能将这个开关表示为表开关。结果将是一个巨大的表，极大地扩展了类文件的大小。这不现实。相反，它会生成一个查找开关:

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

这个表只有5个条目，而不是超过1000个。该表有4个实数，O (log 4)为2(log 在这里是日志到2 BTW 的基数，而不是到10的基数，因为计算机操作二进制数)。这意味着最多需要两次 VM 比较才能找到 inputValue 的标签或得出结论，即该值不在表中，因此必须执行默认值。即使表中有100个条目，也需要最多7次比较的 VM 才能找到正确的标签或者决定跳转到默认标签(7次比较远远少于100次比较，你不这样认为吗.

所以说这两个指令是可以互换的，或者说这两个指令的原因有历史原因，都是无稽之谈。对于两种不同的情况有两种指令，一种用于具有紧凑值的开关(用于最大速度) ，另一种用于具有稀疏值的开关(不是最大速度，但仍然具有良好的速度和非常紧凑的表表示，而不管数字孔)。

小开

javac1.8.0 _ 45如何决定将 switch编译成什么？

要决定什么时候使用哪个，可以使用 javac选择算法作为基础。

我们知道 javac的来源是在 langtools的回购。

然后我们开始寻找:

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;

地点:

  • hi: 最大案例值
  • lo: 最小箱数

因此，我们认为它同时考虑了时间和空间的复杂性，对时间复杂性的权重为 3。

TODO 我不明白为什么 lookup_time_cost = nlabels而不是 log(nlabels)，因为 tableswitch可以在 O (log (n))中进行二进制搜索。

附加事实: C + + 编译器也会在 O (1)跳转表和 O (long (n))二进制搜索之间做出类似的选择: Switch over if-else 语句的优点


提交答案