removal→iterator invalidation:STL,fail fast,ConcurrentMap

This is a blog post tying up a few discussions on this subject. It’s instructive to compare the different iterators in different contexts in the face of a tricky removal operation.

http://tech.puredanger.com/2009/02/02/java-concurrency-bugs-concurrentmodificationexception/ points out that ConcurrentModEx can occur even in single-threaded myList.remove(..). Note this is not using myIterator.remove(void).

[[Java generics]] also says single-threaded program can hit CMEx. The official javadoc https://docs.oracle.com/javase/7/docs/api/java/util/ConcurrentModificationException.html agrees.

ConcurrentHashMap never throws this CMEx. See http://bigblog.tanbin.com/2011/09/concurrent-hash-map-iterator.html. Details? not available yet.

Many jdk5 concurrent collections have thread safe iterators. [[java generics]] covers them in some detail.

As seen in http://bigblog.tanbin.com/2011/09/removeinsert-while-iterating-stl.html, all STL graph containers (include slist) can cope with removals, but contiguous containers can get iterators invalidated. Java arrayList improves on it by allowing iterator to perform thread-safe remove. I guess this is possible because the iterator thread could simplify skip the dead node. Any other iterator is invalidated by CMEx. I guess the previous nodes can shift up.

–brief history

  1. STL iterator invalidation results in undefined behavior. My test shows silent erroneous result. Your code continues to run but result can be subtly wrong.
  2. In java, before fail-fast, the outcome is also undefined behavior.
  3. Fail-fast iterator is the java solution to the iterator invalidation issue. Fail-fast iterators all throw CMEx, quickly and cleanly. I think CMEx is caused by structural changes — mostly removal and insertions.
  4. CHM came after fail-fast, and never throws CMEx
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s