Is it possible for ArrayList to fail in a single-writer-multi-reader system?

Question

I have a List that needs to called by multiple threads. There will be only a single writer, and this writer will add elements and do nothing else. Elements are never removed or modified. Many concurrent reader threads will call list.size() and list.get(index).

We must assume that on occasion the internal array will need to grow as elements are added.

Can I get away with using a plain ArrayList, or do I need to implement some fancy concurrent structure to avoid exceptions?

Answer 1

If your readers all need to be reading the same state of the List, meaning that the writer can't write between all readers reading, then yes, you'll need to use ReadWriteLock or some more complex method of handling this case.

If you're not spared for memory usage, don't mind if your readers always have the most current data available, and your only goal is just to avoid exceptions, consider a CopyOnWriteArrayList, which is built to avoid exceptions on write/iteration conflicts. When you write to this List, it makes a new one as the finished result but the readers currently using the List continue reading the "old" (pre-write) one instead.

Answer 2

So first off the documentation for ArrayList says it's not thread safe- so I wouldn't recommend using it in such a case. Furthermore even if this did theoretically work you'd have the problem of ensuring that whoever maintains this program remembered the strict constraints you've imposed on reading and writing with hilarity ensuing if they didn't! That said, your question is really interesting from a theoretical perspective so I thought I'd take a look.

The first thing to note is that any of the readers tried to access the list through an iterator then sooner or later the read would fail with a ConcurrentModificationException. That's because every modification to the list is tracked and the Iterator fails fast if it detects a modification outside the iterator.

That said, you don't specify the need to use iterators in your original question so what happens if you restrict yourself to simply appending by add and reading by get() and size()? In this case I still think you might see the occasional failure because internally the list stores the current size along with the backing data array and neither variable is marked as volatile. As a result (and due to Java's Memory guarantees) I would think it theoretically possible for one of the reader threads to see an updated size variable while the data still hasn't been updated. In this case you could end up junk data being returned or even an indexOutOfBounds.