2012年03月30日

java.util.concurrent 〜CopyOnWriteArrayList〜


突然ですが、java.util.concurrent使ってますか?
僕は使ってません。また、使っている人をあんまり見たことがありません。

java.util.concurrentはJava5.0から追加された並列プログラミングの要求に応えるためのパッケージです。WEBアプリの開発者ならばほぼ間違いなく、そうでない人も結構な頻度で並列処理に注意を払わねばならない場面は多いと思います。しかしながら、前述の通り、java.util.concurrentを僕自身あまり使っていません。それはなぜか?真っ先に思いつく答えは「synchronizedで十分だから」というものでしょう。確かに、一般的な排他処理はsynchronizedで十分でしょう。しかし、明示的な排他処理は実に骨が折れる作業であるし、ソースの可読性も下がっていくことは確かです。

ただ、僕個人としてはjava.util.concurrentがなにがしか素敵な道具箱であることはわかっているものの「でもなんだかよく分からんから使いたくない」というのが正直なところです。ということで、java.util.concurrentをいろいろ試してみることにします。お勉強がてら。
初回はCopyOnWriteArrayListです。では行きます。

ArrayListがスレッドセーフでないのはよく知られています。ArrayListはリストの走査を行っている最中に要素の変更が加わるとConcurrentModificationExceptionが発生します。

以下のような場合です。

List<String> list = new ArrayList<String>();
Collections.addAll(list, "aa","bb","cc");
for(String h : list){
    System.out.println(h);
    list.remove(h);
}

実行結果は以下の通り。
aa
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.AbstractList$Itr.checkForComodification(AbstractList.java:372)
at java.util.AbstractList$Itr.next(AbstractList.java:343)
at test1.Main1.main(Main1.java:16)

ちょっと注意すべきなのが、このConcurrentModificationExceptionが発生するタイミングです。感覚的にはlist.remove(h)のような気もしますが、そうではなくfor(String h : list){の部分になります。なぜなら、このConcurrentModificationExceptionをスローするのはこのコレクションの反復子、つまりIteratorだからです。

上記の例では単一スレッドですが、当然マルチスレッドでも同じことが発生します。

public class ArrayListTest {

	//test対象となるリスト。ArrayListで宣言
	private static List<String> arrayList = new ArrayList<String>();

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		//適当にいっぱい要素追加
		long time = System.currentTimeMillis();
		for(int i = 0; i < 10000; i++){
			arrayList.add("hogehoge" + i);
		}
		System.out.print("所要時間:");
		System.out.print(System.currentTimeMillis()-time);
		System.out.println("ミリ秒");

		//別スレッドでリストを走査する
		Thread th = new Thread(new Runnable(){
			@Override
			public void run() {
				for(String h : arrayList){			//ConcurrentModificationExceptionはここで発生します。
				}
			}
		});
		th.start();

		//走査中に操作するためにちょろっと待つ
		try {
			Thread.sleep(5);
		} catch (InterruptedException e) {
			e.printStackTrace();
		}

		//操作中に削除
		arrayList.remove("hogehoge0");
		System.out.println("削除!");

	}

}

実行結果はこちら
所要時間:20ミリ秒
削除!
Exception in thread "Thread-0" java.util.ConcurrentModificationException
at java.util.AbstractList$Itr.checkForComodification(AbstractList.java:372)
at java.util.AbstractList$Itr.next(AbstractList.java:343)
at copyOnWriteArrayListTest.ArrayListTest$1.run(ArrayListTest.java:30)
at java.lang.Thread.run(Thread.java:662)

この問題を解決すべく作られたのがCopyOnWriteArrayListさんです。CopyOnWriteArrayListは配列に対しておこなう全ての操作を配列を新規コピーすることで実装しているスレッドセーフなArrayListです。では上記のプログラムのListの宣言を以下のように変更してみましょう。

private static List<String> arrayList = new CopyOnWriteArrayList<String>();

実行結果はこちら。

所要時間:285ミリ秒
削除!

おお、うまくいきました。素晴らしいです。でもちょっと気になるのが処理時間。Stringの要素を10000件挿入するのにArrayListでは20ミリ秒だったのに大して、CopyOnWriteArrayListでは285ミリ秒もかかってます。10倍以上遅い・・・?というわけでもないのです。

試しに要素の挿入数を100000に増やしてみます。

ArrayListの結果がこちら。
所要時間:184ミリ秒
Exception in thread "Thread-0" java.util.ConcurrentModificationException
at java.util.AbstractList$Itr.checkForComodification(AbstractList.java:372)
at java.util.AbstractList$Itr.next(AbstractList.java:343)
at copyOnWriteArrayListTest.ArrayListTest$1.run(ArrayListTest.java:30)
at java.lang.Thread.run(Thread.java:662)削除!

対してCopyOnWriteArrayListがこれ
所要時間:37085ミリ秒
削除!

うへえ。超遅い。でもよく考えれば当たり前で、CopyOnWriteArrayListは「変更のたびに全体をコピーする」ものです。つまり、全体の要素数が増えれば増えるほど、また総称型の引数のサイズが大きければ大きいほど、操作の処理時間は累乗的に増えていきます。

以上より、CopyOnWriteArrayListを使用すべき場面は以下のようになるでしょう。

@排他処理が必要
A変更の操作がほとんどない
Bリストサイズがそれほど巨大でない(作成時に時間がかかるから)
C読み取りは多い

とりあえず今回はこれまで
posted by sandman at 15:29| Comment(0) | Java | このブログの読者になる | 更新情報をチェックする
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。
×

この広告は1年以上新しい記事の投稿がないブログに表示されております。