Wednesday, February 10, 2010

A Concurrent Modification Exception corner case

CME has always piqued my curiosity, and today I finally went ahead and examined the java.util.* source codes to figure out how modification is detected. As can be predicted, one best-effort implementation uses a counter to facilitate the test (see: AbstractList's modCount field). I've never been a fan of such technique, and the fact that the counter is only 32-bit makes the point all the more demonstratable:
import java.util.*;

public class ConcuMod {
   public static void main(String[] args) {
      List<String> list = new ArrayList<String>();
      for (String s : list) {
         for (long reps = (1L << 32); reps --> 0;) {
The strategy is obvious, of course: modify the list exactly 2^32 times. As expected, the iterator fails to detect the modification.
Exception in thread "main" java.util.NoSuchElementException
   at java.util.AbstractList$ Source)
   at ConcuMod.main(
The decision to throw NSEE instead of CME in this case is worth studying. It would at first seem reasonable to expect CME to be thrown even though the counter test yields a (false) negative, precisely because the test is not 100% foolproof to begin with. However, translating the underlying IndexOutOfBoundsException to NSEE turns out to be better because:
  • It's not presumptuous. IOOB naturally means NSE; CM is merely a possibility. Undetected modification scenarios such as shown here is admittedly so improbable that it's really not worth considering.
  • In the more common scenario, the IOOBE is probably due to an internal bug in the implementation of an AbstractList subclass (it is, after all, documented for inheritance). Throwing NSEE would quickly distinguish this case. CME would in effect make the wrong accusation against the wrong person.

No comments:

Post a Comment