Impact of code difference in Collection#contains() worth improving?

[Stanimir Simeonoff]

Somewhat off topic.
The linked implementation of android lacks integer overflow on size. That
might be actually irrelevant on android due to OOM happening earlier than
integer overflow.
The latter that made me check the JDK impl. I know most concurrent
collections handle integer overflow (CLQ, CHM for instance) but I didn't
expect LinkedList would be a integer overflow victim.

There is no prevention of size going negative. It's unlikely to cause
security issues as LinkedList is pretty much shunned (rightfully) and
seldom used.

Stanimir




On Sat, Aug 30, 2014 at 8:04 PM, Fabian Lange <lange.fabian at gmail.com>
wrote:

> Hello dear list,
>
> it was not my intention to steal precious developer time by annoying
> you guys with my finding.
> I really wanted to understand why there is a source difference. So I
> went ahead and looked at it from the only aspect I could estimate
> contributing to it.
> I am well aware of the fact that JIT does an amazing job optimizing
> code, so it surprises me how in some replies there is an negative
> undertone and randomness attributed to JIT.
> Right now I assume that my question upset some people, because it is
> of course not nice that people question code which was written over a
> decade ago.
> If not discussing the question on a technical level, I do not know why
> the argument of time wasting on micro level is made in multiple page
> long e-mails, which for sure also took precious time to write.
>
> So thanks to everybody who taught me a bit about inner workings of JIT,
> and special thanks to Martin who did have the courage to submit a bug
> and webrev!
>
> Fabian:
>
> PS: Out of curiosity I looked at the contains implementation here:
>
> https://android.googlesource.com/platform/libcore/+/master/luni/src/main/java/java/util/LinkedList.java
> it is manually inlined to avoid counting the position at all.
> I wonder if JIT would do that at any point as well.
>
> On Wed, Aug 27, 2014 at 4:02 PM, Fabian Lange <lange.fabian at gmail.com>
> wrote:
> > Hi all,
> > I have been involved recently in some theoretical or nonsensical
> > discussions about microbenchmarking, jit compiling assemblies and so
> > fort.
> > One example was LinkedList vs ArrayList.
> >
> > What I noticed is that those two have a different implementation for
> contains():
> >
> > ArrayList:
> >
> >     public boolean contains(Object o) {
> >         return indexOf(o) >= 0;
> >     }
> >
> > LinkedList:
> >
> >     public boolean contains(Object o) {
> >         return indexOf(o) != -1;
> >     }
> >
> > Logically this is of course identical due to the contract of contains
> > which returns either -1 or the >=0 index of the element.
> >
> > This code has been like this almost forever, and I was wondering if
> > this actually makes a difference in CPU cycles.
> >
> > And in fact this code compiles into different assembler instructions.
> > The array list does a test against 0 and conditional move, while the
> > linked list does a jump equals on -1.
> >
> > Again that is not surprising, because the actual java source is
> > different. But I wonder if both options are equally good in cold
> > performance and when jitted based on parameter values.
> >
> > Wouldn't one implementation be better than the other? And why is not
> > the "better" implementation taken in both classes (and maybe other
> > Collections which use indexOf) ?
> >
> > Is the answer that this has always been like this and the benefit is
> > not worth the risk of touching ancient code?
> >
> > And if not for performance, would code clarify and similarity be an
> argument?
> >
> > (this message was posted to jdk8-dev initially, thanks to Dalibor
> > Topic for the pointer to this list)
> >
> > Fabian
>