Very fast List/Deque to java.util?

[Rob Spoor]

I'd like to point out that rodde has also asked this project to be 
included in Apache Commons Collections: 
https://lists.apache.org/thread/klwtkbz96rp9zfr1077sc9r8tjtthfl4


On 11/06/2022 15:53, - wrote:
> 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 <coderodd3 at 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