Potential performance improvement for java.util.AbstractList?

[Vitaly Davidovich]

sent from my phone
On Dec 8, 2015 12:07 AM, "David Holmes" <david.holmes at oracle.com> wrote:
>
> 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'.

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

Also, I don't think RandomAccess says anything about size() necessarily
being constant time.  Really, subclasses are in better position to
determine this (short of another marker interface to indicate constant time
size()).

>
>
>> 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
>>>>
>>>>
>>>