Concurrent ArrayList

Question

I need an ArrayList-like structure allowing just the following operations

• get(int index)
• add(E element)
• set(int index, E element)
• iterator()

Because of the iterator being used in many places, using Collections#synchronizedList would be too error-prone. The list can grow to a few thousand elements and gets used a lot, so I'm pretty sure, that CopyOnWriteArrayList will be too slow. I'll start with it to avoid premature optimizations, but I'd bet it won't work well.

Most accesses will be single-threaded reads. So I'm asking what's the proper data structure for this.

---

I though that wrapping the synchronizedList in something providing a synchronized iterator would do, but it won't because of the ConcurrentModificationException. Concenrning concurrent behavior, I obviously need that all changes will be visible by subsequent reads and iterators.

The iterator doesn't have to show a consistent snapshot, it may or may not see the updates via set(int index, E element) as this operation gets used only to replace an item with its updated version (containing some added information, which is irrelevant for the user of the iterator). The items are fully immutable.

---

I clearly stated why CopyOnWriteArrayList would not do. ConcurrentLinkedQueue is out of question as it lacks an indexed access. I need just a couple of operations rather than a fully fledged ArrayList. So unless any java concurrent list-related question is a duplicate of this question, this one is not.

Solution

In your case you can use a ReadWriteLock to access a backed List, this allows multiple Threads to read your list. Only if one Thread needs write access all reader-Thread must wait for the operation to complete. The JavaDoc make's it clear:

A ReadWriteLock maintains a pair of associated locks, one for read-only operations and one for writing. The read lock may be held simultaneously by multiple reader threads, so long as there are no writers. The write lock is exclusive.

Here is a sample:

public class ConcurrentArrayList<T> {

    /** use this to lock for write operations like add/remove */
    private final Lock readLock;
    /** use this to lock for read operations like get/iterator/contains.. */
    private final Lock writeLock;
    /** the underlying list*/
    private final List<T> list = new ArrayList();

    {
        ReentrantReadWriteLock rwLock = new ReentrantReadWriteLock();
        readLock = rwLock.readLock();
        writeLock = rwLock.writeLock();
    }

    public void add(T e){
        writeLock.lock();
        try{
            list.add(e);
        }finally{
            writeLock.unlock();
        }
    }

    public void get(int index){
        readLock.lock();
        try{
            list.get(index);
        }finally{
            readLock.unlock();
        }
    }

    public Iterator<T> iterator(){
        readLock.lock();
        try {
            return new ArrayList<T>( list ).iterator();
                   //^ we iterate over an snapshot of our list 
        } finally{
            readLock.unlock();
        }
    }

Comments

[maaartinus]

That's fine, but I can't use the ArrayList's iterator, as it'd throw a ConcurrentModificationException. I guess, there's a simple workaround.

[Chriss]

You can't avoid the ´ConcurrentModificationException´ if you want to be ableto add elements while iterating. Imagin your next element while iterating is at index 5, but in the same time an other Thread adds an element at index 1, what should happen now? The only way out is to create a immutalbe copy of the List to get an independend iterator or to abuse the writeLock to lock the iteration loop block.

[maaartinus]

"what should happen now" - Exactly this can't happen, as there'll be no such operation. But appending or replacing elements can, and then I just don't care. Getting the old value is fine and so it getting the new one.

[cic]

This solution might be inappropriate for large lists are you are doing lots of copying while holding the lock (both in add and iterator). (Your iterator implementation also provides a stronger consistency guarantee that necessary.)