[concurrency-interest] CopyOnWriteArrayNavigableSet too late for JEP 266?
openjdk at duigou.org
Tue Oct 13 00:52:18 EDT 2015
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)?
More information about the Concurrency-interest