Friday, February 10, 2012

fail-safe vs fail-fast Iterator in Java

Difference between fail-safe and fail-fast Iterator is becoming favorite core java interview questions day by day, reason
it touches concurrency a bit and interviewee can go deep on it to ask how fail-safe or fail-fast behavior is implemented.
In this article article we will see what is fail-safe and fail fast iterators in java and differences between fail-fast and fail-safe iterators . Concept of fail-safe iterator are relatively new in Java and first introduced with Concurrent Collections in Java 5 like ConcurrentHashMap and CopyOnWriteArrayList.

 

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

fail-fast Iterators in Java

Difference between fail-safe vs fail-fast iterator in javaAs name suggest fail-fast Iterators fail as soon as they realized that structure of Collection has been changed since iteration has begun. Structural changes means adding, removing or updating any element from collection while one thread is Iterating over that collection. fail-fast behavior is implemented by keeping a modification count and if iteration thread realizes the change in modification count it throws ConcurrentModificationException.

Java doc says this is not a guaranteed behavior instead its done of "best effort basis", So application programming can not  rely on this behavior. Also since multiple threads are involved while updating and checking modification count and this check  is done without synchronization, there is a chance that Iteration thread still sees a stale value and might not be able to detect any change done by parallel threads. Iterators returned by most of JDK1.4 collection are fail-fast including Vector, ArrayList, HashSet etc. to read more about Iterator see my post What is Iterator in Java.

fail-safe Iterator in java

Contrary to fail-fast Iterator, fail-safe iterator doesn't throw any Exception if Collection is modified structurally
while one thread is Iterating over it because they work on clone of Collection instead of original collection and that’s why they are called as fail-safe iterator. Iterator of CopyOnWriteArrayList is an example of fail-safe Iterator also iterator written by ConcurrentHashMap keySet is also fail-safe iterator and never throw ConcurrentModificationException in Java.


That’s all on difference between fail-safe vs fail-fast Iterator in Java, As I said due to there confusing or not to easy differentiation they are quickly becoming popular java collection questions asked on various level of java interview. Let me know if you are aware of any other difference between fail-fast and fail-safe iterator.


Other Interview question you may like

8 comments :

skataria said...

Structural changes means adding or removing. Updating any element from collection is not structural change.

Please check as I found on net at many places this definition.

Joro Mitev said...
This comment has been removed by the author.
Anonymous said...

1) Please give example code of ConcurrentModificationException
2) How it happens?
3) How we can avoid the ConcurrentModificationException in the code?

Sanjeev Kumar said...

CopyOnWrite concept is useful only when thread need copy of collection for read purpose.

Anonymous said...

Hey mate, what is difference between fail-fast and weekly consistent iterator? does fail-safe and weekly consistent iterator refers to same thing? As you pointed out that iterators of many concurrent collections e.g. ConcurrentHashMap and CopyOnWriteArrayList are fail-safe, which I have read somewhere that they are also weekly consistent with original collection.

Achint Mittal said...

Hi

very nice article. But i would suggest you to correct the statement : "Structural changes means adding, removing or updating any element from collection while one thread is Iterating over that collection".

Structural change does not include updating element. So, for example, while iterating over HashMap, if we update 'value' object for a key using put() operation, then this is not a structural change and ConcurrentModificationException is not thrown. The reason being that modCount variable is not incremented when we update 'value' object for an existing key.

Here is Java HashMap put() implementation :

public V More ...put(K key, V value) {
387 if (key == null)
388 return putForNullKey(value);
389 int hash = hash(key.hashCode());
390 int i = indexFor(hash, table.length);
391 for (Entry e = table[i]; e != null; e = e.next) {
392 Object k;
393 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
394 V oldValue = e.value;
395 e.value = value;
396 e.recordAccess(this);
397 return oldValue;
398 }
399 }
400
401 modCount++;
402 addEntry(hash, key, value, i);
403 return null;
404 }

So, modCount is incremented only when a new key-value pair is added, and not for updating an existing entry.

Best regards, Achint Mittal

praveen said...

public class FailFastTest {
public static void main(String[] args) {

ArrayList nameList = new ArrayList();
nameList.add("praveen");
nameList.add("ravi");
nameList.add("javarevisited");
nameList.add("chinni");

Iterator itr = nameList.iterator();
while (itr.hasNext()) {
String string = (String) itr.next();
int temp = string.indexOf(string);
if ("javarevisited".equals(string)) {
nameList.remove(temp);
}
System.out.println(string);
}
}
}
Console:
praveen
ravi
john
javarevisited
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(Unknown Source)
at java.util.ArrayList$Itr.next(Unknown Source)
at com.failfast.component.FailFastTest.main(FailFastTest.java:24)

SARAL SAXENA said...

@Javin nice article one very important thing that is missing Ithat I want to highlight is that..

you look at the code for a Collection implementation, lets pick ArrayList; we have a modCount variable declared in AbstractList:

protected transient int modCount = 0;

And then in each and every modifying method (for example remove) for the ArrayList we have

public E remove(int index) {
rangeCheck(index);

modCount++;
//....

So the modCount is only ever incremented; it is never decremented.

In the Iterator we then have:

final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}

Where expectedModCount is a snapshot of the modCount taken at Iterator creation.

So if there is any modification to the underlying List while the same instance of an Iterator is in use then a ConcurrentModificationException will be thrown.

I suppose there is a corner case where if you carried out enough modifications then the int would overflow and return to it's original value again - this would be a rather large number or modifications however; 232 to be precise.

Post a Comment