The Java Specialists' Newsletter
Issue 1712009-03-09 Category: Tips and Tricks Java version: Java 1.2 - 6.0

Welcome to the 171st issue of The Java(tm) Specialists' Newsletter, written at 30.000 feet en route to another Java Specialist Master Course. The frequent traveler knows that an emergency exit seat in economy (coach) is often superior to what is on offer in business class on the shorter European flights. My dad was 1.94m (6'4") and when we traveled together, he always requested emergency exit seats. Fortunately my height stayed a manageable 1.88m, so I'm tall enough to beg for an emergency exit seat, but won't be crippled if I don't get one. I keep on telling my son Maxi that 1.88m is a perfect height, but he is adamant that he will overtake me in the next few years. Time will tell, but I fear he is right in his predictions.

My father took me along on some of his business trips. When I was 16, we almost pushed someone off the road by accident. My dad was rather large and also rather impatient. Driving the speed limit was just not an option, so he manouvered his Mazda 323, with trailer, into oncoming traffic until he found a little gap, which, it turned out, was perfect for a Mazda 323 without trailer. A traffic cop pulled us over about thirty minutes later and the poor man who had almost been pushed into a ravine stopped behind us. However, they became most apologetic when my father got out of the car: A huge guy with a black beard and carrying a 9mm Browning on his hip. Looked a bit like Bud Spencer, just a bit taller. We were let off with a warning. My dad felt quite bad about the incident and rather sorry for the little terrified traffic cop. These short business trips taught me more about dealing with customers and how to sell, than all the years at school. If you have kids, do them a favour and teach them what you know.

Upcoming Java Specialist Master Courses: - please click here to sign up.

As from May 2010, we are also offering this course on the island of Crete. We only accept 6 students per class in Crete, due to the size of our conference room. Please book early to avoid disappointment!

San Jose CA, Mar 16-19 2010, $3500
Ottawa, Canada, Mar 22-25 2010, $3500
Oslo, Norway, Apr 13-16 2010, Kr 24500
Montreal, Canada, Apr 20-23 2010, $3500
Toronto, Canada, May 17-20 2010, $3500
Chania, Crete, May 25-28, Jun 29-Jul 2 or Aug 24-27 2010, €2500

In-house courses if these dates or locations do not suit you - click here for more information.

Throwing ConcurrentModificationException Early

After my last newsletter, one of my readers asked whether I knew of a way to figure out who was modifying a collection concurrently, causing a ConcurrentModificationException on iteration. This could happen if you shared a collection between lots of objects and you had lost track of who was modifying it when. This is of course an example of bad design, but sometimes we inherit such code from others. I had often thought about this particular exception and had used it as an example in my courses of an exception that causes problems because it is not thrown early. Also have a look at my Newsletter on Exceptions.

One possible solution to this problem is to write a wrapper collection, much like the synchronized collections in the java.util.Collections, which would maintain a set of active iterators. If that set was non-empty, we would throw a ConcurrentModificationException on the collection's modification methods. Here is my attempt to define the term active iterator:

Active Iterator: an iterator is active when hasNext() has not yet returned false AND when there exists a strong reference to it.

We could thus easily mark an iterator as inactive when it has walked through the entire collection. The tricky case is where someone walks through a section of the collection and then stops. If they keep a strong reference to the iterator, it would stay active until they de-reference it.

Here is the method that checks how many active iterators are associated with the collection. The first step is to check whether an active iterator might exist, by checking whether the iterators set returns elements. If it does, we calls System.gc() explicitely, which will hopefully clear the WeakReferences to the inactive iterators.

private final Map<WeakReference<Iterator<E>>, Object> iterators =
    new ConcurrentHashMap<WeakReference<Iterator<E>>, Object>();

private void checkForCurrentIteration() {
  boolean perhapsConcurrentIteration = false;
  for (WeakReference<Iterator<E>> ref : iterators.keySet()) {
    Iterator<E> iterator = ref.get();
    if (iterator != null) {
      perhapsConcurrentIteration = true;
      break;
    }
  }
  if (perhapsConcurrentIteration) {
    System.gc();
    for (WeakReference<Iterator<E>> ref : iterators.keySet()) {
      if (ref.get() == null) {
        iterators.remove(ref);
      }
    }
    int currentIterators = iterators.size();
    if (currentIterators != 0) {
      throw new ConcurrentModificationException(
          "Iteration might currently be happening with " +
              currentIterators + " iterators");
    }
  }
}

  

Under normal circumstances, calling System.gc() directly is strongly discouraged. In our case we are trying to discover a specific problem and so System.gc() is appropriate. However, it is not guaranteed that it will clear all the WeakReferences, so we could get false alarms. Our class is only intended for debugging and not for production code.

The rest of the collection class delegates to another collection and is easy to understand:

import java.lang.ref.WeakReference;
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;

public class FailFastCollection<E> implements Collection<E> {
  private final Collection<E> delegate;

  private final Map<WeakReference<Iterator<E>>, Object> iterators =
      new ConcurrentHashMap<WeakReference<Iterator<E>>, Object>();

  public FailFastCollection(Collection<E> delegate) {
    this.delegate = delegate;
  }

  private void checkForCurrentIteration() {
    boolean perhapsConcurrentIteration = false;
    for (WeakReference<Iterator<E>> ref : iterators.keySet()) {
      Iterator<E> iterator = ref.get();
      if (iterator != null) {
        perhapsConcurrentIteration = true;
        break;
      }
    }
    if (perhapsConcurrentIteration) {
      System.gc();
      for (WeakReference<Iterator<E>> ref : iterators.keySet()) {
        if (ref.get() == null) {
          iterators.remove(ref);
        }
      }
      int currentIterators = iterators.size();
      if (currentIterators != 0) {
        throw new ConcurrentModificationException(
            "Iteration might currently be happening with " +
                currentIterators + " iterators");
      }
    }
  }

  // Non-modifying safe operations
  public int size() {
    return delegate.size();
  }

  public boolean isEmpty() {
    return delegate.isEmpty();
  }

  public boolean contains(Object o) {
    return delegate.contains(o);
  }

  public Object[] toArray() {
    return delegate.toArray();
  }

  public <T> T[] toArray(T[] a) {
    return delegate.toArray(a);
  }

  public boolean containsAll(Collection<?> c) {
    return delegate.containsAll(c);
  }

  public boolean equals(Object o) {
    return delegate.equals(o);
  }

  public int hashCode() {
    return delegate.hashCode();
  }

  public String toString() {
    return delegate.toString();
  }

  // Operations that might modify the underlying collection - unsafe
  public boolean add(E e) {
    checkForCurrentIteration();
    return delegate.add(e);
  }

  public boolean remove(Object o) {
    checkForCurrentIteration();
    return delegate.remove(o);
  }

  public boolean addAll(Collection<? extends E> c) {
    checkForCurrentIteration();
    return delegate.addAll(c);
  }

  public boolean removeAll(Collection<?> c) {
    checkForCurrentIteration();
    return delegate.removeAll(c);
  }

  public boolean retainAll(Collection<?> c) {
    checkForCurrentIteration();
    return delegate.retainAll(c);
  }

  public void clear() {
    checkForCurrentIteration();
    delegate.clear();
  }

  public Iterator<E> iterator() {
    return new NoFailIterator(delegate.iterator());
  }

  private class NoFailIterator implements Iterator<E> {
    private final Iterator<E> delegate;
    private final WeakReference<Iterator<E>> reference;

    private NoFailIterator(Iterator<E> delegate) {
      this.delegate = delegate;
      reference = new WeakReference<Iterator<E>>(this);
      iterators.put(reference, "dummy");
    }

    public boolean hasNext() {
      if (delegate.hasNext()) {
        return true;
      } else {
        iterators.remove(reference);
        return false;
      }
    }

    public E next() {
      E e = delegate.next();
      if (!delegate.hasNext()) {
        iterators.remove(reference);
      }
      return e;
    }

    public void remove() {
      delegate.remove();
    }
  }
}
  

Test Code

We have several test cases that should all pass and which will show you the intended use of this FailFastCollection class:

import junit.framework.TestCase;

import java.util.*;
import java.util.concurrent.*;

public class FailFastCollectionTest extends TestCase {
  private final Collection<String> safe_names =
      new FailFastCollection<String>(new ArrayList<String>());

  protected void setUp() throws Exception {
    safe_names.clear();
    Collections.addAll(safe_names, "Anton", "John", "Heinz");
  }

  public void testBasicIteration() {
    for (String name : safe_names) {
    }
  }

  public void testBasicModification() {
    // we first iterate
    for (String name : safe_names) {
    }
    // then we add Dirk - should work as no client code has a
    // handle to the iterator and we ran the iterator to
    // completion
    safe_names.add("Dirk");
    assertEquals(4, safe_names.size());
    Iterator<String> it = safe_names.iterator();
    assertEquals("Anton", it.next());
    assertEquals("John", it.next());
    assertEquals("Heinz", it.next());
    assertEquals("Dirk", it.next());
  }

  public void testModificationFromAnotherThread() throws InterruptedException {
    // this test is more tricky.  Once we have iterated through
    // two elements, we want to add "Neil" to the list.  Since
    // that is done in another thread, we get the exception using
    // futures and check it is a ConcurrentModificationException

    final CountDownLatch latch = new CountDownLatch(2);

    ExecutorService executor = Executors.newSingleThreadExecutor();
    Future<?> future = executor.submit(new Callable<Object>() {
      public Object call() throws Exception {
        latch.await();
        safe_names.add("Neil");
        return null;
      }
    });

    for (String name : safe_names) {
      System.out.println(name);
      latch.countDown();
      Thread.sleep(50);
    }

    try {
      future.get();
      fail("expected a ConcurrentModificationException!");
    } catch (ExecutionException e) {
      if (e.getCause() instanceof ConcurrentModificationException) {
        // success
      } else {
        fail("expected a ConcurrentModificationException!");
      }
    }
  }


  public void testModificationFromSameThread() {
    // iteration does not run to completion, but iterator is out
    // of scope
    try {
      for (String name : safe_names) {
        if (name.equals("John")) {
          safe_names.add("Andre");
        }
      }
    } catch (ConcurrentModificationException ex) {
      System.out.println("Expected the error " + ex);
    }

    // now we should be able to use the collection still.
    assertEquals(3, safe_names.size());
    Iterator<String> it = safe_names.iterator();
    assertEquals("Anton", it.next());
    assertEquals("John", it.next());
    assertEquals("Heinz", it.next());

    // we have run to completion, thus the iterator is inactive

    safe_names.add("Andre");

    assertEquals(4, safe_names.size());
    Iterator<String> it2 = safe_names.iterator();
    assertEquals("Anton", it2.next());
    assertEquals("John", it2.next());
    assertEquals("Heinz", it2.next());
    assertEquals("Andre", it2.next());
  }
}
  

Set, List, Map Implementations

We can use the same approach for producing Fail-Fast wrappers for the Set, List and Map interfaces, but that is beyond the scope of this newsletter. List might be a bit tricky, since the ListIterator can also go back in the collection. Thus we can only define an inactive list iterator as one that is not being referenced from anywhere.

WeakReference vs. Finalizers?

We could also have overridden the finalize() method in our NoFailIterator, but that would not worked well at all. Finalization occurs in a separate thread, which would introduce a racing condition into our code. The calling thread should know immediately if one of the references has been cleared, but with the Finalizer thread involved, it would have to wait an indeterminate amount of time to be sure that the finalize() method had in fact been called. In our solution we remove the blank reference with the calling thread.

WeakHashMap vs. ConcurrentHashMap?

Instead of the ConcurrentHashMap, we could also have used a WeakHashMap, which would have reduced our code a bit. However, I wanted to be able to access the map concurrently and WeakHashMap is not threadsafe. We could have made it threadsafe by wrapping it with a synchronized map, an idiom quite common in the JDK, but that would have added unnecessary contention.

Next time you have a hard-to-find ConcurrentModificationException, try this approach to help find the code that is causing the collection to be modified whilst you are iterating. Please let me know if this was of help to you.

Kind regards

Heinz

Tips and Tricks Articles Related Java Course