CopyOnWriteArrayList and Concurrent Collections

CopyOnWriteArrayList makes every write copy the whole array, so readers never need a lock and never see a change mid-iteration. That trade is excellent for lists that are read constantly and changed rarely, such as listener lists, and terrible for anything else. This page shows how it works, measures both sides of the trade, and introduces the other concurrent collections for queues and sorted data.

Share

Contents

How copy-on-write works

CopyOnWriteArrayList, added in Java 5 in java.util.concurrent, keeps its elements in an array referenced by a volatile field. Reading, including iteration, simply uses whatever array the field points to, without any lock. Every write, whether add, set or remove, takes a lock, copies the whole array with the change applied, and then points the field at the new copy.

Two properties follow. An iterator works on the array that existed when it was created, a snapshot, so it can never throw ConcurrentModificationException and never sees later changes. And each write costs time proportional to the size of the list, so n additions cost about n2/2 element copies. The class is meant for lists that are read far more often than they are written.

Concurrent collections in java.util.concurrent
ClassSinceHow it is safeBest for
CopyOnWriteArrayList, CopyOnWriteArraySetJava 5Copy the array on every writeListener lists, configuration read by many threads
ConcurrentHashMapJava 5Lock-free reads, per-bin write locksShared maps; see ConcurrentHashMap
ConcurrentLinkedQueue, ConcurrentLinkedDequeJava 5, Java 7Lock-free linked nodesUnbounded queues that never block
LinkedBlockingQueue, ArrayBlockingQueueJava 5Locks with waitingProducer and consumer threads
ConcurrentSkipListMap, ConcurrentSkipListSetJava 6Lock-free skip listSorted data shared between threads
Collections.synchronizedListJava 1.2One lock on every callSimple sharing with frequent writes

The programs ran on JDK 21. The multi-threaded ones give different numbers on each run.

Snapshot iteration

The program adds an element while looping over a list, once on an ArrayList and once on a CopyOnWriteArrayList, the situation that crashes ordinary lists.

Java
import java.util.ArrayList;
import java.util.ConcurrentModificationException;
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;

public class SnapshotIteration {

    public static void main(String[] args) {
        List<String> plain = new ArrayList<>(List.of("a", "b", "c"));
        try {
            for (String s : plain) {
                if (s.equals("a")) {
                    plain.add("d");
                }
            }
        } catch (ConcurrentModificationException e) {
            System.out.println("ArrayList: ConcurrentModificationException");
        }

        List<String> cow = new CopyOnWriteArrayList<>(List.of("a", "b", "c"));
        for (String s : cow) {
            if (s.equals("a")) {
                cow.add("d");               // writes go to a NEW array
            }
            System.out.print(s + " ");      // the loop keeps reading the OLD array
        }
        System.out.println();
        System.out.println("after loop: " + cow);

        // The iterator is read-only
        try {
            cow.iterator().remove();
        } catch (UnsupportedOperationException e) {
            System.out.println("iterator.remove: UnsupportedOperationException");
        }
    }
}

Output:

Output
ArrayList: ConcurrentModificationException
a b c 
after loop: [a, b, c, d]
iterator.remove: UnsupportedOperationException
  • The ArrayList loop threw ConcurrentModificationException on the next step after the add.
  • The copy-on-write loop printed only a b c: the iterator kept walking the old array, while the list itself now holds d as well.
  • Because the iterator's array is a snapshot, iterator.remove() is not supported and throws UnsupportedOperationException. Remove through the list, or use removeIf.

Removing elements from ordinary lists while looping is covered on the removing while iterating page.

The classic use: listener lists

An event source notifies listeners, and listeners may subscribe or unsubscribe while an event is being delivered. The program has a one-shot listener that removes itself and a late listener that subscribes during delivery.

Java
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.function.Consumer;

public class Listeners {

    // The classic use: many events fired, listeners rarely added or removed
    static final List<Consumer<String>> listeners = new CopyOnWriteArrayList<>();

    static void fire(String event) {
        for (Consumer<String> l : listeners) {      // no lock, no exception
            l.accept(event);
        }
    }

    public static void main(String[] args) throws InterruptedException {
        listeners.add(e -> System.out.println("logger got " + e));

        // A listener that removes itself while being called
        listeners.add(new Consumer<>() {
            @Override
            public void accept(String e) {
                System.out.println("one-shot got " + e + ", unsubscribing");
                listeners.remove(this);
            }
        });

        fire("start");
        fire("stop");

        Thread adder = new Thread(() -> listeners.add(e -> System.out.println("late got " + e)));
        adder.start();
        adder.join();
        fire("restart");
    }
}

Output:

Output
logger got start
one-shot got start, unsubscribing
logger got stop
logger got restart
late got restart
  • The one-shot listener unsubscribed inside its own callback, and the loop that was calling it continued safely; it did not receive stop.
  • The late listener was added during the stop event but only received restart, because each fire iterates the snapshot taken when it started.
  • No locks appear in the code. Listeners change rarely and events are frequent, which is exactly the trade copy-on-write makes. Swing, Android and many event libraries use this pattern.

The cost of writes

To show the other side, the program adds 20,000 and then 40,000 elements one at a time to a synchronized list and to a copy-on-write list, and finally adds 40,000 in a single addAll. Each figure is the best of three runs.

Java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.function.Supplier;

public class WriteCost {

    // Best of 3: fill a fresh list from the supplier with n single adds
    static double timeAdds(Supplier<List<Integer>> make, int n) {
        long best = Long.MAX_VALUE;
        for (int run = 0; run < 3; run++) {
            List<Integer> list = make.get();
            long start = System.nanoTime();
            for (int i = 0; i < n; i++) {
                list.add(i);
            }
            best = Math.min(best, System.nanoTime() - start);
        }
        return best / 1e6;
    }

    public static void main(String[] args) {
        timeAdds(CopyOnWriteArrayList::new, 5_000);           // warm-up
        List<Integer> source = new ArrayList<>();
        for (int i = 0; i < 40_000; i++) {
            source.add(i);
        }
        System.out.println("best of 3 runs:");
        for (int n : new int[] {20_000, 40_000}) {
            System.out.printf("  %,d adds, synchronizedList:     %7.1f ms%n", n,
                timeAdds(() -> Collections.synchronizedList(new ArrayList<>()), n));
            System.out.printf("  %,d adds, CopyOnWriteArrayList: %7.1f ms%n", n,
                timeAdds(CopyOnWriteArrayList::new, n));
        }
        long best = Long.MAX_VALUE;
        for (int run = 0; run < 3; run++) {
            long start = System.nanoTime();
            List<Integer> cow = new CopyOnWriteArrayList<>();
            cow.addAll(source);
            best = Math.min(best, System.nanoTime() - start);
        }
        System.out.printf("  40,000 elements, one addAll:     %7.2f ms%n", best / 1e6);
    }
}

Output (JDK 21 on a shared 2-CPU Linux machine; treat the times as rough):

Output
best of 3 runs:
  20,000 adds, synchronizedList:         0.5 ms
  20,000 adds, CopyOnWriteArrayList:   104.1 ms
  40,000 adds, synchronizedList:         1.1 ms
  40,000 adds, CopyOnWriteArrayList:   446.1 ms
  40,000 elements, one addAll:        0.02 ms
  • The synchronized list took about a millisecond either way. The copy-on-write list took over a hundred times as long for 20,000 adds, because the 20,000th add copied 20,000 elements and all of them together copied about 200 million.
  • Doubling the adds to 40,000 made the copy-on-write list between about three and four and a half times slower across runs, close to the quadrupling that quadratic copying predicts, while the synchronized list barely changed.
  • One addAll of 40,000 elements took a fraction of a millisecond, because it copies the array once. When a copy-on-write list must be filled, build it in one step with new CopyOnWriteArrayList<>(existingList) or addAll.

Where it wins: many readers, rare writes

Three threads iterate a 100-element list in a loop for 300 ms while a fourth adds one element every 10 ms. With synchronizedList, each reader must hold the list's lock during the whole loop; with CopyOnWriteArrayList, readers need no lock at all. The program warms up once and reports the second round.

Java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.atomic.AtomicBoolean;

public class ReadHeavy {

    public static void main(String[] args) throws InterruptedException {
        for (int round = 0; round < 2; round++) {
            List<Integer> sync = Collections.synchronizedList(new ArrayList<>());
            List<Integer> cow = new CopyOnWriteArrayList<>();
            for (int i = 0; i < 100; i++) {
                sync.add(i);
                cow.add(i);
            }
            long a = run(sync, true);
            long b = run(cow, false);
            if (round == 1) {
                System.out.printf("3 readers iterating a 100-element list, 1 rare writer:%n"
                    + "  synchronizedList (lock around each loop): %,d iterations%n"
                    + "  CopyOnWriteArrayList (no lock):           %,d iterations%n", a, b);
            }
        }
    }

    // Runs 3 readers for 300 ms while a writer adds one element every 10 ms
    static long run(List<Integer> list, boolean lockToIterate) throws InterruptedException {
        AtomicBoolean stop = new AtomicBoolean();
        long[] counts = new long[3];
        Thread[] readers = new Thread[3];
        for (int r = 0; r < 3; r++) {
            int id = r;
            readers[r] = new Thread(() -> {
                while (!stop.get()) {
                    long sum = 0;
                    if (lockToIterate) {
                        synchronized (list) {
                            for (int x : list) {
                                sum += x;
                            }
                        }
                    } else {
                        for (int x : list) {
                            sum += x;
                        }
                    }
                    if (sum >= 0) {
                        counts[id]++;
                    }
                }
            });
            readers[r].start();
        }
        Thread writer = new Thread(() -> {
            while (!stop.get()) {
                list.add(1);
                sleep(10);
            }
        });
        writer.start();
        sleep(300);
        stop.set(true);
        for (Thread t : readers) {
            t.join();
        }
        writer.join();
        return counts[0] + counts[1] + counts[2];
    }

    static void sleep(long ms) {
        try {
            Thread.sleep(ms);
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    }
}

Output (counts vary between runs):

Output
3 readers iterating a 100-element list, 1 rare writer:
  synchronizedList (lock around each loop): 1,004,717 iterations
  CopyOnWriteArrayList (no lock):           4,800,863 iterations
  • The copy-on-write list completed several times as many iterations. With the synchronized list, the readers queue for one lock, so only one of them can iterate at a time, even though none of them changes anything.
  • The writer's 30 or so additions per run cost little with copy-on-write, because the list is small and writes are rare.
  • With more cores, the gap grows: lock-free readers scale with the number of CPUs, a single lock does not.

Other concurrent collections

Copy-on-write fits only one pattern. The program shows the tools for the others: sets of unique listeners, queues filled by several threads, a producer and consumer pair, and a sorted map shared between threads.

Java
import java.util.List;
import java.util.NavigableMap;
import java.util.Queue;
import java.util.Set;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.ConcurrentSkipListMap;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.CopyOnWriteArraySet;
import java.util.concurrent.LinkedBlockingQueue;

public class OtherConcurrent {

    public static void main(String[] args) throws InterruptedException {
        // addIfAbsent and CopyOnWriteArraySet: small sets of listeners or flags
        CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>(List.of("a"));
        System.out.println("addIfAbsent(a): " + list.addIfAbsent("a") + ", addIfAbsent(b): "
            + list.addIfAbsent("b") + " -> " + list);
        Set<String> set = new CopyOnWriteArraySet<>(List.of("x", "y", "x"));
        System.out.println("CopyOnWriteArraySet keeps insertion order: " + set);

        // ConcurrentLinkedQueue: lock-free, unbounded, never blocks
        Queue<Integer> queue = new ConcurrentLinkedQueue<>();
        Thread[] producers = new Thread[4];
        for (int t = 0; t < producers.length; t++) {
            producers[t] = new Thread(() -> {
                for (int i = 0; i < 10_000; i++) {
                    queue.offer(i);
                }
            });
            producers[t].start();
        }
        for (Thread p : producers) {
            p.join();
        }
        System.out.println("ConcurrentLinkedQueue size after 4 x 10,000 offers: " + queue.size());

        // BlockingQueue: the consumer waits for work; a bounded queue makes producers wait
        BlockingQueue<String> work = new LinkedBlockingQueue<>(2);
        Thread consumer = new Thread(() -> {
            try {
                String job;
                while (!(job = work.take()).equals("STOP")) {
                    System.out.println("  consumed " + job);
                }
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        });
        consumer.start();
        for (String job : List.of("job1", "job2", "job3", "STOP")) {
            work.put(job);                      // blocks while the queue holds 2 items
        }
        consumer.join();

        // ConcurrentSkipListMap: sorted and thread-safe
        NavigableMap<Integer, String> prices = new ConcurrentSkipListMap<>();
        prices.put(30, "c");
        prices.put(10, "a");
        prices.put(20, "b");
        System.out.println("skip list map: " + prices + ", ceilingKey(15) = "
            + prices.ceilingKey(15) + ", headMap(20) = " + prices.headMap(20));
    }
}

Output:

Output
addIfAbsent(a): false, addIfAbsent(b): true -> [a, b]
CopyOnWriteArraySet keeps insertion order: [x, y]
ConcurrentLinkedQueue size after 4 x 10,000 offers: 40000
  consumed job1
  consumed job2
  consumed job3
skip list map: {10=a, 20=b, 30=c}, ceilingKey(15) = 20, headMap(20) = {10=a}
  • addIfAbsent adds only when the element is missing, atomically. CopyOnWriteArraySet is built on it, keeps insertion order, and has the same cost profile as the list.
  • ConcurrentLinkedQueue accepted 40,000 offers from four threads without losing any and without locks. It is unbounded and poll returns null when empty, so it never blocks.
  • A LinkedBlockingQueue with capacity 2 made the producer wait in put until the consumer had taken items, and the consumer waited in take until work arrived. A sentinel value, STOP, ends the consumer. Blocking queues are the basis of thread pools.
  • ConcurrentSkipListMap is the concurrent counterpart of TreeMap, with the same navigation methods such as ceilingKey and headMap; see NavigableMap and NavigableSet.

Compound actions and visibility

Thread-safe collections make each single call safe, but code often combines calls, and that combination is not atomic. Three patterns cause most bugs with concurrent lists:

  • Check then act: if (!list.contains(x)) list.add(x) lets two threads both see "missing" and both add. addIfAbsent does the check and the add under the list's lock.
  • Size then index: list.get(list.size() - 1) can throw IndexOutOfBoundsException if another thread removes an element between the two calls. With copy-on-write, iterate a snapshot or use getLast() (Java 21), which reads one array.
  • Iterate then modify by index: positions found during one iteration may be stale by the time they are used. Use removeIf or replaceAll, which each work on the list in one locked step.

The collections in java.util.concurrent also guarantee visibility. Their documentation states that actions in a thread before placing an object into a concurrent collection happen-before actions after another thread retrieves it. A producer can therefore fill in an object's fields, put it into a BlockingQueue, and the consumer will see those fields fully set, without any extra volatile or locking. A plain ArrayList shared without synchronization gives no such guarantee, and a reader may see stale or partly built objects.

Compound actions, shown running

The three patterns above are easy to agree with and easy to write anyway. This program runs the first two with real threads on a CopyOnWriteArrayList, whose single calls are all thread-safe, and then shows the snapshot fix.

Java
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.atomic.AtomicInteger;

public class CompoundRace {

    public static void main(String[] args) throws InterruptedException {
        // 1. Check then act: contains followed by add, from 4 threads
        int dupRuns = 0;
        for (int run = 0; run < 20; run++) {
            List<Integer> list = new CopyOnWriteArrayList<>();
            runThreads(4, () -> {
                for (int i = 0; i < 1_000; i++) {
                    if (!list.contains(i)) {
                        list.add(i);
                    }
                }
            });
            if (list.size() != 1_000) {
                dupRuns++;
            }
        }
        System.out.println("contains + add: duplicates in " + dupRuns + " of 20 runs");

        int okRuns = 0;
        for (int run = 0; run < 20; run++) {
            CopyOnWriteArrayList<Integer> list = new CopyOnWriteArrayList<>();
            runThreads(4, () -> {
                for (int i = 0; i < 1_000; i++) {
                    list.addIfAbsent(i);
                }
            });
            if (list.size() == 1_000) {
                okRuns++;
            }
        }
        System.out.println("addIfAbsent: exactly 1,000 elements in " + okRuns + " of 20 runs");

        // 2. Size then index: another thread removes between the two calls, 10 rounds
        AtomicInteger failures = new AtomicInteger();
        int reads = 0;
        for (int round = 0; round < 10; round++) {
            CopyOnWriteArrayList<Integer> shared = new CopyOnWriteArrayList<>();
            for (int i = 0; i < 1_000; i++) {
                shared.add(i);
            }
            Thread remover = Thread.ofPlatform().start(() -> {
                while (!shared.isEmpty()) {
                    try {
                        shared.remove(shared.size() - 1);
                    } catch (IndexOutOfBoundsException e) {
                        failures.incrementAndGet();
                    }
                }
            });
            while (!shared.isEmpty()) {
                try {
                    shared.get(shared.size() - 1);
                    reads++;
                } catch (IndexOutOfBoundsException e) {
                    failures.incrementAndGet();
                }
            }
            remover.join();
        }
        System.out.println("get(size() - 1) while another thread removes, 10 rounds: " + reads
            + " reads, " + failures.get() + " IndexOutOfBoundsException");

        // 3. A snapshot of the array answers both questions consistently
        CopyOnWriteArrayList<String> names = new CopyOnWriteArrayList<>(List.of("ann", "bo", "cy"));
        Object[] snap = names.toArray();
        names.remove("cy");
        System.out.println("snapshot last element: " + snap[snap.length - 1] + " of " + snap.length
            + ", list now " + names);
    }

    static void runThreads(int n, Runnable task) throws InterruptedException {
        Thread[] ts = new Thread[n];
        for (int i = 0; i < n; i++) {
            ts[i] = Thread.ofPlatform().start(task);
        }
        for (Thread t : ts) {
            t.join();
        }
    }
}
Output
contains + add: duplicates in 17 of 20 runs
addIfAbsent: exactly 1,000 elements in 20 of 20 runs
get(size() - 1) while another thread removes, 10 rounds: 9489955 reads, 369 IndexOutOfBoundsException
snapshot last element: cy of 3, list now [ann, bo]
  • Four threads each ran if (!list.contains(i)) list.add(i) for the numbers 0 to 999. In most of the 20 runs the list ended with duplicates, because two threads both saw a number as missing before either added it.
  • The same work with addIfAbsent left exactly 1,000 elements in all 20 runs. It checks and adds while holding the list's internal lock, so no other write can slip in between.
  • Reading get(size() - 1) while another thread removed from the end threw IndexOutOfBoundsException a few hundred times across 10 rounds, out of millions of reads. A bug that rare passes every test and then fails in production.
  • toArray() returned the current array, and its last element stayed cy after cy was removed from the list. Every question asked of the snapshot gets a consistent answer, at the cost of possibly being out of date.

The same rules apply to ConcurrentHashMap, where get followed by put loses updates and merge or compute do the job atomically, as the ConcurrentHashMap page shows.

Which collection to use
Choosing a thread-safe collection
SituationUse
Read constantly, changed rarely, smallCopyOnWriteArrayList or CopyOnWriteArraySet
Listeners or observersCopyOnWriteArrayList
Frequent writes to a shared listCollections.synchronizedList, locking around iteration
Work handed from producers to consumersLinkedBlockingQueue or ArrayBlockingQueue
Queue that never blocksConcurrentLinkedQueue
Shared mapConcurrentHashMap
Shared sorted map or setConcurrentSkipListMap or ConcurrentSkipListSet
Data that never changes after creationList.of, Map.of: immutable and safe to share

Immutable collections are often the simplest thread-safe choice of all; see immutable collections. Queues are covered further on the Queue and Deque page.

Related articles

All Java articles →
Immutable Collections in Java: List.of, copyOf and ViewsImmutable collections in Java with real output: List.of, Set.of and Map.of rules, views vs copies, shallow immutability, which methods throw, and defensive copies.Java Collections Utility Class: sort, binarySearch, WrappersThe java.util.Collections helpers with real output: sort and binary search, counting and filling, unmodifiable, synchronized and checked wrappers, rarer methods, speed.Sorting Collections in Java: List.sort, Arrays.sort, StreamsSort Java lists, arrays, sets and maps with real output: comparators, the algorithms behind sort, stability, nulls and doubles, sorted structures, and measured speed.Java ConcurrentHashMap: How It Works, Atomic Updates, PitfallsConcurrentHashMap explained with real output: per-bin locking, lost updates with get and put, atomic compute and merge, bulk operations, compute traps and throughput.