RFR: 8035584: (s) ArrayList(c) should avoid inflation if c is empty

Wed Mar 12 14:43:56 UTC 2014

Jason is right.  IIRC, the atomicity of toArray is a reason for the
ArrayList(Collection) constructor being written the way it is.

On Wed, Mar 12, 2014 at 7:06 AM, Jason Mehrens <jason_mehrens at hotmail.com>wrote:

> Mike,
>
> In the constructor do you think you should skip the call to isEmpty and
> just check the length of toArray?  Seems like since the implementation of
> the given collection is unknown it is probably best to perform as little
> interaction with it as possible.  Also it would be possible for isEmpty to
> return false followed by toArray returning a zero length array that is
> different from cached copies.
>
> Jason
>
> > Subject: Re: RFR: 8035584: (s) ArrayList(c) should avoid inflation if c
> is empty
> > From: mike.duigou at oracle.com
> > Date: Tue, 11 Mar 2014 18:18:26 -0700
> > To: martinrb at google.com
> > CC: core-libs-dev at openjdk.java.net
>
> >
> >
> > On Mar 11 2014, at 17:42 , Martin Buchholz <martinrb at google.com> wrote:
> >
> > > I'm hoping y'all have evidence that empty ArrayLists are common in the
> wild.
> > Yes, certainly. From the original proposal:
> > > [This change] based upon analysis that shows that in large
> applications as much as 10% of maps and lists are initialized but never
> receive any entries. A smaller number spend a large proportion of their
> lifetime empty. We've found similar results across other workloads as well.
> >
> > > It is curious that empty lists grow immediately to 10, while ArrayList
> with capacity 1 grows to 2, then 3... Some people might think that a bug.
> > Yes, that's unfortunate. I've made another version that uses a second
> sentinel for the default sized but empty case.
> >
> > Now I want to reduce the ensureCapacity reallocations! It seems like
> insane churn to replace the arrays that frequently.
> > > There are more   changes that need to be reverted.
> > > Else looks good.
> > > - * More formally, returns the lowest index <tt>i</tt> such that
> > > - *
> <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
> > > + * More formally, returns the lowest index {@code i} such that
> > > + * {@code
> (o==null ? get(i)==null : o.equals(get(i)))},
> >
> > Corrected. Thank you.
> >
> > http://cr.openjdk.java.net/~mduigou/JDK-8035584/2/webrev/
> >
> >
> > Mike
> >
> >
> >
> > >
> > >
> > > On Tue, Mar 11, 2014 at 5:20 PM, Mike Duigou <mike.duigou at oracle.com>
> wrote:
> > > I've actually always used scp. :-)
> > >
> > > Since I accepted all of your changes as suggested and had no other
> changes I was just going to go ahead and push once testing was done.
> > >
> > > I've now prepared a revised webrev and can still accept feedback.
> > >
> > > http://cr.openjdk.java.net/~mduigou/JDK-8035584/1/webrev/
> > >
> > > (Note: The webrev also contains
> https://bugs.openjdk.java.net/browse/JDK-8037097 since I am
> testing/pushing the two issues together.)
> > >
> > > Mike
> > >
> > > On Mar 11 2014, at 16:42 , Martin Buchholz <martinrb at google.com>
> wrote:
> > >
> > >> I don't see the updated webrev. Maybe you also fell victim to "rsync
> to cr no longer working"?
> > >>
> > >>
> > >> On Tue, Mar 11, 2014 at 4:34 PM, Mike Duigou <mike.duigou at oracle.com>
> wrote:
> > >>
> > >> On Feb 21 2014, at 14:56 , Martin Buchholz <martinrb at google.com>
> wrote:
> > >>
> > >>> You should do <tt> -> code conversion separately, and do it
> pervasively across the entire JDK.
> > >>
> > >> From your lips to God's ears.... I keep suggesting this along with a
> restyle to official style every time we create new repos. Seems unlikely
> unfortunately as it makes backports harder.
> > >>
> > >>> This is not right.
> > >>> + * {@code
> (o==null ? get(i)==null : o.equals(get(i)))}
> > >>
> > >> Corrected.
> > >>
> > >>> You accidentally deleted a stray space here?
> > >>>
> > >>> -        this.elementData = EMPTY_ELEMENTDATA;
> > >>> +       this.elementData = EMPTY_ELEMENTDATA;
> > >>
> > >> Corrected.
> > >>
> > >>> public ArrayList(int initialCapacity) {
> > >>> - super();
> > >>> if (initialCapacity < 0)
> > >>> throw new IllegalArgumentException("Illegal Capacity: "+
> > >>>                                                 initialCapacity);
> > >>> -        this.elementData = new Object[initialCapacity];
> > >>> +        this.elementData = (initialCapacity > 0)
> > >>> + ? new Object[initialCapacity]
> > >>> + : EMPTY_ELEMENTDATA;
> > >>> }
> > >>>
> > >>> When optimizing for special cases, we should try very hard minimize
> overhead in the common case. In the above, we now have two branches in the
> common case. Instead,
> > >>>
> > >>> if (initialCapacity > 0) this.elementData = new
> Object[initialCapacity];
> > >>> else if (initialCapacity == 0) this.elementData = EMPTY_ELEMENTDATA;
> > >>> else barf
> > >>
> > >> Corrected.
> > >>
> > >> Thanks as always for the feedback.
> > >>
> > >> Mike
> > >>
> > >>>
> > >>>
> > >>>
> > >>> On Fri, Feb 21, 2014 at 2:41 PM, Mike Duigou <mike.duigou at oracle.com>
> wrote:
> > >>> Hello all;
> > >>>
> > >>> This changeset consists of two small performance improvements for
> ArrayList. Both are related to the lazy initialization introduced in
> JDK-8011200.
> > >>>
> > >>> The first change is in the ArrayList(int capacity) constructor and
> forces lazy initialization if the requested capacity is zero. It's been
> observed that in cases where zero capacity is requested that it is very
> likely that the list never receives any elements. For these cases we
> permanently avoid the allocation of an element array.
> > >>>
> > >>> The second change, noticed by Gustav Åkesson, involves the
> ArrayList(Collection c) constructor. If c is an empty collection then there
> is no reason to inflate the backing array for the ArrayList.
> > >>>
> > >>> http://cr.openjdk.java.net/~mduigou/JDK-8035584/0/webrev/
> > >>>
> > >>> I also took the opportunity to the <tt></tt> -> {@code } conversion
> for the javadoc.
> > >>>
> > >>> Enjoy!
> > >>>
> > >>> Mike
> > >>>
> > >>
> > >>
> > >
> > >
> >
>