オワコンであるVectorとListの同期の話 - プログラマーの脳みそ

JJUG Night Seminarへ行ってきました - 虎塚にあったjava.util.Vectorの話。

java.util.Vectorは随分前にオワコン化していて、今、新たにVectorを使ってコードを書く人がいたら優しく諌めてあげるべきシロモノ。

「VectorとArrayListだとArrayListの方が同期化されていなくて速いです！」と習った人も多いのではないかと。

    public synchronized E get(int index) {
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index);

        return elementData(index);
    }

これはJDK7u7のVectorのコードのうちget()の部分の抜粋なのだけど、synchronizedメソッドになってる。synchronizedメソッド。このJavaのsynchronizedキーワードはいまいちよくわからんという人が多いと思います。

synchronized句

synchronizedについて理解するなら知るべきはsynchronized句。メソッドの宣言にsynchronizedキーワードをつけるというのは糖衣構文でしかない。本来のsynchronizedの使い方を理解するにはsynchronized句を書けと言っておきましょう。

Object o = new Object();
synchronized(o) {
    // 処理
}

synchronized句はオブジェクトを指定する。このオブジェクトのインスタンスが同じsynchronized句同士は同時にひとつしか動かない。複数のThread A, B, Cで処理が動いたとして、synchronized句に同じインスタンス oが指定されているのであれば、どれかひとつのThreadが処理をして、他の2つはsynchronized句のブロックの手前で待機する。

たとえばAが先に処理を始めたなら、その間 thread B, C はsynchronizedのブロックには入れず手前で待機。Aが処理を抜けるとBかCのどちらかがブロックの処理に移る。あぶれた方はまだ待機。

ところが、例えば

synchronized(new Object()) {
    // 処理
}

のように書いたとすれば、このsynchronized句と同じインスタンスのsynchronizedブロックは存在しないので、実質的に意味がないことに*1。

というわけで、synchronized句はこのインスタンスが何か？というのが大事。このオブジェクトをロックオブジェクトという。

synchronizedキーワード

さて、メソッドにsynchronizedキーワードをつけた場合。これは

synchronized (this) {
    // ...
}

と同じ挙動をする。但し、staticメソッドの場合は

synchronized (Hoge.class) {
    // ...
}

のように、メソッドが宣言されているクラスのClassオブジェクトをロックオブジェクトとする。

さて、ここでVectorの話に戻るのだけどget()とかput()とかとにかくVectorのメソッドはみんなsynchronizedメソッドになっている。ということはthisオブジェクトをロックオブジェクトとして同期がされているのだから、一応はマルチスレッド下でput()したりget()したりしても壊れないと言える。

ただし、get()した値を加工して別の値をput()する、などという非アトミックな操作をしちゃうとマルチスレッド下で破壊されちゃうのでやっぱり使いにくいという話。

Collections#synchronizedList

さて、そんなオワコンなVectorですが、そんな簡易な同期化でもいいんだよ！というケースもあるでしょう。一応そういうときに使えるCollections#synchronizedList()というものがある。

指定されたリストに連動する同期 (スレッドセーフな) リストを返します。確実に直列アクセスを実現するには、基になるリストへのアクセスはすべて、返されたリストを介して行う必要があります。
返されたリストの繰り返し処理を行う場合、ユーザは、次に示すように手動で同期をとる必要があります。
List list = Collections.synchronizedList(new ArrayList());
...
synchronized(list) {
Iterator i = list.iterator(); // Must be in synchronized block
while (i.hasNext())
foo(i.next());
}

これを行わない場合、動作は保証されません。
返されたリストは、指定されたリストが直列化可能の場合にだけ直列化可能になります。
Collections (Java Platform SE 6)

というわけで、Vectorとは違ってLinckedListの同期版が欲しいとかそういう要望にも応え、同期するラッパーListが同期化してくれるというシロモノなのだけど、じゃぁどういう実装になってんの、どこまで同期してくれんのと思うのが人情だろう

というわけで、このsynchronizedList()で返されるCollections.SynchronizedListクラスのソースを抜粋してみた。

    static class SynchronizedList<E>
        extends SynchronizedCollection<E>
        implements List<E> {
        private static final long serialVersionUID = -7754090372962971524L;

        final List<E> list;

        SynchronizedList(List<E> list) {
            super(list);
            this.list = list;
        }
        SynchronizedList(List<E> list, Object mutex) {
            super(list, mutex);
            this.list = list;
        }

        public boolean equals(Object o) {
            if (this == o)
                return true;
            synchronized (mutex) {return list.equals(o);}
        }
        public int hashCode() {
            synchronized (mutex) {return list.hashCode();}
        }

        public E get(int index) {
            synchronized (mutex) {return list.get(index);}
        }
        public E set(int index, E element) {
            synchronized (mutex) {return list.set(index, element);}
        }
        public void add(int index, E element) {
            synchronized (mutex) {list.add(index, element);}
        }
        public E remove(int index) {
            synchronized (mutex) {return list.remove(index);}
        }

        public int indexOf(Object o) {
            synchronized (mutex) {return list.indexOf(o);}
        }
        public int lastIndexOf(Object o) {
            synchronized (mutex) {return list.lastIndexOf(o);}
        }

        public boolean addAll(int index, Collection<? extends E> c) {
            synchronized (mutex) {return list.addAll(index, c);}
        }

        public ListIterator<E> listIterator() {
            return list.listIterator(); // Must be manually synched by user
        }

        public ListIterator<E> listIterator(int index) {
            return list.listIterator(index); // Must be manually synched by user
        }

        public List<E> subList(int fromIndex, int toIndex) {
            synchronized (mutex) {
                return new SynchronizedList<>(list.subList(fromIndex, toIndex),
                                            mutex);
            }
        }

        /**
         * SynchronizedRandomAccessList instances are serialized as
         * SynchronizedList instances to allow them to be deserialized
         * in pre-1.4 JREs (which do not have SynchronizedRandomAccessList).
         * This method inverts the transformation.  As a beneficial
         * side-effect, it also grafts the RandomAccess marker onto
         * SynchronizedList instances that were serialized in pre-1.4 JREs.
         *
         * Note: Unfortunately, SynchronizedRandomAccessList instances
         * serialized in 1.4.1 and deserialized in 1.4 will become
         * SynchronizedList instances, as this method was missing in 1.4.
         */
        private Object readResolve() {
            return (list instanceof RandomAccess
                    ? new SynchronizedRandomAccessList<>(list)
                    : this);
        }
    }

それとsuperクラスであるCollections.SynchronizedCollectionクラス。

    static class SynchronizedCollection<E> implements Collection<E>, Serializable {
        private static final long serialVersionUID = 3053995032091335093L;

        final Collection<E> c;  // Backing Collection
        final Object mutex;     // Object on which to synchronize

        SynchronizedCollection(Collection<E> c) {
            if (c==null)
                throw new NullPointerException();
            this.c = c;
            mutex = this;
        }
        SynchronizedCollection(Collection<E> c, Object mutex) {
            this.c = c;
            this.mutex = mutex;
        }

        public int size() {
            synchronized (mutex) {return c.size();}
        }
        public boolean isEmpty() {
            synchronized (mutex) {return c.isEmpty();}
        }
        public boolean contains(Object o) {
            synchronized (mutex) {return c.contains(o);}
        }
        public Object[] toArray() {
            synchronized (mutex) {return c.toArray();}
        }
        public <T> T[] toArray(T[] a) {
            synchronized (mutex) {return c.toArray(a);}
        }

        public Iterator<E> iterator() {
            return c.iterator(); // Must be manually synched by user!
        }

        public boolean add(E e) {
            synchronized (mutex) {return c.add(e);}
        }
        public boolean remove(Object o) {
            synchronized (mutex) {return c.remove(o);}
        }

        public boolean containsAll(Collection<?> coll) {
            synchronized (mutex) {return c.containsAll(coll);}
        }
        public boolean addAll(Collection<? extends E> coll) {
            synchronized (mutex) {return c.addAll(coll);}
        }
        public boolean removeAll(Collection<?> coll) {
            synchronized (mutex) {return c.removeAll(coll);}
        }
        public boolean retainAll(Collection<?> coll) {
            synchronized (mutex) {return c.retainAll(coll);}
        }
        public void clear() {
            synchronized (mutex) {c.clear();}
        }
        public String toString() {
            synchronized (mutex) {return c.toString();}
        }
        private void writeObject(ObjectOutputStream s) throws IOException {
            synchronized (mutex) {s.defaultWriteObject();}
        }
    }

final な Object型フィールド mutex を使ってsynchronized句でラップしているという仕掛け。でもまぁ、これだとVector同様にget()して加工してput()とかするとやっぱりその非アトミックな操作の間に破壊されるのであまりツカエナイという結論に。

CopyOnWriteArrayList

場合によってはjava.util.concurrent.CopyOnWriteArrayListクラスを使用することで同期化できる場合もある。

基になる配列の新しいコピーを作成することにより、すべての推移的操作 (add、set など) が実装される ArrayList のスレッドセーフな変数です。
通常、これは非常に効率が悪いのですが、トラバーサル操作が変更を数の点で大幅に上回る場合には、代替手段よりも効率が良い場合があります。また、これは、トラバーサルを同期できない場合や、同期することを望まないが、並行スレッド間の干渉を排除する必要がある場合に有用です。|
CopyOnWriteArrayList (Java Platform SE 6)

javadocを読んでわかる通り、特性がピーキーなのでシチュエーションを選んで使う必要がある。

まとめ

Vectorはオワコン
代替するならCollections.synchronizedList()だが、本当にこれでちゃんと同期できるシチュエーション？
CopyOnWriteArrayListが使えないか検討する
仕方がない場合は自分でListを同期する
synchronizedでちゃんと同期するのは結構難しい
synchronizedはロックしちゃうのでパフォーマンスを出したければロックフリーなアルゴリズムを考えることになってさらに難しい

つまり、マルチスレッド爆発しろ、ということ。

*1:メモリの同期は行われるだろうけど