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