我很难理解 Java 字节码中的 LookUpSwitch 和 TableSwitch。
如果我理解的很好,LookUpSwitch和TableSwitch都对应switch
Java源码的语句?为什么一个 JAVA 语句会生成 2 个不同的字节码?
每个 Jasmin 文档:
不同之处在于
执行tableswitch时,直接将栈顶的 int 值作为 table 的索引,以获取跳转目的地并立即执行跳转。整个查找+跳转过程是一个O(1) 操作,这意味着它非常快。
执行lookupswitch时,堆栈顶部的int值与表中的键进行比较,直到找到匹配项,然后使用该键旁边的跳转目标执行跳转。由于lookupswitch表总是必须排序,使得keyX < keyY对于每个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) 甚至更糟)。
编译器根据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(开关中的最低 case 值)和high
3(开关中的最高 case 值)。
即使有一些孔,开关也可以很紧凑,例如
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 不是 switch 的实际值,FakeTwoLabel
实际上是一个标签,可以准确地更改默认情况所在的代码流,因为值 2 实际上应该执行默认情况。
因此,编译器创建 tableswitch 的 switch 不必非常紧凑,但它至少应该非常接近紧凑。现在考虑以下开关:
switch (inputValue) {
case 1: // ...
case 10: // ...
case 100: // ...
case 1000: // ...
default: // ...
}
这个开关远非紧凑,它的孔比 values多一百倍。人们会称之为稀疏开关。编译器必须生成近千个假案例才能将此开关表示为 tableswitch。结果将是一个巨大的表,大大增加了类文件的大小。这是不切实际的。相反,它将生成一个查找开关:
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 次比较,你不觉得吗?)。
所以说这两条指令是可以互换的,或者说两条指令的原因是有历史原因的,都是无稽之谈。对于两种不同的情况有两种指令,一种用于具有紧凑值的开关(用于最大速度),另一种用于具有稀疏值的开关(不是最大速度,但仍然具有良好的速度和非常紧凑的表格表示,无论数字孔如何)。
1.8.0_45如何javac
决定编译switch
成什么?
要决定何时使用哪个,您可以使用javac
选择算法作为基础。
我们知道来源javac
是在langtools
回购。
然后我们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;
在哪里:
hi
: 最大案例值lo
: 最小案例值因此我们得出结论,它同时考虑了时间和空间复杂度,时间复杂度的权重为3。
TODO 我不明白为什么lookup_time_cost = nlabels
和不log(nlabels)
,因为 atableswitch
可以在 O(log(n)) 中通过二分搜索完成。
额外的事实:C++ 编译器也在 O(1) 跳转表和 O(long(n)) 二进制搜索之间做出类似的选择:切换 if-else 语句的优势
Java 虚拟机规范描述了差异。“当 switch 的情况可以有效地表示为目标偏移表中的索引时,使用 tableswitch 指令。” 该规范描述了更多细节。
我怀疑这主要是历史原因,因为 Java 字节码与底层机器代码(例如 Sun 自己的 CPU)的某些特定绑定。
这tableswitch
本质上是一个计算跳转,其中目的地是从查找表中获取的。相比之下,lookupswitch
需要比较每个值,基本上是遍历表元素直到找到匹配值。
显然,这些操作码是可互换的,但基于值,一个或另一个可能更快或更紧凑(例如,比较之间有较大间隙的一组键和一组顺序键)。