<html><head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body>
<p>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).</p>
<p>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.</p>
<p>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.<br>
</p>
<p>Maurizio<br>
</p>
<div class="moz-cite-prefix">On 11/07/2022 11:22, John Hendrikx
wrote:<br>
</div>
<blockquote type="cite" cite="mid:11b988e7-82fe-2835-37b4-106b58e1efb4@gmail.com">
<p>I'm curious, why isn't ArrayDeque or ConcurrentLinkedDeque used
instead? Or is there another requirement?</p>
<p>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).</p>
<p>ConcurrentLinkedDeque would be useful in the face of multiple
threads (it uses nodes though, so won't be as fast as
ArrayDeque).<br>
</p>
<p>--John<br>
</p>
<div class="moz-cite-prefix">On 11/07/2022 11:58, Maurizio
Cimadamore wrote:<br>
</div>
<blockquote type="cite" cite="mid:56a19568-2adc-7f38-3ff0-13b069ff09a3@oracle.com">
<p>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).</p>
<p>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.</p>
<p>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.</p>
<p>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.<br>
</p>
<p>Maurizio<br>
</p>
<div class="moz-cite-prefix">On 09/07/2022 20:33, Tagir Valeev
wrote:<br>
</div>
<blockquote type="cite" cite="mid:CAE+3fjYgWPT9cZZCCYUN-hHu_s1=8C85zQahbF+07VFCh-gfig@mail.gmail.com">
<div dir="auto">
<div>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.</div>
<div dir="auto"><br>
</div>
<div dir="auto">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:</div>
<div dir="auto"><a href="https://bugs.openjdk.org/browse/JDK-8143850" target="_blank" rel="noreferrer" moz-do-not-send="true" class="moz-txt-link-freetext">https://bugs.openjdk.org/browse/JDK-8143850</a><br>
</div>
<div dir="auto"><br>
</div>
<div dir="auto">There were also discussions to enhance
collections in general, adding more useful methods like
getFirst() or removeLast() to ArrayList, etc. See for
details:</div>
<div dir="auto"><a href="https://bugs.openjdk.org/browse/JDK-8266572" moz-do-not-send="true" class="moz-txt-link-freetext">https://bugs.openjdk.org/browse/JDK-8266572</a><br>
</div>
<div dir="auto"><br>
</div>
<div dir="auto">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.</div>
<div dir="auto"><br>
</div>
<div dir="auto">With best regards,</div>
<div dir="auto">Tagir Valeev<br>
<br>
<div class="gmail_quote" dir="auto">
<div dir="ltr" class="gmail_attr">сб, 9 июл. 2022 г.,
11:22 Rodion Efremov <<a href="mailto:coderodd3@gmail.com" target="_blank" rel="noreferrer" moz-do-not-send="true" class="moz-txt-link-freetext">coderodd3@gmail.com</a>>:<br>
</div>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr">Hello,
<div><br>
</div>
<div>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.</div>
<div><br>
</div>
<div>Best regards,</div>
<div>rodde</div>
</div>
<div dir="ltr"><br>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Sat, Jul 9,
2022 at 11:19 AM Tagir Valeev <<a href="mailto:amaembo@gmail.com" rel="noreferrer
noreferrer" target="_blank" moz-do-not-send="true" class="moz-txt-link-freetext">amaembo@gmail.com</a>>
wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px
0px 0px 0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex">
<div dir="auto">Hello!
<div dir="auto"><br>
</div>
<div dir="auto">Are there real world
problems/use cases where IndexedLinkedList
would be preferred in terms of CPU/memory
usage over ArrayList? </div>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">сб, 9 июл.
2022 г., 07:18 Rodion Efremov <<a href="mailto:coderodd3@gmail.com" rel="noreferrer noreferrer" target="_blank" moz-do-not-send="true" class="moz-txt-link-freetext">coderodd3@gmail.com</a>>:<br>
</div>
<blockquote class="gmail_quote" style="margin:0px 0px 0px
0.8ex;border-left:1px solid
rgb(204,204,204);padding-left:1ex">Data
structure repo:
<div><a href="https://github.com/coderodde/IndexedLinkedList" rel="noreferrer noreferrer noreferrer" target="_blank" moz-do-not-send="true" class="moz-txt-link-freetext">https://github.com/coderodde/IndexedLinkedList</a></div>
<div dir="auto"><br>
</div>
Benchmark repo:
<div dir="auto"><a href="https://github.com/coderodde/IndexedLinkedListBenchmark" rel="noreferrer noreferrer noreferrer" target="_blank" moz-do-not-send="true" class="moz-txt-link-freetext">https://github.com/coderodde/IndexedLinkedListBenchmark</a></div>
<div><br>
</div>
<div dir="auto">I have profiled my data
structure and it seems it’s more performant
than java.util.LinkedList or TreeList, if
nothing else.</div>
<div dir="auto"><br>
</div>
<div dir="auto">So, is there any chance of
including IndexedLinkedList to JDK?</div>
<div dir="auto"><br>
</div>
<div dir="auto">Best regards,</div>
<div dir="auto">rodde</div>
</blockquote>
</div>
</blockquote>
</div>
</blockquote>
</div>
</div>
</div>
</blockquote>
</blockquote>
</blockquote>
</body>
</html>