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

○Javaバイトコード

Javaは仮想機械 (Virtual Machine) と呼ばれる処理系の上で実行される.  こ
の仮想機械が入力とするプログラムの実行形式のことをJavaバイトコードと呼
ぶ.  Javaバイトコードは, その名の通り, 各命令が1バイトに納まるように定
義されている.  本演習では, 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	// もしスタックの最上位(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がデータを使用していないとみなすタイミングは, 
  1. ローカル変数がそのスコープ (関数やブロック) を抜けた後
  2. 明示的に null を代入した後
がある. メモリを多く使用するプログラムにおいては, その値が必要なくなった
ところで null を代入してメモリの回収を促進することが効果的である.

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

○本日の課題

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

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

補足: 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;
  }
}

課題33 (挑戦): ごみ集めをシミュレートするプログラムを作成せよ. 入力の
データであるヒープの割り当ては, 次の形式で与えられる.
    * allocate <変数番号> <サイズ> // 変数番号にサイズ分の領域を割りあてる
    * substitute <変数1> <変数2>   // 変数1から変数2を参照する
    * remove <変数1>               // 変数1の領域を削除する

例えば, 次のプログラム
    a = new int[10];
    a[1] = new int[5];
    a = null;
に対応する入力は
    alloate 2 10  
    substitute 1 2            // スタック(1)にa(2)を代入
    allocate 3 5
    substitute 2 3
    remove 2
となる.

問題を簡単にするために次を仮定して良い.
    * 変数番号は, 1から9とする (1はスタックと考え, 常に存在する)

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