RFR: 8371164: ArrayList.addAll() optimizations

[Oli Gillespie]

On Mon, 3 Nov 2025 20:45:44 GMT, jengebr <duke at openjdk.org> wrote:

> # JVM Collections Optimizations: Eliminating toArray() Performance Bottlenecks
> 
> ## Summary
> 
> This PR addresses performance bottlenecks in ArrayList.addAll() and Collections.SingletonSet.toArray() methods by implementing direct optimizations that bypass inefficient intermediate allocations and abstract implementations. The optimizations target high-frequency operations identified through profiling analysis, delivering 37% performance improvements for ArrayList operations and 17-43% performance improvements for SingletonSet operations under real-world conditions where multiple collection types are used.
> 
> ## Problem Context
> 
> ### ArrayList.addAll() Inefficiency
> ArrayList.addAll() currently calls `c.toArray()` on the source collection to avoid iterator-based copying, but this creates unnecessary intermediate array allocation when the source is also an ArrayList. The method performs:
> 
> 1. Call `c.toArray()` - creates intermediate array
> 2. Call `System.arraycopy()` to copy from intermediate array to destination
> 3. Discard intermediate array
> 
> When both source and destination are ArrayList instances, this can be optimized to direct array copying.
> 
> ### Collections.SingletonSet toArray() Missing Implementation
> Collections.SingletonSet inherits the default `AbstractCollection.toArray()` implementation, which:
> 
> 1. Creates an Object[] of the expected size
> 2. Iterates through the collection (1 element)
> 3. Ensures "expected" size is the actual size
> 4. Returns the array
> 
> For a single-element collection, this overhead is disproportionate to the actual work needed. Additionally, this implementation is vulnerable to call site poisoning, showing 74-118% performance degradation under megamorphic conditions.
> 
> ## Optimized Methods
> 
> ### ArrayList
> - **`addAll(Collection<? extends E> c)`**: Added fast path for ArrayList-to-ArrayList copying using direct `System.arraycopy()` from source's internal `elementData` array, eliminating intermediate `toArray()` allocation
> 
> ### Collections.SingletonSet
> - **`toArray()`**: Direct implementation returning `new Object[] {element}`
> - **`toArray(T[] a)`**: Direct implementation with proper array sizing and null termination per Collection contract
> 
> ## Performance Impact
> 
> | Class | Method | Size | Baseline | Optimized | Improvement |
> |-------|--------|------|----------|-----------|-------------|
> | ArrayList | addAll | 0 | 10.149 ns/op, 40 B/op | 3.929 ns/op, 24 B/op | **61% faster, 40% less allocation** |
> | ArrayList | addAll | 5 | 23.804 ns/op, 104 B...

test/micro/org/openjdk/bench/java/util/ArrayListBulkOpsBenchmark.java line 60:

> 58: @Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
> 59: @Fork(value = 1, jvmArgs = { "-XX:+UseParallelGC", "-Xmx3g" })
> 60: public class ArrayListBulkOpsBenchmark {

You might find a layout like this a bit neater:


@State(Scope.Benchmark)
public class ArrayListBulkOpsBench {
    @Param({"0", "1", "5", "75"})
    int size;

    @Param({"ArrayList", "LinkedList"})
    String type;

    @Param({ "false", "true" })
    private boolean poison;

    List<String> source;

    @Setup(Level.Trial)
    public void setup() {
        switch (type) {
            case "ArrayList" -> source = new ArrayList<>(size);
            case "LinkedList" -> source = new LinkedList<>();
        }
        for (int i = 0; i < size; i++) source.add("key" + i);
        if (poison) poisonCallSites();
    }

    @Benchmark
    public ArrayList<String> addAll() {
        ArrayList<String> result = new ArrayList<>(size);
        result.addAll(source);
        return result;
    }

    static void poisonCallSites() {
        HashMap<String, String> hashMapSource = new HashMap<>();
        TreeSet<String> treeSetSource = new TreeSet<>();
        WeakHashMap<String, String> weakHashMapSource = new WeakHashMap<>();
        for (int i = 0; i < 75; i++) {
            hashMapSource.put("key" + i, "value" + i);
            treeSetSource.add("key" + i);
            weakHashMapSource.put("key" + i, "value" + i);
        }
        // Poison ArrayList.addAll() with different Collection types
        for (int i = 0; i < 40_000; i++) {
            ArrayList<Object> temp = new ArrayList<>();
            temp.addAll(hashMapSource.entrySet());
            temp.addAll(treeSetSource);
            temp.addAll(weakHashMapSource.keySet());
        }
    }

    @State(Scope.Benchmark)
    public static class SingletonSet {
        Set<String> singletonSetSource = Collections.singleton("key");

        @Param({ "false", "true" })
        private boolean poison;

        @Setup(Level.Trial)
        public void setup() {
            if (poison) poisonCallSites();
        }

        @Benchmark
        public ArrayList<String> addAllSingletonSet() {
            ArrayList<String> result = new ArrayList<>(1);
            result.addAll(singletonSetSource);
            return result;
        }
    }
}


addAll will be run against all permutations of size/type/poison. addAllSingletonSet will just be run against false/true poison.

-------------

PR Review Comment: https://git.openjdk.org/jdk/pull/28116#discussion_r2489955314