Java7のswitch文から得られるバイトコードの考察
仕事ではJava6しか使ってないが(ごめんなさい)、Java7に関する以下の文章を読んでいたらswitch文というものがよく分からなくなった。
Java SE 7 で導入された言語機能の 1 つは、switch 文の判断基準の対象としてプリミティブ型や列挙型と同様に文字列型の変数を使えるようになったことです。
(中略)
一見、switch 文はネストされた if ... else 文に対する構文糖にすぎないように思えます。実際、開発者は、switch 文とネストされた if ... else 文のうち、どちらがコード内での見栄えが良いかを大方の基準として、いずれかを選ぶことが頻繁にあります。しかし、switch 文とネストされた if ... else 文は同じではありません。switch 文にはパフォーマンスと安全性の両方の理由から、switch 文に特有の制約があります。その制約とは、case ラベルは定数値でなければならず、switch のオペランドは定数のように振る舞う型に制限される、というものです。ラベルを定数に制限することで、分岐計算は O(n) ではなく O(1) の演算になります。
えっと...何を言っているのかわからない。実際にコードを書いて確認しよう。
switchの仕組み
以下の簡単なswitch文のソースコードをコンパイルして得られるバイトコードについて考える。
public class Testing { public static void main(String[] args) { String num = "one"; int result; switch (num) { case "zero": result = 0; break; case "one": result = 1; break; case "two": result = 2; break; default: result = -1; break; } System.out.println(result); } }
Java7でコンパイルして得られるのは以下のバイトコード。javap -cコマンドで出力する。
Compiled from "Testing.java" public class Testing extends java.lang.Object{ public Testing(); Code: 0: aload_0 1: invokespecial #8; //Method java/lang/Object."<init>":()V 4: return public static void main(java.lang.String[]); Code: 0: ldc #16; //String one 2: astore_1 3: aload_1 4: dup 5: astore_3 6: invokevirtual #18; //Method java/lang/String.hashCode:()I 9: lookupswitch{ //3 110182: 44; 115276: 56; 3735208: 68; default: 95 } 44: aload_3 45: ldc #16; //String one 47: invokevirtual #24; //Method java/lang/String.equals:(Ljava/lang/Object;)Z 50: ifne 85 53: goto 95 56: aload_3 57: ldc #28; //String two 59: invokevirtual #24; //Method java/lang/String.equals:(Ljava/lang/Object;)Z 62: ifne 90 65: goto 95 68: aload_3 69: ldc #30; //String zero 71: invokevirtual #24; //Method java/lang/String.equals:(Ljava/lang/Object;)Z 74: ifne 80 77: goto 95 80: iconst_0 81: istore_2 82: goto 97 85: iconst_1 86: istore_2 87: goto 97 90: iconst_2 91: istore_2 92: goto 97 95: iconst_m1 96: istore_2 97: getstatic #32; //Field java/lang/System.out:Ljava/io/PrintStream; 100: iload_2 101: invokevirtual #38; //Method java/io/PrintStream.println:(I)V 104: return
上記のバイトコードを要点だけまとめると
- 6:でStringのgetHash()を呼び出して文字列のハッシュ値を取り出す
- 9:でlookupswitch命令を使ってハッシュ値に対応するcase処理を呼び出す
- caseの飛び先(oneなら45:)で、equalsメソッドを呼び出して一致すれば値を格納、そうでなければデフォルトの処理(95:)へ飛ぶ
「パフォーマンスの面によりcaseが定数値でなければならない」という制約は、Stringに限って言えばequalsメソッドを呼ぶ回数が1回で済むように、予め文字列のハッシュを計算おく為にあるのだと考えられる。
疑問
ここで疑問が出てくる。getHash()が一致するにも関わらずequalsがfalseになるような値があった場合どうなるのか?例えば以下のようなコード。
public class Switch { public static void main(String[] args) { String hoge = "FB"; switch (hoge) { case "Ea": System.out.println("Ea"); break; case "FB": System.out.println("FB"); break; case "Hoge": System.out.println("Hoge"); break; default: System.out.println("DEFAULT"); break; } } }
上記のコードは一見何の変哲も無いコードに見えるが、"Ea"と"FB"のgetHash()の値が衝突(2236)する。先程と同じようなバイトコードが出力されていればハッシュが同じなので"FB"の番地に飛び、switch対象の"FB"と"Ea"とのequalsメソッドが呼ばれてfalseとなり、defaultの番地に飛ばされるはずである。
Compiled from "Switch.java" public class Switch extends java.lang.Object{ public Switch(); Code: 0: aload_0 1: invokespecial #8; //Method java/lang/Object."<init>":()V 4: return public static void main(java.lang.String[]); Code: 0: getstatic #16; //Field java/lang/System.out:Ljava/io/PrintStream; 3: ldc #22; //String FB 5: invokevirtual #24; //Method java/lang/String.hashCode:()I 8: invokevirtual #30; //Method java/io/PrintStream.println:(I)V 11: getstatic #16; //Field java/lang/System.out:Ljava/io/PrintStream; 14: ldc #36; //String Ea 16: invokevirtual #24; //Method java/lang/String.hashCode:()I 19: invokevirtual #30; //Method java/io/PrintStream.println:(I)V 22: ldc #22; //String FB 24: astore_1 25: aload_1 26: dup 27: astore_2 28: invokevirtual #24; //Method java/lang/String.hashCode:()I 31: lookupswitch{ //2 2236: 56; 2254917: 77; default: 122 } 56: aload_2 57: ldc #36; //String Ea 59: invokevirtual #38; //Method java/lang/String.equals:(Ljava/lang/Object;)Z 62: ifne 89 65: aload_2 66: ldc #22; //String FB 68: invokevirtual #38; //Method java/lang/String.equals:(Ljava/lang/Object;)Z 71: ifne 100 74: goto 122 77: aload_2 78: ldc #42; //String Hoge 80: invokevirtual #38; //Method java/lang/String.equals:(Ljava/lang/Object;)Z 83: ifne 111 86: goto 122 89: getstatic #16; //Field java/lang/System.out:Ljava/io/PrintStream; 92: ldc #36; //String Ea 94: invokevirtual #44; //Method java/io/PrintStream.println:(Ljava/lang/String;)V 97: goto 130 100: getstatic #16; //Field java/lang/System.out:Ljava/io/PrintStream; 103: ldc #22; //String FB 105: invokevirtual #44; //Method java/io/PrintStream.println:(Ljava/lang/String;)V 108: goto 130 111: getstatic #16; //Field java/lang/System.out:Ljava/io/PrintStream; 114: ldc #42; //String Hoge 116: invokevirtual #44; //Method java/io/PrintStream.println:(Ljava/lang/String;)V 119: goto 130 122: getstatic #16; //Field java/lang/System.out:Ljava/io/PrintStream; 125: ldc #47; //String DEFAULT 127: invokevirtual #44; //Method java/io/PrintStream.println:(Ljava/lang/String;)V 130: return }
実際にコンパイルしてみたところ、ハッシュで特定の番地(56:)に飛ぶところまでは同じだが、飛んだ先でequalsとifne命令ででそれぞれ文字列をチェックしている。まあこのくらい当然か。
パフォーマンスだけを考慮するとハッシュだけを利用するのが良さそうに見えるが、安全性を確保(衝突を回避)する為にequalsも並行して使用しているようだ。
後半に書かれているオーダーについては以下のブログが参考になる。自分でもそのうち記事にするかもしれない。
http://d.hatena.ne.jp/taka_2/20110922/p1