You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Rodion Efremov <co...@gmail.com> on 2022/06/10 19:29:43 UTC
[collections] Add a list/deque faster than TreeList?
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?
Posted by Matt Sicker <bo...@gmail.com>.
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 <co...@gmail.com> 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 <bo...@gmail.com> 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 <co...@gmail.com> 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?
Posted by Matt Juntunen <ma...@gmail.com>.
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 <co...@gmail.com> 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 <bo...@gmail.com> 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 <co...@gmail.com> 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-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [collections] Add a list/deque faster than TreeList?
Posted by Rodion Efremov <co...@gmail.com>.
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 <bo...@gmail.com> 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 <co...@gmail.com> 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?
Posted by Matt Sicker <bo...@gmail.com>.
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 <co...@gmail.com> 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