lookupswitchとtableswitchの違い
昨日に引き続きJavaのswitchをコンパイルしたときに使われるtableswitch命令とlookupswitch命令をそれぞれ見ていく。switch難しいです＞＜
tableswitch命令
tableswitch命令は、switchにおける各ケースをターゲット・オフセットのテーブルに対するインデックスとして効率的に表現出来る場合に用いられる。
(中略)
switchにおけるケースがまばらになっている場合、tableswitch命令におけるテーブル表現では、スペース効率が悪いものとなる。
効率的とはいったい何なのか...。とりあえず以下のコードを書いてコンパイルしてみる。
public class Switch { public static void main(String[] args) { int a = 10; String b; switch(a) { case 0: b = "zero"; break; case 1: b = "one"; break; case 2: b = "two"; break; case 4: b = "four"; break; default: b = "default"; } System.out.println(b); } }
case節に0, 1, 2と連続して並んでいるところに3を飛ばして4を入れた。これをコンパイルすると以下のバイトコードが得られる。
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: bipush 10 2: istore_1 3: iload_1 4: tableswitch{ //0 to 4 0: 40; 1: 46; 2: 52; 3: 64; 4: 58; default: 64 } 40: ldc #16; //String zero 42: astore_2 43: goto 67 46: ldc #18; //String one 48: astore_2 49: goto 67 52: ldc #20; //String two 54: astore_2 55: goto 67 58: ldc #22; //String four 60: astore_2 61: goto 67 64: ldc #24; //String default 66: astore_2 67: getstatic #26; //Field java/lang/System.out:Ljava/io/PrintStream; 70: aload_2 71: invokevirtual #32; //Method java/io/PrintStream.println:(Ljava/lang/String;)V 74: return }
なるほど。4:のtableswitch命令を見るとソースコードには書かれていない、3の場合のジャンプ先が書かれている(ジャンプ先はdefaultと同様)。tableswitchは開始インデックスと終了インデックスの値を持ち、その後にジャンプ先のアドレスが連続して並んでいるようだ。
87654321 0011 2233 4455 6677 8899 aabb ccdd eeff 0123456789abcdef ------------------------------------------------------------------- 00000230: f700 0200 0300 0000 4b10 0a3c 1baa 0000 ........K..<.... 00000240: 0000 0000 3c00 0000 0000 0000 0400 0000 ....<........... 00000250: 2400 0000 2a00 0000 3000 0000 3c00 0000 $...*...0...<... 00000260: 3612 104d a700 1812 124d a700 1212 144d 6..M.....M.....M
バイナリエディタで見てみよう。0x23dからがtableswitch(0xaa)の命令。0x241-0x244がデフォルトの飛び先(0x0000003c)、0x245-0x248が開始インデックス(0x00000000)、0x249-24cが終了インデックス(0x00000004)。その後は4バイト毎にジャンプ先が並んでいる。
tableswitchの中の実装は見ていないが、実行時はswitchの対象の値から開始インデックスを引いた値*4に対して、オフセット(開始インデックスのジャンプ先が書かれている位置)を足すだけでジャンプ先のアドレスを特定できそうな気がする。tableswitchは二分探索っていう記事を見たが本当か...？
lookupswitch
tableswitchでは連続している値を利用する場合は効率良くジャンプ出来るが、そうでない場合にtableswitchを使うと無駄なジャンプ先のアドレスを定義する必要が出てきて無駄が多くなる。そういう場合に使われるのがlookupswitchだ。
以下のようにcase節が連続でないコードを書いてみる。
public class Switch { public static void main(String[] args) { int a = 10; String b; switch(a) { case 0: b = "zero"; break; case 1000: b = "one"; break; case 50: b = "two"; break; case 800: b = "four"; break; default: b = "default"; } System.out.println(b); } }
これをコンパイルすると以下のバイトコードが得られる。
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: bipush 10 2: istore_1 3: iload_1 4: lookupswitch{ //4 0: 48; 50: 60; 800: 66; 1000: 54; default: 72 } 48: ldc #16; //String zero 50: astore_2 51: goto 75 54: ldc #18; //String one 56: astore_2 57: goto 75 60: ldc #20; //String two 62: astore_2 63: goto 75 66: ldc #22; //String four 68: astore_2 69: goto 75 72: ldc #24; //String default 74: astore_2 75: getstatic #26; //Field java/lang/System.out:Ljava/io/PrintStream; 78: aload_2 79: invokevirtual #32; //Method java/io/PrintStream.println:(Ljava/lang/String;)V 82: return }
lookupswitch命令には開始/終了インデックスという概念は無く、単純にジャンプ先の数を持ち、その数の分だけキーとジャンプ先のペアを持つ。キーはコンパイル時に昇順にソートして配置される。昇順に配置することで二分探索することが可能になるのでおそらく実行時は二分探索をしている。ただJVMの仕様上は昇順に並べるとしか定義されていない為、どう探索するかは実装によるのだと思う。
87654321 0011 2233 4455 6677 8899 aabb ccdd eeff 0123456789abcdef ------------------------------------------------------------------- 00000230: ff00 0200 0300 0000 5310 0a3c 1bab 0000 ........S..<.... 00000240: 0000 0000 4400 0000 0400 0000 0000 0000 ....D........... 00000250: 2c00 0000 3200 0000 3800 0003 2000 0000 ,...2...8... ... 00000260: 3e00 0003 e800 0000 3212 104d a700 1812 >.......2..M....
バイナリを見てみよう。0x23dがlookupswitch(0xab)だ。0x240-0x243がデフォルトのジャンプ先(0x00000044)、0x245-0x249がジャンプ先の数(0x00000004)、それ以降が4バイトのキーと、4バイトのジャンプ先アドレスのペアが4つ並ぶ。実行時はキーを探索し、マッチしたキーに対応するジャンプ先に飛ぶ。
少しだけswitchについて理解できたかも。
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
eclipseでプラグインが認識されない場合のチェックリスト
eclipseのプラグインを開発している際、デバッグ実行している時はいいのだが実際にjarにしてフォルダに格納した時にプラグインを認識しないことがある。そういうときのチェック方針を適当にメモ。
1. jarファイルが正しい位置に格納されているか？
eclipseプラグインのjarファイルは以下のフォルダ配下に配置出来る。
2. 依存関係が正しく解決されているか？
WindowsならHelp->About eclipse、Macならeclipse-> About eclipseメニューを開き、Installation Detailsボタンを押す。Installation DetailsウィンドウのPlug-insタブから追加したいプラグインが追加されているかを確認する。
もし追加されていなければ、依存関係が正しく追加されていない可能性がある。
開発中のMANIFEST.MFのRequire-Bundle:に書かれているプラグインが実行環境で追加されていることを確認する。上の画像のようにエディタのDependenciesタブからも編集できる。
3. build.propertiesが正しく設定されているか？
必要であればjarを解凍して、plugin.xml、META-INF/MANIFEST.MF、.classファイルの3つが正しく格納されていることを確認する。もし書いてなければbuild.propertiesのbin.includesに以下の3つが書かれていることを確認する。
bin.includes = plugin.xml,\
META-INF/,\
.,\これをBuildタブでUIをつかって編集していると . が消えることがあるようで、jarに.classファイルが一切格納されず、ClassNotDefFoundErrorが出る事がある。
Guiceでジェネリクス型をインジェクションする方法
関連1: 分からない！ジェネリクス
関連2: Java VMとコンパイラ、型システム
この数日、Guiceでジェネリクス型をインジェクションできない問題について考えていた。解決の糸口としてコンパイラやJVM、型について調べていたのだが、どうやらTypeLiteralというGuiceのクラスを使うことで解決するようだ。
public static void main(String[] args) { Injector injector = Guice.createInjector(new AbstractModule() { @Override protected void configure() { List<String> list = new ArrayList<String>(); list.add("AAA"); list.add("BBB"); // これ bind(new TypeLiteral<List<String>>(){}).toInstance(list); } }); injector.getInstance(Hoge.class).hoge(); }
ジェネリクス型のクラスインスタンスを取得する方法がJavaでは提供されていないので、実行時に強制的にサブクラスを作って型情報を取得する、とJavadocの概要に書かれている。
分からない！ジェネリクス
昨日の記事を書いたのは、Google Guiceを使うときにジェネリクスのクラスインスタンスを指定しようとしたがその方法がわからなかったからだった。
ジェネリクス型を使うのは非常に便利なのだが、こうやって困ったときにどうしたらいいのか分からなくなる。
困った事
Guiceのbind関数の引数にクラスインスタンスを渡し、返ってきたオブジェクトに対してtoInstance関数を呼び、引数にそのクラスのオブジェクトを渡す。String型ならこんな感じ。
bind(String.class).toInstance("hoge");このbind関数にList<String>のクラスインスタンスを渡したい。しかしそもそもList<String>のクラスインスタンスとは何なのか分かっていない。まず、List<String>とListというのは同じクラスインスタンスを持つのではないかと推測し、それを調べるために以下のコードを実行してみた。
public class Test {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<String>();
System.out.println(list.getClass().equals(ArrayList.class)); }
}結果、trueが返ってきた。ジェネリクス型はコンパイラが静的に解析してエラーを出すだけで、クラスインスタンスそのものは同じなようだ。そこで以下のコードを書いてみた。
Test.java
public class Test { public static void main(String[] args) { Injector injector = Guice.createInjector(new AbstractModule() { @Override protected void configure() { List<String> list = new ArrayList<String>(); list.add("AAA"); list.add("BBB"); bind(List.class).toInstance(list); } }); injector.getInstance(Hoge.class).hoge(); } }
Hoge.java
public class Hoge { @Inject private List<String> list; public void hoge() { for(String str : list) { System.out.println(str); } } }
この2つのクラスはコンパイルが通るが、実行時にGuiceが以下のような例外を出す。Guiceがしっかりと型チェックをしているようだが、java.util.List
1) No implementation for java.util.List<java.lang.String> was bound.
while locating java.util.List<java.lang.String>
for field at Hoge.list(Hoge.java:6)
while locating Hoge
まあジェネリクス型を使わなければコンパイルは通るのだが、型チェックしたいしなんとかしてコンパイラを黙らせたい。何かいい方法は無いものか...。安直に以下のコードで黙ってくれるかと思ったがコンパイルエラーになった。
@Override protected void configure() { List<String> list = new ArrayList<String>(); list.add("AAA"); list.add("BBB"); bind(list.getClass()).toInstance(list); }
The method toInstance(capture#1-of ? extends List) in the type LinkedBindingBuilder<capture#1-of ? extends List> is not applicable for the arguments (List<String>)
何がどうなってるのやら。インターフェース型かクラス型か、その辺りで引っかかっているような気もするなあ。眠いのでまた明日。
Java VMとコンパイラ、型システム
あー、Javaわからん。型システムもよくわからん。普段そこまで意識することは無いのだが、Javaを使っているとたまに型でハマることがある。いまからJava仮想マシン仕様を読んで読み取れたことと適当な推測をメモしておくので、間違っていたらどなたかコメントして欲しい。
Java言語の仕様とVMの仕様がごっちゃになっているので、そのあたりを整理したい。
Java仮想マシン仕様から読み取れたこと
推測
クラスHogeの変数に互換性の無いクラスFugaのオブジェクトを代入するようなコードをJavaで書き、Javaコンパイラでコンパイルするとコンパイルエラーになる。これは単にJavaの言語仕様上そうなっており、Java VMの仕様では無い。上記のような代入をするバイトコードを手で書けば正しいクラスファイルとしてJava VM上で動かせるはず(Class Cast Exceptionは出るが)。
例
public class Test {
public Hoge hoge = new Hoge();
...
}上記のソースコードをJavaコンパイラでコンパイルしたとき、クラスファイル内で変数hogeは単なる参照型(クラス型)のhogeとして宣言されている。そして
public class Test {
Hoge hoge = new Fuga();
...
}上記のソースコードをJavaコンパイラでコンパイルするとき、HogeがFugaのスーパークラスであるかどうかはJavaコンパイラがチェックしてコンパイルエラーを出す。この上記ソースコードと等価な処理をバイトコードで上記を代入するようなコードを書く事はできるが、実行時にJava VMがClassCastExceptionをスローする。
- 作者: Benjamin C. Pierce,住井英二郎,遠藤侑介,酒井政裕,今井敬吾,黒木裕介,今井宜洋,才川隆文,今井健男
- 出版社/メーカー: オーム社
- 発売日: 2013/03/26
- メディア: 単行本（ソフトカバー）
- クリック: 68回
- この商品を含むブログ (7件) を見る
これでも買うか...。
