On Mon, 15 May 2023 13:42:05 GMT, Claes Redestad <[email protected]> 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
