Why doesn't ArrayList throw ConcurrentModificationException when modified from multiple threads?
ConcurrentModificationException: This exception can be thrown by methods that have detected a concurrent modification to an object if such a modification is invalid.
The above is the definition of ConcurrentModificationException from javadoc.
So I am trying to test the code below:
final List<String> tickets = new ArrayList<String>(100000);
for (int i = 0; i < 100000; i++) {
tickets.add("ticket NO," + i);
}
for (int i = 0; i < 10; i++) {
Thread salethread = new Thread() {
public void run() {
while (tickets.size() > 0) {
tickets.remove(0);
System.out.println(Thread.currentThread().getId()+"Remove 0");
}
}
};
salethread.start();
}
The code is simple. 10 threads remove an element from the arraylist object. It is sure that multiple threads are accessing the same object. But it works fine. No exception is thrown. Why?
source to share
I am quoting a large ArrayList
Javadoc section for your benefit. Relevant parts are highlighted that explain the behavior you see.
Note that this implementation is out of sync. If multiple threads access the ArrayList instance at the same time and at least one of the threads changes the list structurally, it must be synchronized externally . (Structural modification is any operation that adds or removes one or more elements, or explicitly resizes the backing array; just setting the value of an element is not a structural modification.) This is usually done by synchronization on some object that naturally encapsulates the list. If no such object exists, the list must be "wrapped" using the Collections.synchronizedList method. This is best done at creation time to prevent accidental unsynchronized access to the list:
List List = Collections.synchronizedList (new ArrayList (...));
The iterators returned by these class iterator and listIterator methods are volatile: if the list is structurally changed at any time after the iterator is created, in any way other than through the iterator to remove or add methods, the iterator will be ConcurrentModificationException. Thus, in the face of concurrent modifications, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an indefinite time in the future.
Note that inefficient iterator behavior cannot be guaranteed because, generally speaking, it is impossible to make any hard guarantees in the presence of unsynchronized parallel modification . Normal-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depends on this exception for its correctness: the fail-safe behavior of iterators should only be used to catch errors.
ArrayLists will typically throw concurrent modification exceptions if you modify the list structurally when you access it through your iterator (but even that is not an absolute guarantee). Note that in your example, you are removing elements from the list directly and you are not using an iterator.
If it tickles your imagination, you can also review the implementation ArrayList.remove
to better understand how it works.
source to share
I don't think "parallel" means thread-related in this case, or at least it doesn't necessarily mean it. ConcurrentModificationException
usually occur when the collection changes as you iterate over it.
List<String> list = new ArrayList<String>();
for(String s : list)
{
//modifying list results in ConcurrentModificationException
list.add("don't do this");
}
Note that the class Iterator<>
has several methods that can work around this:
for(Iterator it = list.iterator(); it.hasNext())
{
//no ConcurrentModificationException
it.remove();
}
source to share
The reason you don't receive ConcurrentModificationException
is because you ArrayList.remove
don't throw it away. You can probably get it by starting an additional thread that iterates through the array:
final List<String> tickets = new ArrayList<String>(100000);
for (int i = 0; i < 100000; i++) {
tickets.add("ticket NO," + i);
}
for (int i = 0; i < 10; i++) {
Thread salethread = new Thread() {
public void run() {
while (tickets.size() > 0) {
tickets.remove(0);
System.out.println(Thread.currentThread().getId()+"Remove 0");
}
}
};
salethread.start();
}
new Thread() {
public void run() {
int totalLength = 0;
for (String s : tickets) {
totalLength += s.length();
}
}
}.start();
source to share
But it works fine. No exception is thrown. Why?
Simply because this parallel modification is allowed.
The description of the exception says the following:
"This exception can be thrown by methods that have detected a concurrent modification to an object when such modification is invalid. "
Explicit implications are (or could be) valid concurrent modifications. And in fact, concurrent modifications are allowed to standard classes of mismatched Java classes ... provided they do not happen during iteration.
The rationale for this is that, for non-co-local collections, iteration modification is fundamentally unsafe and unpredictable. Even if you've synchronized correctly (and that's not easy 1 ), the result will still be unpredictable. "Failed" checks for concurrent updates were included in regular collections because it was a common source of Heisenbugs in multithreaded applications that used Java 1.1 collection classes.
1- For example, "synchronizedXxx" wrapper classes do not execute and cannot synchronize with iterators. The problem is that iteration involves interleaved calls next()
and hasNext()
, and the only way to make a pair of method calls, excluding other threads, is to use external synchronization. The workaround is not practical in Java.
source to share