jvm中的switch和String为条件时的思考


jvm中的switch以及String在switch和if-else-if中的思考

引言

在日常玩耍(开发)的过程中,我们常常会使用到比较,有的时候比较次数少,就直接用if-else就好了,但是情况比较多的时候,还会用到switch。以前也对switch认识的不多,今天就记录一下
本小节根据java虚拟机规范SE8版

tableswitch和lookupswitch

java编译器会使用tableswitch和lookupswitch两种指令生成switch语句的编译代码。其中tableswitch指令用于表示switch结构中的case语句块,它可以高效地从索引表中确定case语句块的分支偏移量。当switch语句中的条件不能对应于索引表中的任何一个case语句块的分支偏移量时,default分支将起作用。举个例子:

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

编译之后就成了下面这个样子:

    Method int chooseNear(int)
    0   iload_1                 //将变量表中下标1的元素压入栈 :  i->stack
    1   tableswitch 0 to 2      //从栈中弹出元素,检查是否在0~2之间 : i in (0,2)?
        0: 28                   //i==0?pc->28:
        1: 30                   //i==1?pc->30
        2: 32                   //i==32?pc->32
        default: 34             //不在(0,2)之间。pc->34
    28  iconst_0                //将int值0压入栈: 0->stack
    29  ireturn                 //从栈中弹出元素,返回: return 0;
    30  iconst_1                //将int值1压入栈: 1->stack
    31  ireturn                 //从栈中弹出元素,返回: return 1;
    32  iconst_2                // 2->stack
    33  ireturn                 // return 2
    34  iconst_m1               // m1表示 -1,所以是: -1 -> stack
    35  ireturn                 // return -1;

这种方式编译成的switch语句有个好处:只需要对索引值进行一次范围检查,就能快速的得到条件是否成立,并得到case语句块的分支偏移量因为这里的case语句是连续的,所以如果case分支条件值比较密集的话,tableswitch将会很快的找到需要处理的情况。

接下来看看lookupswitch的应用场景:如果switch语句中的case分支条件值比较稀疏时,tableswithc指令的空间使用率偏低(有兴趣的小伙伴可以试试给上面的栗子加上case 4,和case 6看看会编译成什么),这种情况下可以用lookupswitch指令替代,lookupswitch的要求是其索引表必须根据键值排序,这样就可以使用其他的搜索方法(比如二分搜索)来帮助提高找到对应case的效率。有兴趣的小伙伴可以试试将上述栗子中的case值换成100,600,1000或者跨度更大的值,看看会编译成什么样子。具体逻辑差不多,这里就不贴代码了。

值得注意的是

值得注意的是,根据java虚拟机规范,java虚拟机的tableswitch和lookupswitch指令都只能支持int类型的条件值。如果选择其他数值类型的条件值,那就必须窄化成int类型。

考虑String

这个时候可能就有小伙伴恍然大悟,哦豁,原来说String当switch条件用的是糖语法原来是因为这个原因(jvm不支持String类型的case值,所以需要编译器帮忙调用String.hashCode并以此为case的条件)。有的时候通过学习jvm能够解决很多我们平时不注意的小困惑。本着折腾的精神,我们看看String为case条件时会有哪些有趣的现象。

String在switch中

这里跟大家分享一下怎么反编译java文件吧。考虑Linux环境下(windows应该差不多),首先写好一个java文件比如test.java,然后进入对应的目录之后,使用
javac ./test.java,这个时候目录下就多了一个叫test.class的文件,然后使用
javap -c test > test.dcmp,然后就能看到目录下多了一个(或者本来就有,但是内容被换掉了)test.dcmp的文件,当然文件名字随你喜欢,之后打开这个文件就能看到反编译之后的代码了。

emmm,回归正题,考虑以下java代码:

    public class Switch{
    public static void main(String[] args){
        String i="abc";
        String j = testSwitch(i);
    }

    static String testSwitch(String i){
        switch(i){
            case "aba": return "0a";
            case "abb": return "1b";
            case "abc": return "2c";
            case "abd": return "5d";
            default: return "-1e";
        }
    }
}

可以看到我们使用的String是很相近的,这里说的相近是hashCode相近,并不是说字母差不多。反编译了一下,果然是用tableswitch来检索case的:

     static java.lang.String testSwitch(java.lang.String);
    Code:
       0: aload_0
       1: astore_1
       2: iconst_m1
       3: istore_2
       4: aload_1
       5: invokevirtual #4                  // Method java/lang/String.hashCode:()I
       8: tableswitch   { // 96352 to 96355

                 96352: 40

                 96353: 54

                 96354: 68

                 96355: 82
               default: 93
          }
      40: aload_1
      41: ldc           #5                  // String aba
      43: invokevirtual #6                  // Method java/lang/String.equals:(Ljava/lang/Object;)Z
      46: ifeq          93
      49: iconst_0
      50: istore_2
      51: goto          93
      // 省略一些差不多的判断,直接看pc->93
      93: iload_2
      94: tableswitch   { // 0 to 3

                     0: 124

                     1: 127

                     2: 130

                     3: 133
               default: 136
          }
     124: ldc           #9                  // String 0a
     126: areturn
     127: ldc           #10                 // String 1b
     129: areturn
     130: ldc           #11                 // String 2c
     132: areturn
     133: ldc           #12                 // String 5d
     135: areturn
     136: ldc           #13                 // String -1e
     138: areturn

可以看到整个流程可以归纳为:

  1. 查找case
  2. 使用String.equals比较该case值与传参是否相等
  3. 一系列逻辑运算
  4. 又一次switch找到对应case
  5. 取出要返回的值,返回

使用hashCode比较稀疏的case条件时除了第一步的switch改为使用lookupswitch外其他都一样。

String在if-eles-if中

同样的代码使用if-else-if或怎么样呢?

//编译前
static String testIfElse(String i){
        if("aba".equals(i)){
            return "0a";
        }else if("abb".equals(i)){
            return "1b";
        }else if ("abc".equals(i)) {
            return "3c";
        }else if ("abd".equals(i)) {
            return "4d";
        }else{
            return "-1e";
        }
    }

===============================================================================

static java.lang.String testIfElse(java.lang.String);
    Code:
       0: ldc           #15                 // String aba
       2: aload_0
       3: invokevirtual #6                  // Method java/lang/String.equals:(Ljava/lang/Object;)Z
       6: ifeq          12
       9: ldc           #10                 // String 0a
      11: areturn
      12: ldc           #7                  // String abb
      14: aload_0
      15: invokevirtual #6                  // Method java/lang/String.equals:(Ljava/lang/Object;)Z
      18: ifeq          24
      21: ldc           #11                 // String 1b
      23: areturn
      24: ldc           #2                  // String abc
      26: aload_0
      27: invokevirtual #6                  // Method java/lang/String.equals:(Ljava/lang/Object;)Z
      30: ifeq          36
      33: ldc           #16                 // String 3c
      35: areturn
      36: ldc           #17                 // String abd
      38: aload_0
      39: invokevirtual #6                  // Method java/lang/String.equals:(Ljava/lang/Object;)Z
      42: ifeq          48
      45: ldc           #18                 // String 4d
      47: areturn
      48: ldc           #14                 // String -1e
      50: areturn

可以看到这是一条直直的流水线,中间没有跳转,找到对应的情况就返回

现在来简单分析一下,假设有N中case,其分支条件值为String类型,为了不失一般性,我们假设这里的case的hashCode比较稀疏(相差比较大),所以在swtich中使用的是lookupswitch。那么有:

简单分析

在switch中
  1. 一次String.hashCode调用
  2. 第一次switch操作的时间复杂度为O(logN),如果为tableswitch则为O(1)
  3. 一次String.equals
  4. 一次tableswitch,时间复杂度为O(1)
  5. 返回值

这里列出的是除了case中的逻辑所需要的时间,因为case中的逻辑不管在switch中还是if-else中都是一样的,所以不做考虑

在if-else-if中
  1. 线性String.equals操作,最差的情况需要进行N次比较

于是:

switch中:time = hashCode+log(N)+equals+1+case中的逻辑
if-else-if中: time = equals*caseIndex+逻辑处理 其中caseIdex为从上到下第几个if子句

不知道有没有小伙伴发现了这两种方式的本质可以抽象为一种是排序了的数组使用二分法查找,一种是暴力遍历数组,所以在什么情况下使用哪种情况呢,大概的作出以下推论:

  1. case数量多,使用switch
  2. case数量少,使用if-else-if
  3. 有极大概率发生的情况,且case数量可以接受的,使用if-else-if,且将最容易发生的条件放在上面

1条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

昵称 *