Potential performance improvement for java.util.AbstractList?

[Martin Buchholz]

On Tue, Dec 8, 2015 at 10:17 PM, Nicholas Cull <run2000 at gmail.com> wrote:

> Yes, the time performance of size() appears to be unspecified by the whole
> Collections framework: the implementation of equals() in AbstractSet uses
> size() as an optimization, though AbstractCollection does not. Naively it seems
> odd that we don't perform this check inside AbstractList. What contract is
> AbstractList implying that would be broken by doing so?

Using size in AbstracList is not unreasonable.  size is rather likely
to be O(1) because the List interface is concurrency-hostile.  OTOH
creating ListIterators and each check of equality for an index is also
O(1), so this is a significant optimization only for lists that
generally share a common prefix.  And sorry, but that's not a good
enough reason to change AbstractList.  Especially given that the
current implementation is specified!  It's easier adding optimized
equals methods to subclasses.

It's more reasonable for AbstractSet to call size() because you cannot
have O(1) element by element comparison.  You have to call
set.contains which is much more likely to be O(N).