java.util.concurrent.CopyOnWriteArrayList Example

Armando FloresOctober 13th, 2014Last Updated: October 13th, 2014

1 101 7 minutes read

In this post, we are going to discuss about the class java.util.concurrent.CopyOnWriteArrayList and give you and idea of how you can use it on your own code when building robust multi-threaded applications.

1. Introduction

Data structures are a basic element in programming. Almost every program uses one or more types of data structures to store and manage their data. Java API provides the Java Collections Framework that contains interfaces, classes, and algorithms, which implement a lot of different data structures that you can use in your programs.

When you need to work with data collections in a concurrent program, you must be very careful with the implementation you choose. Most collection classes are not ready to work with concurrent applications because they don’t control the concurrent access to its data. If some concurrent tasks share a data structure that is not ready to work with concurrent tasks, you can have data inconsistency errors that will affect the correct operation of the program. One example of this kind of data structures is the ArrayList class.

Java provides data collections that you can use in your concurrent programs without any problems or inconsistency. Basically, Java provides two kinds of collections to use in concurrent applications:

Blocking collections: This kind of collection includes operations to add and remove data. If the operation can’t be made immediately, because the collection is full or empty, the thread that makes the call will be blocked until the operation can be made.
Non-blocking collections: This kind of collection also includes operations to add and remove data. If the operation can’t be made immediately, the operation returns a null value or throws an exception, but the thread that makes the call won’t be blocked.

1.1 Synchronized Collections

Java provides synchronized collection classes which includes Vector and Hashtable, part of the original JDK, as well their cousins added in JDK 1.2, the synchronized wrapper classes created by the Collections.synchronizedXxx factory methods. These classes achieve thread safety by encapsulating their sate and synchronizing every public method so that only one thread at a time can access the collection state.

1.1.1 Problems with Synchronized Collections

The synchronized collections are thread-safe, but you may sometimes need to use additional client-side locking to guard compound actions Common compound actions on collections include iteration (repeatedly fetch elements until the colletion is exhausted), navigation (find the next element after this one according to some order), and conditional operations such as put-if-absent (check if a Map has a mapping for key K, and if not, add the mapping (K,V)). With a synchronized collection, these compound actions are still technically thread-safe even without client-side locking, but they may not behave as you might expect when other threads can concurrently modify the collection.

1.1.2 Iterators and the ConcurrentModificationException

The standard way to iterate a Collection is with an Iterator, either explicitly or through the for-each loop syntax introduced in Java 5, but using iterators does not obviate the need to lock the collection are not designed to deal with concurrent modification, and they are fail-fast – meaning that if they detect that the collection has changed since iteration began, they throw the unchecked ConcurrentModificationException.

These fail-fast iterators are not designed to be foolproof, they are designed to catch concurrency errors on a “good faith-effort” basis and thus act only as early-warning indicators for concurrency problems. They are implemented by associating a modification count with the collection: if the modification count changes during iteration, hasNext or next throws ConcurrentModificationException. However, this check is donde without synchronization, so there is a risk of seeing a stale value of the modification count and therefore that the iterator does not realize a modification has been made. This was a debilerate design tradeoff to reduce the performance impact of the concurrent modification detection code.

1.2 Concurrent Collections

Java 5 improves on the synchronized collections by providing several concurrent collection classes. Synchronized collections achieve their thread safety by serializing all access the collection’s state. The cost of this approach is poor concurrency; when multiple threads contend for the collection-wide lock, throughput suffers.

The concurrent collections, on the other hand, are designed for concurrent access from multiple threads. Java 5 adds ConcurrentHashMap, a replacement for synchronized hash-based Map implementations, and CopyOnWriteArrayList, a replacement for synchronized List implementations for cases where traversal is the dominant operation. The new ConcurrentMap interface adds support for common compound actions such as put-if-absent, replace, and conditional remove.

The concurrent collections provide high-performance concurrent implementations of standard collection interfaces such as List, Queue, and Map. To provide high concurrency, these implementations manage their own synchronization internally. Therefore, it is impossible to exclude concurrent activity from a concurrent collection; locking it will have no effect but to slow the program.

Replacing synchronized collections with concurrent collections can offer dramatic scalability improvements with little risk.

2. CopyOnWriteArrayList Class

CopyOnWriteArrayList is a concurrent replacement for a synchronized List that offers better concurrency in some common situations and eliminates the need to lock or copy the collection during iteration. (Similary, CopyOnWriteArraySet is a concurrent replacement for a synchronized Set.)

The copy-on-write collections derive their thread safety from the fact that as long as an effectively immutable object is properly published, no further synchronization is required when accessing it. They implement mutability by creating and republishing a new copy of the collection every time it is modified. Iterators for the copy-on-write collections retain a reference to be backing array that was current at the start of iteration, and since this will never change, they need to synchronize only briefly to ensure visibility of the array contents. As a result, multiple threads can iterate the collection without interference from threads wanting to modify the collection. The iterators returned by the copy-on-write collections do not throw ConcurrentModificationException and return exactly as they were at the time the iterator was created, regardless of subsequent modifications.

Obviously, there is some cost to copying the backing array every time the collection is modified, especially if the collection is large; the copy-on-write collections are reasonable to use only when iteration is far more common than modification. This criterion exactly describes many event-notification systems: delivering a notification requires iterating the list of registered listeners and calling each one of them, and in most cases registering or unregistering an event listener is far less common than receiving an event notification.

3. Executing some code

IterateMe.java

package com.javacodegeeks.examples.copyonwritearraylist.runnables;

//~--- JDK imports ------------------------------------------------------------

import java.util.Iterator;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.TimeUnit;
import java.util.logging.Level;
import java.util.logging.Logger;

public class IterateMe implements Runnable {
    private static final CopyOnWriteArrayList<String> nameList = new CopyOnWriteArrayList<>(new String[] { "Peter",
            "Bruce", "Clark", "Barry", "Lex" });
    private final Logger logger = Logger.getLogger("IterateMe");
    private String       threadName;
    private boolean      goToSleep;

    public IterateMe() {}

    public IterateMe(String threadName, boolean goToSleep) {
        this.threadName = threadName;
        this.goToSleep  = goToSleep;
    }

    public static CopyOnWriteArrayList<String> getNameList() {
        return nameList;
    }

    public void setGoToSleep(boolean goToSleep) {
        this.goToSleep = goToSleep;
    }

    @Override
    public void run() {
        if (this.goToSleep) {
            try {
                logger.info(this.threadName + " sleeping...");
                TimeUnit.SECONDS.sleep(3);
            } catch (InterruptedException ie) {
                logger.log(Level.SEVERE, ie.getLocalizedMessage());
            }
        }

        logger.info(this.threadName + ", nameList:");

        Iterator<String> it = nameList.iterator();

        while (it.hasNext()) {
            System.out.println(it.next());
        }
    }
}

ResultTask.java

package com.javacodegeeks.examples.copyonwritearraylist;

//~--- non-JDK imports --------------------------------------------------------

import com.javacodegeeks.examples.copyonwritearraylist.runnables.IterateMe;

//~--- JDK imports ------------------------------------------------------------

import java.util.Iterator;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.logging.Logger;

public class App {
    private static final Logger  logger         = Logger.getLogger("App");
    private static final Integer NUM_OF_THREADS = 3;

    public static void main(String[] args) {

        // Create ExecutorService using the newFixedThreadPool() method
        // of the Executors class.
        ExecutorService executorService = Executors.newFixedThreadPool(App.NUM_OF_THREADS);

        // Create an array to store IterateMe objects.
        IterateMe[] iterateMes = new IterateMe[App.NUM_OF_THREADS];
        for (int i = 0; i < App.NUM_OF_THREADS; i++) {
            iterateMes[i] = new IterateMe("Thread-" + i, false);
        }

        // Print IterateMe.nameList original context
        logger.info("Original content:");

        // "for" variant uses internally an Iterator
        for (String name : IterateMe.getNameList()) {
            System.out.println(name);
        }

        // Execute Thread
        executorService.submit(iterateMes[0]);

        // Costly operation - A new copy of the collection is created
        IterateMe.getNameList().addIfAbsent("Oliver");

        // Execute Thread
        iterateMes[1].setGoToSleep(true);
        executorService.submit(iterateMes[1]);

        // Costly operation - A new copy of the collection is created
        IterateMe.getNameList().remove("Lex");

        // Execute Thread
        executorService.submit(iterateMes[2]);

        // Try to remove an element using Iterator methods
        // This is NOT supported by CopyOnWriteArrayList's Iterator
        Iterator<String> it = IterateMe.getNameList().iterator();
        while (it.hasNext()) {
            try {
                it.remove();
            } catch (UnsupportedOperationException uoe) {
                uoe.printStackTrace(System.err);

                break;
            }
        }

        // Shutdown ExecutionService
        executorService.shutdown();
    }
}

Let’s explain the methods used in the previous code

public boolean addIfAbsent(E e) – Append the element if not present.
public boolean remove(Object o) – Removes the first occurrence of the specified element from this list, if it is present. If this list does not contain the element, it is unchanged. More formally, removes the element with the lowest index i such that (o==null ? get(i)==null : o.equals(get(i))) (if such an element exists). Returns true if this list contained the specified element (or equivalently, if this list changed as a result of the call).
public Iterator iterator() – Returns an iterator over the elements in this list in proper sequence. The returned iterator provides a snapshot of the state of the list when the iterator was constructed. No synchronization is needed while traversing the iterator. The iterator does NOT support the remove method.
void remove() – Removes from the underlying collection the last element returned by this iterator (optional operation). This method can be called only once per call to next(). The behavior of an iterator is unspecified if the underlying collection is modified while the iteration is in progress in any way other than by calling this method.

The output of the command

com.javacodegeeks.examples.copyonwritearraylist.App

should be similar to:

Oct 12, 2014 4:47:33 PM com.javacodegeeks.examples.App main
INFO: Original content:
Peter
Bruce
Clark
Barry
Lex
java.lang.UnsupportedOperationException
	at java.util.concurrent.CopyOnWriteArrayList$COWIterator.remove(CopyOnWriteArrayList.java:1040)
	at com.javacodegeeks.examples.App.main(App.java:58)
Oct 12, 2014 4:47:33 PM com.javacodegeeks.examples.runnables.IterateMe run
INFO: Thread-0, nameList:
Peter
Bruce
Clark
Barry
Oliver
Oct 12, 2014 4:47:33 PM com.javacodegeeks.examples.runnables.IterateMe run
INFO: Thread-2, nameList:
Peter
Bruce
Clark
Barry
Oliver
Oct 12, 2014 4:47:33 PM com.javacodegeeks.examples.runnables.IterateMe run
INFO: Thread-1 sleeping...
Oct 12, 2014 4:47:36 PM com.javacodegeeks.examples.runnables.IterateMe run
INFO: Thread-1, nameList:
Peter
Bruce
Clark
Barry
Oliver