CopyOnWriteArrayNavigableSet discussion on concurrency-interest

[Mike Duigou]

Hello all;

For those that don't regularly read the JSR-166 concurrency-interest 
list (http://cs.oswego.edu/mailman/listinfo/concurrency-interest) I 
wanted to make note of a discussion there that some reading here may be 
interested in.

I have recently proposed a new NavigableSet implementation which, 
similar to CopyOnWriteArraySet, uses CopyOnWriteArrayList for storing 
the Set elements.  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. As with all uses of 
CopyOnWriteArraySet the mutation rate is usually the practical limiting 
factor influencing the size of viable supported sets.

If you have suggestions, feedback or comments please contribute to the 
discussion on concurrency-interest. Assuming the idea is accepted for 
inclusion there would still be an eventual pre-integration RFC review 
through this list, but in the meantime any discussion can be sent to me 
directly or concurrency-interest.

Cheers,

Mike