On 7/10/22 8:25 AM, Tagir Valeev wrote:
Hello!

On Sun, Jul 10, 2022 at 6:33 AM Rodion Efremov <codero...@gmail.com> wrote:
I am interested in
https://bugs.openjdk.org/browse/JDK-8143850

Is there a way for becoming an assignee for the above issue? If yes, how do I 
proceed and what is the schedule?

Stuart Marks might be the right person to ask. Adding to CC.

Thanks Tagir.

There is already a considerable implementation overlap between ArrayList and ArrayDeque that seems difficult to unify. I'm loathe to add yet another data structure implementation that's functionally similar to the existing ones but has a bunch of subtle performance and usage tradeoffs. Doing this would add to the maintenance cost of the JDK and also make it more difficult for programmers to choose the "right" data structure for their application.

Already there is a problem with ArrayList and ArrayDeque being separate classes. ArrayDeque "fixes" the performance problem with addition/removal at the front of an ArrayList; yet last time I checked, ArrayDeque was used only about 1% as frequently as ArrayList. Maybe this is because people don't know about it, or maybe because people are uncomfortable losing List-like indexed access with ArrayDeque.

Regarding JDK-8143850 there is a twisty maze through the constraints of avoiding adding too much code, avoiding too much API surface area, and maintaining performance. I have a prototype of ArrayList that makes it double-ended, which seems promising, to me at least. (This is independent of SequencedCollection -- JDK-8266572 -- which is an API move, not an implementation move.) But doing this necessarily slows down append-only operations, while providing a performance boon for operations at the front for all but the smallest lists. The tradeoffs here are quite subtle.

In any case I think the best path forward for "new" data structures with interesting performance characteristics is to publish an artifact on Maven central. This will allow people who have specialized performance needs to use it.

s'marks


With best regards,
Tagir Valeev.


Best regards,
rodde

la 9.7.2022 klo 22.33 Tagir Valeev <amae...@gmail.com> kirjoitti:

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 <codero...@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 <amae...@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 <codero...@gmail.com>:

Data structure repo:
https://urldefense.com/v3/__https://github.com/coderodde/IndexedLinkedList__;!!ACWV5N9M2RV99hQ!LBLiZkI0ZS8UoU_DXtnXCXGFsFzBUd3q7qyok0L3vUbTQXbnDnXoyb8GsZUyyt2pnCjra9VSKVLJG8h-$

Benchmark repo:
https://urldefense.com/v3/__https://github.com/coderodde/IndexedLinkedListBenchmark__;!!ACWV5N9M2RV99hQ!LBLiZkI0ZS8UoU_DXtnXCXGFsFzBUd3q7qyok0L3vUbTQXbnDnXoyb8GsZUyyt2pnCjra9VSKafWnZNi$

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

Reply via email to