RFR: 8371164: ArrayList.addAll() optimizations [v2]

[Johannes Döbler]

On Tue, 4 Nov 2025 18:35:23 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 | **...
>
> jengebr has updated the pull request incrementally with one additional commit since the last revision:
> 
>   Adding direct unit tests, minor revisions to optimizations

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

> 61: public class ArrayListBulkOpsBenchmark {
> 62:     @Param({"0", "1", "5", "75"})
> 63:     int size;

The size parameter is used twice:
- to construct a collection of varying sizes which is to be added
- as initialCapacity of the receiving ArrayList
Can this impact the benchmark results? Maybe introduce two independent params.

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

> 66:     String type;
> 67: 
> 68:     List<String> source;

Suggestion: rename, e.g. `toBeAdded`

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

> 108:     @Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
> 109:     @Fork(value = 1, jvmArgs = { "-XX:+UseParallelGC", "-Xmx3g" })
> 110:     public static class SingletonSet {

Your PR targets bottlenecks in ArrayList.addAll() and Collections.SingletonSet.toArray() and introduces two independent optimizations. Having a inner class which benchmarks Collections.SingletonSet.toArray() performance by calling ArrayList.addAll() is a bit confusing. Maybe split into two independent benchmarks?

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

PR Review Comment: https://git.openjdk.org/jdk/pull/28116#discussion_r2492014189
PR Review Comment: https://git.openjdk.org/jdk/pull/28116#discussion_r2491983107
PR Review Comment: https://git.openjdk.org/jdk/pull/28116#discussion_r2491980487