読者です 読者をやめる 読者になる 読者になる

この日記は私的なものであり所属会社の見解とは無関係です。 GitHub: takahashikzn

caseがStringなswitch文はmapで実装されている?

http://java-performance.info/string-switch-performance/

こちらより。


最後のまとめだけ書くと、

Summary

  • String switch in Java 7 is implemented using a fixed size map with a number of slots close to 20. This means that you can freely use it in most of cases not worrying about its performance at all. As you have seen, string switch has identical performance compared to manually implemented maps when you have under 100 cases in the switch.
  • String.equals/equalsIgnoreCase perform great as a replacement for string switch while all your cases have different length (or at least the number of cases with the same string length is too low compared to the total number of cases) and the number of string cases is not too big. This property is achieved by comparing string length prior to comparing the actual contents in String.equals/equalsIgnoreCase.

まとめ

  • Java7では、Stringのswitch文は固定サイズのmapで実装されている。で、スロットの数はおよそ20くらいなので、大抵の状況ではパフォーマンスに関して敏感になる必要はない。caseが100以下ならば、Mapを使って自前でswitch文的なことを実現するより速い。
  • case文の文字列の長さが全て異なるか、同じ長さのcase文字列があったとしてもかなり少ない場合で、かつ全体としてcaseの数自体がそれほど多くない場合は、String.equals/equalsIgnoreCaseを使ったほうが速い。これは、String.lengthの実装が「まず最初に文字列長をチェックする」という最適化を使っている事による。

だそうです。ふーん。


最初にこの記事を見た時、mapってjava.util.Mapのことかよマジか、とビビりましたが、
調べてみるとどうやら、バイトコード上の表現であるジャンプテーブルのことを指しているっぽい。

switch文を逆コンパイルした結果

バイトコード上どうなるのか知りたかったので逆コンパイルしてみました。

public static int test(final String str) {

    switch (str) {
        case "case1": return 1;
        case "case2": return 2;
        case "case3": return 3;

           // ...中略 

        case "case29": return 29;
        default: -1;
    }
}

のようなコードをecjでコンパイルして逆コンパイルすると、

public final class Sample
{

    public static int test(String s)
    {
        String s1;
        switch((s1 = s).hashCode())
        {
        default:
            break;

        case -1367575217:
            if(s1.equals("case10"))
                return 10;
            break;

        case -1367575216:
            if(s1.equals("case11"))
                return 11;
            break;

       // ...中略

    }    

    return -1;
}

になりました。コンパイル時に静的にhashCodeを計算しておいて、結局はintのswitch文にしているということです。こちらで説明がある通り。
http://argius.hatenablog.jp/entry/20110906/1315313934


ecjとjavacで結果が違う

ところで、ecjとjavacでは結果が違います。

ecjの結果は上にある通り。javacの結果は

public static int shortSwitch(String s)
{
    String s1 = s;
    byte byte0 = -1;
    switch(s1.hashCode())
    {
    case 94432001: 
        if(s1.equals("case1"))
            byte0 = 0;
        break;

    case 94432002: 
        if(s1.equals("case2"))
            byte0 = 1;
        break;

    // ...中略

    case -1367575217: 
        if(s1.equals("case10"))
            byte0 = 9;
        break;
    }

    switch(byte0)
    {
    case 0: // '\0'
        return 1;

    case 1: // '\001'
        return 2;

    case 2: // '\002'
        return 3;

    // ...中略

    case 9: // '\t'
        return 10;
    }
    return -1;
}

になります。switch文が2回出てきます。何ぞこれ。

ググってみると、ここに詳しいことが書いてあります。
http://d.hatena.ne.jp/taka_2/20110922/p1
最適化により異なるバイトコードが吐かれるっぽい。


コンパイラにはみんな大好きjadを使っているわけですが、
そろそろこいつも限界なのかもしれませんね…

case文が256を超えると?

先ほどの例では、一旦byteに2つ目のswitchのためのジャンプ先を格納するという実装でした。
では、byteの範囲を超えると何が起きるのか…?

public static int shortSwitch(String s)
{
    String s1 = s;
    char c = '\uFFFF';
    switch(s1.hashCode())
    {
    case 94432000: 
        if(s1.equals("case0"))
            c = '\0';
        break;

    case 94432001: 
        if(s1.equals("case1"))
            c = '\001';
        break;

    case 94432002: 
        if(s1.equals("case2"))
            c = '\002';
        break;

    // ...以下略
}

今度はcharになりました。まあ言いたいことはわかるけどさw