RE: RFR: 8035584 : (s) ArrayList(c) should avoid inflation if c is empty
Looks good to me. Jason From: mike.dui...@oracle.com Subject: RFR: 8035584 : (s) ArrayList(c) should avoid inflation if c is empty Date: Wed, 23 Apr 2014 15:33:48 -0700 To: core-libs-dev@openjdk.java.net Hello all; Revisiting this issue again at long last I have updated the proposed changeset based upon Jason Mehren's most recent feedback. http://cr.openjdk.java.net/~mduigou/JDK-8035584/4/webrev/ This version reverts the prior changes to toArray(). Mike
RE: RFR: 8035584: (s) ArrayList(c) should avoid inflation if c is empty - (toArray spec)
MIke, The inner T.V. lawyer in me has been trying and find some loophole that will allow returning the same empty array from toArray. The spec states ..no references to it are maintained by this collection. The Saul Goodman loophole is that this collection implies object member reference. Which means that returning an empty array held by static field would be legal under that interpretation. So that leaves the final hurdle which is that the spec states ...method must allocate a new array I don't see a way around that unless the spec is changed. I can appreciate the reluctance to change spec as you pointed out bellow. Jason JMThe modification for toArray violates the List contract because the returned array must be safe (must use 'new' and must not retain reference). I think you'll have JMto back out that change. Contract violation aside, the only case that I can see that might unsafe for an empty array would be acquiring the monitor of JMEMPTY_ELEMENTDATA array. When we patched the Collections$EmptyXXX classes we avoided returning a cached empty array for this reason. MDYou are of course correct. Yet another reminder to avoid unnecessary promises when creating specifications. sigh The Collection.toArray() javadoc could have MDbeen written to allow for a shared empty array but isn't and can't be changed to be allow for this. We did eliminate the requirement to return a new instance MDsome cases for String/CharSequence/StringBuilder/StringBuffer in https://bugs.openjdk.java.net/browse/JDK-7174936 and MDhttps://bugs.openjdk.java.net/browse/JDK-8028757 that were similar to this but those changes for the most part were to sync the javadoc to the longstanding MDactual behaviour.
Re: RFR: 8035584: (s) ArrayList(c) should avoid inflation if c is empty
On Mar 13 2014, at 08:56 , Jason Mehrens jason_mehr...@hotmail.com wrote:
Mike,
The constructor modification looks good. The only other alternative I can
think would be to use 'c.toArray(EMPTY_ELEMENTDATA)' to avoid creating an
extra array. I'm guessing that version would not perform as well as your
current version.
Good idea, but you're also correct that it didn't perform as well (for either
Arrays.ArrayList or ArrayList itself)
The modification for toArray violates the List contract because the returned
array must be safe (must use 'new' and must not retain reference). I think
you'll have to back out that change. Contract violation aside, the only case
that I can see that might unsafe for an empty array would be acquiring the
monitor of EMPTY_ELEMENTDATA array. When we patched the Collections$EmptyXXX
classes we avoided returning a cached empty array for this reason.
You are of course correct. Yet another reminder to avoid unnecessary promises
when creating specifications. sigh The Collection.toArray() javadoc could
have been written to allow for a shared empty array but isn't and can't be
changed to be allow for this. We did eliminate the requirement to return a
new instance some cases for String/CharSequence/StringBuilder/StringBuffer in
https://bugs.openjdk.java.net/browse/JDK-7174936 and
https://bugs.openjdk.java.net/browse/JDK-8028757 that were similar to this but
those changes for the most part were to sync the javadoc to the longstanding
actual behaviour.
Mike
Jason
Subject: Re: RFR: 8035584: (s) ArrayList(c) should avoid inflation if c is
empty
From: mike.dui...@oracle.com
Date: Wed, 12 Mar 2014 12:41:00 -0700
CC: marti...@google.com; core-libs-dev@openjdk.java.net
To: jason_mehr...@hotmail.com
Hi Jason,'
Using isEmpty() was intended to save the array creation but you make a valid
point regarding correctness. I have amended the webrev. This handling
suggests that it would useful for implementation to cache the empty result
for toArray() and I have also added this to ArrayList's toArray.
http://cr.openjdk.java.net/~mduigou/JDK-8035584/3/webrev/
Mike
On Mar 12 2014, at 07:06 , Jason Mehrens jason_mehr...@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.dui...@oracle.com
Date: Tue, 11 Mar 2014 18:18:26 -0700
To: marti...@google.com
CC: core-libs-dev@openjdk.java.net
On Mar 11 2014, at 17:42 , Martin Buchholz marti...@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 nbsp; changes that need to be reverted.
Else looks good.
- * More formally, returns the lowest index tti/tt such that
- *
tt(o==nullnbsp;?nbsp;get(i)==nullnbsp;:nbsp;o.equals(get(i)))/tt,
+ * More formally, returns the lowest index {@code i} such that
+ * {@code
(o==nullnbsp;?nbsp;get(i)==nullnbsp;:nbsp;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.dui...@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 marti...@google.com wrote:
I don't see the updated webrev. Maybe you also
Re: RFR: 8035584: (s) ArrayList(c) should avoid inflation if c is empty
On Mar 13 2014, at 09:53 , Martin Buchholz marti...@google.com wrote:
It's time to add general purpose public static final empty arrays to
Arrays.java for Object, all the primitive types, and perhaps also String,
instead of local copies scattered around the JDK; then have ArrayList use
Arrays.EMPTY_OBJECT_ARRAY.
In general I agree though Jason has me all paranoid now about people
synchronizing on these shared instances.
Mike
On Thu, Mar 13, 2014 at 8:56 AM, Jason Mehrens jason_mehr...@hotmail.com
wrote:
Mike,
The constructor modification looks good. The only other alternative I can
think would be to use 'c.toArray(EMPTY_ELEMENTDATA)' to avoid creating an
extra array. I'm guessing that version would not perform as well as your
current version.
The modification for toArray violates the List contract because the returned
array must be safe (must use 'new' and must not retain reference). I think
you'll have to back out that change. Contract violation aside, the only case
that I can see that might unsafe for an empty array would be acquiring the
monitor of EMPTY_ELEMENTDATA array. When we patched the Collections$EmptyXXX
classes we avoided returning a cached empty array for this reason.
Jason
Subject: Re: RFR: 8035584: (s) ArrayList(c) should avoid inflation if c is
empty
From: mike.dui...@oracle.com
Date: Wed, 12 Mar 2014 12:41:00 -0700
CC: marti...@google.com; core-libs-dev@openjdk.java.net
To: jason_mehr...@hotmail.com
Hi Jason,'
Using isEmpty() was intended to save the array creation but you make a valid
point regarding correctness. I have amended the webrev. This handling
suggests that it would useful for implementation to cache the empty result
for toArray() and I have also added this to ArrayList's toArray.
http://cr.openjdk.java.net/~mduigou/JDK-8035584/3/webrev/
Mike
On Mar 12 2014, at 07:06 , Jason Mehrens jason_mehr...@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.dui...@oracle.com
Date: Tue, 11 Mar 2014 18:18:26 -0700
To: marti...@google.com
CC: core-libs-dev@openjdk.java.net
On Mar 11 2014, at 17:42 , Martin Buchholz marti...@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 nbsp; changes that need to be reverted.
Else looks good.
- * More formally, returns the lowest index tti/tt such that
- *
tt(o==nullnbsp;?nbsp;get(i)==nullnbsp;:nbsp;o.equals(get(i)))/tt,
+ * More formally, returns the lowest index {@code i} such that
+ * {@code
(o==nullnbsp;?nbsp;get(i)==nullnbsp;:nbsp;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.dui...@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 marti...@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.dui...@oracle.com
wrote:
On Feb 21 2014, at 14:56 , Martin Buchholz marti...@google.com wrote:
You should do tt - code conversion separately, and do
RFR: 8035584 : (s) ArrayList(c) should avoid inflation if c is empty
Hello all; Revisiting this issue again at long last I have updated the proposed changeset based upon Jason Mehren's most recent feedback. http://cr.openjdk.java.net/~mduigou/JDK-8035584/4/webrev/ This version reverts the prior changes to toArray(). Mike
RE: RFR: 8035584: (s) ArrayList(c) should avoid inflation if c is empty
Mike,
The constructor modification looks good. The only other alternative I can
think would be to use 'c.toArray(EMPTY_ELEMENTDATA)' to avoid creating an extra
array. I'm guessing that version would not perform as well as your current
version.
The modification for toArray violates the List contract because the returned
array must be safe (must use 'new' and must not retain reference). I think
you'll have to back out that change. Contract violation aside, the only case
that I can see that might unsafe for an empty array would be acquiring the
monitor of EMPTY_ELEMENTDATA array. When we patched the Collections$EmptyXXX
classes we avoided returning a cached empty array for this reason.
Jason
Subject: Re: RFR: 8035584: (s) ArrayList(c) should avoid inflation if c is empty
From: mike.dui...@oracle.com
Date: Wed, 12 Mar 2014 12:41:00 -0700
CC: marti...@google.com; core-libs-dev@openjdk.java.net
To: jason_mehr...@hotmail.com
Hi Jason,'
Using isEmpty() was intended to save the array creation but you make a valid
point regarding correctness. I have amended the webrev. This handling suggests
that it would useful for implementation to cache the empty result for toArray()
and I have also added this to ArrayList's toArray.
http://cr.openjdk.java.net/~mduigou/JDK-8035584/3/webrev/
Mike
On Mar 12 2014, at 07:06 , Jason Mehrens jason_mehr...@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.dui...@oracle.com
Date: Tue, 11 Mar 2014 18:18:26 -0700
To: marti...@google.com
CC: core-libs-dev@openjdk.java.net
On Mar 11 2014, at 17:42 , Martin Buchholz marti...@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 nbsp; changes that need to be reverted.
Else looks good.
- * More formally, returns the lowest index tti/tt such that
- *
tt(o==nullnbsp;?nbsp;get(i)==nullnbsp;:nbsp;o.equals(get(i)))/tt,
+ * More formally, returns the lowest index {@code i} such that
+ * {@code
(o==nullnbsp;?nbsp;get(i)==nullnbsp;:nbsp;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.dui...@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 marti...@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.dui...@oracle.com
wrote:
On Feb 21 2014, at 14:56 , Martin Buchholz marti...@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==nullnbsp;?nbsp;get(i)==nullnbsp;:nbsp;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
Re: RFR: 8035584: (s) ArrayList(c) should avoid inflation if c is empty
You could definitely safely do a check to see if elementData ==
EMPTY_ELEMENTDATA (irrespective of size), and if so, return
EMPTY_ELEMENTDATA instead of copying.
I don't think however that that method, as is, is actually unsafe. I
can't think of a code path where, say, a sudden concurrent change in
size would cause a problem that wouldn't already be a problem with the
original method. If size was 0 when the assignment and check took
place, and suddenly grew, returning an empty array is OK at this point.
If size was 0 and then suddenly shrunk or went to 0, the copy would
copy extra elements - but that would already be the case with the
original implementation.
On 03/13/2014 10:56 AM, Jason Mehrens wrote:
Mike,
The constructor modification looks good. The only other alternative I can
think would be to use 'c.toArray(EMPTY_ELEMENTDATA)' to avoid creating an extra
array. I'm guessing that version would not perform as well as your current
version.
The modification for toArray violates the List contract because the returned
array must be safe (must use 'new' and must not retain reference). I think
you'll have to back out that change. Contract violation aside, the only case
that I can see that might unsafe for an empty array would be acquiring the
monitor of EMPTY_ELEMENTDATA array. When we patched the Collections$EmptyXXX
classes we avoided returning a cached empty array for this reason.
Jason
Subject: Re: RFR: 8035584: (s) ArrayList(c) should avoid inflation if c is empty
From: mike.dui...@oracle.com
Date: Wed, 12 Mar 2014 12:41:00 -0700
CC: marti...@google.com; core-libs-dev@openjdk.java.net
To: jason_mehr...@hotmail.com
Hi Jason,'
Using isEmpty() was intended to save the array creation but you make a valid
point regarding correctness. I have amended the webrev. This handling suggests
that it would useful for implementation to cache the empty result for toArray()
and I have also added this to ArrayList's toArray.
http://cr.openjdk.java.net/~mduigou/JDK-8035584/3/webrev/
Mike
On Mar 12 2014, at 07:06 , Jason Mehrens jason_mehr...@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.dui...@oracle.com
Date: Tue, 11 Mar 2014 18:18:26 -0700
To: marti...@google.com
CC: core-libs-dev@openjdk.java.net
On Mar 11 2014, at 17:42 , Martin Buchholz marti...@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 nbsp; changes that need to be reverted.
Else looks good.
- * More formally, returns the lowest index tti/tt such that
- *
tt(o==nullnbsp;?nbsp;get(i)==nullnbsp;:nbsp;o.equals(get(i)))/tt,
+ * More formally, returns the lowest index {@code i} such that
+ * {@code (o==nullnbsp;?nbsp;get(i)==nullnbsp;:nbsp;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.dui...@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 marti...@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.dui...@oracle.com wrote:
On Feb 21 2014, at 14:56 , Martin Buchholz marti...@google.com wrote:
You should do tt - code conversion separately, and do it pervasively across
the entire
RE: RFR: 8035584: (s) ArrayList(c) should avoid inflation if c is empty
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.dui...@oracle.com
Date: Tue, 11 Mar 2014 18:18:26 -0700
To: marti...@google.com
CC: core-libs-dev@openjdk.java.net
On Mar 11 2014, at 17:42 , Martin Buchholz marti...@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 nbsp; changes that need to be reverted.
Else looks good.
- * More formally, returns the lowest index tti/tt such that
- *
tt(o==nullnbsp;?nbsp;get(i)==nullnbsp;:nbsp;o.equals(get(i)))/tt,
+ * More formally, returns the lowest index {@code i} such that
+ * {@code
(o==nullnbsp;?nbsp;get(i)==nullnbsp;:nbsp;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.dui...@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 marti...@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.dui...@oracle.com
wrote:
On Feb 21 2014, at 14:56 , Martin Buchholz marti...@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==nullnbsp;?nbsp;get(i)==nullnbsp;:nbsp;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.dui...@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
Re: RFR: 8035584: (s) ArrayList(c) should avoid inflation if c is empty
Hi Jason,'
Using isEmpty() was intended to save the array creation but you make a valid
point regarding correctness. I have amended the webrev. This handling suggests
that it would useful for implementation to cache the empty result for toArray()
and I have also added this to ArrayList's toArray.
http://cr.openjdk.java.net/~mduigou/JDK-8035584/3/webrev/
Mike
On Mar 12 2014, at 07:06 , Jason Mehrens jason_mehr...@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.dui...@oracle.com
Date: Tue, 11 Mar 2014 18:18:26 -0700
To: marti...@google.com
CC: core-libs-dev@openjdk.java.net
On Mar 11 2014, at 17:42 , Martin Buchholz marti...@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 nbsp; changes that need to be reverted.
Else looks good.
- * More formally, returns the lowest index tti/tt such that
- *
tt(o==nullnbsp;?nbsp;get(i)==nullnbsp;:nbsp;o.equals(get(i)))/tt,
+ * More formally, returns the lowest index {@code i} such that
+ * {@code
(o==nullnbsp;?nbsp;get(i)==nullnbsp;:nbsp;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.dui...@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 marti...@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.dui...@oracle.com
wrote:
On Feb 21 2014, at 14:56 , Martin Buchholz marti...@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==nullnbsp;?nbsp;get(i)==nullnbsp;:nbsp;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.dui...@oracle.com
wrote:
Hello all;
This changeset consists of two small performance improvements
Re: RFR: 8035584: (s) ArrayList(c) should avoid inflation if c is empty
On Mar 11 2014, at 17:42 , Martin Buchholz marti...@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 nbsp; changes that need to be reverted.
Else looks good.
- * More formally, returns the lowest index tti/tt such that
- *
tt(o==nullnbsp;?nbsp;get(i)==nullnbsp;:nbsp;o.equals(get(i)))/tt,
+ * More formally, returns the lowest index {@code i} such that
+ * {@code
(o==nullnbsp;?nbsp;get(i)==nullnbsp;:nbsp;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.dui...@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 marti...@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.dui...@oracle.com wrote:
On Feb 21 2014, at 14:56 , Martin Buchholz marti...@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==nullnbsp;?nbsp;get(i)==nullnbsp;:nbsp;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.dui...@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
Re: RFR: 8035584: (s) ArrayList(c) should avoid inflation if c is empty
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 marti...@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.dui...@oracle.com wrote:
On Feb 21 2014, at 14:56 , Martin Buchholz marti...@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==nullnbsp;?nbsp;get(i)==nullnbsp;:nbsp;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.dui...@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
Re: RFR: 8035584: (s) ArrayList(c) should avoid inflation if c is empty
On Feb 21 2014, at 14:56 , Martin Buchholz marti...@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==nullnbsp;?nbsp;get(i)==nullnbsp;:nbsp;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.dui...@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
RFR: 8035584: (s) ArrayList(c) should avoid inflation if c is empty
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
