JVM的LookupSwitch和TableSwitch的区别？

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

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

每个茉莉花文档：

查找开关
表切换
双

区别在于

查找开关使用带有键和标签的表
切换仅使用带有标签的表。

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

执行查找开关时，堆栈顶部的 int 值与表中的键进行比较，直到找到匹配项，然后使用此键旁边的跳转目标执行跳转。由于查找开关表始终必须排序，以便 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），甚至更糟）。

编译器根据 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

如您所见，编译器必须为 2， 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 个条目，而不是一千多个条目。该表有 4 个实数值，O（log 4）是 2（log 在这里对数以 2 BTW 为底，而不是以 10 为底，因为计算机在二进制数上运行）。这意味着虚拟机最多需要两次比较才能找到inputValue的标签或得出结论，即该值不在表中，因此必须执行默认值。即使表有 100 个条目，VM 最多需要 7 次比较才能找到正确的标签或决定跳转到默认标签（7 次比较比 100 次比较少得多，你不觉得吗？

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

1.8.0_45 javac如何决定将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））二叉搜索之间进行类似的选择：切换 if-else 语句的优势

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

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

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

显然，这些操作码是可以互换的，但基于值，一个或另一个可以更快或更紧凑（例如，比较中间有较大间隙的键集和一组顺序键）。

相关内容

最新更新

热门标签：