Page History

Wiki Markup According to the Java API documentation \ [[API 2006|AA. References#API 06] \] for the {{Iterator.remove()}} method:

The behavior of an iterator is unspecified if the underlying collection is modified while the iteration is in progress in any way other than by calling this method.

Concurrent modification in single-threaded programs is usually a result of inserting or removing an element during iteration. Multithreaded programs add the possibility that a collection may be modified by one thread while another thread iterates over the collection. Undefined behavior results in either case. Many implementations throw a ConcurrentModificationException when they detect concurrent modification.

Wiki MarkupAccording to the Java API documentation \[ [API 2006|AA. References#API 06]\] for {{ConcurrentModificationException}}:

It is not generally permissible for one thread to modify a Collection while another thread is iterating over it. In general, the results of the iteration are undefined under these circumstances. Some Iterator implementations (including those of all the general purpose collection implementations provided by the JRE) may choose to throw this exception if this behavior is detected. Iterators that do this are known as fail-fast iterators, as they fail quickly and cleanly, rather that risking arbitrary, non-deterministic behavior at an undetermined time in the future.

Note that fail-fast behavior cannot be guaranteed because it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast operations throw ConcurrentModificationException on a best-effort basis. Consequently, it would be wrong to write a program that depended on this exception for its correctness: ConcurrentModificationException should be used only to detect bugs.

...

Reliance on {{ConcurrentModificationException}} is inadequate to prevent undefined behavior resulting from modifying an underlying collection while simultaneously iterating over the collection. The fail-fast behavior may occur only after processing an arbitrary number of elements. In _Java Concurrency in Practice_ \[ [Goetz 2006a|AA. References#Goetz 06]\], Goetz and colleagues note:

Wiki Markup\[Fail-fast iterators\] are implemented by associating a modification count with the collection: if the modification count changes during iteration, {{hasNext}} or {{next}} throws {{ConcurrentModificationException}}. However, this check is done without synchronization, so there is a risk of seeing a stale value of the modification count and therefore...that the iterator does not realize a modification has been made. This was a deliberate design tradeoff to reduce the performance impact of the concurrent modification detection code.

Note that the enhanced for loop (for-each idiom) uses an Iterator internally. Consequently, enhanced for loops can also participate in concurrent modification issues, even though they lack an obvious iterator.

...

List<Widget> widgetList = 
    Collections.synchronizedList(new ArrayList<Widget>());

public void widgetOperation() {
  for (Widget w : widgetList) {
    doSomething(w);
  }
}

...

This approach must be implemented correctly to avoid starvation, deadlock, and scalability issues \ [[Goetz 2006a|AA. References#Goetz 06]\].

Compliant Solution (Deep Copying)

...

List<Widget> widgetList = new ArrayList<Widget>();

public void widgetOperation() {
  List<Widget> deepCopy = new ArrayList<Widget>();
  synchronized (widgetList) { // Client-side locking
    for (Object obj : widgetList) {
      deepCopy.add(obj.clone());
    }
  } 

  for (Widget w : deepCopy) {
    doSomething(w);
  }
}

Wiki MarkupCreating deep copies of the list prevents underlying changes in the original list from affecting the iteration in progress. "Since the clone is thread-confined, no other thread can modify it during iteration, eliminating the possibility of {{ConcurrentModificationException}}. (The collection still must be locked during the clone operation itself)" \[ [Goetz 2006a|AA. References#Goetz 06]\]. However, this approach is often more expensive than other techniques. There is also a risk of operating on stale data, which may affect the correctness of the code.

Compliant Solution (CopyOnWriteArrayList)

...

The Apache Harmony bug HARMONY-6236 documents an ArrayList breaking when given concurrent collections as input.

Bibliography

...

      49. Miscellaneous (MSC)