Thread-safe collection selection — the read/write shape picks the collection

The idea

The read/write shape picks the collection

A registry read on every hot-path call and written to only a handful of times, ever, wants a collection whose write is the expensive side and whose read is free. corpus/logger keeps its appenders in a List<Registration>: log() walks that list on every call, while addAppender writes to it only a few times at start-up and rarely again. corpus/lru-cache has the identical shape for its eviction listeners. Both ship a CopyOnWriteArrayList, and both say why in their own javadoc: a write there replaces the whole backing array instead of mutating it. A mid-walk reader therefore keeps reading the array it started with, never a half-written one.

The tempting fix is Collections.synchronizedList(new ArrayList<>()), because every individual call into it is now safe on its own. Iterating, though, is a sequence of calls, not one, and the wrapper's own javadoc says the caller must hold the list's lock for the whole walk by hand. Skip that, and a write landing mid-iteration still throws ConcurrentModificationException.

lru-cache's DECISION_LOG.md measured exactly that swap: CopyOnWriteArrayList down to a plain ArrayList, nothing else changed. Under the full stress suite it failed with "12 of 400 threads failed: java.util.ConcurrentModificationException," caught on 6 of 6 consecutive runs. One isolated attempt at the same crowd size caught it 0 times out of 15, because the failing write has to land inside one specific iterator step. A small number of attempts can miss that window entirely, which is why a quiet test run here is not evidence the collection is safe. No race is even required to see the same defect on a single thread. A listener that registers a second listener while the first is still running hits that exact window every time.

Ask the same read/write question of a map instead of a list and the answer keeps its shape. ConcurrentHashMap is weakly consistent by contract, where a HashMap guarded by Collections.synchronizedMap is only guarded the same half-way.

Reach for copy-on-write when reads dominate and writes are rare. Frequent writes make the full-array copy on every one the wrong bill — see when-not.md.

Worked walkthrough

NOTES — three files, one defect, and a trigger that needs no thread at all

Run it first

..\..\..\..\.toolchain\jdk-21\bin\javac.exe -Xlint:all -d out src\*.java
..\..\..\..\.toolchain\jdk-21\bin\java.exe -cp out Main

javac -Xlint:all prints nothing and exits 0. Real output, verbatim, from one run:

--- 1. a listener that subscribes a second listener, mid-publish ---
  Racy      ConcurrentModificationException, saw [first-saw-hello] before it threw
  Wrapped   ConcurrentModificationException, saw [first-saw-hello] before it threw
  Snapshot  no exception, saw [first-saw-hello, first-saw-world, second-saw-world]

--- 2. the same trigger, for a Map instead of a List ---
  Racy        ConcurrentModificationException, visited [requests] before it threw
  Wrapped     ConcurrentModificationException, visited [requests] before it threw
  Concurrent  no exception, visited [requests, errors]

--- 3. a real crowd: 200 readers publishing, 20 writers subscribing, 10 runs ---
  Racy     CME count per run: 3328 0 0 0 0 0 0 0 0 0
  Wrapped  CME count per run: 4912 959 1798 909 868 1458 2954 1229 1975 3810
  Snapshot CME count per run: 0 0 0 0 0 0 0 0 0 0

--- 4. the cost Snapshot is not free of: subscribing into a long list ---
  2000 subscribe() calls into a registry already holding 5000 listeners:
    Snapshot (CopyOnWriteArrayList)         5 ms
    Wrapped  (synchronizedList(ArrayList))  0 ms

Which numbers you can rely on, measured across 30 runs (three sets of ten)

Block 3's crowd was rerun twice more, for 30 independent storms total per class. A single batch of ten can make a narrow bug look tamer or wilder than it is.

The two rows that say no are the point of this file's title. Under a real crowd, the exact same defect that block 1 and block 2 catch on one thread, every time, shows up in fewer than half of thirty storms. When it does show up, the count ranges from single digits to thousands, which is a coin landing on its edge, not a fixed number to memorize. corpus/lru-cache's own DECISION_LOG.md reports the identical shape for this exact bug: 0 catches out of 15 isolated attempts at CROWD = 200. Only the full stress suite, at 20 repetitions, catches it reliably. A candidate testing this under a stopwatch draws the wrong conclusion more often than the right one. GapTest does not use the crowd at all — see below.

The rule the four blocks add up to

A collection read on every hot-path call and written rarely wants a write that replaces the whole structure rather than mutating it: CopyOnWriteArrayList for a list, ConcurrentHashMap for a map. A synchronized-wrapped plain collection makes every individual call safe and leaves the walk unsafe. Its contract puts the burden of locking the whole iteration back on the caller. Neither defect needs two threads to demonstrate. It needs one modification landing between two steps of an iterator that has already started.

Registry.java — three designs, the same two methods

private final List<Listener> subscribers = new ArrayList<>();

No guard, and none of the three designs pretends this one has one. Racy exists to be the class a candidate writes in the first thirty seconds, before concurrency is even in the room. Every single-threaded test passes against it — any test that never registers a listener from inside another listener's callback.

private final List<Listener> subscribers = Collections.synchronizedList(new ArrayList<>());

Every call into subscribers is now individually thread-safe, and publish's for loop still is not. The for-each desugars to iterator() once, then repeated hasNext()/next() calls: three separate calls, none of them synchronized as a unit with whatever subscribe does in between. Collections.synchronizedList's own javadoc says the caller must wrap the entire iteration in a synchronized block on the list itself to be safe. Wrapped does not do that. That is the mistake a reviewer who sees the word synchronized in the type, and stops reading, will miss.

private final List<Listener> subscribers = new CopyOnWriteArrayList<>();

A write replaces the array reference; it never touches the array an iterator already holds. Snapshot.publish calls iterator() once, gets a handle to the current array, and walks exactly that array to the end. A subscribe call that runs while the walk is in progress builds a new array and swaps it in, and the walk already under way never finds out. That is the whole mechanism, and it is why block 1's Snapshot line never throws.

Dashboard.java — the same three answers, for a Map

private final Map<String, Long> counts = new HashMap<>();      // Racy
private final Map<String, Long> counts = Collections.synchronizedMap(new HashMap<>());  // Wrapped
private final Map<String, Long> counts = new ConcurrentHashMap<>();                     // Concurrent

entrySet().iterator() on a synchronizedMap-wrapped HashMap is the backing HashMap's own iterator, unwrapped. Collections.synchronizedMap's javadoc states this as plainly as the list version does: iterating requires the caller to hold the map's own lock for the whole walk. Nothing in Wrapped.report does that, so it fails exactly where Racy.report does.

ConcurrentHashMap's iterators are weakly consistent by contract, not by luck. The javadoc guarantees they never throw ConcurrentModificationException, and may or may not reflect an insertion that happens during the walk. Concurrent.increment("timeouts") mid-report in block 2 has no guarantee of being seen by that walk, only a guarantee that it will not break it.

increment uses merge, not get then put. That choice is E2's ground, not this file's. A single merge call is already the whole read-modify-write, on any of the three map types, and none of the three Dashboard variants above differ in that line at all. What differs between them, and what this lesson is about, is only which Map implementation backs the field.

Main.java — the trigger that needs no thread

broadcaster.subscribe(event -> {
    seen.add("first-saw-" + event);
    broadcaster.subscribe(e -> seen.add("second-saw-" + e));
});

One listener, reacting to an event by registering a second listener. That second subscribe call runs from inside the for loop publish is already running, on the same thread, with no scheduler involved. For Racy and Wrapped this is a structural modification landing inside an iterator's hasNext/next pair — exactly the shape a real race needs two threads to produce by luck. Producing it on purpose, on one thread, is what makes GapTest deterministic. It does not wait for block 3's crowd to roll a low number, and there is only one outcome to report, not a run count.

int readers = 200;
int writers = 20;

Block 3 is the honest version, and the table above says why it stays out of GapTest. A test suite that relies on this crowd to fail reliably would need lru-cache's tuning: a large crowd and many repetitions. It would still cost real wall-clock time for a defect block 1 already proves in under a millisecond, with no pool, no latch, and no timeout.

for (int i = 0; i < newSubscriptions; i++) snap.subscribe(e -> { });

Block 4 measures the bill this lesson's whole answer is not free of. Every one of those calls against Snapshot copies the entire current array; against Wrapped it does not. when-not.md is the other side of that same number.

On block 4's timing, and why it is quoted as a range

The 5 ms above is verbatim output from the run captured in this file. Re-running the same block on a different machine gave 13, 14 and 15 ms across three consecutive runs, with synchronizedList reporting 0 ms every time.

Both numbers are real, and that is the point. Block 4 is wall-clock time over a few thousand array copies, so its absolute value belongs to the machine that ran it rather than to CopyOnWriteArrayList. when-not.md therefore quotes the range and asks you to run it yourself, because a single figure presented as the measurement would be no more than a record of whoever ran it last.

What is stable across every run, and is the actual claim: the copy-on-write side scales with how many members are already subscribed, and the wrapped-ArrayList side does not.

When not to

When copy-on-write is the wrong bill

CopyOnWriteArrayList and a ConcurrentHashMap-backed set built the same way are not a default you reach for on every shared collection. The write side has a real cost, and it is only cheap because logger's and lru-cache's registries write a handful of times, ever, and read constantly.

The concrete bad example, measured

Say a chat room keeps its member list in a CopyOnWriteArrayList<Member> because "it is the thread-safe one." Members join and leave constantly. Every connect and every disconnect is a write, and the room also broadcasts to everyone on every message, so reads are frequent too. Neither side is rare, which is exactly the case this class was not built for.

Every CopyOnWriteArrayList write copies the entire current array, so the cost of one join grows with how many members are already in the room. Block 4 of lessons/E4/worked/src/Main.java measures that shape directly, subscribing 2000 more listeners into a registry that already holds 5000. The copy-on-write version has taken between 5ms and 15ms across the runs recorded for this lesson, while synchronizedList(ArrayList) reports 0ms every time.

Treat the spread, not the figure, as the finding. This is wall-clock time on one machine, so the absolute number moves with the hardware and a single quoted value would be a measurement of whoever ran it last. What holds across every run is the shape: one side scales with the number of members already present and the other does not. Run block 4 yourself and read your own number. A room that churns members at any real rate pays for a new 5000-element array on every arrival. That expense buys protection for a read pattern this room does not actually have — nobody walks the member list while somebody else joins nearly as often as messages get sent.

The threshold

Reach for copy-on-write when reads happen on every hot-path call and writes are rare: start-up registration, occasional configuration changes. corpus/logger's appenders and corpus/lru-cache's listeners both have exactly that shape. When writes run at close to the same rate as reads, a ConcurrentHashMap (or a set built the same way) costs a per-bucket lock rather than a full copy per write. Its iterators stay weakly consistent, so no ConcurrentModificationException, without paying for a fresh array on every join. A chat room's member list belongs there, not behind copy-on-write.

Worked source

The 3 files of the worked design

Every file below is the one the app opens, verbatim. This is the part worth reading slowly: the prose above argues for a shape, and these are the lines that have it.

• worked/src/Dashboard.java 57 lines
• worked/src/Registry.java 58 lines
• worked/src/Main.java 237 lines

worked/src/Dashboard.java57 lines

import java.util.HashMap;
import java.util.Collections;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.function.Consumer;

// Dashboard.java
//
// The same question, asked of a Map instead of a List. increment() runs on every request, from
// whichever thread served it, on a metric name it may or may not have seen before. report() runs
// far less often — a monitoring poll walking every entry to render a page — and it must never see
// a torn walk and must never make increment() remember to take a lock.
public final class Dashboard {

    /** No protection. A plain HashMap does not expect two threads near it at once, ever. */
    public static final class Racy {
        private final Map<String, Long> counts = new HashMap<>();

        public void increment(String metric) { counts.merge(metric, 1L, Long::sum); }

        public void report(Consumer<Map.Entry<String, Long>> visitor) {
            for (Map.Entry<String, Long> entry : counts.entrySet()) visitor.accept(entry);
        }
    }

    /**
     * {@code get} and {@code put} are now individually safe. {@code entrySet().iterator()} is
     * still the backing {@code HashMap}'s own iterator — {@code synchronizedMap} does not wrap
     * it, and its javadoc says so: the caller must hold the map's own lock for the entire walk,
     * by hand, or the walk is exactly as unsafe as the plain map above.
     */
    public static final class Wrapped {
        private final Map<String, Long> counts = Collections.synchronizedMap(new HashMap<>());

        public void increment(String metric) { counts.merge(metric, 1L, Long::sum); }

        public void report(Consumer<Map.Entry<String, Long>> visitor) {
            for (Map.Entry<String, Long> entry : counts.entrySet()) visitor.accept(entry);
        }
    }

    /**
     * The corpus's answer for a map instead of a list. {@code ConcurrentHashMap}'s iterators are
     * weakly consistent by contract: a walk in progress never throws for a write that lands
     * during it, and {@code increment} needs no lock of its own because a single {@code merge}
     * call is the whole read-modify-write.
     */
    public static final class Concurrent {
        private final Map<String, Long> counts = new ConcurrentHashMap<>();

        public void increment(String metric) { counts.merge(metric, 1L, Long::sum); }

        public void report(Consumer<Map.Entry<String, Long>> visitor) {
            for (Map.Entry<String, Long> entry : counts.entrySet()) visitor.accept(entry);
        }
    }
}

worked/src/Registry.java58 lines

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;

// Registry.java
//
// Three ways to hold a list of subscribers that get read on every event and written only when
// something new signs up — the exact shape of corpus/logger's appender registrations and
// corpus/lru-cache's eviction listeners. Both of those files ship the same answer, and both say
// so in their own javadoc, tagged E4.
public final class Registry {

    public interface Listener {
        void onEvent(String event);
    }

    /** No protection at all. Compiles clean. Breaks the moment a read and a write overlap. */
    public static final class Racy {
        private final List<Listener> subscribers = new ArrayList<>();

        public void subscribe(Listener listener) { subscribers.add(listener); }

        public void publish(String event) {
            for (Listener listener : subscribers) listener.onEvent(event);
        }
    }

    /**
     * Every individual call — {@code add}, {@code get}, {@code size} — is now safe on its own.
     * Iterating the list is a sequence of calls, not one, and nothing here makes the sequence
     * safe: {@code publish} still walks a plain {@code ArrayList}'s iterator underneath.
     */
    public static final class Wrapped {
        private final List<Listener> subscribers = Collections.synchronizedList(new ArrayList<>());

        public void subscribe(Listener listener) { subscribers.add(listener); }

        public void publish(String event) {
            for (Listener listener : subscribers) listener.onEvent(event);
        }
    }

    /**
     * The corpus's answer. A write replaces the whole backing array rather than mutating it, so
     * an iterator already in flight keeps reading the array it started with. {@code publish}
     * never blocks and never throws, no matter what {@code subscribe} does while it runs.
     */
    public static final class Snapshot {
        private final List<Listener> subscribers = new CopyOnWriteArrayList<>();

        public void subscribe(Listener listener) { subscribers.add(listener); }

        public void publish(String event) {
            for (Listener listener : subscribers) listener.onEvent(event);
        }
    }
}

worked/src/Main.java237 lines

import java.util.ArrayList;
import java.util.ConcurrentModificationException;
import java.util.List;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * Four blocks. The first two need no threads at all: a listener that reacts to an event by
 * registering another listener is a single thread modifying the registry while it is still
 * being walked, and that is enough to tell the three designs apart. The third block is the
 * honest version, with a real crowd, because a single-threaded trigger proves the defect exists
 * but says nothing about how often a real storm would find it. The fourth is the cost the
 * correct answer is not free of.
 */
public class Main {

    public static void main(String[] args) throws Exception {
        System.out.println("--- 1. a listener that subscribes a second listener, mid-publish ---");
        block1();

        System.out.println();
        System.out.println("--- 2. the same trigger, for a Map instead of a List ---");
        block2();

        System.out.println();
        System.out.println("--- 3. a real crowd: 200 readers publishing, 20 writers subscribing, 10 runs ---");
        block3();

        System.out.println();
        System.out.println("--- 4. the cost Snapshot is not free of: subscribing into a long list ---");
        block4();
    }

    // ------------------------------------------------------------------------------------------
    // Block 1 — List. No threads. One listener registers another while publish() is mid-walk.
    // ------------------------------------------------------------------------------------------

    private static void block1() {
        reentrant("Racy    ", new Registry.Racy());
        reentrant("Wrapped ", new Registry.Wrapped());
        reentrant("Snapshot", new Registry.Snapshot());
    }

    private static void reentrant(String label, Object target) {
        List<String> seen = new ArrayList<>();
        try {
            if (target instanceof Registry.Racy racy) {
                racy.subscribe(mkFirst(racy::subscribe, seen));
                racy.publish("hello");
                racy.publish("world");
            } else if (target instanceof Registry.Wrapped wrapped) {
                wrapped.subscribe(mkFirst(wrapped::subscribe, seen));
                wrapped.publish("hello");
                wrapped.publish("world");
            } else if (target instanceof Registry.Snapshot snap) {
                snap.subscribe(mkFirst(snap::subscribe, seen));
                snap.publish("hello");
                snap.publish("world");
            }
            System.out.println("  " + label + "  no exception, saw " + seen);
        } catch (ConcurrentModificationException cme) {
            System.out.println("  " + label + "  ConcurrentModificationException, saw " + seen + " before it threw");
        }
    }

    private static Registry.Listener mkFirst(java.util.function.Consumer<Registry.Listener> subscribeBack,
                                              List<String> seen) {
        return event -> {
            seen.add("first-saw-" + event);
            subscribeBack.accept(e -> seen.add("second-saw-" + e));
        };
    }

    // ------------------------------------------------------------------------------------------
    // Block 2 — Map. Same trigger: a visitor that inserts a brand-new key mid-walk.
    // ------------------------------------------------------------------------------------------

    private static void block2() {
        reentrantMap("Racy      ", new Dashboard.Racy());
        reentrantMap("Wrapped   ", new Dashboard.Wrapped());
        reentrantMap("Concurrent", new Dashboard.Concurrent());
    }

    private static void reentrantMap(String label, Object target) {
        List<String> visited = new ArrayList<>();
        try {
            if (target instanceof Dashboard.Racy d) {
                d.increment("requests");
                d.increment("errors");
                d.report(entry -> {
                    visited.add(entry.getKey());
                    if (visited.size() == 1) d.increment("timeouts");
                });
            } else if (target instanceof Dashboard.Wrapped d) {
                d.increment("requests");
                d.increment("errors");
                d.report(entry -> {
                    visited.add(entry.getKey());
                    if (visited.size() == 1) d.increment("timeouts");
                });
            } else if (target instanceof Dashboard.Concurrent d) {
                d.increment("requests");
                d.increment("errors");
                d.report(entry -> {
                    visited.add(entry.getKey());
                    if (visited.size() == 1) d.increment("timeouts");
                });
            }
            System.out.println("  " + label + "  no exception, visited " + visited);
        } catch (ConcurrentModificationException cme) {
            System.out.println("  " + label + "  ConcurrentModificationException, visited " + visited + " before it threw");
        }
    }

    // ------------------------------------------------------------------------------------------
    // Block 3 — a real crowd. 10 independent runs, so a lucky quiet run does not stand for all.
    // ------------------------------------------------------------------------------------------

    private static void block3() throws Exception {
        for (String label : new String[] {"Racy", "Wrapped", "Snapshot"}) {
            int[] failures = new int[10];
            for (int run = 0; run < 10; run++) {
                failures[run] = crowdRun(label);
            }
            StringBuilder sb = new StringBuilder();
            for (int f : failures) sb.append(f).append(' ');
            System.out.println("  " + pad(label) + " CME count per run: " + sb.toString().trim());
        }
    }

    private static int crowdRun(String label) throws Exception {
        Object target = switch (label) {
            case "Racy" -> new Registry.Racy();
            case "Wrapped" -> new Registry.Wrapped();
            default -> new Registry.Snapshot();
        };
        int readers = 200;
        int writers = 20;
        int crowd = readers + writers;
        ExecutorService pool = Executors.newFixedThreadPool(crowd, r -> {
            Thread t = new Thread(r);
            t.setDaemon(true);
            return t;
        });
        CountDownLatch ready = new CountDownLatch(crowd);
        CountDownLatch go = new CountDownLatch(1);
        CountDownLatch done = new CountDownLatch(crowd);
        AtomicInteger cmeCount = new AtomicInteger();
        try {
            for (int i = 0; i < readers; i++) {
                pool.submit(() -> {
                    ready.countDown();
                    await(go);
                    for (int k = 0; k < 2000; k++) {
                        try {
                            publish(target, "e" + k);
                        } catch (ConcurrentModificationException cme) {
                            cmeCount.incrementAndGet();
                        }
                    }
                    done.countDown();
                });
            }
            for (int i = 0; i < writers; i++) {
                pool.submit(() -> {
                    ready.countDown();
                    await(go);
                    for (int k = 0; k < 500; k++) {
                        subscribe(target, e -> { });
                    }
                    done.countDown();
                });
            }
            ready.await(10, TimeUnit.SECONDS);
            go.countDown();
            done.await(10, TimeUnit.SECONDS);
        } finally {
            pool.shutdownNow();
        }
        return cmeCount.get();
    }

    private static void publish(Object target, String event) {
        if (target instanceof Registry.Racy r) r.publish(event);
        else if (target instanceof Registry.Wrapped w) w.publish(event);
        else if (target instanceof Registry.Snapshot s) s.publish(event);
    }

    private static void subscribe(Object target, Registry.Listener listener) {
        if (target instanceof Registry.Racy r) r.subscribe(listener);
        else if (target instanceof Registry.Wrapped w) w.subscribe(listener);
        else if (target instanceof Registry.Snapshot s) s.subscribe(listener);
    }

    private static void await(CountDownLatch latch) {
        try {
            latch.await();
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    }

    private static String pad(String label) {
        StringBuilder sb = new StringBuilder(label);
        while (sb.length() < 8) sb.append(' ');
        return sb.toString();
    }

    // ------------------------------------------------------------------------------------------
    // Block 4 — the cost. Subscribing into a registry that already has 5000 listeners.
    // ------------------------------------------------------------------------------------------

    private static void block4() {
        int existing = 5000;
        int newSubscriptions = 2000;

        Registry.Snapshot snap = new Registry.Snapshot();
        for (int i = 0; i < existing; i++) snap.subscribe(e -> { });
        long snapStart = System.nanoTime();
        for (int i = 0; i < newSubscriptions; i++) snap.subscribe(e -> { });
        long snapMs = (System.nanoTime() - snapStart) / 1_000_000;

        Registry.Wrapped wrap = new Registry.Wrapped();
        for (int i = 0; i < existing; i++) wrap.subscribe(e -> { });
        long wrapStart = System.nanoTime();
        for (int i = 0; i < newSubscriptions; i++) wrap.subscribe(e -> { });
        long wrapMs = (System.nanoTime() - wrapStart) / 1_000_000;

        System.out.println("  " + newSubscriptions + " subscribe() calls into a registry already holding "
                + existing + " listeners:");
        System.out.println("    Snapshot (CopyOnWriteArrayList)         " + snapMs + " ms");
        System.out.println("    Wrapped  (synchronizedList(ArrayList))  " + wrapMs + " ms");
    }
}