JMH results for IndexedLinkedList

[John Hendrikx]

I think there might be room for another List implementation in the JDK, 
one that fits in between ArrayList and LinkedHashMap. I've been looking 
for something to manage lists of listeners (which allow arbitrary 
removal), must be called in order, and should handle duplicates (at 
their respective positions).  Both ArrayList and LinkedHashMap are 
close.  LinkedHashMap has quite some overhead (Entry instance per 
element) and poor cache locality while iterating and doesn't allow 
duplicates.  ArrayList has poor remove performance.

It should offer O(1) performance for add(Last), contains, remove(T) and 
near O(1) performance for operations that operate near the head/tail of 
the list (like getFirst, getLast, removeFirst, removeLast).  Iteration 
performance would be similar to ArrayList.  Basically an ArrayDeque, but 
with fast contains/remove(T).  The sacrifice made is poor index based 
access (with the exception of the head/tail).

It should be useful as a queue as well that allows quick removal (in 
order to cancel tasks for example, or to move a task up/down the queue).

--John

On 09/07/2022 21:33, Tagir Valeev wrote:
> Note that nobody these days cares about LinkedList. Use-cases where 
> LinkedList outperforms careful use of ArrayList or ArrayDeque are next 
> to none. So saying that your data structure is better than LinkedList 
> is totally not a reason to add it to JDK. It should be better than 
> ArrayList and ArrayDeque.
>
> Having a single data structure that provides list and deque interface 
> is a reasonable idea. However it would be much simpler to retrofit 
> existing data structure like ArrayDeque, rather than create a new data 
> structure. Here's an issue for this:
> https://bugs.openjdk.org/browse/JDK-8143850
>
> There were also discussions to enhance collections in general, adding 
> more useful methods like getFirst() or removeLast() to ArrayList, etc. 
> See for details:
> https://bugs.openjdk.org/browse/JDK-8266572
>
> To conclude, the idea of adding one more collection implementation 
> looks questionable to me. It will add more confusion when people need 
> to select which collection fits their needs better. It will require 
> more learning. This could be justified if there are clear benefits in 
> using it in real world problems, compared to existing collections. But 
> so far I don't see the examples of such problems.
>
> With best regards,
> Tagir Valeev
>
> сб, 9 июл. 2022 г., 11:22 Rodion Efremov <coderodd3 at gmail.com>:
>
>     Hello,
>
>     My benchmarking suggests, that, if nothing else, my
>     IndexedLinkedList outperforms gracefully the java.util.LinkedList,
>     so the use case should be the same (List<E> + Deque<E>
>     -interfaces) for both of the aforementioned data structures.
>
>     Best regards,
>     rodde
>
>
>     On Sat, Jul 9, 2022 at 11:19 AM Tagir Valeev <amaembo at gmail.com>
>     wrote:
>
>         Hello!
>
>         Are there real world problems/use cases where
>         IndexedLinkedList would be preferred in terms of CPU/memory
>         usage over ArrayList?
>
>         сб, 9 июл. 2022 г., 07:18 Rodion Efremov <coderodd3 at gmail.com>:
>
>             Data structure repo:
>             https://github.com/coderodde/IndexedLinkedList
>
>             Benchmark repo:
>             https://github.com/coderodde/IndexedLinkedListBenchmark
>
>             I have profiled my data structure and it seems it’s more
>             performant than java.util.LinkedList or TreeList, if
>             nothing else.
>
>             So, is there any chance of including IndexedLinkedList to JDK?
>
>             Best regards,
>             rodde
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.openjdk.org/pipermail/core-libs-dev/attachments/20220709/4572fa2d/attachment-0001.htm>