Potential performance improvement for java.util.AbstractList?

[Nicholas Cull]

Mon Dec 7 15:31:56 UTC 2015 Cédric Champeau <cedric.champeau at gmail.com> :

> I assume one reason it's done this way is that depending on the list
> implementation you are using, getting the size might involve iterating over
> all elements, so you would be iterating twice at worst case.

If calling size() was a non-trivial operation for AbstractList, it would
already be a problem for its listIterator(int) and the internal Iterator
implementations, which both call size(), and in turn are used by the provided
equals() method.

I had a quick look at the JDK code base to see what happens in practice. All
implementations I could find had a constant time lookup for size().

Looking at a more broad code base, the only example that wasn't guaranteed
constant time was in a Groovy class, which performs a lazy evaluation of
size(), resulting in constant amortized time.

Tue Dec 8 12:17:17 UTC 2015 Vitaly Davidovich <vitalyd at gmail.com> :

> Which also begs the question of why not override this in subclasses that
> have fast size().  Yes there may be some duplication but it's "simple"
> duplication

>From all the code I looked at in the JDK, few of the subclasses of AbstractList
override the equals() method, and all have constant time size(). If this check
is to be duplicated, it would be duplication over many classes.

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?

Regards,

Nicholas.