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

- 1 min

编译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指令有更高的执行效率。

comments powered by Disqus
rss facebook twitter github youtube mail spotify lastfm instagram linkedin google google-plus pinterest medium vimeo stackoverflow reddit quora quora