JVM指令集中tableswitch和lookupswitch指令的区别

[aCoder2013]

编译Switch语句

编译器会使用tableswitch和lookup指令来生成Switch语句的编译代码，并且都只能支持int类型的条件值.因此byte,char,short类型的值都会被向上拓展为int类型。

TableSwitch

tableswitch的做法是直接将条件值和case进行一一比较，整个操作为O(1)，因此非常快。
例如下面这段代码

int chooseNear(int i) {
    switch (i) {
        case 0:  return  0;
        case 1:  return  1;
        case 2:  return  2;
        default: return -1;
    }
}

可以发现，case分支的条件值很紧凑，中间没有断层，编译后的代码为：

tableswitch 1 3
    OneLabel
    TwoLabel
    ThreeLabel
  default: DefaultLabel

但是如果中间有断层的话，编译器会进行一些优化，看这段代码：

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

这段代码可以说近乎是紧凑的，只有2是缺少的，编译代码如下：

tableswitch 1 6
    OneLabel
    FakeTwoLabel
    ThreeLabel
    FourLabel
    FiveLabel
  default: DefaultLabel

  ; 
  ......
  FakeTwoLabel:
  DefaultLabel:
    ; default code

可以看到编译器为‘2’这种情况，自动生成了一个虚假的case：FakeTwoLabel，而当执行到case 2的时候，会自动跳转到default的处理代码。

lookupswitch

lookupswitch是对索引表中的键进行比较，如果条件值和某个键匹配，则跳转到这个键对应的分支偏移量继续执行，若没有键值符合，那么就执行default处理代码段。而且键值必须是排序过的，这样将会比线性查找效率好很多，例如采用二分查找，效率为O(log n)。
下面这段代码，case的条件值很分散，有上百个断层，因此编译器也必须生成上百个fake case，结果会生成一个超大的table，class文件的大小爆炸式增长，这种做法显然不符合现实，因此编译器会生成一段lookupswitch指令

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

编译后的代码为：

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

这个表只有五项，4个真实的值，如果采用二分查找，log4=2,JVM至多只需要2次就可以找到结果。就算表有100项，也才比较7次左右好么。

结论

tableswitch用于case比较紧凑的代码，而lookup用于case比较分散的代码。如果不考虑空间的话，tableswitch指令比lookup指令有更高的执行效率。