[concurrency-interest] Should CopyOnWriteArrayList implement RandomAccess?

Doug Lea dl at cs.oswego.edu
Thu Jun 27 11:09:06 EDT 2013


The lead sentence in RandomAccess says:

"Marker interface used by List implementations to indicate that they support 
fast (generally constant time) random access."

This is true of CopyOnWriteArrayList. For example get(43) is as fast as get(0).

One unfortunate aspect of this and other marker interfaces is that
some other code might make further assumptions based on instanceof
RandomAccess that don't hold here. One nice thing about JDK8 extension
methods is that you can overcome some of these problems by overriding
default implementations rather than worrying about non-overridable
utilities in classes like Collections. So JDK8 COWAL does in fact
do this. For example, you can actually sort one in reasonable time.

-Doug


On 06/26/13 06:55, Nitsan Wakart wrote:
> Hi,
> Given the the javadoc for RandomAccess suggests that:
> "As a rule of thumb, a List implementation should implement this interface if, for typical instances of the class, this loop:
> for (int i=0, n=list.size(); i < n; i++) list.get(i);
>
> runs faster than this loop:
> for (Iterator i=list.iterator(); i.hasNext(); ) i.next();"
> But the above is not true for CopyOnWriteArrayList where the iterator performs better as the volatile read of the array is avoided on each entry and where the first loop is incorrect in any case(can lead to index out of bounds).
> Is that a bug or am I missing something here?
> Thanks,
> Nitsan
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>



More information about the Concurrency-interest mailing list