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 <matt.a.juntu...@gmail.com> 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 10000. > > 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 <ki...@apache.org> 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 <codero...@gmail.com> > 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 <matt.a.juntu...@gmail.com> > 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 <codero...@gmail.com> > > > 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 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 < > matt.a.juntu...@gmail.com> > > > > > > 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 > > > > > > > > > > <https://github.com/coderodde/IndexedLinkedList> > > > > > > > > > > Benchmark: IndexedLinkedListBenchmark > > > > > > > > > > <https://github.com/coderodde/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 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