Sunday 19 February 2012

Difference between fail-fast Iterator vs fail-safe Iterator in Java

Fail-fast Iterators fail as soon as they realized that structure of Collection has been changed since iteration has begun.
The iterators returned by ArrayList's iterator and listIterator methods are fail-fast: if list is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove or add methods, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

Implementation of fail-fast Iterators

AbstractList class contains a field protected transient int modCount,stores the number of times this list has been structurally modified. Structural modifications are those that change the size of the list, or otherwise perturb it in such a fashion that iterations in progress may yield incorrect results.
This field is used by the iterator and list iterator implementation returned by the iterator and listIterator methods. If the value of this field changes unexpectedly, the iterator (or list iterator) will throw a ConcurrentModificationException in response to the next, remove, previous, set or add operations. This provides fail-fast behavior, rather than non-deterministic behavior in the face of concurrent modification during iteration.


Let us see one example :

 import java.util.*;

public class Main {

    public static void main(String[] args) {
        ArrayList list = new ArrayList();
        list.add("one");
        Iterator i = list.iterator();
        list.add("two");
        while(i.hasNext())
        System.out.println(i.next());
    }

}

The output is : 

Exception in thread "main" java.util.ConcurrentModificationException
    at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:782)
    at java.util.ArrayList$Itr.next(ArrayList.java:754)
    at Main.main(Main.java:11)

The reason for this exception is that after the creation of the iterator i the structure of the list has been changed by adding one element "two" into it.

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

The fail-fast behavior of iterator is not mandatory for all the implementations of the Collection.You can implement Collection with fail-safe iterator by just ignoring the above mentioned modCount field.

Let us discuss about one fail-safe iterator implementation:


java.util.concurrent.CopyOnWriteArrayList<E>

Type Parameters:
E - the type of elements held in this collection
All Implemented Interfaces:
Serializable, Cloneable, Iterable<E>, Collection<E>, List<E>, RandomAccess
A thread-safe variant of ArrayList in which all mutative operations (add, set, and so on) are implemented by making a fresh copy of the underlying array.
This is ordinarily too costly, but may be more efficient than alternatives when traversal operations vastly outnumber mutations, and is useful when you cannot or don't want to synchronize traversals, yet need to preclude interference among concurrent threads. The "snapshot" style iterator method uses a reference to the state of the array at the point that the iterator was created. This array never changes during the lifetime of the iterator, so interference is impossible and the iterator is guaranteed not to throw ConcurrentModificationException. The iterator will not reflect additions, removals, or changes to the list since the iterator was created. Element-changing operations on iterators themselves (remove, set, and add) are not supported. These methods throw UnsupportedOperationException.

See the above example with CopyOnWriteArrayList class

import java.util.Iterator;
import java.util.concurrent.CopyOnWriteArrayList;

public class Main {

    public static void main(String[] args) {
        CopyOnWriteArrayList list = new CopyOnWriteArrayList();
        list.add("one");
        Iterator i = list.iterator();
        list.add("two");
        while (i.hasNext())
            System.out.println(i.next());
    }

}

The output is

 one

You can see that ConcurrentModificationException is not thrown by the iterator even then the list structure has changed after the iterator creation.The iterator does not reflect the addition of an element "two" to the list since the iterator was created.

1 comment: