RFR: 8306842: Classfile API performance improvements [v4]

[Claes Redestad]

On Fri, 12 May 2023 13:19:44 GMT, Chen Liang <liach at openjdk.org> wrote:

>> Adam Sotona has updated the pull request incrementally with one additional commit since the last revision:
>> 
>>   fixed jmh benchmark parameters
>
> 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.

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

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