Unnecessary logic is added to removeFirst and removeLast of ArrayList.

[forax at univ-mlv.fr]

> From: "Chen Liang" <chen.l.liang at oracle.com>
> To: "Remi Forax" <forax at univ-mlv.fr>
> Cc: "core-libs-dev" <core-libs-dev at openjdk.org>
> Sent: Sunday, May 11, 2025 5:41:25 PM
> Subject: Re: Unnecessary logic is added to removeFirst and removeLast of
> ArrayList.

> > where the generated assembly code by the JITs is checked by humans

> Is it?

At least, it was true during the Java 8 timeframe :) 
At that time, i was involved in the effort of updating the collection API to use lambdas. 

I suppose that the introduction of value types will trigger a similar effort (even if it seems less easier to use value types to optimize the collection API because the spec allows a lot of modifications). 

> I have heard anecdotes that it is still slower than direct array usage,
> presumably due to the modCount tracking mechanism. Don't know if escape
> analysis and the resulting stack allocation in the compiled code eliminates
> that field.

I've recently bench array vs arraylist (while testing the performance of StableValue.list()), 
for 1024 string ("0", "1", "2" etc), on my Mac M2 air, i get 

// Benchmark                    Mode  Cnt     Score   Error  Units 
// StableListBench.array        avgt    5   427,889 ± 1,553  ns/op 
// StableListBench.arraylist    avgt    5   605,542 ± 1,372  ns/op 
// StableListBench.asList       avgt    5   572,532 ± 2,574  ns/op 
// StableListBench.list_of      avgt    5   615,069 ± 0,341  ns/op 
// StableListBench.stable_list  avgt    5  1897,948 ± 2,119  ns/op 
with 
@Benchmark 
public int list_of () { 
var sum = 0 ; 
for ( var item : listof ) { 
sum += item .length(); 
} 
return sum ; 
} 

So at least, I can say that on my mac, direct array usage is more efficient. 
(BTW, using an arraylist is more effcient than using List.of()/List.copyOf() because ListN inherits from the iterator of AbstractList instead of having its own). 

regards, 
Rémi 

> From: core-libs-dev <core-libs-dev-retn at openjdk.org> on behalf of Remi Forax
> <forax at univ-mlv.fr>
> Sent: Sunday, May 11, 2025 5:16 AM
> To: 임민수 <godmlzkf1 at naver.com>
> Cc: core-libs-dev <core-libs-dev at openjdk.org>
> Subject: Re: Unnecessary logic is added to removeFirst and removeLast of
> ArrayList.
> Duplicating the logic is bad in some cases and not that bad in other cases.

> Here ArrayList is one of the most used class in Java (with String and HashMap),
> it is heavily optimized (to the point where the generated assembly code by the
> JITs is checked by humans), so duplicating the logic is not a bad idea,
> From a documentation POV, you do not have to jump through many methods if you
> want to see the implementation and in terms of performance, you want the
> inlining to be done by hand because the methods of ArrayList are usually deep
> in the call graph, so you may reach the inlining threshold right inside
> removeFirst().

> In general, you do not optimize applications and libraries the same way.
> Usually, you do not optimize application code that often but for a library, if a
> lot of people are using it, it may worth to spend time to optimize for the
> benefit of everybody.

> regards,
> Rémi
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.openjdk.org/pipermail/core-libs-dev/attachments/20250511/211c962c/attachment-0001.htm>