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 > > > > > > > >
rodde-perf.ods
Description: application/vnd.oasis.opendocument.spreadsheet
--------------------------------------------------------------------- To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
