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

lookupswitchとtableswitchの違い

昨日に引き続きJavaのswitchをコンパイルしたときに使われるtableswitch命令とlookupswitch命令をそれぞれ見ていく。switch難しいです><

tableswitch命令

tableswitch命令は、switchにおける各ケースをターゲット・オフセットのテーブルに対するインデックスとして効率的に表現出来る場合に用いられる。
(中略)
switchにおけるケースがまばらになっている場合、tableswitch命令におけるテーブル表現では、スペース効率が悪いものとなる。

Java仮想マシン仕様 第2版 p.347


効率的とはいったい何なのか...。とりあえず以下のコードを書いてコンパイルしてみる。

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ファイルは以下のフォルダ配下に配置出来る。

  • eclipseの実行ファイルがあるフォルダと同じ階層にあるpluginsフォルダ配下
  • eclipseの実行ファイルがあるフォルダの配下のdropins/[フォルダ名]/plugins配下

2. 依存関係が正しく解決されているか?

WindowsならHelp->About eclipse、Macならeclipse-> About eclipseメニューを開き、Installation Detailsボタンを押す。Installation DetailsウィンドウのPlug-insタブから追加したいプラグインが追加されているかを確認する。

f:id:mi_kami:20130701233619p:plain


もし追加されていなければ、依存関係が正しく追加されていない可能性がある。

f:id:mi_kami:20130701233908p:plain

開発中の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が出る事がある。

Option型とは

Play Framework Starter Guideを読み進めていてScalaでOption型というものがよく使われていることに気付いた。軽くメモ。

Optionクラスとは

Option型とは値があるかないかを表すクラスで、caseクラスと組み合わせてよく利用される。まだうまくまとめられてないのでまた後日追記予定。

(参考)

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仮想マシン仕様から読み取れたこと

型はコンパイル時の概念である

変数や式には型がある。しかしオブジェクトや配列には型が無く、その代わりにクラスに属している。

Java仮想マシン仕様 第2版 P14

型とは

プログラミング言語Javaは強く片付けされた(strongly typed)言語、つまりすべての変数や式の型がコンパイル時に決定出来る言語である。型とは、変数が保持する値、あるいは式が生成する値を制限し、それらの値に対する演算を制限し、また操作の意味を決定するものである。

Java仮想マシン仕様 第2版 P6

変数とは

変数(variable)とは、記憶領域のことであり、コンパイル時の型(compile-time type)と呼ばれるプリミティブ型($2.4.1)や参照型($2.4.6)といった型に対応づけられている。変数には、常にその型に対して代入互換性($2.6.7)のある値が保持される。プリミティブがたの変数には、常にそのプリミティブ型の値が保持される。参照型の変数には、null参照、あるいはその変数の型に対して代入互換性($2.6.7)のあるクラスの任意のオブジェクトへの参照を保持させることができる

Java仮想マシン仕様 第2版 P11

推測

クラス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件) を見る

これでも買うか...。