−−−−−−−−−−−−−−−−−−−−−−−
−−−　第９回数理情報演習　Java処理系　−−−
−−−−−−−−−−−−−−−−−−−−−−−

○Javaバイトコード

Javaは仮想機械 (Virtual Machine) と呼ばれる処理系の上で実行される.  こ
の仮想機械が入力とするプログラムの実行形式のことをJavaバイトコードと呼
ぶ.  Javaバイトコードは, その名の通り, 各命令が1バイト (=8ビット) に納
まるように定義されている.  本演習では, Javaバイトコードを実際に見てプロ
グラムがどのように実行されるのかを勉強する.

Javaバイトコードを読み易くしたものを出力するには, 例えばプログラムが
Sum.javaであるとき,
    javac Sum.java
    javap -c sum
とすることで標準出力に出力される.

// ---- Sum.java ----
public class Sum {
  public static void main( String[] args ) {
    System.out.println( sum( 20 ) );
  }

  static int sum( int n ) {
    int total = 0;
    for ( int i = 0; i < n; i++ ) {
      total += i;
    }
    return total;
  }
}

// ---- バイトコードを読み易くしたもの ----
Compiled from "Sum.java"
public class Sum extends java.lang.Object{
public Sum();
  Code:
   0:	aload_0
   1:	invokespecial	#1; //Method java/lang/Object."<init>":()V
   4:	return

public static void main(java.lang.String[]);
  Code:
   0:	getstatic	#2; //Field java/lang/System.out:Ljava/io/PrintStream;
   3:	bipush	20
   5:	invokestatic	#3; //Method sum:(I)I
   8:	invokevirtual	#4; //Method java/io/PrintStream.println:(I)V
   11:	return

static int sum(int);
  Code:
   0:	iconst_0
   1:	istore_1
   2:	iconst_0
   3:	istore_2
   4:	iload_2
   5:	iload_0
   6:	if_icmpge	19
   9:	iload_1
   10:	iload_2
   11:	iadd
   12:	istore_1
   13:	iinc	2, 1
   16:	goto	4
   19:	iload_1
   20:	ireturn

}

以下, 関数 sum(int) について説明を加える. 
1. 左端の数字はその命令の出現バイト位置である. 例えば, 
       9:  iload_1
   は, 9バイト目にあることを示している. 各命令は1バイトであるが,
   引数 (オペランドと呼ぶ) をとる場合には出現バイト位置は連続しない.
2. 変数は出現順に番号で管理される. この場合には,
      変数番号  変数名
      0         n
      1         total
      2         i
   という対応となる.

static int sum(int);
  Code:
   0:	iconst_0		// スタックに0をpush
   1:	istore_1		// 変数1(total)にスタックからpop
   2:	iconst_0		// スタックに0をpush
   3:	istore_2		// 変数2(i)にスタックからpop
   4:	iload_2			// スタックに変数2(i)をpush
   5:	iload_0			// スタックに変数0(n)をpush
   6:	if_icmpge	19	// スタックの上から2つめ (i) が1つめ (n) 以上なら19へ
   9:	iload_1			// スタックに変数1(total)をpush
   10:	iload_2			// スタックに変数2(i)をpush
   11:	iadd			// 和を計算(total + i)
   12:	istore_1		// 変数1(total)にスタックからpop
   13:	iinc	2, 1		// 変数2(i)をインクリメント(++)
   16:	goto	4		// 4へ移動
   19:	iload_1			// スタックに変数1(total)をpush
   20:	ireturn			// 整数値を返す

変数テーブルとスタックの状況を追うことで仮想機械の動作が見えてくるはずである.

○Java仮想機械のメモリ管理

Java仮想機械は, スタックとヒープと呼ばれる2つのメモリ空間を持つ.
 - スタック: スタック構造によって管理され, 関数呼び出しと関数内のロー
   カル変数 (プリミティブ型, 参照) などを保持する.
 - ヒープ: スタックで管理されないすべての実体が管理される. 特に, new
   で確保されるオブジェクトはすべてヒープにとられる.

スタックと異なり, ヒープの割り当て位置には特に制限がないため, ヒープ上で
メモリの確保を繰り返すと実際には使っていない領域でヒープが埋まっていく.
この使っていない領域を再利用できるようにすることをごみ集め (Garbage
Collection) と呼ぶ. Javaの場合には, 基本的に自動で行われるため, プログラ
マがメモリの管理を意識する必要はない. これはJava言語の一つの特徴である.

Javaがデータを使用していないとみなすタイミングは, 
  1. ローカル変数がそのスコープ (関数やブロック) を抜けた後
  2. 明示的に null を代入した後
がある. メモリを多く使用するプログラムにおいては, その値が必要なくなった
ところで null を代入してメモリの回収を促進することが効果的である.

Javaの仮想機械ヒープサイズを変更するには, 
    java -Xmx256m Sum
と -Xmx オプションを使って指定する. 上記において, オプションの後の数字は,
256 MByte確保するという意味である.

○本日の課題

課題32 (必須): 自分の課題2のJavaプログラムに対して, javap -c として生成
したバイトコードにコメントをつけよ. コメントは計算のメインの部分だけで
良いが, 余力のある者はすべてにコメントをつけてもよい. 提出はもとのプロ
グラムとコメントをつけたテキストファイルとする.

課題33 (必須): 以下のプログラム BadProgram.java はメモリ効率が非常に
良くない.  このプログラムは, java -Xmx2m BadProgram では動作しない.
(java -Xmx8mでは動作するが) このプログラムを, java -Xmx2m の環境で動作
するように書き換えよ.  java -Xmx2m というオプションをつけて提出せよ.

補足: BadProgram.javaは, オプションを指定しない場合には動作します. 
(環境によるが, ヒープは12MByte程度は確保される) 問題の意図は, このヒー
プの大きさを限定した環境の上で動作するようにしてもらいたいということで
ある. コードに加える変更は処理の内容が変わらないようにすること.

// ---- BadProgram.java ----
class BadProgram {
  public static void main( String[] args ) {
    double[][] numbers = new double[1000][1000];
    double[]   vars    = new double[1000];

    for ( int i = 0; i < 1000; i++ ) {
      for ( int j = 0; j < 1000; j++ ) {
	numbers[ i ][ j ] = i * j + 1;
      }
      vars[ i ] = computeVariance( numbers[ i ] );
    }

    double ave = 0;
    for ( int i = 0; i < 1000; i++ ) {
      ave += vars[ i ];
    }
    ave /= 1000;

    System.out.println( ave );
  }

  static double computeVariance( double[] numbers ) {
    double ave = 0;
    for ( int i = 0; i < 1000; i++ ) {
      ave += numbers[ i ];
    }
    ave /= 1000;

    double var = 0;
    for ( int i = 0; i < 1000; i++ ) {
      var += ( numbers[ i ] - ave ) * ( numbers[ i ] - ave );
    }
    var /= 1000;
    return var;
  }
}


課題34 (挑戦): ごみ集めをシミュレートするプログラムを作成せよ. 入力の
データであるヒープの割り当ては, 次の形式で与えられる.
  * a <変数記号> <サイズ> // 変数記号にサイズ分の領域を割りあてる (allocate)
  * r <変数1> <変数2>     // 変数1から変数2を参照する (refer)
  * k <変数1> <変数2>     // 変数1から変数2の参照をなくす (kill)
問題を簡単にするために次を仮定して良い.
  * 変数記号は, BからZとする (変数Aをスタックと解釈する)
例えば下記のような入力が渡される, (//以下はコメントで入力には含まない)
  a B 10    // 変数Bにサイズ10をわりあてる  (1)
  r A B     // 変数Aから, 変数Bを参照する   (2)
  a C 10    // 変数Cにサイズ10をわりあてる  (3)
  r B C     // 変数Bから, 変数Bを参照する   (4)
  k A B     // 変数Aから変数Bの参照をなくす (5)
  a D 10    // 変数Dにサイズ10をわりあてる  (6)
これに対して, あるプログラムの動作は
  (1) BBBBBBBBBB__________ : 
  (2) BBBBBBBBBB__________ : A->B
  (3) BBBBBBBBBBCCCCCCCCCC : A->B
  (4) BBBBBBBBBBCCCCCCCCCC : A->B, B->C
  (5) BBBBBBBBBBCCCCCCCCCC : 
  <<<GC Occurred>>
  (6) DDDDDDDDDD__________ :
となるであろう.

入力を取って, その過程を出力するプログラムを作成すること.  提出には,
java XXX < iuput.txt として実行せよ.  データの出力形式, ごみ集めの方法
については特に指定しないので, 適切な方法を採用してくれれば結構である.
ごみ集めをした場合にヒープ領域のサイズは20で足りるようにデータを作って
おきます.