Is `ArrayList::get` thread-safe?

Question

I understand that modifying an ArrayList makes it not thread-safe.

➠ But if the ArrayList is not being modified, perhaps protected by a call to Collections.unmodifiableList, is calling ArrayList::get thread-safe?

For example, can an ArrayList be passed to a Java Stream for parallel-processing of its elements?

Answer 1

But if the ArrayList is not being modified is calling ArrayList::get thread-safe?

No it is not thread-safe.

The problems arise if you do something like the following:

1. Thread A creates and populates list.
2. Thread A passes reference to list to thread B (without a happens before relationship)
3. Thread B calls get on the list.

Unless there is a proper happens before chain between 1 and 3, thread B may see stale values ... occasionally ... on some platforms under certain work loads.

There are ways to address this. For example, if thread A starts thread B after step 1, there will be a happens before. Similarly, there will be happens before if A passes the list reference to B via properly synchronized setter / getter calls or a volatile variable.

But the bottom line is that (just) not changing the list is not sufficient to make it thread-safe.

---

... perhaps protected by a call to Collections.unmodifiableList

The creation of the Collections.unmodifiableList should provide the happens before relationship ... provided that you access the list via the wrapper not directly via ArrayList::get.

---

For example, can an ArrayList be passed to a Java Stream for parallel-processing of its elements?

That's a specific situation. The stream mechanisms will provide the happens before relationship. Provided they are used as intended. It is complicated.

This comes from the Spliterator interface javadoc.

"Despite their obvious utility in parallel algorithms, spliterators are not expected to be thread-safe; instead, implementations of parallel algorithms using spliterators should ensure that the spliterator is only used by one thread at a time. This is generally easy to attain via serial thread-confinement, which often is a natural consequence of typical parallel algorithms that work by recursive decomposition. A thread calling trySplit() may hand over the returned Spliterator to another thread, which in turn may traverse or further split that Spliterator. The behaviour of splitting and traversal is undefined if two or more threads operate concurrently on the same spliterator. If the original thread hands a spliterator off to another thread for processing, it is best if that handoff occurs before any elements are consumed with tryAdvance(), as certain guarantees (such as the accuracy of estimateSize() for SIZED spliterators) are only valid before traversal has begun."

In other words, thread safety is a joint responsibility of the Spliterator implementation and Stream implementation.

The simple way to think about this is that "magic happens" ... because if it didn't then parallel streams would be unusable.

But note that the Spliterator is not necessarily using ArrayList::get at all.

Answer 2

Thread safety is only a concern, as you stated when values can change between the threads. If the elements aren't being added or removed, the object remains the same and all threads can easily operate on it. This is the same for most objects in Java.

You may be able to get away with adding to an ArrayList across threads as seen here but I wouldn't bank on it.

Answer 3

No, ArrayList.get() is not inherently thread-safe just because it does not modify the List. You still need something to create a happens-before relationship between each get() and each method invocation that does modify the list.

Suppose, however, that you instantiate and populate the list first, and then perform multiple get()s, never modifying it again, or at least not until after some synchronization point following all the get()s. You do not then need mutual synchronization between the various get()s, and you may be able to obtain cheap synchronization between the get()s and the end of the initialization phase. This is effectively the situation you will have with an otherwise non-shared List that you provide as input to a parallel stream computation.