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

Mike Duigou openjdk at duigou.org
Tue Oct 13 00:52:18 EDT 2015


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


More information about the Concurrency-interest mailing list