JMH results for IndexedLinkedList
Maurizio Cimadamore
maurizio.cimadamore at oracle.com
Mon Jul 11 09:58:52 UTC 2022
The implementation of the Foreign Function & Memory API uses an internal
custom linked list to add native resources to a "memory session"
abstraction (things that need to be cleaned up at a later point).
Linked list is quite critical in our use case because we need something
that has a very fast insertion (in the head), and can scale gracefully
to handle multiple threads.
In our case LinkedList is not good enough (because we want to deal with
concurrent writes ourselves) - but aside from that, note that, at least
looking at the numbers posted in your benchmarks, it seems that
prepending an element to a classic LinkedList is 10x faster than
ArrayList and 5x faster IndexList. Perhaps that's a case where IndexList
has not been fully optimized - but for prepend-heavy code (and the javac
compiler is another one of those), I think performance of addFirst is
the number to look at.
As Tagir said, of course these use cases are very "niche" - and, at
least in my experience, deevelopers in this "niche" tend to come up with
ad-hoc specialized data structures anyways. So the return of investment
for adding another collection type in this space seems relatively low.
Maurizio
On 09/07/2022 20: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/20220711/49ca548e/attachment-0001.htm>
More information about the core-libs-dev
mailing list