Re: [collections] JMH results for IndexedLinkedList

[Rodion Efremov]

Hello Matt and community,

I have created an ASF JIRA issue back in the days:
https://issues.apache.org/jira/projects/COLLECTIONS/issues/COLLECTIONS-797?filter=allopenissues

Best regards,
rodde

On Mon, Jul 11, 2022 at 6:23 AM Matt Juntunen 
wrote:

> Hello rodde,
>
> Thanks for your patience while I looked at this. I've made a PR [1] on
> your benchmark project with an updated benchmark class. (I used the
> completely uninspired class name of IndexedLinkedListPerformance2 :-)
> The results back up what you've been saying about the performance of
> this list implementation. I've attached a spreadsheet summarizing the
> data for a number of different operations along with some images of
> some of the most interesting comparisons. I've compared results for
> java.util.ArrayList, java.util.LinkedList,
> org.apache.commons.collections4.list.TreeList, and
> com.github.coderodde.util.IndexedLinkedList (the list in question
> here) using JDK 18 on list sizes of 10, 100, 1000, and 1.
>
> Below are some notes on the attached images.
> - get-random.png - Displays timings for element access at random
> indices. As expected, ArrayList is by far the best. TreeList and
> IndexedLinkedList are relatively close to each other but
> IndexedLinkedList is consistently faster. LinkedList was too terrible
> to even include on the graph.
> - iterate.png - Displays timings for list traversal using the list's
> iterator. This was unexpectedly bad for TreeList, which performed far
> worse than the others. The performance of IndexedLinkedList was on par
> with the JDK lists overall.
> - iterate-and-modify.png - Displays timings for iterating through the
> list while randomly adding and removing elements via the iterator.
> IndexedLinkedList did extraordinarily well here, with performance very
> close to LinkedList. Surprisingly, TreeList did worse than all of the
> others, including ArrayList.
>
> Overall, I think this list implementation would be a good option to
> include in commons-collections. Does anyone have any objections to
> opening a Jira ticket to pursue this?
>
> Regards,
> Matt J
>
> [1] https://github.com/coderodde/IndexedLinkedListBenchmark/pull/3
>
> On Sun, Jul 10, 2022 at 4:16 AM Bruno Kinoshita  wrote:
> >
> > Hi Rodde,
> >
> > It has been almost a week since your last response. Did you take a look
> at
> > > my work?
> > >
> >
> > Please note that we are all volunteers here, so sometimes we may be able
> to
> > respond quickly, others we may take a few days/weeks/months/...
> >
> > I know Matt is active in other Apache mailing lists, and that he works on
> > multiple Apache components. Besides also having $work, personal life,
> etc.,
> > of course. So please be patient :)
> >
> > Cheers
> > -Bruno
> >
> > On Sun, 10 Jul 2022 at 17:03, Rodion Efremov 
> wrote:
> >
> > > Hi Matt,
> > >
> > > It has been almost a week since your last response. Did you take a
> look at
> > > my work?
> > >
> > > Best regards,
> > > rodde
> > >
> > > ma 4.7.2022 klo 20.51 Matt Juntunen 
> kirjoitti:
> > >
> > > > Thanks, rodde! I should have some time this week to take a closer
> > > > look. I plan on playing with the benchmarks a bit on my own. I'll let
> > > > you know what I find.
> > > >
> > > > Regards,
> > > > Matt J
> > > >
> > > > On Mon, Jul 4, 2022 at 4:53 AM Rodion Efremov 
> > > wrote:
> > > > >
> > > > > Hi Matt and community,
> > > > >
> > > > > I have compiled the benchmark result data into 3 tables [1] (three
> > > > > different load sizes) [2]. If nothing else, IndexedLiinkedList
> (called
> > > > > RoddeList in output) is faster than both java.util.LinkedList and
> > > > TreeList.
> > > > >
> > > > > If, for further discussion, you require something else, please let
> me
> > > > know.
> > > > >
> > > > > Best regards,
> > > > > rodde
> > > > >
> > > > > [1]
> https://github.com/coderodde/indexedLinkedList/#benchmark-with-jmh
> > > > > [2]
> > > > >
> > > >
> > >
> https://github.com/coderodde/IndexedLinkedListBenchmark/blob/main/src/main/java/com/coderodde/IndexedLinkedListPerformance.java
> > > > >
> > > > > On Fri, Jul 1, 2022 at 6:11 AM Matt Juntunen <
> > > matt.a.juntu...@gmail.com>
> > > > > wrote:
> > > > >
> > > > > > Hello rodde,
> > > > > >
> > > > > > Thank you for sending me a reminder on this. Unfortunately, I
> haven't
> > > > > > had time to look at the code yet. Gilles suggestions are
> something I
> > > > > > would like to see as well. Having tables of JMH results for the
> > > > > > different algorithms at different sizes would be very helpful.
> > > > > >
> > > > > > Regards,
> > > > > > Matt J
> > > > > >
> > > > > > On Thu, Jun 30, 2022 at 11:34 AM Gilles Sadowski <
> > > gillese...@gmail.com
> > > > >
> > > > > > wrote:
> > > > > > >
> > > > > > > Hello.
> > > > > > >
> > > > > > > Le jeu. 30 juin 2022 à 07:54, Rodion Efremov <
> codero...@gmail.com>
> > > a
> > > > > > écrit :
> > > > > > > >
> > > > > > > > Hi Matt and community,
> > > > > > > >
> > > > > > > > Have you take a look at 

Re: [collections] JMH results for IndexedLinkedList

[Matt Juntunen]

Hello rodde,

Thanks for your patience while I looked at this. I've made a PR [1] on
your benchmark project with an updated benchmark class. (I used the
completely uninspired class name of IndexedLinkedListPerformance2 :-)
The results back up what you've been saying about the performance of
this list implementation. I've attached a spreadsheet summarizing the
data for a number of different operations along with some images of
some of the most interesting comparisons. I've compared results for
java.util.ArrayList, java.util.LinkedList,
org.apache.commons.collections4.list.TreeList, and
com.github.coderodde.util.IndexedLinkedList (the list in question
here) using JDK 18 on list sizes of 10, 100, 1000, and 1.

Below are some notes on the attached images.
- get-random.png - Displays timings for element access at random
indices. As expected, ArrayList is by far the best. TreeList and
IndexedLinkedList are relatively close to each other but
IndexedLinkedList is consistently faster. LinkedList was too terrible
to even include on the graph.
- iterate.png - Displays timings for list traversal using the list's
iterator. This was unexpectedly bad for TreeList, which performed far
worse than the others. The performance of IndexedLinkedList was on par
with the JDK lists overall.
- iterate-and-modify.png - Displays timings for iterating through the
list while randomly adding and removing elements via the iterator.
IndexedLinkedList did extraordinarily well here, with performance very
close to LinkedList. Surprisingly, TreeList did worse than all of the
others, including ArrayList.

Overall, I think this list implementation would be a good option to
include in commons-collections. Does anyone have any objections to
opening a Jira ticket to pursue this?

Regards,
Matt J

[1] https://github.com/coderodde/IndexedLinkedListBenchmark/pull/3

On Sun, Jul 10, 2022 at 4:16 AM Bruno Kinoshita  wrote:
>
> Hi Rodde,
>
> It has been almost a week since your last response. Did you take a look at
> > my work?
> >
>
> Please note that we are all volunteers here, so sometimes we may be able to
> respond quickly, others we may take a few days/weeks/months/...
>
> I know Matt is active in other Apache mailing lists, and that he works on
> multiple Apache components. Besides also having $work, personal life, etc.,
> of course. So please be patient :)
>
> Cheers
> -Bruno
>
> On Sun, 10 Jul 2022 at 17:03, Rodion Efremov  wrote:
>
> > Hi Matt,
> >
> > It has been almost a week since your last response. Did you take a look at
> > my work?
> >
> > Best regards,
> > rodde
> >
> > ma 4.7.2022 klo 20.51 Matt Juntunen  kirjoitti:
> >
> > > Thanks, rodde! I should have some time this week to take a closer
> > > look. I plan on playing with the benchmarks a bit on my own. I'll let
> > > you know what I find.
> > >
> > > Regards,
> > > Matt J
> > >
> > > On Mon, Jul 4, 2022 at 4:53 AM Rodion Efremov 
> > wrote:
> > > >
> > > > Hi Matt and community,
> > > >
> > > > I have compiled the benchmark result data into 3 tables [1] (three
> > > > different load sizes) [2]. If nothing else, IndexedLiinkedList (called
> > > > RoddeList in output) is faster than both java.util.LinkedList and
> > > TreeList.
> > > >
> > > > If, for further discussion, you require something else, please let me
> > > know.
> > > >
> > > > Best regards,
> > > > rodde
> > > >
> > > > [1] https://github.com/coderodde/indexedLinkedList/#benchmark-with-jmh
> > > > [2]
> > > >
> > >
> > https://github.com/coderodde/IndexedLinkedListBenchmark/blob/main/src/main/java/com/coderodde/IndexedLinkedListPerformance.java
> > > >
> > > > On Fri, Jul 1, 2022 at 6:11 AM Matt Juntunen <
> > matt.a.juntu...@gmail.com>
> > > > wrote:
> > > >
> > > > > Hello rodde,
> > > > >
> > > > > Thank you for sending me a reminder on this. Unfortunately, I haven't
> > > > > had time to look at the code yet. Gilles suggestions are something I
> > > > > would like to see as well. Having tables of JMH results for the
> > > > > different algorithms at different sizes would be very helpful.
> > > > >
> > > > > Regards,
> > > > > Matt J
> > > > >
> > > > > On Thu, Jun 30, 2022 at 11:34 AM Gilles Sadowski <
> > gillese...@gmail.com
> > > >
> > > > > wrote:
> > > > > >
> > > > > > Hello.
> > > > > >
> > > > > > Le jeu. 30 juin 2022 à 07:54, Rodion Efremov 
> > a
> > > > > écrit :
> > > > > > >
> > > > > > > Hi Matt and community,
> > > > > > >
> > > > > > > Have you take a look at my work? If so, what do you think?
> > > > > >
> > > > > > Perhaps you missed that feedback:
> > > > > >   https://markmail.org/message/y3tozjdke2ivz3dr
> > > > > >
> > > > > > >
> > > > > > > Best regards,
> > > > > > > rodde
> > > > > > >
> > > > > > > to 23.6.2022 klo 19.06 Matt Juntunen 
> > > > > kirjoitti:
> > > > > > >
> > > > > > > > Hello,
> > > > > > > >
> > > > > > > > Thanks for providing the data here. I will hopefully have time
> > to
> > > > > take
> > > > > > > > a look at this over the weekend. Send me a ping here on the 

Re: [collections] JMH results for IndexedLinkedList

[Bruno Kinoshita]

Hi Rodde,

It has been almost a week since your last response. Did you take a look at
> my work?
>

Please note that we are all volunteers here, so sometimes we may be able to
respond quickly, others we may take a few days/weeks/months/...

I know Matt is active in other Apache mailing lists, and that he works on
multiple Apache components. Besides also having $work, personal life, etc.,
of course. So please be patient :)

Cheers
-Bruno

On Sun, 10 Jul 2022 at 17:03, Rodion Efremov  wrote:

> Hi Matt,
>
> It has been almost a week since your last response. Did you take a look at
> my work?
>
> Best regards,
> rodde
>
> ma 4.7.2022 klo 20.51 Matt Juntunen  kirjoitti:
>
> > Thanks, rodde! I should have some time this week to take a closer
> > look. I plan on playing with the benchmarks a bit on my own. I'll let
> > you know what I find.
> >
> > Regards,
> > Matt J
> >
> > On Mon, Jul 4, 2022 at 4:53 AM Rodion Efremov 
> wrote:
> > >
> > > Hi Matt and community,
> > >
> > > I have compiled the benchmark result data into 3 tables [1] (three
> > > different load sizes) [2]. If nothing else, IndexedLiinkedList (called
> > > RoddeList in output) is faster than both java.util.LinkedList and
> > TreeList.
> > >
> > > If, for further discussion, you require something else, please let me
> > know.
> > >
> > > Best regards,
> > > rodde
> > >
> > > [1] https://github.com/coderodde/indexedLinkedList/#benchmark-with-jmh
> > > [2]
> > >
> >
> https://github.com/coderodde/IndexedLinkedListBenchmark/blob/main/src/main/java/com/coderodde/IndexedLinkedListPerformance.java
> > >
> > > On Fri, Jul 1, 2022 at 6:11 AM Matt Juntunen <
> matt.a.juntu...@gmail.com>
> > > wrote:
> > >
> > > > Hello rodde,
> > > >
> > > > Thank you for sending me a reminder on this. Unfortunately, I haven't
> > > > had time to look at the code yet. Gilles suggestions are something I
> > > > would like to see as well. Having tables of JMH results for the
> > > > different algorithms at different sizes would be very helpful.
> > > >
> > > > Regards,
> > > > Matt J
> > > >
> > > > On Thu, Jun 30, 2022 at 11:34 AM Gilles Sadowski <
> gillese...@gmail.com
> > >
> > > > wrote:
> > > > >
> > > > > Hello.
> > > > >
> > > > > Le jeu. 30 juin 2022 à 07:54, Rodion Efremov 
> a
> > > > écrit :
> > > > > >
> > > > > > Hi Matt and community,
> > > > > >
> > > > > > Have you take a look at my work? If so, what do you think?
> > > > >
> > > > > Perhaps you missed that feedback:
> > > > >   https://markmail.org/message/y3tozjdke2ivz3dr
> > > > >
> > > > > >
> > > > > > Best regards,
> > > > > > rodde
> > > > > >
> > > > > > to 23.6.2022 klo 19.06 Matt Juntunen 
> > > > kirjoitti:
> > > > > >
> > > > > > > Hello,
> > > > > > >
> > > > > > > Thanks for providing the data here. I will hopefully have time
> to
> > > > take
> > > > > > > a look at this over the weekend. Send me a ping here on the dev
> > list
> > > > > > > if you don't hear back from me (or someone else) within a week.
> > > > > > >
> > > > > > > Regards,
> > > > > > > Matt J
> > > > > > >
> > > > > > > On Tue, Jun 21, 2022 at 7:22 AM Rodion Efremov <
> > codero...@gmail.com>
> > > > > > > wrote:
> > > > > > > >
> > > > > > > > Hi,
> > > > > > > >
> > > > > > > > Data structure: IndexedLinkedList
> > > > > > > > 
> > > > > > > > Benchmark: IndexedLinkedListBenchmark
> > > > > > > > 
> > > > > > > >
> > > > > > > > Benchmark output:
> > > > > > > >
> > https://github.com/coderodde/indexedLinkedList/#benchmark-output
> > > > > > > >
> > > > > > > > From the benchmark output, we can judge that
> IndexedLinkedList
> > > > > > > outperforms
> > > > > > > > both java.util.LinkedList and the Apache Commons Collections
> > > > TreeList.
> > > > > > > It,
> > > > > > > > however, does not seem to supersede the java.util.ArrayList.
> > > > > > > >
> > > > > > > > Basically, I would expect the IndexedLinkedList to beat the
> > > > ArrayList
> > > > > > > where
> > > > > > > > we have a lot of following operations:
> > > > > > > >
> > > > > > > >- addFirst(E)
> > > > > > > >- add(int, E)
> > > > > > > >- remove(int)
> > > > > > > >
> > > > > > > > So, what do you think? I am getting anywhere with that?
> > > > > > > >
> > > > > > > > Best regards,
> > > > > > > > rodde
> > > > >
> > > > >
> -
> > > > > To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
> > > > > For additional commands, e-mail: dev-h...@commons.apache.org
> > > > >
> > > >
> > > > -
> > > > To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
> > > > For additional commands, e-mail: dev-h...@commons.apache.org
> > > >
> > > >
> >
> > -
> > To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org
> > For additional