Potential performance improvement for java.util.AbstractList?

[David Holmes]

On 8/12/2015 1:39 AM, Rafael Winterhalter wrote:
> In this case, one might consider:
>
> if (o instanceof java.util.RandomAccess && (List<?>)o).size() != size())
>    return false;

You'd also have to check the type of 'this'.

> Type checks are cheap, so the overhead of this additional statement should
> not be too big. Yet, maybe many list comparisons in practice involve lists
> of equal size. Otherwise, the contract of the List::equals method would
> allow for such a short-wiring.

These type of functions are generally already "optimal" for the range of 
cases they have to accommodate. Invariably you can't improve your case 
of interest without potentially impacting a lot of other cases.

David
-----

> 2015-12-07 16:31 GMT+01:00 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.
>>
>> 2015-12-07 16:28 GMT+01:00 Langer, Christoph <christoph.langer at sap.com>:
>>
>>> Hi all,
>>>
>>> a Java application developer of our company has indicated that it might
>>> yield some performance benefit to modify the coding of
>>> java.util.AbstractList.equals() that it would first compare the size of
>> the
>>> lists before iterating the elements. It would for sure be better in cases
>>> where one compares lists which don't have the same size. In case of
>>> comparing "equal" lists it would add some minor cost, though.
>>>
>>> Currently the implementation is like this:
>>>
>>> public boolean equals(Object o) {
>>>          if (o == this)
>>>              return true;
>>>          if (!(o instanceof List))
>>>              return false;
>>>
>>>          ListIterator<E> e1 = listIterator();
>>>          ListIterator<?> e2 = ((List<?>) o).listIterator();
>>>          while (e1.hasNext() && e2.hasNext()) {
>>>              E o1 = e1.next();
>>>              Object o2 = e2.next();
>>>              if (!(o1==null ? o2==null : o1.equals(o2)))
>>>                  return false;
>>>          }
>>>          return !(e1.hasNext() || e2.hasNext());
>>>      }
>>>
>>> One could do for instance:
>>>
>>>
>>> public boolean equals(Object o) {
>>>
>>>          if (o == this)
>>>
>>>              return true;
>>>
>>>          if (!(o instanceof List))
>>>
>>>              return false;
>>>
>>>          if ((List<?>)o).size() != size())
>>>
>>>              return false;
>>>
>>>
>>>
>>>          ListIterator<E> e1 = listIterator();
>>>
>>>          ListIterator<?> e2 = ((List<?>) o).listIterator();
>>>
>>>          while (e1.hasNext() && e2.hasNext()) {
>>>
>>>              E o1 = e1.next();
>>>
>>>              Object o2 = e2.next();
>>>
>>>              if (!(o1==null ? o2==null : o1.equals(o2)))
>>>
>>>                  return false;
>>>
>>>          }
>>>
>>>          return !(e1.hasNext() || e2.hasNext());
>>>
>>>      }
>>>
>>> How would you assess this idea? Are there other drawbacks/showstoppers to
>>> this which I don't see?
>>>
>>> Thanks in advance for comments.
>>>
>>> Best regards
>>> Christoph
>>>
>>>
>>