CopyOnWriteArrayNavigableSet too late for JEP 266?

classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

CopyOnWriteArrayNavigableSet too late for JEP 266?

Mike Duigou
Hello all;

I noticed today that JEP 266 has been accepted in to Java 9.
Congratulations! The news spurred me to finally finish the couple
remaining failing MOAT tests for the CopyOnWriteArray based
implementation of NavigableSet I have been working on occasionally for
the last six months or so.

The main difference between this new implementation and the existing
CopyOnWriteArraySet is that the new implementation keeps the backing
array in sorted order and can use binary search for some operations.
Some applications may find either it's implementation of the
NavigableSet interface, the sorted behaviour or the O(log2 n)
performance useful. In my particular use case, both of the later
attributes are most useful to me. I suspect that once it's available
many usages of CopyOnWriteArraySet for Comparable types could be
converted for an easy boost from O(n) to O(log2 n) performance. I have
done no performance analysis but my gut feel is that it will be a win
for sets with dozens to thousands of elements. For larger numbers of
elements the mutation rate must be really low for CopyOnWriteArray to be
a win at all.

The implementation currently passes the MOAT tests as well other
collection tests in the jdk_utils suite but almost certainly requires
additional testing and polish. I also took some performance shortcuts in
corner cases that some may care about. (descendingSet() and
descendingIterator() in particular are gross hacks).

Implementing the NavigableSet subSet operations is NOT a lot of fun!

Is it likely too late to consider this for inclusion in JEP 266? What's
the best way to contribute it for inclusion in the JSR-166 CVS (assuming
there is interest)?

Cheers,

Mike
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: CopyOnWriteArrayNavigableSet too late for JEP 266?

Martin Buchholz-3
I just submitted JEP 266, so yeah it's too late to get a ride on that train!
But I think there's still enough time to get things into jdk9 (if we hurry), and if not, there's always jdk10.

It's true that implementing the many methods in NavigableSet is very tedious.  It helps to have a high tolerance for tedium!

In principle I support the idea of CopyOnWriteArrayNavigableSet.

On Mon, Oct 12, 2015 at 9:52 PM, Mike Duigou <[hidden email]> wrote:
Hello all;

I noticed today that JEP 266 has been accepted in to Java 9. Congratulations! The news spurred me to finally finish the couple remaining failing MOAT tests for the CopyOnWriteArray based implementation of NavigableSet I have been working on occasionally for the last six months or so.

The main difference between this new implementation and the existing CopyOnWriteArraySet is that the new implementation keeps the backing array in sorted order and can use binary search for some operations. Some applications may find either it's implementation of the NavigableSet interface, the sorted behaviour or the O(log2 n) performance useful. In my particular use case, both of the later attributes are most useful to me. I suspect that once it's available many usages of CopyOnWriteArraySet for Comparable types could be converted for an easy boost from O(n) to O(log2 n) performance. I have done no performance analysis but my gut feel is that it will be a win for sets with dozens to thousands of elements. For larger numbers of elements the mutation rate must be really low for CopyOnWriteArray to be a win at all.

The implementation currently passes the MOAT tests as well other collection tests in the jdk_utils suite but almost certainly requires additional testing and polish. I also took some performance shortcuts in corner cases that some may care about. (descendingSet() and descendingIterator() in particular are gross hacks).

Implementing the NavigableSet subSet operations is NOT a lot of fun!

Is it likely too late to consider this for inclusion in JEP 266? What's the best way to contribute it for inclusion in the JSR-166 CVS (assuming there is interest)?

Cheers,

Mike
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: CopyOnWriteArrayNavigableSet too late for JEP 266?

Doug Lea
In reply to this post by Mike Duigou
On 10/13/2015 12:52 AM, Mike Duigou wrote:
>
> The main difference between this new implementation and the existing
> CopyOnWriteArraySet is that the new implementation keeps the backing array in
> sorted order and can use binary search for some operations.
> ...
> Is it likely too late to consider this for inclusion in JEP 266? What's the best
> way to contribute it for inclusion in the JSR-166 CVS (assuming there is interest)?

There are a couple of senses of the "too late" question here:

Backing up (about 18 years!): SortedArray{List,Set} (non-concurrent)
were considered for initial inclusion in Collections. My vague
recollection is that they were triaged out because the combination of
sort and binarySearch on arrays and lists covered most use cases
(including for example: creating, adding a bunch of items, sorting,
then using binary search thereafter).

Not all use cases though. The missing ones are the same as those
{Sorted,Navigable}CopyOnWriteArray{List,Set} would address.
(Even though "Navigable" replaced "Sorted" interface, class names
can still use the friendlier term.) All of these might be good
choices for collections with approximately 10 < size < 100 and/or
with very low insertion rates after initial construction.

So, one question is whether all four of SortedArrayList, SortedArraySet,
SortedCopyOnWriteArrayList, and SortedCopyOnWriteArraySet should now be
introduced to fill in the coverage gaps. Or whether the use cases
covered by only SortedCopyOnWriteArraySet are special enough to
warrant inclusion without the others. This is the kind of question
that tends to lead to prolonged inaction in JDK. So any thoughts on
resolving it quickly would be welcome.

-Doug






I'm not sure about prospects for jdk9.


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: CopyOnWriteArrayNavigableSet too late for JEP 266?

Mike Duigou
In reply to this post by Mike Duigou
  Doug Lea wrote:
>   So, one question is whether all four of SortedArrayList,
> SortedArraySet,
>   SortedCopyOnWriteArrayList, and SortedCopyOnWriteArraySet should now
> be
>   introduced to fill in the coverage gaps. Or whether the use cases
>   covered by only SortedCopyOnWriteArraySet are special enough to
>   warrant inclusion without the others. This is the kind of question
>   that tends to lead to prolonged inaction in JDK. So any thoughts on
>   resolving it quickly would be welcome.

I recall closing at least a few RFEs for these during my time as core
collections maintainer and I largely agree that the sorted variations
aren't essential.

COWL and COWSet both end up getting used for small to medium sized
collections where the non-interference between mutation and iteration is
useful--such as collections of listeners. Some also like that COWL has a
lower synchronization overhead than using
Collections.synchronized(List|Set) on another List or Set type. Prior to
Java 8 the availability of the *IfAbsent without needing to worry about
how synchronization was to be handled was also a plus.

Is NavigableCopyOnWriteArraySet useful and sufficiently different in
performance characteristics from other already available NavigableSet
implementations? I hope so.

>   I'm not sure about prospects for jdk9.

I will remain hopeful.  :-) I have the source as a patch against
jdk9-dev currently. The only aspect that I know still needs attention is
serialization but I otherwise think we can move quickly. Since the
implementation is derived from CopyOnWriteArraySet there is no question
of offering it under any license other than the same Public Domain
license as the rest of the J.U.C code. Can we start the process of
integrating it into the JSR-166 repo?

Mike
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: CopyOnWriteArrayNavigableSet too late for JEP 266?

Jason Mehrens
Hi Mike,

What are your thoughts on creating wrappers to implement the copy on write behavior (Collections.copyOnWriteXXX(Supplier))?  I always had a bias toward CopyOnWriteTreeSet instead of NavigableCopyOnWriteArraySet as a name.

Jason

________________________________________
From: [hidden email] <[hidden email]> on behalf of Mike Duigou <[hidden email]>
Sent: Wednesday, October 14, 2015 10:08 PM
To: Concurrency Interest
Subject: Re: [concurrency-interest] CopyOnWriteArrayNavigableSet too late for JEP 266?

  Doug Lea wrote:
>   So, one question is whether all four of SortedArrayList,
> SortedArraySet,
>   SortedCopyOnWriteArrayList, and SortedCopyOnWriteArraySet should now
> be
>   introduced to fill in the coverage gaps. Or whether the use cases
>   covered by only SortedCopyOnWriteArraySet are special enough to
>   warrant inclusion without the others. This is the kind of question
>   that tends to lead to prolonged inaction in JDK. So any thoughts on
>   resolving it quickly would be welcome.

I recall closing at least a few RFEs for these during my time as core
collections maintainer and I largely agree that the sorted variations
aren't essential.

COWL and COWSet both end up getting used for small to medium sized
collections where the non-interference between mutation and iteration is
useful--such as collections of listeners. Some also like that COWL has a
lower synchronization overhead than using
Collections.synchronized(List|Set) on another List or Set type. Prior to
Java 8 the availability of the *IfAbsent without needing to worry about
how synchronization was to be handled was also a plus.

Is NavigableCopyOnWriteArraySet useful and sufficiently different in
performance characteristics from other already available NavigableSet
implementations? I hope so.

>   I'm not sure about prospects for jdk9.

I will remain hopeful.  :-) I have the source as a patch against
jdk9-dev currently. The only aspect that I know still needs attention is
serialization but I otherwise think we can move quickly. Since the
implementation is derived from CopyOnWriteArraySet there is no question
of offering it under any license other than the same Public Domain
license as the rest of the J.U.C code. Can we start the process of
integrating it into the JSR-166 repo?

Mike
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: CopyOnWriteArrayNavigableSet too late for JEP 266?

Doug Lea
In reply to this post by Mike Duigou
On 10/14/2015 11:08 PM, Mike Duigou wrote:

> Is NavigableCopyOnWriteArraySet useful and sufficiently different in performance
> characteristics from other already available NavigableSet implementations? I
> hope so.
>

I've been sitting on this question. The range of applicability
is narrow, but it is clearly useful in that range. Other opinions
about including it (or any other concurrent collection for that
matter) would be welcome.

-Doug


_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: CopyOnWriteArrayNavigableSet too late for JEP 266?

Aaron Grunthal
In reply to this post by Doug Lea
One useful advantage of Navigable-/SortedSet is that one can not only
test the presence of an element but also extract the matching element by
(ab)using the floor/ceil methods.

Regular sets cannot be used for interning and a Map has the added
overhead/indirection with its Map.Entry objects.


On 14.10.2015 14:41, Doug Lea wrote:
> So, one question is whether all four of SortedArrayList, SortedArraySet,
> SortedCopyOnWriteArrayList, and SortedCopyOnWriteArraySet should now be
> introduced to fill in the coverage gaps. Or whether the use cases
> covered by only SortedCopyOnWriteArraySet are special enough to
> warrant inclusion without the others. This is the kind of question
> that tends to lead to prolonged inaction in JDK. So any thoughts on
> resolving it quickly would be welcome.

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: CopyOnWriteArrayNavigableSet too late for JEP 266?

Nathan Reynolds-2
There is a JDK bug on using sets for interning.  See https://bugs.openjdk.java.net/browse/JDK-8025414
-Nathan
On 10/24/2015 6:02 PM, Aaron Grunthal wrote:
One useful advantage of Navigable-/SortedSet is that one can not only test the presence of an element but also extract the matching element by (ab)using the floor/ceil methods.

Regular sets cannot be used for interning and a Map has the added overhead/indirection with its Map.Entry objects.


On 14.10.2015 14:41, Doug Lea wrote:
So, one question is whether all four of SortedArrayList, SortedArraySet,
SortedCopyOnWriteArrayList, and SortedCopyOnWriteArraySet should now be
introduced to fill in the coverage gaps. Or whether the use cases
covered by only SortedCopyOnWriteArraySet are special enough to
warrant inclusion without the others. This is the kind of question
that tends to lead to prolonged inaction in JDK. So any thoughts on
resolving it quickly would be welcome.

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest




_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: CopyOnWriteArrayNavigableSet too late for JEP 266?

Justin Sampson
Nathan Reynolds wrote:

> There is a JDK bug on using sets for interning.
> See https://bugs.openjdk.java.net/browse/JDK-8025414
>
> Aaron Grunthal wrote:
>
> > One useful advantage of Navigable-/SortedSet is that one can not
> > only test the presence of an element but also extract the
> > matching element by (ab)using the floor/ceil methods.
> >
> > Regular sets cannot be used for interning and a Map has the
> > added overhead/indirection with its Map.Entry objects.

I'm probably just confused as usual, but don't most of the standard
Set implementations simply wrap a Map anyway? E.g. a HashSet wraps a
HashMap; a TreeSet wraps a TreeMap; a ConcurrentSkipListSet wraps a
ConcurrentSkipListMap...

Cheers,
Justin

_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest