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

[Stuart Marks]

On Mon, 10 Nov 2025 16:31:37 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:
> 
>   Whitespace fixes

test/jdk/java/util/Collection/MOAT.java line 890:

> 888:     }
> 889: 
> 890:     private static void testAddAll(Collection<Integer> c) {

Thanks for moving this test into MOAT. Overall it seems like a large reduction in test bulk, which simplifies a lot of things. Great!

test/jdk/java/util/Collection/MOAT.java line 892:

> 890:     private static void testAddAll(Collection<Integer> c) {
> 891:         if (!supportsAdd(c))
> 892:             return;

There's already a check for `supportsAdd()` in the testCollection1() method, which is the only caller, so it doesn't seem necessary to have one here.

test/jdk/java/util/Collection/MOAT.java line 898:

> 896:         // Test empty ArrayList source
> 897:         ArrayList<Integer> emptySource = new ArrayList<>();
> 898:         check(!c.addAll(emptySource));

It seems like there's an assertion missing here. We check the return value from addAll(), but not the state of the collection after the operation. Maybe something like `check(c.isEmpty())` ?

test/jdk/java/util/Collection/MOAT.java line 905:

> 903:         arraySource.add(99);
> 904:         check(c.addAll(arraySource));
> 905:         equal(new ArrayList<Integer>(c), arraySource);

Here and at line 913 it seems a bit odd to copy `c` into a new ArrayList to compare equality. I think it's trying to assert that `c` contains only the expected elements. Unfortunately `c` can be any collection, not just a List, and to use List equality it needs to be copied into an actual List. Doubly unfortunately, the new List will capture the encounter order of whatever collection `c` is, which might not be well-defined -- for example if `c` is a HashSet. So I don't think this is the right assertion. Probably a size check and a containsAll() check, as is done in the bottom case, is sufficient.

test/jdk/java/util/Collection/MOAT.java line 922:

> 920:         check(c.addAll(arraySource));
> 921:         equal(c.size(), sizeBefore + arraySource.size());
> 922:         check(c.containsAll(arraySource));

As I said in another comment, this (size check and containsAll check) looks like a better set of assertions than using List equality as in the earlier test cases.

I'm confused about the scope of cases being covered here. It seems like there are potentially three different axes of cases that potentially could be tested:

1) source is ArrayList / other kind of List
2) source is empty / not empty
3) destination is empty / not empty

That would indicate having eight test cases. That's kind of at the outer limit for hand-coded cases. At this point or beyond, having some automated case generation would be preferable. And this is MOAT and not JUnit, so test generation would have to be done _ad hoc_. I could imagine doing it in about the same amount of code (say 30 or fewer lines). But if you're not up for doing this, it's probably sufficient for this change to test just the ArrayList and non-ArrayList sources, since that should be sufficient to test the code path you're changing.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/28116#discussion_r2520427236
PR Review Comment: https://git.openjdk.org/jdk/pull/28116#discussion_r2520350910
PR Review Comment: https://git.openjdk.org/jdk/pull/28116#discussion_r2520359830
PR Review Comment: https://git.openjdk.org/jdk/pull/28116#discussion_r2520399855
PR Review Comment: https://git.openjdk.org/jdk/pull/28116#discussion_r2520522638