import java.util.*; /** * This test program compares performance of Vector versus ArrayList * @author www.codejava.net * */ public class CollectionsThreadSafeTest { public void testVector() { long startTime = System.currentTimeMillis(); Vector<Integer> vector = new Vector<>(); for (int i = 0; i < 10_000_000; i++) { vector.addElement(i); } long endTime = System.currentTimeMillis(); long totalTime = endTime - startTime; System.out.println("Test Vector: " + totalTime + " ms"); } public void testArrayList() { long startTime = System.currentTimeMillis(); List<Integer> list = new ArrayList<>(); for (int i = 0; i < 10_000_000; i++) { list.add(i); } long endTime = System.currentTimeMillis(); long totalTime = endTime - startTime; System.out.println("Test ArrayList: " + totalTime + " ms"); } public static void main(String[] args) { CollectionsThreadSafeTest tester = new CollectionsThreadSafeTest(); tester.testVector(); tester.testArrayList(); } }This program performs the test by comparing the time needed to add ten millions of elements into each collection. And here’s a result:
Test Vector: 9266 ms Test ArrayList: 4588 ms
List<String> listNames = Arrays.asList("Tom", "Joe", "Bill", "Dave", "John"); Iterator<String> iterator = listNames.iterator(); while (iterator.hasNext()) { String nextName = iterator.next(); System.out.println(nextName); }Here, we use the collection’s iterator to traverse through elements in the collection. Imagine the listNames is shared between two threads: the current thread that executes the iteration, and another thread. Now imagine the second thread is modifying the collection (adding or removing elements) while the first thread is still iterating over the elements. Can you guess what happens?The iteration code in the first thread throws ConcurrentModificationException and fails immediately, hence the term ‘fail-fast iterators’.Why does the iterator fail so fast? It’s because iterating a collection while it is being modified by another thread is very dangerous: the collection may have more, less or no elements after the iterator has been obtained, so that leads to unexpected behavior and inconsistent result. And this should be avoided as early as possible, thus the iterator must throw an exception to stop the execution of the current thread.The following test program mimics a situation that throws ConcurrentModificationException:
import java.util.*; /** * This test program illustrates how a collection's iterator fails fast * and throw ConcurrentModificationException * @author www.codejava.net * */ public class IteratorFailFastTest { private List<Integer> list = new ArrayList<>(); public IteratorFailFastTest() { for (int i = 0; i < 10_000; i++) { list.add(i); } } public void runUpdateThread() { Thread thread1 = new Thread(new Runnable() { public void run() { for (int i = 10_000; i < 20_000; i++) { list.add(i); } } }); thread1.start(); } public void runIteratorThread() { Thread thread2 = new Thread(new Runnable() { public void run() { ListIterator<Integer> iterator = list.listIterator(); while (iterator.hasNext()) { Integer number = iterator.next(); System.out.println(number); } } }); thread2.start(); } public static void main(String[] args) { IteratorFailFastTest tester = new IteratorFailFastTest(); tester.runIteratorThread(); tester.runUpdateThread(); } }As you can see, the thread1 is iterating the list, while the thread2 adds more elements to the collection. This causes the ConcurrentModificationException to be thrown.Note that the fail-fast behavior of collection’s iterators intends to help find and diagnose bugs easily. We should not rely on it to handle ConcurrentModificationException in our programs, because the fail-fast behavior is not guaranteed. That means if this exception is thrown, the program should stop immediately, instead of continuing the execution.Now you understand how ConcurrentModificationExceptionworks and it’s better to avoid it.
Collections.synchronizedXXX(collection)
These factory methods wrap the specified collection and return a thread-safe implementation. Here, XXX can be Collection, List, Map, Set, SortedMap and SortedSet implementations. For example, the following code creates a thread-safe list collection:List<String> safeList = Collections.synchronizedList(new ArrayList<>());If we have an existing non-thread-safe collection, we can wrap it in a thread-safe collection like this:
Map<Integer, String> unsafeMap = new HashMap<>(); Map<Integer, String> safeMap = Collections.synchronizedMap(unsafeMap);You see, these factory methods wrap the specified collection in an implementation having same interfaces as the wrapped collection but all the methods are synchronized to provide thread-safety, hence the term ‘synchronized wrappers’. Actually, the synchronized collection delegate all work to the wrapped collection. NOTE: When using the iterator of a synchronized collection, we should use synchronized block to safeguard the iteration code because the iterator itself is not thread-safe. Consider the following code:
List<String> safeList = Collections.synchronizedList(new ArrayList<>()); // adds some elements to the list Iterator<String> iterator = safeList.iterator(); while (iterator.hasNext()) { String next = iterator.next(); System.out.println(next); }Although the safeList is thread-safe, its iterator is not, so we should manually add synchronized block like this:
synchronized (safeList) { while (iterator.hasNext()) { String next = iterator.next(); System.out.println(next); } }Also note that the iterators of the synchronized collections are fail-fast.Although synchronized wrappers can be safely used in multi-threaded applications, they have drawbacks as explained in the next section. 4. Concurrent CollectionsA drawback of synchronized collections is that their synchronization mechanism uses the collection object itself as the lock object. That means when a thread is iterating over elements in a collection, all other collection’s methods block, causing other threads having to wait. Other threads cannot perform other operations on the collection until the first thread release the lock. This causes overhead and reduces performance.That’s why Java 5 (and beyond) introduces concurrent collections that provide much better performance than synchronized wrappers. The concurrent collection classes are organized in the java.util.concurrent package. They are categorized into 3 groups based on their thread safety mechanisms. * The first group is copy-on-write collections: this kind of thread-safe collections stores values in an immutable array; any change to the value of the collection results in a new array being created to reflect the new values. These collections are designed for situations in which read operations greatly predominate write operations. There are two implementations of this kind: CopyOnWriteArrayList and CopyOnWriteArraySet.Note that copy-on-write collections have snapshot iterators which do not throw ConcurrentModificationException. Since these collections are backed by immutable arrays, an iterator can read the values in one of these arrays (but never modify them) without danger of them being changed by another thread. * The second group is Compare-And-Swap or CAS collections: the collections in this group implement thread safety using an algorithm called Compare-And-Swap (CAS) which can be understood like this:To perform calculation and update value of a variable, it makes a local copy of the variable and performs the calculation without getting exclusive access. When it is ready to update the variable, it compares the variable’s value with its value at the start and, if they are the same, updates it with the new value.If they are not the same, the variable must have been changed by another thread. In this situation, the CAS thread can try the whole computation again using the new value, or give up, or continue. Collections using CAS include ConcurrentLinkedQueue and ConcurrentSkipListMap.Note that the CAS collections have weakly consistent iterators, which reflect some but not necessarily all of the changes that have been made to their backing collection since they were created. Weakly consistent iterators do not throw ConcurrentModificationException. * The third group is concurrent collections using a special lock object (java.util.concurrent.lock.Lock): This mechanism is more flexible than classical synchronization. This can be understood as following:A lock has the same basic behavior as classical synchronization but a thread can also acquire it under special conditions: only if the lock is not currently held, or with a timeout, or if the thread is not interrupted.Unlike synchronization code, in which an object lock is held while a code block or a method is executed, a Lock is held until its unlock() method is called. Some implementations make use of this mechanism to divide the collection into parts that can be separately locked, giving improved concurrency. For example, LinkedBlockingQueue has separate locks for the head and the tail ends of the queue, so that elements can be added and removed in parallel.Other collections using this lock include ConcurrentHashMap and most of the implementations of BlockingQueue.Collections in this group also have weakly consistent iterators and do not throw ConcurrentModificationException.Let’s summarize the most important points we’ve learned so far today: