ArrayListは、通常固定されている配列のサイズを拡張しながら利用できる、非常に便利なクラスです。このクラスによって、我々は配列のサイズとメモリを管理するという煩雑な仕事から解放されました。
今回は、ArrayListの初期値を予め確保しておくコンストラクタであるnew ArrayList(int size)のパフォーマンスを検証してみます。
ArrayListの動き
ArrayListは、指定がなければ初期値10で初期化され、addメソッドが呼ばれる度に内部の配列が拡張されます。普段は意識する必要がないのですが、パフォーマンスが少しでも欲しい場合、ここを適切に設定することで改善する可能性があります。
addメソッドの中身
ここで、理解を深めるためにaddメソッドの中身を見てみましょう。パフォーマンスチューニングは、メソッドの内部処理を把握することから始まります。
grepcodeという便利なサイトがあります。このサイトのArrayList.addを抜粋します。
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
ensureCapacityInternalというメソッドが呼ばれています。ここで内部に持っている配列の領域を確保しているわけです。このメソッドの中身も見てみます。
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
更にgrowメソッドが呼ばれていますね。
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
最終的には、elementData = Arrays.copyOf(elementData, newCapacity);の部分で新しい配列が作られています。Arrays.copyOfの内容は割愛しますが、このように、サイズを拡張するためには様々な処理が呼ばれていることがわかります。
パフォーマンスを向上させるには
さて、addメソッドの内部処理をご覧頂ければわかるとおり、ensureExplicitCapacity(int minCapacity)の内部処理でif文が書かれています。これは現在のサイズをminCapacityが超えていればgrowメソッドを実行するという意味の処理です。
つまり、現在のサイズがminCapacity以上であれば、その処理はスキップされるのです。この処理自体はそこまでの負荷ではありませんが、100万件を超えるadd呼び出しが繰り返されている場合は、適切な初期値を設定することにより大幅な性能アップが期待できます。
検証する
それでは、この仮説を検証してみましょう。
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
List<Integer> list = new ArrayList<>();
List<Integer> sizedList = new ArrayList<>(1000000);
perform(list); // 152
perform(sizedList); // 119
}
static long perform(List<Integer> list){
long start = System.currentTimeMillis();
for(int i = 0; i < 1000000; i++){
list.add(i);
}
long end = System.currentTimeMillis();
long result = end - start;
System.out.println(result);
}
}
| 初期値 | 時間(ms) |
|---|---|
| 10 | 152 |
| 1000000 | 119 |
約20％の性能向上が見られます。もちろん、List::addを頻繁に利用するシステムでないと効果は薄いですが、パフォーマンスチューニングとしては有意な結果を得られるようです。
最適な値を探る
ここまでで、ArrayListに初期値を与えればパフォーマンスによい影響を及ぼすことがわかりました。しかし、ただ闇雲にメモリ領域を確保するのはあまりよくない作りです。
現代のプログラムは、優秀なメモリ管理（Garbage Collection）や、潤沢なリソースのおかげで、メモリを昔ほど意識しなくても、高い品質のプログラミングを行えるようになりました。
ですが、メモリの使用効率を意識してプログラミングを行うことは、いわばプログラマにとっての礼節であると言えます。とはいえ、パフォーマンスを重視するのであれば、想定数より少し余裕を持った領域を確保していても文句は言われないでしょう。
ただ、想定値を検証せず、無為に大きい値を確保することは避けるべきです。
たとえば、先ほどの検証コードでは、その後のコードで100万件のデータをaddすることが事前にわかっているわけですから、サイズは100万が最適です。しかし、そうでない場合は、少しの計算が必要です。
まとめ
今回は、パフォーマンスチューニングに有用なArrayListの初期値に関する話題でした。addを繰り返すような状況でない限りはあまり役に立たないかもしれませんが、処理が遅いときは見直してみるのも良いかもしれません。