Friday, November 29, 2013

Fail-Safe vs Fail-Fast Iterator in Java Collections

Fail-Safe vs Fail-Fast Iterator in Java Collections Framework

In the face of concurrent modification, the fail-fast iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future

Fail-Fast Iterator

java.util Package
Classes in java.util package provide fail-fast iterator by Design - ArrayList, HashMap, HashSet, TreeSet, etc.
Iterator is called fail-fast if the underlying collection 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. Iterator fails as soon as it realizes that the structure of the underlying data structure has been modified since the iteration has begun.
Most Collection’s Iterator & listIterator under package java.util package are fail-fast by Design. These are not meant for multi-threading/ structural modification while iteration.
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. This class is a member of the Java Collections Framework.
Java Source - Fail-fast Iterator
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package com.shunya.tutorials;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class FailFastIterator {
    public static void main(String args[]) {
        List<Integer> failFastList = new ArrayList<>();
        failFastList.add(10);
        failFastList.add(20);
        failFastList.add(30);
        failFastList.add(40);
        int indexFlag = 0;
        Iterator it = failFastList.iterator();
        while (it.hasNext()) {
            if (++indexFlag == 2) {    (1)
                failFastList.remove(indexFlag);
            }
            System.out.println(it.next());
        }
    }
}
  1. This program will throw java.util.ConcurrentModificationException after printing 10, because a structural modification was done to the collection by means other than iterator’s own add or remove method.
Program output
10
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:907)
at java.util.ArrayList$Itr.next(ArrayList.java:857)
at com.shunya.tutorials.FailFastIterator.main(FailFastIterator.java:20)
Same Java Program but using Iterator to remove the element
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private static void failFastProperWay() {
        List<Integer> failFastList = new ArrayList<>();
        failFastList.add(10);
        failFastList.add(20);
        failFastList.add(30);
        failFastList.add(40);
        int indexFlag = 0;
        Iterator it = failFastList.iterator();
        while (it.hasNext()) {
            if (++indexFlag == 2) {
                it.remove();    (1)
            }
            System.out.println(it.next());
        }
    }
Program output
10, 20, 30, 40,
  1. Since we are using Iterator to remove the element, this code will not throw ConcurrentModificationException.
Important Takeaways
  1. Collection.toString() method requires iteration over the elements of collection, so they may throw exception if some parallel thread modifies the underlying collection data at the same time. This may happen even while logging a collection in the logger/Sysytem.out.println()
  2. Structural changes means adding, removing any element from the collection, merely updating some value in the data structure does not count for the structural modifications. It is implemented by keeping a modification count and if iterating thread realizes the changes in modification count, it throws ConcurrentModificationException.

Fail-Safe Iterator

java.util.concurrent Package
Classes in java.util.concurrent package provide fail-safe iterator by Design - ConcurrentSkipListSet, CopyOnWriteArrayList, ConcurrentHashMap, ConcurrentLinkedQueue, etc.
Fail-safe Iterator is "Weakly Consistent" and does not throw any exception if collection is modified structurally during the iteration. Such Iterator may work on clone of collection instead of original collection - such as in CopyOnWriteArrayList. While ConcurrentHashMap’s iterator returns the state of the hashtable at some point at or since the creation of iterator. Most collections under java.util.concurrent offer fail-safe Iterators to its users and that’s by Design. Fail safe collections should be preferred while writing multi-threaded applications to avoid concurrency related issues.
Fail Safe Iterator is guaranteed to list elements as they existed upon construction of Iterator, and may reflect any modifications subsequent to construction (without guarantee).
Java Source fail-safe Iterator
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private static void failSafeIterator() {
        List<Integer> failSafeList = new CopyOnWriteArrayList<>();
        failSafeList.add(10);
        failSafeList.add(20);
        failSafeList.add(30);
        failSafeList.add(40);
        int indexFlag = 0;
        Iterator it = failSafeList.iterator();
        while (it.hasNext()) {
            if (++indexFlag == 2) {
                failSafeList.remove(indexFlag);
            }
            System.out.print(it.next()+", ");
        }
    }
Program Output
10, 20, 30, 40,

For more such questions, you can get my ebook

No comments:

Post a Comment

Your comment will be published after review from moderator