[concurrency-interest] CopyOnWriteArrayNavigableSet too late for JEP 266?

Martin Buchholz martinrb at google.com
Tue Oct 13 21:50:53 EDT 2015


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 <openjdk at duigou.org> 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
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20151013/4e7b3638/attachment-0001.html>


More information about the Concurrency-interest mailing list