Friday, November 13, 2009

Do your Iterators always fail-fast?

The iterators of the Collection implementations of the Java runtime throw a ConcurrentModificationException[1] when they detect that another thread has modified the Collection while a thread is iterating over it. Such iterators are generally called fail-fast iterators.

Looking at the implementation one can see how this has been made possible. The Collection subclass maintains an integer modCount that is incremented on every operation that structurally modifies the collection (like add, remove, clear). The fail-fast iterators also contain an integer field expectedModCount which is initialized to the modCount while the iterator is created. Later on, during every iteration, the iterator verifies if the expectedModCount is same as the modCount of the collection it is iterating over. A mismatch means that the collection has been modified during the life cycle of the iterator and a ConcurrentModificationException is thrown. The same happens during the collection serialization process. The modification count prior to writing to the stream should be same as the count after writing to the stream.

But is this behavior guaranteed? Are these iterators always fail-fast? I used to think so, until I saw the declaration of the modCount field in the Collection implementations.

The modCount field is not marked as volatile. This would mean - while a thread makes structural changes to the collection and increments the modCount field, the other thread that performs the iteration or serialization might not see the incremented value of the modCount field. It might end up doing a comparison with the stale modCount that is visible to it. This might cause the fail-fast iterators to behave in a different way and failing at a later point.
The field is non-volatile in Apache Harmony too.

A bug[2] in Sun Java explains this. It says the modCount was intentionally made non-volatile. Making it volatile would have added contention at every collection modification operation because of the memory fencing that’s required.

Also the Javadoc clearly says “fail-fast behavior cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification”.


This behavior would be the same even on the Synchronized wrapper's of these collections.

[1] http://java.sun.com/j2se/1.5.0/docs/api/java/util/ConcurrentModificationException.html
[2] http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6625725

12 comments:

Dhananjay Nene said...

If the iterator is certainly going to fail a little later in a some few cases, I can't see why this is an issue. Its OK imo to treat failfast as a soft constraint.

Bharath said...

Yeah, the point here is you should not be relying on ConcurrentModificationException in your code.

Odi said...

The mechanism isn't primarily useful for concurrent threads, but for nested calls:

for (Object o : list) {
...
list.remove(0);
...
}

Unsynchronized Collection don't need to guard for concurrent threads: they are not thread-safe anyway. Synchronized Collections update modCount consistently (all operations are synchronized) and the field doesn't need to be volatile.

Bharath said...

Unsynchronized Collection don't need to guard for concurrent threads: they are not thread-safe anyway.

True, but their iterator operations claim to throw an exception in case of modification. So its a kind of optimistic approach taken by the iterators. And that's fail-fast

Synchronized Collections update modCount consistently (all operations are synchronized) and the field doesn't need to be volatile.


No, even in the case of Synchronized collections only the add, remove, clear operations are synchronized. The iterator operations are not synchronized, So there would be visibility issues with the value of the modCount field. The thread that does the iterator operations might not work with the updated value of the modCount field.

Anonymous said...

Hello!
You may probably be very curious to know how one can manage to receive high yields on investments.
There is no initial capital needed.
You may commense to get income with a sum that usually is spent
for daily food, that's 20-100 dollars.
I have been participating in one project for several years,
and I'll be glad to let you know my secrets at my blog.

Please visit my pages and send me private message to get the info.

P.S. I earn 1000-2000 per day now.

http://theinvestblog.com [url=http://theinvestblog.com]Online Investment Blog[/url]

Joshua Smith said...

The survey is good. Thanks for news. To protect yourself from future losses try compare homeowners insurance quotes by zip code to save more on home insurance policies.

Free Poker said...

This is really very informative service and all your articles are hot as hell, lots of useful stuff. One thing I just want to say is that your site is so great to me.
--------------------------
Our website: Texas Holdem Poker

Poker said...

This is extremely impressive content. I like how you brought forward many clear viewpoints and I agree with many. Your article coaxes thought out of the reader from start to finish. I really like this.
--------------------------
Bonus Sans Depot & Bonos Sin Deposito Poker & Bonus ohne einzahlung & Poker Bonus senza deposito

Poker said...

Your blog post is very unique and well research, Thanks for your research on academic knowledge…
--------------------------
My site: Poker Without Deposit 100% free online poker !

medical loupes said...

Câble 30 PIN pour l’outil de diagnostic Citroën Lexia-3
AK-47

Poker Bonus said...

I was really happy to visit this service. I needed to thank you for this fantastic posts!
Regards
--------------

Holdem Poker Bonuses
Learn free holdem no limit poker easy
Instant Poker Bankroll
Play online games like casino slots poker blackjack form free
Darmowy kapitał startowy
Darmowy bonus na pokera za darmo bonusy bez depozytu
Poker bonus senza deposito
No deposit poker bonus
Poker online promotions
Play texas holdem games with players from Ukraine Belarus Korea Canada
Start capital poker
Get startup capital to playing poker every day
no deposit poker






All best for visitors in new year 2013.
--------------
Cheap 15 inch laptop
Sony 42 inch Tv

No Deposit Bonus said...

like to play other poker games like bingo but texas poker is one of my famous currently