ConcurrentLinkedDeque was tested and it has similar thoughput to what we
use, slightly higher memory footprint per element added, so we opted
against it (but might re-eval in the future).
In the specific case of the FFM API, it is not uncommon to have a
session with just 1-2 resources attached to it. So having a data
structure backed by an array becomes a bit problematic, while data
structures where you pay for what you use are instead preferrable.
We only scan the contents of the data strtucture once (when we bring
down the session), to call the various cleanup actions, so we're
absolutely not interested in random access.
Maurizio
On 11/07/2022 11:22, John Hendrikx wrote:
I'm curious, why isn't ArrayDeque or ConcurrentLinkedDeque used
instead? Or is there another requirement?
ArrayDeque has amortized O(1) for inserts at head and tail (and faster
and more memory efficient than LinkedList as it doesn't use nodes).
ConcurrentLinkedDeque would be useful in the face of multiple threads
(it uses nodes though, so won't be as fast as ArrayDeque).
--John
On 11/07/2022 11:58, Maurizio Cimadamore wrote:
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 <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://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
