Re: [collections] Add a list/deque faster than TreeList?
Hello, I agree that this looks interesting. I personally would like to see the following before weighing in on whether or not to include it in commons: 1. A list of use cases where this data structure would be potentially more performant or useful than existing data structures. 2. A set of JMH[1] benchmarks that compares this data structure to TreeList and ArrayList (and others if needed). I see that there are basic benchmarks already in the code, but JMH will give us much more accurate and reproducible results. There are examples of such benchmarks in several commons projects, e.g., commons-numbers [2] and commons-geometry [3]. Regardless, thank you for your proposal and code, rodde. It is much appreciated. Regards, Matt J [1] https://openjdk.java.net/projects/code-tools/jmh/ [2] https://github.com/apache/commons-numbers/tree/master/commons-numbers-examples/examples-jmh [3] https://github.com/apache/commons-geometry/tree/master/commons-geometry-examples/examples-jmh On Sat, Jun 11, 2022 at 1:25 PM Rodion Efremov wrote: > > Hi Matt and community, > > About thread safety: I keep an int counting modifications (called > modCount). Now, spliterator/iterator/sublist check that modCount == > expectedModCount, and if that is not the case, throws > ConcurrentModificationException. Basically, it resembles the fail-fast > behavior of ArrayList/LinkedList. In order to deal with concurrency, one > should wrap an instance of IndexedLinkedList into > Collections.synchronizedList(...). > > About Guava: they happily turned down my offer. > > Best regards, > rodde > > la 11.6.2022 klo 19.44 Matt Sicker kirjoitti: > > > Looks pretty interesting. I’ll be honest that my own data structure > > expertise revolves around immutable persistent patterns rather than mutable > > ones, but your class makes perfect sense as a mutable one. > > > > Do you have any notes on thread safety? > > > > While it’s neat that you’re submitting to the JDK as well, that sort of > > process is fairly long term, so I’d imagine that Collections would be a > > great place for it. If you’re trying to donate this to multiple projects, > > then Eclipse also has a collections library that might like it, and Guava > > might like it, too. > > > > — > > Matt Sicker > > > > > On Jun 10, 2022, at 14:30, Rodion Efremov wrote: > > > > > > Hi, > > > > > > I have this List/Deque data structure: > > > > > > https://github.com/coderodde/IndexedLinkedList > > > > > > In a versatile benchmark, it outperforms the O(log n) TreeList easily by > > > the factor of 2. (Also, it requires less memory than TreeList.) > > > > > > What do you think? Does it deserve to be included in collections? > > > > > > Best regards, > > > rodde > > - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
Re: [collections] Add a list/deque faster than TreeList?
About thread safety, I was mostly interested in yes or no, though the details are neat. We have annotations for that so that users know which classes are applicable to different situations. Guava seems to be more of a giant toolbox than an easily embedded library like things at Commons, so I suppose that doesn’t surprise me too much. — Matt Sicker > On Jun 11, 2022, at 12:25, Rodion Efremov wrote: > > Hi Matt and community, > > About thread safety: I keep an int counting modifications (called > modCount). Now, spliterator/iterator/sublist check that modCount == > expectedModCount, and if that is not the case, throws > ConcurrentModificationException. Basically, it resembles the fail-fast > behavior of ArrayList/LinkedList. In order to deal with concurrency, one > should wrap an instance of IndexedLinkedList into > Collections.synchronizedList(...). > > About Guava: they happily turned down my offer. > > Best regards, > rodde > > la 11.6.2022 klo 19.44 Matt Sicker kirjoitti: > >> Looks pretty interesting. I’ll be honest that my own data structure >> expertise revolves around immutable persistent patterns rather than mutable >> ones, but your class makes perfect sense as a mutable one. >> >> Do you have any notes on thread safety? >> >> While it’s neat that you’re submitting to the JDK as well, that sort of >> process is fairly long term, so I’d imagine that Collections would be a >> great place for it. If you’re trying to donate this to multiple projects, >> then Eclipse also has a collections library that might like it, and Guava >> might like it, too. >> >> — >> Matt Sicker >> On Jun 10, 2022, at 14:30, Rodion Efremov wrote: >>> >>> Hi, >>> >>> I have this List/Deque data structure: >>> >>> https://github.com/coderodde/IndexedLinkedList >>> >>> In a versatile benchmark, it outperforms the O(log n) TreeList easily by >>> the factor of 2. (Also, it requires less memory than TreeList.) >>> >>> What do you think? Does it deserve to be included in collections? >>> >>> Best regards, >>> rodde >>
Re: [collections] Add a list/deque faster than TreeList?
Hi Matt and community, About thread safety: I keep an int counting modifications (called modCount). Now, spliterator/iterator/sublist check that modCount == expectedModCount, and if that is not the case, throws ConcurrentModificationException. Basically, it resembles the fail-fast behavior of ArrayList/LinkedList. In order to deal with concurrency, one should wrap an instance of IndexedLinkedList into Collections.synchronizedList(...). About Guava: they happily turned down my offer. Best regards, rodde la 11.6.2022 klo 19.44 Matt Sicker kirjoitti: > Looks pretty interesting. I’ll be honest that my own data structure > expertise revolves around immutable persistent patterns rather than mutable > ones, but your class makes perfect sense as a mutable one. > > Do you have any notes on thread safety? > > While it’s neat that you’re submitting to the JDK as well, that sort of > process is fairly long term, so I’d imagine that Collections would be a > great place for it. If you’re trying to donate this to multiple projects, > then Eclipse also has a collections library that might like it, and Guava > might like it, too. > > — > Matt Sicker > > > On Jun 10, 2022, at 14:30, Rodion Efremov wrote: > > > > Hi, > > > > I have this List/Deque data structure: > > > > https://github.com/coderodde/IndexedLinkedList > > > > In a versatile benchmark, it outperforms the O(log n) TreeList easily by > > the factor of 2. (Also, it requires less memory than TreeList.) > > > > What do you think? Does it deserve to be included in collections? > > > > Best regards, > > rodde >
Re: [collections] Add a list/deque faster than TreeList?
Looks pretty interesting. I’ll be honest that my own data structure expertise revolves around immutable persistent patterns rather than mutable ones, but your class makes perfect sense as a mutable one. Do you have any notes on thread safety? While it’s neat that you’re submitting to the JDK as well, that sort of process is fairly long term, so I’d imagine that Collections would be a great place for it. If you’re trying to donate this to multiple projects, then Eclipse also has a collections library that might like it, and Guava might like it, too. — Matt Sicker > On Jun 10, 2022, at 14:30, Rodion Efremov wrote: > > Hi, > > I have this List/Deque data structure: > > https://github.com/coderodde/IndexedLinkedList > > In a versatile benchmark, it outperforms the O(log n) TreeList easily by > the factor of 2. (Also, it requires less memory than TreeList.) > > What do you think? Does it deserve to be included in collections? > > Best regards, > rodde
RE: [collections] Add a list/deque faster than TreeList?
I'd like to point out that rodde has also asked this project to be included in OpenJDK: https://mail.openjdk.java.net/pipermail/core-libs-dev/2022-June/091412.html On 2022/06/10 19:29:43 Rodion Efremov wrote: Hi, I have this List/Deque data structure: https://github.com/coderodde/IndexedLinkedList In a versatile benchmark, it outperforms the O(log n) TreeList easily by the factor of 2. (Also, it requires less memory than TreeList.) What do you think? Does it deserve to be included in collections? Best regards, rodde - To unsubscribe, e-mail: dev-unsubscr...@commons.apache.org For additional commands, e-mail: dev-h...@commons.apache.org
