-1-
Java 標準ライブラリを対象とした配列参照の最適化
Optimization Techniques for Array References in the Java Standard Library
情報工学専攻 柳 優 Yu YANAGI 概要 本論文では，Java標準ライブラリ内にある配
列参照向けの最適化技法を提案する．本提案の目的は，
従来のデータフロー解析では削除しきれなかったが 冗長なnull 検査および配列添字検査を削除すること により，Javaアプリケーションの実行速度向上をは かることである．Java標準ライブラリ内でおこなわ れる null検査および配列添字検査には，リフレクシ ョンやネイティブメソッドが動作しているか否かで，
冗長か否かが決まる箇所が多い．そこで，リフレクシ ョンやネイティブメソッドの振る舞いを監視するこ とにより，これらのnull 検査および配列添字検査の 削 除 を 可 能 に し た ． SPECjvm98 お よ び
SPECjbb2005を用いた評価の結果から，提案技法に
よって実行速度を最大で 2.74%高速化できることが 判った．
1. はじめに
Java における実行時オーバヘッドの発生原因の 1 つに，セキュリティ機能の強化を目的として配列参照 に先だって行われるnull検査や配列添字検査がある．
しかし，この null検査と配列添字検査は，配列参照 の度に必ず必要なものではなく，冗長とみなせる場合 には削除することにより，Javaプログラムの実行速 度向上を図ることが可能である．
冗長なnull検査および配列添字検査を削除する技 法は既に多く提案されており，その1つにデータフロ ー解析を用いた最適化がある．しかし，従来のデータ フロー解析を用いた技法では，コンパイラによる解析 が困難な場合も多く，冗長な検査が削除しきれない．
より多くの冗長な検査を削除可能にするためには，デ ータフロー解析系の強化をすることも可能だが，ほと んど有用にならない解析系を実現しても，逆にコンパ イル時間に影響を与えてしまい，新たな実行時オーバ ヘッドの原因となってしまう．
そこで本提案では，Java標準ライブラリ内にある 配列参照に特化した最適化技法を提案する．Java標 準ライブラリ内でおこなわれる null検査および配列 添字検査の中には，従来のデータフロー解析では削除 できないが冗長なものや，リフレクションやネイティ ブメソッドの影響さえ受けなければ冗長になるもの がある．本提案では，解析系を用いずにこれらの冗長 な検査を削除可能にする技法を示す．
2. 関連事項
2.1 Javaにおける配列参照
本節では，Java における配列参照の動作仕様を示 す．Javaにおける配列参照の記述を図 1 (a)に，その 動作仕様をCのコードで書いたものを図 1 (b)に示す．
(a) Javaによる配列参照の記述
(b) 配列参照の実現
図 1 Javaにおける配列参照の実現 図 1(a)のとおり，Javaにおける配列参照の記述は
C や C++における配列参照と見た目は同じである．
そこで，その動作仕様を考える．
図 1 (b)から，Javaにおける配列参照では2つの例 外処理，まず最初に配列へのポインタbyte_arrayが nullではないかを検査するnull検査をおこない，続
いて添字 index が不正なメモリ参照をしていないか
を検査する配列添字検査をおこなうことが判る．これ らの検査は，セキュリティ面を強化する目的で付加さ れているが，C や C++ではおこなわれていない検査 であるため，Java における実行時オーバヘッドの一 因となっている．しかしながら，これらの検査は必ず しも必要な検査ではなく，冗長と見なせる場合には削 除する事が可能である．
2.2 リフレクションおよびネイティブメソッド リフレクションおよびネイティブメソッドは，アク セス指定子privateやfinalなどの可視範囲の制限を 無視して，インスタンス変数を書き換え可能な機能で ある．したがって，null検査および配列添字検査が冗 長か否かを決定する際に，これらの機能との関係を考 える必要がある．
3. 既存の最適化技法
本章では，冗長な null検査および配列添字検査の 削除に関する既存の最適化技法を概観する．
1: //null検査
2: if(byte_array == NULL)
3: 例外発生;
4: //配列添字検査 5: if((index < 0) ||
6: (byte_array->length<=index)) 7: 例外発生;
8: //配列参照
9: value = byte_array[index];
1: value = byte_array[index];
-2- 3.1 データフロー解析を利用した最適化技法
データフロー解析を利用した最適化は，既に多くの Java 向けコンパイラに実装されており，プログラム 中のデータの流れを解析することによって，冗長と判 断できる null検査および配列添字検査を削除する．
データフロー解析によって削除可能なnull 検査およ び配列添字検査を含むコードの例を図 2に示す．
図 2の3行目では配列参照がおこなわれており，
ここでも図 1(b)で示したとおり配列参照に先だって null検査および配列添字検査がおこなわれるが，ここ での null検査および配列添字検査は削除が可能であ る．まず，null検査に関しては，1行目でローカル変 数byte_arrayが非nullの値に初期化されており，他 にローカル変数 byte_array を上書き(変更)する箇所 がないため，3行目のnull検査は削除可能である．
また，配列添字検査に関しては，配列の添字iの値域 は for ル ー プ 全 体 を 解 析 す る と 0 ≦ i<byte_array.length であることが判るため，この配 列添字検査も削除可能である．この例のように，解析 が可能な場合にはデータフロー解析によって冗長な null検査と配列添字検査を削除することができる．
また，他にもデータフロー解析を利用した最適化技 法がいくつか提案されている．その例を次に示す．
Field Analysisを利用した最適化技法[1]
Related Field Analysisを利用した最適化技法[2]
3.2 クラスファイルへの指示文の付与
クラスファイルへ指示文を付与することで，null 検査および配列添字検査の削除をおこなう技法があ る．この技法の1つは，Pominvilleらによって提案 されたものであり，クラスファイルに予め最適化対象 となる箇所の情報を付与しておき，動的コンパイラが この情報を解釈して最適化を適用する．
3.3 暗黙のnull検査
暗黙のnull検査は，川人らによって提案された技 法であり，null検査のための比較，分岐命令を省略し，
代わりに，ページトラップを使って例外を検出するこ とで，実行時オーバヘッドを軽減する最適化技法であ る．ここでページトラップとは，確保済みのアドレス 以外をアクセスした際に発生する権限違反を検出す る機能である．
4. null検査および配列添字検査の削除
本章では，冗長なnull 検査および配列添字検査の 削除にあたって問題となる点を明らかにするために，
Java 標準ライブラリのメソッドをとりあげ，その内 部にある検査の削除を困難にする要因を示す．データ
フロー解析を利用した最適化では削除できない検査 を含む配列参照はたとえば次のメソッド中にあるこ とが確認済みである．
java.lang.String.charAt()
java.lang.Long.getChars()
本章では，1つ目のString.charAt()をとりあげる．
4.1 java.lang.String.charAt()
クラスjava.lang.Stringは文字列を表しており，そ のメソッドcharAt(int i)は文字列から引数iで指定さ れたインデックス位置にある要素を返戻する．メソッ ドcharAt()の実装を図 3に示す．
図 3の13行目では配列参照がおこなわれるが，こ こでの null検査および配列添字検査は多くの場合冗 長になる．まず，null検査が冗長となる理由は，イン スタンス変数valueが，文字列のコンストラクト時に 非 nullの値に初期化され，その後，リフレクション やネイティブメソッドが働かない限り，上書きされる ことはないことがデータフロー解析によって判るた めである．また，配列添字検査が冗長となる理由は，
配列参照に先だって，変数iは10～12行目で文字列 の長さを越えて不正にメモリ参照をしないことを検 査しているからである．
では，13行目におけるnull検査および配列添字検 査が既存の技法によって削除可能か否かを考える．ま ず，null 検査に関しては，3.1 節で示した Field
Analysis を利用した最適化を応用すれば削除可能に
なる．Field Analysisでは，非nullの値に初期化さ れ，その後上書きされないフィールドを求め，このフ ィールドが格納する値に対する null 検査を冗長と判 断可能にする．しかし，リフレクションやネイティブ メソッドによるフィールドの書き換えを考慮してい ないので，そのままでは実用化できない．
一方，配列添字検査に関しては，既存の技法では削 除することができない．なぜなら，13 行目における 配列添字検査を削除するためには，3つのインスタン ス 変 数 value，count，offset 間 に 成 立 す る 関 係 count+offset < value.length を求める必要があるた めである．これに類する技法としては，3.1節で述べ
1: public class String{
2: /*value:配列へのポインタ*/
3: private final char[] value;
4: /* offset:部分配列の先頭の文字までの長さ*/
5: private final int offset;
6: /* count: 部分配列の長さ*/
7: private final int count;
8: ・・・
9: public char charAt(int i) { 10: if ((i < 0) || (i >= count)) { 11: 例外発生;
12: }
13: return value[i + offset];
14: } 15: } 1: int[] byte_array ={1,2,…,n};
2: for(int i=0; i < byte_array.length; i++) 3: System.out.println(byte_array[i]);
図 2 データフロー解析によって 削除可能な検査を含むコードの例
図 3 charAt()の実装
-3- た Aggarwal らによって提案された Related Field Analysis がある．Aggarwalらの提案では，1つの配 列の長さと，1つの整数型のインスタンス変数間に成 立する関係を解析し，この結果を使って配列添字検査 を削除する．しかし，13 行目における配列添字検査 を削除するためには，1つの配列の長さと，2つの整 数型のインスタンス変数間に成立する関係を求める 必要があるため，Aggarwalらの技法を適用すること はできない．彼らの技法を応用して，3つのインスタ ンス変数間に成立する解析系を作成するという技法 も考えられるが，このような滅多に有用にならない解 析系を作成しても，コンパイル時間が増加するだけで，
実行速度の改善に役立たないという結果を招く可能 性がある．さらに，Aggarwalらの技法でも，リフレ クションやネイティブメソッドから受ける影響を考 慮していないため，そのままでは適用することができ ない．
本節で述べた既存技法の問題点をまとめる．
1. 添字の値域の解析が困難
2. リフレクションやネイティブメソッド向け対策 がおこなわれていない
4.2 提案技法
本節では，4.1節で挙げた既存技法の問題点を解決 する，新たな最適化技法を提案する．
提案技法の概要を図 4に示す．
図 4 提案技法の概要
本提案技法では，既存技法の1つ目の問題点を解決 するために，解析系を作るのではなく，あらかじめ Java 標準ライブラリ中の冗長な検査の所在を動的コ ンパイラに教えておき，この情報を用いて最適化をお こなう．実際にバイトコードを動的コンパイルする際 には，コンパイラに教えておいたものか否かを調べ，
教えておいたものならばnull 検査および配列添字検 査を削除したネイティブコードを生成し，教えておい たものでなければ必要な検査と判断し，これらの検査 を付加したネイティブコードを生成する．この冗長な 検査の所在情報は，実用的なJavaアプリケーション を構成要素とするベンチマーク SPECjvm98[3]およ
び SPECjbb2005[4]を用いてプロファイルをおこな
った結果のうち，CPU使用率が高いメソッドについ て冗長な検査を含むか否かを目視で調査し，収集した．
また，既存技法の2つ目の問題点を解決するために，
リフレクションおよびネイティブメソッドの振る舞 いを監視する機能を追加した．Java 標準ライブラリ 中の配列参照には，リフレクションおよびネイティブ メソッドが働いているか否かで，null検査および配列 添字検査が冗長になるか否かが決まるものがある．た とえ修飾子privateやfinalをつけたメンバ変数であ っても，これらの機能の影響で，可視範囲の制限を無 視して可視範囲の外から値を書き換えられてしまう 可能性がある．そこで，リフレクションおよびネイテ ィブメソッドの振る舞いを監視することにより，これ らの機能が働いていなければ冗長な検査の所在情報 を用いて最適化をおこない，逆にこれらの機能が働い ていれば最適化を適用しない仕組みとした．また，最 適化後に，この監視機能によって，リフレクションや ネイティブメソッドが働いていると判断した場合に は，脱最適化をおこない，これらの検査を含むネイテ ィブコードを生成する仕組みとした．
本提案技法の特徴をまとめる．
欠点
目視により収集をおこなっているため，適用 対象のクラスが限られる．
利点
既存の最適化技法では削除が困難であった null検査および配列添字検査が削除可能．
解析系を用いていないため，コンパイル時間 にもたらす影響が小さい．
4.3 提案技法と既存技法の比較
提案技法と既存技法を比較することで，本提案技法 の有効性について示す．
本提案技法では，あらかじめ動的コンパイラに教え ておいた箇所しか最適化を適用しないため適用対象 箇所が少ない．汎用性のある最適化技法にするために は，解析系を用いる方が適しているが，滅多に有用に ならない解析系を実現しても，コンパイル時間に影響 を与えるばかりで実行速度に貢献しない可能性があ る．したがって，特殊なケースの最適化をおこなう場 合，汎用的な解析系の実現を目指すより，本提案技法 のように，あらかじめコンパイラに教えておくことで 特定の箇所のみを最適化する方が有益になりうる．
また3.2節で紹介したクラスファイルに指示文を付
与する最適化技法もある．しかし指示文を付与する技 法では，ユーザによる指示文の誤用やセキュリティ上 の問題を引き起こす可能性がある．
最後に，3.3節で示した暗黙のnull検査は，比較と 分岐の省略によって null検査の実行時オーバヘッド を軽減する技法であるが，皆無にする技法ではない．
なぜなら，暗黙の null 検査はメモリ参照命令を分岐 として用いる技法であって，分岐を削除する技法では ないからである．このため，暗黙の null 検査を利用 している Java 実行環境向けの動的コンパイラでも，
他の最適化によって冗長な null 検査の削除を試みる 場合が多い．本研究で改良したJava仮想マシンも暗 黙の null検査だけでなく，既存技法であるデータフ ロー解析や本提案技法による null検査の削除もサポ ートしている．
-4- 5. 実装
5.1 最適化を適用する対象となるメソッド
ベンチマークSPECjvm98およびSPECjbb2005を 用いてプロファイルをおこない，ベンチマークごとに 実行にかかる CPU時間全体の0.1%以上を消費して いるメソッドを求める．そして，これらのメソッドに 含まれる冗長な配列添字検査の所在を目視により調 査した．調査の結果．ベンチマークの実行中に冗長な 配列添字検査をおこなうJava標準ライブラリ中のメ ソッドは合計で16個，その定義元のクラスは合計で 10個であった．
5.2 リフレクションやネイティブメソッドの監視 リフレクションの監視には，リフレクション関係の メソッドgetDeclaredField()，またネイティブメソッ ドの監視には，JNI(Java Native Interface)関連のメ
ソッドGetFieldID()を監視対象とした．そして，それ
ぞれのメソッド内部に返戻値に対応するインスタン ス変数iを実行時システムに通知する処理を追加する ことによって，これらの機能の監視をおこなった．
5.3 最適化の実現 実現の概要を次に示す．
手順1. 5.1 節で述べた最適化の対象となるメソッ ドごとに，TargetOffsets 型のデータ構造 を用意する．このデータ構造は，メソッド 内にある null 検査および配列添字検査が 冗長な配列参照の，バイトコード中での所 在を記憶する役割を果たす．
手順2. 最適化対象のクラスごとに，手順1で用意 したデータ構造へのポインタを格納する 配列を定義する．この配列の長さはクラス 内で宣言されたメソッド数と等しく，この 配列中のn番目に宣言された要素は，Java 仮想マシンによってn番目に呼び出される メソッドのTargetOffsets型のデータ構造 へのポインタである．
手順3. 動的コンパイル時には，メソッドのバイト コードを中間表現に変換する際に，まず初 めに，5.2 節で述べた監視機能によってリ フレクションやネイティブメソッドによ る書き換え対象となっていないかを調べ た後，バイトコード中に最適化対象のメソ ッドがあるか否かを検索する．検索の結果，
最適化対象となるメソッドのデータ構造 が見つかった場合には，中間表現に変換す る過程で，配列参照のバイトコードを発見 するたびに，null検査および配列添字検査 が冗長か否かをデータ構造に問い合わせ る．問い合わせの結果，冗長であると判っ た場合には，検査に対応する中間表現の生 成を省略する．
6. 評価
評価に使用した計算機は，PC(CPU: Intel Xeon
E5320 (1.86GHz Quad Core) × 2，RAM: 4GByte)で あり，OSはAMD64アーキテクチャ向けのCentOS 5，
Java 仮 想 マ シ ン は Sun Microsystems 製 Java Development Kit 1.5に付属のものである．
本研究において実装した最適化が，SPECjvm98お
よびSPECjbb2005の実行性能に与える影響を評価し
た結果を図 5に示す．
図 5 本最適化が実行速度に及ぼす影響 図 5から，本最適化によって冗長なnull検査と配 列添字検査の削除を適用した場合，相乗平均で0.65%
の実行速度向上が得られることが判る．ベンチマーク 項目ごとに実行速度向上率を比較すると，_228_jack で特に最適化の効果が表れており，その実行速度向上 率は2.74%になる．
また，本最適化技法によって動的コンパイルの際に 発生する実行時オーバヘッドの増加率を測定した結 果，全ベンチマークを通して，実行時オーバヘッドの 増加率は相乗平均で0.16%であった．
7. おわりに
Java における配列参照の高速化を目的として，
null 検査および配列添字検査を削除する技法を提案 した．提案技法では，Java標準ライブラリ中のnull 検査および配列添字検査を削除し，また，リフレクシ ョンやネイティブメソッドが最適化の妨げとなるか 否かを決定するために，それらの動的な振る舞いを監 視する．評価の結果から，提案技法によって，実行速 度を最大で2.74%高速化できることが判った．
参考文献
[1] S．Ghemawat，K．H．Randall，and D．J．Scales：
Field Analysis：Getting Useful and Low-cost Interprocedural Information，Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation (PLDI)，
pp.334-344(2000)
[2] A．Aggarwal，and K．H．Randall：Related Field Analysis，Proceedings of the ACM SIGPLAN 2001 Conference on Programming Language Design and Implementation (PLDI)，pp.214-220(2001) [3] Standard Performance Evaluation Corporation：
SPEC JVM98 Benchmarks(1998)，
http://www.spec.org/jvm98/
[4] Standard Performance Evaluation Corporation：
SPECjbb2005(2005)，http://www.spec.org/jbb2005/
