On Tue, 4 Nov 2025 10:48:43 GMT, Oli Gillespie <[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 |
>> **...
>
> test/micro/org/openjdk/bench/java/util/ArrayListBulkOpsBenchmark.java line
> 120:
>
>> 118: ArrayList<String> result = new ArrayList<>(75);
>> 119: result.addAll(linkedListSource75);
>> 120: bh.consume(result);
>
> No need for blackholes, just return the result, it has the same effect I
> believe.
(see
https://shipilev.net/jvm/anatomy-quarks/27-compiler-blackholes/#_pure_java_blackholes)
-------------
PR Review Comment: https://git.openjdk.org/jdk/pull/28116#discussion_r2490252260
