チューニング②「オブジェクトの配列化」
2つめに紹介するのは、オブジェクトを生成する代わりにすべて配列化するという、少々強引なチューニング方法です。Javaらしさを完全に失ってしまうため、本当に速度が必要な場合以外は利用するべきではありませんが、チューニングとしてはそれなりの効果が出ます。
今回配列化の対象としたのは、Field という盤面を表すクラスです。Field クラスはループ検出と双方向探索の突き合わせに利用しています。探索を進めて移動を繰り返すと、しばしば同じ盤面に戻ることがあります。そこからさらに探索を進めてしまうとループして、それ以降の探索は無駄になってしまいます。それを防止するために、過去に登場した盤面を記録しておき、移動のたびに過去の盤面に存在しないことを確認しています。また、今回のアルゴリズムは双方向探索を採用しているため、順方向探索の盤面が逆方向探索の盤面に存在する、もしくはその逆ならゴールへの経路が見つかったことになります。その検出にも Field クラスを利用しているため、Field クラスはアルゴリズムの中核をなす重要なクラスです。
利用できるヒープ領域には制限があるため、今回は40万件までという制限を設けていますが、Field クラスはアプリ中で最もメモリを消費するクラスでもあります。
Field クラスの定義は次のとおりです。field、hashCode、operationCount、currentOperation、operations という5つのインスタンス変数を持ちます。
public static class Field {
// 盤面
private int[] field;
// equalsの呼び出し回数が多いのでhashCodeを事前に計算して保持しておく。
// 盤面（field）のみに依存
private int hashCode;
// 移動の回数
private short operationCount;
// 移動の記録（アクティブ）、operationsと合わせることで完全な移動の履歴になる
private byte currentOperation;
// 移動の記録（非アクティブ）、immutable。
// 子孫およびFieldOperationと同一オブジェクトを共有する
private byte[] operations;
public Field(FieldOperation fieldOperation) {
init(fieldOperation);
}
…
…
…
}
配列化した Field クラスは実体を持たなくなりますが、利便性のためにクラス自体は残して配列内の位置情報などを持つように変更しました。
public static class Field {
// 盤面
public static final int FIELD_OFFSET = 0;
public static final int FIELD_SIZE = 8;
// equalsの呼び出し回数が多いのでhashCodeを事前に計算して保持しておく。
// 盤面（field）のみに依存
public static final int HASH_CODE_OFFSET = 8;
// 移動の回数
public static final int OPERATION_COUNT_OFFSET = 9;
// 移動の記録（アクティブ）、operationsと合わせることで完全な移動の履歴になる
public static final int CURRENT_OPERATION_OFFSET = 10;
// 移動の記録（非アクティブ）、immutable。
// 子孫およびFieldOperationと同一オブジェクトを共有する
public static final int OPERATIONS_OFFSET = 11;
public static final int OPERATIONS_SIZE = 12;
public static final int FIELD_ARRAY_SIZE = FIELD_SIZE + OPERATIONS_SIZE + 3;
public static int[] newField() {
return new int[FIELD_ARRAY_SIZE];
}
…
…
…
}
盤面（ Field ）を表すには、1オブジェクトあたり int 配列で23要素に、ハッシュ表を管理する情報の2要素を加えて合計25要素が必要です。そこで 400,000 * 25 + 1、つまり 10,000,001要素の int 配列を確保します。確保する容量は膨大ですが、プリミティブ型の配列は全体で1オブジェクトなので、GCに与える負荷はさほど大きくありません。
配列の利用イメージは図2のようになります。
エラー処理のために先頭アドレスである0は空けておき、1から利用します。1つの Field オブジェクトを表すには巨大な配列とその中の開始アドレスを指定することで特定します。例えば、hugeArray を40万件の Field オブジェクトを保持する巨大な配列とすると、100番目のオブジェクトは hugeArray[2476] ～ hugeArray[2500] の範囲にデータが存在し、移動回数を表す operationCount は int operationCount = hugeArray[2476 + OPERATION_COUNT_OFFSET]; という手順で利用します。
配列化した状態で測定した結果が次の表です。
| プール | Field | 処理時間（秒） | 処理速度（問/分） | 速度指標 | |
|---|---|---|---|---|---|
| Dalvik | OFF | 標準 | 38,959 | 7.70 | 1.00 |
| Dalvik | ON | 標準 | 28,529 | 10.52 | 1.37 |
| Dalvik | ON | 配列化 | 16,740 | 17.92 | 2.33 |
| ART | OFF | 標準 | 24,169 | 12.41 | 1.00 |
| ART | ON | 標準 | 21,950 | 13.67 | 1.10 |
| ART | ON | 配列化 | 18,067 | 16.60 | 1.34 |
| PC（Corei5 3.4GHz） | OFF | 標準 | 179 | 1,675.98 | 1.00 |
| PC（Corei5 3.4GHz） | ON | 標準 | 179 | 1,675.98 | 1.00 |
| PC（Corei5 3.4GHz） | ON | 配列化 | 230 | 1,304.35 | 0.78 |
結果を見ると、配列化したパターンはDalvikのパフォーマンスが2.33倍になりました。マーク＆スイープ方式のGCは、ヒープ領域に存在するオブジェクトをすべて探索してマークした後にマークの付いていないオブジェクトを解放（スイープ）します。そのため、生存オブジェクトの数が極端に多いと、GCのたびに探索コストがかかり効率が悪くなります。
Field クラスのチューニングで、前項のオブジェクトプールではなく配列化という手法を採用したのは「オブジェクトの数」が理由です。生存オブジェクトが極端に多い場合、オブジェクト数を減らすほうがチューニングの効果が高くなることが分かります。
ここで示した例は、1つのクラスを丸ごと配列化するという少々乱暴な手段でしたが、細かいオブジェクトの生成をなるべく減らし、配列化するという方法はパフォーマンス改善に有効です。
また、PCでも速度比較したところ、配列化バージョンはパフォーマンスが大幅に低下しました。この結果は想定どおりで、配列化したバージョンはメモリ上の物理的な位置が固定されるため、参照渡しではなく値渡しのような動作が一部で必要になります。つまり、実際の処理内容としては元の処理よりもオーバーヘッドが大きくなっています。Dalvik/ARTでは、そのオーバーヘッドよりもGCによる負荷のほうが大きいために高速化しましたが、「ヒープ領域が潤沢」「世代別GCが機能」「CPUの余剰コアがある」というPC環境ではGC負荷が大きくなかったため、むしろオーバーヘッドによって性能劣化したと考えられます。
