Problems with two threads accessing a frequently updated Arraylist

I have ArrayLists that store many objects, and objects are frequently added and removed from the ArrayLists. One thread operates on the data structures and updates the ArrayList's objects every 20ms or so. Another thread traverses the ArrayLists and uses their elements to paint the objects (also every 20-30ms).

If the ArrayLists are traversed using a for loop, IndexOutOfBoundsExceptions abound. If the ArrayLists are traversed using iterators, ConcurrentModificationExceptions abound. Synchronizing the ArrayLists like so:

List list = Collections.synchronizedLis开发者_StackOverflow社区t(new ArrayList());
synchronized(list) {
//use iterator for traversals
}

Throws no exceptions but has a substantial performance drain. Is there a way to traverse these ArrayLists without exceptions being throw, and without a performance drain?

THANKS!

---

A good approach to this problem is to make threads work on different copies of the list. However, CopyOnWriteArrayList doesn't fit here well, since it creates a copy at every modification, but in your case it would be better to create copies less frequent.

So, you can implement it manually: the first thread creates a copy of the updated list and publishes it via the volatile variable, the second thread works with this copy (I assume that the first thread modifies only list, not objects in it):

private volatile List publicList;

// Thread A
List originalList = ...;
while (true) {
    modifyList(originalList); // Modify list
    publicList = new ArrayList(originalList); // Pusblish a copy
}

// Thread B
while (true) {
    for (Object o: publicList) { // Iterate over a published copy
        ...
    }
}

---

What about copying the ArrayList into a new variable prior to iterating over it? That way you only need to synchronize the copy block and not the entire iteration of the list.

---

Have you tried using the Iterator and using a CopyOnWriteArrayList? It is guaranteed not to throw ConcurrentModificationExceptions.

From the Oracle javadocs (emphasis added):

A thread-safe variant of ArrayList in which all mutative operations (add, set, and so on) are implemented by making a fresh copy of the underlying array.

This is ordinarily too costly, but may be more efficient than alternatives when traversal operations vastly outnumber mutations, and is useful when you cannot or don't want to synchronize traversals, yet need to preclude interference among concurrent threads. The "snapshot" style iterator method uses a reference to the state of the array at the point that the iterator was created. This array never changes during the lifetime of the iterator, so interference is impossible and the iterator is guaranteed not to throw ConcurrentModificationException. The iterator will not reflect additions, removals, or changes to the list since the iterator was created. Element-changing operations on iterators themselves (remove, set, and add) are not supported. These methods throw UnsupportedOperationException.

---

The CopyOnWriteArrayList class was created to solve this problem.

---

You can use CopyOnWriteArrayList which doesn't get a ConcurrentModificationException nor does it need to be synchronized, or you can do something like.

List list = Collections.synchronizedList(new ArrayList());

List copy;
// lock the list for the minimal amount of time.
synchronized(list) {
    copy = new ArrayList(list);
}
// use the copy of the array list.

BTW CopyOnWriteArrayList would look like

List list = new CopyOnWriteArrayList();

// use the list.

---

Although CopyOnWriteArrayList provides maximum performance for readers, there are writer performance issues if writes are frequent.

If your access pattern is only through the iterator and you don't do any random access, then using a queue may be a better choice, as you can use things like ConcurrentLinkedQueue. See for example JAVA: Concurrency control for access to list in java.