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
