On Mon, 15 May 2023 13:42:05 GMT, Claes Redestad <redes...@openjdk.org> wrote:

>> test/micro/org/openjdk/bench/jdk/classfile/RebuildMethodBodies.java line 57:
>> 
>>> 55:     public void setup() throws IOException {
>>> 56:         shared = new LinkedList<>();
>>> 57:         unshared = new LinkedList<>();
>> 
>> LinkedList should be replaced by ArrayList, as:
>> 1. LinkedList's node wrapper around each object is too heavy, ArrayList has 
>> smaller wrapper
>> 2. LinkedList iteration needs to follow links while ArrayList access can be 
>> machine optimized
>> 3. ArrayList addition is amortized O(1), not really worse than LinkedList 
>> additions.
>
> I have to side with @liach here: `LinkedList` iteration is significantly 
> slower than `ArrayList` even though the computational complexity is 
> identical. Often by an integer factor. This is due to the sparseness of the 
> linked list data structure on heap and the pointer chasing that entails.  
> 
> For minimum overhead of iteration over an immutable list then turning the 
> list into an immutable via `List.copyOf` might be preferable due the JVM's 
> ability to optimize over `@Stable` arrays.
> 
> Adhoc [JMH 
> benchmark](https://gist.github.com/cl4es/1f21812241c47f32a9deaffcc996e8b3):
> 
> 
> Benchmark                            Mode  Cnt    Score    Error   Units
> ListIteration.iterateArrayList      thrpt   15  188,724 ± 10,903  ops/ms
> ListIteration.iterateImmutableList  thrpt   15  230,901 ±  6,513  ops/ms
> ListIteration.iterateLinkedList     thrpt   15   58,289 ±  0,497  ops/ms
> 
> 
> Is it important to fix this? Perhaps not, but in a microbenchmark like this 
> the fewer cycles we spend on "stuff" that isn't really part of the thing 
> we're testing, the better. Increasingly so as the thing we're testing is 
> getting more and more optimized.

I'm not questioning performance differences between list implementations. 
The implementation of top level list for this benchmark is irrelevant because 
~10ns difference cannot affect ~100µs benchmark run.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/13671#discussion_r1193934410

Reply via email to