チューニング①「オブジェクトプールの導入」
Dalvik/ARTのヒープ領域管理が分かったところで、実際にチューニングを行います。まずは、スライドパズルを探索する間にGCがどれくらい動作しているかを測定してみます。
| GC種別 | 回数 | 停止1（秒） | 停止2（秒） | GC停止合計（秒） | GC稼働合計（秒） |
|---|---|---|---|---|---|
| GC_FOR_ALLOC | 2,884 | 1,434.6 | - | 1,434.6 | 1,434.6 |
| GC_CONCURRENT | 3,691 | 6.6 | 119.8 | 126.4 | 784.0 |
| GC_EXPLICIT | 0 | 0.0 | 0.0 | 0.0 | 0.0 |
| GC_BEFORE_OOM | 0 | 0.0 | - | 0.0 | 0.0 |
| WAIT_FOR_CONCURRENT_GC | 3,527 | 0.0 | - | 723.2 | 723.2 |
上記の表は、アプリを実行させて最初の500問の探索をする間に発生したGCの内訳です。その間の実行時間は4,448秒でした。各GCの動作は次のとおりです。
GC_FOR_ALLOC[1]
前節でも出てきましたが、オブジェクトを生成しようとしたスレッド自身がGCを行い、コンカレント動作を行わないため、GC全体にわたってスレッドが停止します。
GC_CONCURRENT
バックグラウンドのGCスレッドが処理を行い、その中で2回、全スレッドをわずかに停止します。
GC_EXPLICIT
GC_CONCURRENTとほぼ同じ動作をしますが、開発者が明示的に System.gc() をコールした際に発生します。
GC_BEFORE_OOM
OutOfMemoryErrorの直前に行われる最後の砦となるGCです。「普通にヒープ領域を確保しようとして失敗」 → 「GC_FOR_ALLOCを発生させてから再度ヒープ領域を確保に失敗」 → 「ヒープ領域を拡張してから領域の確保に失敗」と、3回の確保に失敗したら起動されます。基本的な動作はGC_FOR_ALLOCと同様ですがSoftReferenceを解放するという点のみ異なります。
WAIT_FOR_CONCURRENT_GC
厳密にはGCではありませんが、GC_FOR_ALLOCが発生するタイミングでコンカレントGCが稼働中だった場合にその実行完了を待つので、パフォーマンスへの影響としてはGC_FOR_ALLOCとほぼ同様です。
なお、Dalvikでは、アプリに対してデバッガが接続されていたらGC_CONCURRENTが動作しないので、この測定はデバッガが接続されていない状態で行う必要があります。
[1] 前節では「GC_FOR_MALLOC」と表記していましたが、ここでは「GC_FOR_ALLOC」となっています。これはオブジェクトの生成からメモリ確保までの流れで、Dalvikのソースコードが表記揺れしていることが原因です。変数や関数名にはGC_FOR_MALLOCが使われていますが、文字列として定義されているGC名はGC_FOR_ALLOCとなり、ログなどではGC_FOR_ALLOCが使われます。
細かい事情は推測するしかありませんが、Javaに近い層からはオブジェクトのアロケーションでallocという名称が多く用いられ、より下層にいくとmalloc/calloc系の命名が多用され、中立的な立場であるGCはその表記揺れのちょうど中間で混じってしまったのかもしれません。
結果を見ると、4,448秒の稼働に対して51％にもあたる2,284秒がGCに費やされ、その中でも特に多いのがGC_FOR_ALLOC/WAIT_FOR_CONCURRENT_GCです。GC_CONCURRENTもGC稼働時間としては多いのですが、全スレッドを停止させるのはGC停止合計である126.4秒なので、パフォーマンスをさほど劣化させていません。
DalvikでGC_FOR_ALLOC/WAIT_FOR_CONCURRENT_GCが多くなってしまう理由には、メモリをなるべく節約する方向に最適化されていることが挙げられます。メモリの少ない端末で複数のアプリを同時に動かすための最適化として、このアプローチをとることは間違ってません。しかし逆にいうと、メモリを多めに確保した上での最適化は不得意です。
例えば、Nexus7（2013）では、確保しておく余剰ヒープ領域の上限値（dalvik.vm.heapmaxfree）が8MBと設定されています。そのため、ヒープ領域の確保容量に余裕があっても、現在の使用量＋8MBを超えるとsoftLimit[2]という制限に引っかかり、GC_FOR_ALLOC/WAIT_FOR_CONCURRENT_GCが実行されます[3]。つまり、現在のヒープの空き領域とは関係なく、8MB分のオブジェクトを生成するたびに、パフォーマンスへの影響が大きなGC_FOR_ALLOC/WAIT_FOR_CONCURRENT_GCが実行されることになります。これはDalvikにおけるパフォーマンス劣化の大きな原因ですが、この制限を非root権限のアプリから回避する方法はありません。
そこで、チューニングの方向性として、GCの発生回数を減らすためになるべく新しいオブジェクトを生成しない方法を考えてみます。キーポイントは、余剰ヒープ領域である8MBの壁を突破してGC_FOR_ALLOC/WAIT_FOR_CONCURRENT_GCが発生するよりも前にGC_CONCURRENTが完了することです。これができれば、GCでの待ち時間は減少します。
[2] softLimitはGC_FOR_ALLOCを起動する閾値となるヒープ使用量（オブジェクトがアロケートされている容量）が設定されます。一方、GC_CONCURRENTが起動するヒープ使用量の閾値は
softLimit - 131072と設定されるため、GC_CONCURRENTが終了する前に131,072バイト以上確保してしまうとWAIT_FOR_CONCURRENT_GCが発生します。[3] 説明を簡略化するために余剰ヒープ領域としてdalvik.vm.heapmaxfreeのみを挙げましたが、実際にはdalvik.vm.heaptargetutilizationとdalvik.vm.heapminfreeも関わってきます。ただし、ある程度のヒープ領域を確保しているアプリではすぐにオーバーフローするため、dalvik.vm.heapmaxfreeのみに依存します。
最初に紹介するのは、不要になったオブジェクトをプールして再利用するという古典的なテクニックです。
次のソースコードは、オブジェクトをプールするために作成したシンプルなクラスです。
public static class MemoryPool<T> {
private Object[] pool;
private int index = 0;
private int poolSize;
private Class<T> initializer;
public MemoryPool(Class<T> initializer) {
// プールサイズの初期値、不足すれば自動拡張するので少なめの数を適当に設定
this.poolSize = 1 << 4;
pool = new Object[poolSize];
try {
for (int i = 0; i < poolSize; ++i) {
pool[i] = initializer.newInstance();
}
} catch (InstantiationException | IllegalAccessException e) {
throw new RuntimeException();
}
this.initializer = initializer;
}
public void trash() {
index = 0;
}
@SuppressWarnings("unchecked")
public T get() {
if (index >= poolSize) {
// プールサイズを超えてget()要求が来た場合、
// プールを構成する配列を2倍の容量で生成し直して
// 元の配列からオブジェクトをコピーしてから、
// 増やした領域のオブジェクトをまとめて生成する
int newPoolSize = poolSize << 1;
if (newPoolSize <= poolSize) {
// intのオーバーフロー、対応しない
throw new RuntimeException();
}
Object[] newPool = new Object[newPoolSize];
System.arraycopy(pool, 0, newPool, 0, poolSize);
poolSize = newPoolSize;
pool = newPool;
try {
// 今回増加した分のオブジェクトをまとめて生成
for (int i = index; i < poolSize; ++i) {
pool[i] = initializer.newInstance();
}
} catch (InstantiationException | IllegalAccessException e) {
throw new RuntimeException();
}
}
return (T) pool[index++];
}
}
このクラスは生成時にオブジェクトをまとめて生成しておき、get() メソッドでプールからオブジェクトを取得します。プールが枯渇した場合には2倍の容量で内部配列を作り直し、増加分のオブジェクトを追加で生成します。プールから取得したオブジェクトが不要になったら、trash() メソッドですべて再利用可能にします。この方式はオブジェクトの利用に一定の周期があり、その周期ごとにすべてのオブジェクトを解放できるたぐいの処理に向いています。また、各オブジェクトの解放のタイミングを管理する必要がないので処理が簡潔になる、という利点もあります。
シンプルで軽快なオブジェクトプール
プール管理の方法は他にもあります。各オブジェクトの解放タイミングが明確な場合、すぐに思いつく方法は java.util.LinkedList クラスを利用して、オブジェクトが不要になったら add() メソッドでプールに入れ、新しいオブジェクトが必要になったら poll() メソッドでオブジェクトを取り出すという方法です。しかし、この方法には問題があります。LinkedListクラスはその構造上、オブジェクトを追加するたびに内部で新しい管理用オブジェクトを1つ生成してしまいます。そのため、オブジェクトの生成を1つ削減するために新規オブジェクトを1つ生成するという、本末転倒な事態になります。
そこで、単純に追加と取得のみを行うMemoryPoolの実装を紹介します。
public static class MemoryPool<T> {
private Object[] pool;
private int index = 0;
private int poolSize;
public MemoryPool() {
// プールサイズの初期値、不足すれば自動拡張するので少なめの数を適当に設定
this.poolSize = 1 << 4;
pool = new Object[poolSize];
}
public void add(T o) {
if (index >= poolSize) {
// プールサイズを超えてadd()要求が来た場合
// プールを構成する配列を2倍の容量で生成し直して、
// 元の配列からオブジェクトをコピーする
int newPoolSize = poolSize << 1;
if (newPoolSize <= poolSize) {
// intのオーバーフロー、対応しない
throw new RuntimeException();
}
Object[] newPool = new Object[newPoolSize];
System.arraycopy(pool, 0, newPool, 0, poolSize);
poolSize = newPoolSize;
pool = newPool;
}
pool[index++] = o;
}
@SuppressWarnings("unchecked")
public T get() {
if (index <= 0) {
return null;
}
return (T) pool[--index];
}
}
オブジェクトが不要になったタイミングで add() メソッドでプールに追加し、オブジェクトが必要になったら get() メソッドでプールから取得します。ここでは専用のクラスを用意しましたが、実は後者の実装の代わりに java.util.ArrayList クラスを利用することも可能です。
ArrayListとLinkedListの違いをちゃんと理解していない方も多いと思われるので、速度特性を説明します。
| クラス | 先頭に追加 | 末尾に追加 | 中央に追加 | ランダム位置に追加 | ランダム位置を取得 | 先頭を削除 | 末尾を削除 | 中央を削除 | ランダム位置を削除 |
|---|---|---|---|---|---|---|---|---|---|
| ArrayList | O(n) | O(1) | O(n/2) | O(n/2) | O(1) | O(n) | O(1) | O(n/2) | O(n/2) |
| LinkedList | O(1) | O(1) | O(n/2) | O(n/4) | O(n/4) | O(1) | O(1) | O(n/2) | O(n/4) |
まず指標の説明として、O(n/2)という表現は本来意味をなしませんが、比例する係数も表したかったので便宜上付けています。つまり、ArrayList のO(n/2)と LinkedList のO(n/4)を比較して LinkedList のほうが高速という比較は不正ですが、LinkedList の中央に追加O(n/2)とランダム位置に追加O(n/4)ではランダム位置に追加のほうがおおよそ2倍程度高速というのは期待できます。
表を確認すると、ArrayList は末尾に追加・削除とランダム位置の取得が高速ですが、ランダム位置への追加・削除は不得意です。一方、LinkedList はランダム位置の追加・削除・取得の際に先頭もしくは末尾の近い方向からたどるため、中央が最も性能劣化をするポイントで平均するとO(n/4)となります。
速度特性としては、ランダム位置の取得を除いて LinkedList が優勢に見えますが、前述のとおり LinkedList は内部的に管理オブジェクトを作成するなど基本負荷が高いので、今回の用途では採用できません。一方で、ArrayList は末尾に追加と末尾を削除がO(1)で可能なため、単純なプールとして利用できます。プールとしての利用例としては、オブジェクトを追加する際には pool.add(o) とし、プールから取得する際には pool.size() > 0 ? pool.remove(pool.size() - 1) : null; とします。プールからの取得時の書き方が少々直感的でないのが難点ですが。
オブジェクトプール導入の効果
さて、それではアプリのチューニングを行います。スライドパズルの探索エンジンでは、盤面と移動経路を表す FieldOperation オブジェクトが、最も短い期間で生成と解放を繰り返します。そこで、FieldOperation オブジェクトの生成をプール利用に切り替えてテストした結果が次の表です。
| 実行環境 | プール | 処理時間（秒） | 処理速度（問/分） | 速度指標 |
|---|---|---|---|---|
| Dalvik | OFF | 38,959 | 7.70 | 1.00 |
| Dalvik | ON | 28,529 | 10.52 | 1.37 |
| ART | OFF | 24,169 | 12.41 | 1.00 |
| ART | ON | 21,950 | 13.67 | 1.10 |
| PC（Corei5 3.4GHz） | OFF | 179 | 1,675.98 | 1.00 |
| PC（Corei5 3.4GHz） | ON | 179 | 1,675.98 | 1.00 |
速度指標は、各実行環境のプールOFFの状態を基準とした数値です。プールを利用すると、DalvikとARTともに顕著に高速化していることが分かります。興味深いのはDalvikのほうが高速化の効果が高い点です。ARTはDalvikに比べGCが優秀なので、DalvikほどにはGCチューニングによる高速化の余地がないのです。
一時オブジェクトが大量に必要で、かつGCが頻発しているアプリにおいて、このチューニング方法は手軽な上に効果的です。
なお、PCでは両者に有意な差はでませんでした。なぜなら、PCでは世代別GCが機能するため、短命オブジェクトの生成と解放のコストは限りなく少ないからです。
