JVM的LookupSwitch和TableSwitch之间的区别？

不同之处在于

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

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

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

这段代码非常清楚这种表开关是如何工作的。 是 ，将为 1（交换机中的大小写值），并且为 3（交换机中的大小写值）。valinputValuelowhigh

即使有一些孔，开关也可以是紧凑的，例如

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， 添加一个假大小写。由于 2 不是开关的实际值，因此实际上是一个标签，它恰好在默认大小写所在的位置更改代码流，因为值 2 实际上应该执行默认大小写。FakeTwoLabelFakeTwoLabel

因此，对于编译器来说，切换不必完全紧凑即可创建表开关，但它至少应该非常接近紧凑性。现在考虑以下开关：

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（此处的日志以 2 BTW 为底，而不是以 10 为底，因为计算机对二进制数进行操作）。这意味着 VM 最多需要两次比较才能找到 inputValue 的标签或得出结论，即该值不在表中，因此必须执行默认值。即使表有 100 个条目，VM 最多也需要 7 次比较才能找到正确的标签或决定跳转到默认标签（7 个比较比值远少于 100 个比较，你不觉得吗？）。

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

javac 1.8.0_45 如何决定编译切换到什么？

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

我们知道 的来源在存储库中。javaclangtools

然后我们 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 我不明白为什么和没有，因为可以在 O（log（n）） 中使用二进制搜索来完成。lookup_time_cost = nlabelslog(nlabels)tableswitch

优点：C++编译器也在 O（1） 跳转表和 O（long（n）） 二进制搜索之间做出类似的选择：切换 if-else 语句的优势