On Mon, 10 Nov 2025 16:31:37 GMT, jengebr <[email protected]> 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
