Hello, > What do you think?
First, for your benchmarks, I recommend you write them with https://github.com/openjdk/jmh, a library that allows configuration of warmup time, number of trials, and has utilities that avoid jvm optimization's impact on your benchmarks. A few cents: I recall seeing a similar proposal before. This implementation is definitely superior to the Linked List as an implementation of both deque and list at the cost of an extra finger array allocation, but it probably won't excel compared to dedicated Deque or List implementations in terms of performance and memory usage. Modern JDK List/Deque users usually use the array-focused implementations like ArrayDeque and ArrayList; even though ArrayList is slow at adding or removing at non-tail, most usages of ArrayList is iterating and sometimes adding (predominantly at tail). Array iteration is better optimized by hardware due to arrays. Thus, LinkedList is already out-of-favor like Vector, and there are relevant discussions in https://github.com/openjdk/jdk/pull/2744. The doubly-linked structure of the finger list is at a natural disadvantage (for iteration) here. Even though this finger list won't be a replacement for ArrayList or ArrayDeque, I wonder if it can be modified to become a concurrent collection, so that modifications to the list can be synchronized by the intervals between fingers. If it can, it would probably provide an efficient concurrent list implementation compared to the current CopyOnWriteArrayList, even though your current implementation seems not to support concurrency. > Does it deserve to be included in JDK? Let's revisit your proposal again: if it's in the JDK, where will it be used? After all, JDK is a library that is used by millions or billions of programs. Feel free to come up with a few use cases and we will see if this finger list is the best for those cases. On Sat, Jun 11, 2022 at 2:39 AM Rodion Efremov <codero...@gmail.com> wrote: > > Hi, > > I have this List/Deque implementation that runs (in a rather versatile > benchmark) much faster than ArrayList and LinkedList: > > https://github.com/coderodde/IndexedLinkedList > > What do you think? Does it deserve to be included in JDK? > > Best regards, > rodde
