[(Much) faster java.util.LinkedList]

[Paul Sandoz]

Hi,

Thanks for sharing.

I browsed through the code (not a review) and gave it a test drive, generally it looks of good quality.

Over time, since LinkedList was added, there are less reasons to use it, thereby making such improvements you propose less impactful. CPU caches have got much better, so traversal of ArrayList is really good, whereas traversal of LinkedList is not cache efficient and nor is it easily amenable to runtime compiler optimizations like auto-vectorization. ArrayDeque (almost if not as good as ArrayList) was added that supports efficient first/last addition. I would argue that ArrayList or ArrayDeque are better choices in the majority of cases. In other cases where insertion is more generally required and there is a relation between elements a TreeSet or PriorityQueue may be a better choice.

So while I think you have done a good job implementing an enhanced LinkedList implementation I am not convinced it's worth adding to the JDK.

There are other areas we could enhance that might have more impact. For example, can we improve how ArrayList and ArrayDeque grow in size? When we added the Java Stream API we added an internal data structure SpinedBuffer, which behaves like an append-only array list with better growth characteristics, using an array of arrays (the spine). Maybe such a technique is more broadly applicable to ArrayList and perhaps ArrayDeque?

Paul.

> On Aug 18, 2021, at 8:30 PM, Rodion Efremov <coderodd3 at gmail.com> wrote:
> 
> Hello,
> 
> I have implemented a heuristic, indexed doubly-linked list data structure
> [1][2] implementing java.util.List and java.util.Deque interfaces that has
> superior performance compared to java.util.LinkedList and
> java.util.ArrayList.
> 
> I would like to propose it into the upcoming versions of OpenJDK, but,
> first, I need to know what do you think about it?
> 
> Best regards,
> rodde
> 
> [1] https://github.com/coderodde/LinkedList
> [2] http://coderodde.github.io/weblog/#eill