On Mon, 15 May 2023 14:34:13 GMT, Adam Sotona <asot...@openjdk.org> wrote:
>> 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. Fair point. The only counter-point I'd like to make is that these things tend to percolate and get copied around over to other places where it _could_ matter, so if it's no big deal I'd be slightly happier if we could avoid ever using `LinkedList`. ------------- PR Review Comment: https://git.openjdk.org/jdk/pull/13671#discussion_r1194116650
