RFR JDK-7143928 : (coll) Optimize for Empty ArrayList and HashMap
Hello all; This is a review for optimization work that came out of internal analysis of Oracle's Java applications. It's 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. This patch is not a substitute for pre-sizing your collections and maps--doing so will *always* have better results. This patch extends HashMap and ArrayList to provide special handling for newly created instances that avoids creating the backing array until needed. There is a very small additional cost for detecting when to inflate the map or list that is measurable in interpreted tests but disappears in JITed code. http://cr.openjdk.java.net/~mduigou/JDK-7143928/0/webrev/ We expect that should this code prove successful in Java 8 it will be backported to Java 7 updates. The unit test may appear to be somewhat unrelated. It was created after resolving a bug in an early version of this patch to detect the issue encountered (LinkedHashMap.init() was not being called in readObject() when the map was empty). Mike
This adds an extra field to every ArrayList - a tax paid by every carefully constructed ArrayList so that sloppy instances can get away with their sloppiness, which is pretty distasteful. If I was going to "spend" an extra field of ArrayList, it would be to implement a circular array like ArrayDeque and have O(1) deletion of element 0. An alternative is to make elementData null when there are no elements. We can then reuse the size field for initialCapacity. Yes, it's true that you then have to introduce more null checks into the code, but hotspot will likely do that anyways in the jitted code, and elide them if you provide them, so cost of the null checks may be zero or even negative! Much more difficult would be the alternative of automatically snipping the tail (as with trimToSize) of any inactive ArrayList occasionally, e.g. after a gc cycle.
What percentage of the empty lists are default-sized? I suspect it is large, in which case we could apply this trick only for the default-sized lists, and eliminate the extra field. On Mar 26, 2013, at 5:25 PM, Mike Duigou wrote:
Hello all;
This is a review for optimization work that came out of internal analysis of Oracle's Java applications. It's 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. This patch is not a substitute for pre-sizing your collections and maps--doing so will *always* have better results.
This patch extends HashMap and ArrayList to provide special handling for newly created instances that avoids creating the backing array until needed. There is a very small additional cost for detecting when to inflate the map or list that is measurable in interpreted tests but disappears in JITed code.
http://cr.openjdk.java.net/~mduigou/JDK-7143928/0/webrev/
We expect that should this code prove successful in Java 8 it will be backported to Java 7 updates.
The unit test may appear to be somewhat unrelated. It was created after resolving a bug in an early version of this patch to detect the issue encountered (LinkedHashMap.init() was not being called in readObject() when the map was empty).
Mike
On 03/27/2013 06:53 AM, Brian Goetz wrote:
What percentage of the empty lists are default-sized? I suspect it is large, in which case we could apply this trick only for the default-sized lists, and eliminate the extra field.
yes, very good idea indeed. Rémi
On Mar 26, 2013, at 5:25 PM, Mike Duigou wrote:
Hello all;
This is a review for optimization work that came out of internal analysis of Oracle's Java applications. It's 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. This patch is not a substitute for pre-sizing your collections and maps--doing so will *always* have better results.
This patch extends HashMap and ArrayList to provide special handling for newly created instances that avoids creating the backing array until needed. There is a very small additional cost for detecting when to inflate the map or list that is measurable in interpreted tests but disappears in JITed code.
http://cr.openjdk.java.net/~mduigou/JDK-7143928/0/webrev/
We expect that should this code prove successful in Java 8 it will be backported to Java 7 updates.
The unit test may appear to be somewhat unrelated. It was created after resolving a bug in an early version of this patch to detect the issue encountered (LinkedHashMap.init() was not being called in readObject() when the map was empty).
Mike
This seems like a good idea. I will follow up with the performance people to see if their findings include the requested initial size. Mike On Mar 26 2013, at 22:53 , Brian Goetz wrote:
What percentage of the empty lists are default-sized? I suspect it is large, in which case we could apply this trick only for the default-sized lists, and eliminate the extra field.
On Mar 26, 2013, at 5:25 PM, Mike Duigou wrote:
Hello all;
This is a review for optimization work that came out of internal analysis of Oracle's Java applications. It's 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. This patch is not a substitute for pre-sizing your collections and maps--doing so will *always* have better results.
This patch extends HashMap and ArrayList to provide special handling for newly created instances that avoids creating the backing array until needed. There is a very small additional cost for detecting when to inflate the map or list that is measurable in interpreted tests but disappears in JITed code.
http://cr.openjdk.java.net/~mduigou/JDK-7143928/0/webrev/
We expect that should this code prove successful in Java 8 it will be backported to Java 7 updates.
The unit test may appear to be somewhat unrelated. It was created after resolving a bug in an early version of this patch to detect the issue encountered (LinkedHashMap.init() was not being called in readObject() when the map was empty).
Mike
But you can support any requested initial size if stored in the size field when list is empty. On Wed, Mar 27, 2013 at 8:02 AM, Mike Duigou <mike.duigou@oracle.com> wrote:
This seems like a good idea. I will follow up with the performance people to see if their findings include the requested initial size.
Mike
On Mar 26 2013, at 22:53 , Brian Goetz wrote:
What percentage of the empty lists are default-sized? I suspect it is large, in which case we could apply this trick only for the default-sized lists, and eliminate the extra field.
On Mar 26, 2013, at 5:25 PM, Mike Duigou wrote:
Hello all;
This is a review for optimization work that came out of internal analysis of Oracle's Java applications. It's 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. This patch is not a substitute for pre-sizing your collections and maps--doing so will *always* have better results.
This patch extends HashMap and ArrayList to provide special handling for newly created instances that avoids creating the backing array until needed. There is a very small additional cost for detecting when to inflate the map or list that is measurable in interpreted tests but disappears in JITed code.
http://cr.openjdk.java.net/~mduigou/JDK-7143928/0/webrev/
We expect that should this code prove successful in Java 8 it will be backported to Java 7 updates.
The unit test may appear to be somewhat unrelated. It was created after resolving a bug in an early version of this patch to detect the issue encountered (LinkedHashMap.init() was not being called in readObject() when the map was empty).
Mike
I started looking at crafty reuse of size but found too many direct references to size to attempt getting this right in the current iteration. Reusing size is definitely still available to someone who wants to dive in and prepare an implementation. Mike On Mar 27 2013, at 09:17 , Martin Buchholz wrote:
But you can support any requested initial size if stored in the size field when list is empty.
On Wed, Mar 27, 2013 at 8:02 AM, Mike Duigou <mike.duigou@oracle.com> wrote: This seems like a good idea. I will follow up with the performance people to see if their findings include the requested initial size.
Mike
On Mar 26 2013, at 22:53 , Brian Goetz wrote:
What percentage of the empty lists are default-sized? I suspect it is large, in which case we could apply this trick only for the default-sized lists, and eliminate the extra field.
On Mar 26, 2013, at 5:25 PM, Mike Duigou wrote:
Hello all;
This is a review for optimization work that came out of internal analysis of Oracle's Java applications. It's 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. This patch is not a substitute for pre-sizing your collections and maps--doing so will *always* have better results.
This patch extends HashMap and ArrayList to provide special handling for newly created instances that avoids creating the backing array until needed. There is a very small additional cost for detecting when to inflate the map or list that is measurable in interpreted tests but disappears in JITed code.
http://cr.openjdk.java.net/~mduigou/JDK-7143928/0/webrev/
We expect that should this code prove successful in Java 8 it will be backported to Java 7 updates.
The unit test may appear to be somewhat unrelated. It was created after resolving a bug in an early version of this patch to detect the issue encountered (LinkedHashMap.init() was not being called in readObject() when the map was empty).
Mike
Hi Mike, Have you considered the possibility to re-constitute the initial capacity from threshold and loadFactor? Regards, Peter On 03/27/2013 05:28 PM, Mike Duigou wrote:
I started looking at crafty reuse of size but found too many direct references to size to attempt getting this right in the current iteration. Reusing size is definitely still available to someone who wants to dive in and prepare an implementation.
Mike
On Mar 27 2013, at 09:17 , Martin Buchholz wrote:
But you can support any requested initial size if stored in the size field when list is empty.
On Wed, Mar 27, 2013 at 8:02 AM, Mike Duigou <mike.duigou@oracle.com> wrote: This seems like a good idea. I will follow up with the performance people to see if their findings include the requested initial size.
Mike
On Mar 26 2013, at 22:53 , Brian Goetz wrote:
What percentage of the empty lists are default-sized? I suspect it is large, in which case we could apply this trick only for the default-sized lists, and eliminate the extra field.
On Mar 26, 2013, at 5:25 PM, Mike Duigou wrote:
Hello all;
This is a review for optimization work that came out of internal analysis of Oracle's Java applications. It's 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. This patch is not a substitute for pre-sizing your collections and maps--doing so will *always* have better results.
This patch extends HashMap and ArrayList to provide special handling for newly created instances that avoids creating the backing array until needed. There is a very small additional cost for detecting when to inflate the map or list that is measurable in interpreted tests but disappears in JITed code.
http://cr.openjdk.java.net/~mduigou/JDK-7143928/0/webrev/
We expect that should this code prove successful in Java 8 it will be backported to Java 7 updates.
The unit test may appear to be somewhat unrelated. It was created after resolving a bug in an early version of this patch to detect the issue encountered (LinkedHashMap.init() was not being called in readObject() when the map was empty).
Mike
On 03/27/13 12:17, Martin Buchholz wrote:
But you can support any requested initial size if stored in the size field when list is empty.
In other words: Mike, please do not add a field if your goal is to save space! Also, I hope you or the performance testing folks have extensive and accurate enough tests to show that the change not only helps the empty case but does not hurt the vastly more common non-empty case. Considering that this is the most commonly used java.util class, there should be empirical evidence that this is a net improvement. My guess is that it can be done (we did something similar for ConcurrentHashMap) but it takes a lot of care. -Doug
On Wed, Mar 27, 2013 at 8:02 AM, Mike Duigou <mike.duigou@oracle.com> wrote:
This seems like a good idea. I will follow up with the performance people to see if their findings include the requested initial size.
Mike
On Mar 26 2013, at 22:53 , Brian Goetz wrote:
What percentage of the empty lists are default-sized? I suspect it is large, in which case we could apply this trick only for the default-sized lists, and eliminate the extra field.
On Mar 26, 2013, at 5:25 PM, Mike Duigou wrote:
Hello all;
This is a review for optimization work that came out of internal analysis of Oracle's Java applications. It's 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. This patch is not a substitute for pre-sizing your collections and maps--doing so will *always* have better results.
This patch extends HashMap and ArrayList to provide special handling for newly created instances that avoids creating the backing array until needed. There is a very small additional cost for detecting when to inflate the map or list that is measurable in interpreted tests but disappears in JITed code.
http://cr.openjdk.java.net/~mduigou/JDK-7143928/0/webrev/
We expect that should this code prove successful in Java 8 it will be backported to Java 7 updates.
The unit test may appear to be somewhat unrelated. It was created after resolving a bug in an early version of this patch to detect the issue encountered (LinkedHashMap.init() was not being called in readObject() when the map was empty).
Mike
We have heard back from the performance folks that 85% of empty lists are created at default size. The proposed patch is going to be revised to do the inflation trick only for default sized maps which will eliminate the need for a new field. Something creative involving the use of the existing size field can certainly be considered for a future optimization. On Mar 28 2013, at 04:59 , Doug Lea wrote:
On 03/27/13 12:17, Martin Buchholz wrote:
But you can support any requested initial size if stored in the size field when list is empty.
In other words: Mike, please do not add a field if your goal is to save space!
Part of the analysis was that with current object layouts the added fields did not change the memory footprint of either class. This, of course only applies to current versions of Hotspot and it's object layout.
Also, I hope you or the performance testing folks have extensive and accurate enough tests to show that the change not only helps the empty case but does not hurt the vastly more common non-empty case.
They do. I believe that the object layout hides any increase in size.
Considering that this is the most commonly used java.util class, there should be empirical evidence that this is a net improvement.
I will try to find how much of the analysis I can share.
My guess is that it can be done (we did something similar for ConcurrentHashMap) but it takes a lot of care.
-Doug
On Wed, Mar 27, 2013 at 8:02 AM, Mike Duigou <mike.duigou@oracle.com> wrote:
This seems like a good idea. I will follow up with the performance people to see if their findings include the requested initial size.
Mike
On Mar 26 2013, at 22:53 , Brian Goetz wrote:
What percentage of the empty lists are default-sized? I suspect it is large, in which case we could apply this trick only for the default-sized lists, and eliminate the extra field.
On Mar 26, 2013, at 5:25 PM, Mike Duigou wrote:
Hello all;
This is a review for optimization work that came out of internal analysis of Oracle's Java applications. It's 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. This patch is not a substitute for pre-sizing your collections and maps--doing so will *always* have better results.
This patch extends HashMap and ArrayList to provide special handling for newly created instances that avoids creating the backing array until needed. There is a very small additional cost for detecting when to inflate the map or list that is measurable in interpreted tests but disappears in JITed code.
http://cr.openjdk.java.net/~mduigou/JDK-7143928/0/webrev/
We expect that should this code prove successful in Java 8 it will be backported to Java 7 updates.
The unit test may appear to be somewhat unrelated. It was created after resolving a bug in an early version of this patch to detect the issue encountered (LinkedHashMap.init() was not being called in readObject() when the map was empty).
Mike
On 03/28/2013 06:38 PM, Mike Duigou wrote:
We have heard back from the performance folks that 85% of empty lists are created at default size. The proposed patch is going to be revised to do the inflation trick only for default sized maps which will eliminate the need for a new field. Something creative involving the use of the existing size field can certainly be considered for a future optimization.
This is actually a better approach, since it leaves a gate to non-lazy allocation. As with all lazy things, delaying failure can have undesirable effects. Catching OOME at HashMap construction vs. 1st put... Regards, Peter
On Mar 28 2013, at 04:59 , Doug Lea wrote:
On 03/27/13 12:17, Martin Buchholz wrote:
But you can support any requested initial size if stored in the size field when list is empty. In other words: Mike, please do not add a field if your goal is to save space! Part of the analysis was that with current object layouts the added fields did not change the memory footprint of either class. This, of course only applies to current versions of Hotspot and it's object layout.
Also, I hope you or the performance testing folks have extensive and accurate enough tests to show that the change not only helps the empty case but does not hurt the vastly more common non-empty case. They do. I believe that the object layout hides any increase in size.
Considering that this is the most commonly used java.util class, there should be empirical evidence that this is a net improvement. I will try to find how much of the analysis I can share.
My guess is that it can be done (we did something similar for ConcurrentHashMap) but it takes a lot of care.
-Doug
On Wed, Mar 27, 2013 at 8:02 AM, Mike Duigou <mike.duigou@oracle.com> wrote:
This seems like a good idea. I will follow up with the performance people to see if their findings include the requested initial size.
Mike
On Mar 26 2013, at 22:53 , Brian Goetz wrote:
What percentage of the empty lists are default-sized? I suspect it is large, in which case we could apply this trick only for the default-sized lists, and eliminate the extra field. On Mar 26, 2013, at 5:25 PM, Mike Duigou wrote:
Hello all;
This is a review for optimization work that came out of internal analysis of Oracle's Java applications. It's 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. This patch is not a substitute for pre-sizing your collections and maps--doing so will *always* have better results. This patch extends HashMap and ArrayList to provide special handling for newly created instances that avoids creating the backing array until needed. There is a very small additional cost for detecting when to inflate the map or list that is measurable in interpreted tests but disappears in JITed code. http://cr.openjdk.java.net/~mduigou/JDK-7143928/0/webrev/
We expect that should this code prove successful in Java 8 it will be backported to Java 7 updates. The unit test may appear to be somewhat unrelated. It was created after resolving a bug in an early version of this patch to detect the issue encountered (LinkedHashMap.init() was not being called in readObject() when the map was empty). Mike
Hello all; I have posted an updated version of the empty ArrayList and HashMap patch. http://cr.openjdk.java.net/~mduigou/JDK-7143928/1/webrev/ This revised implementation introduces *no new fields* to either class. For ArrayList the lazy allocation of the backing array occurs only if the list is created at default size. According to our performance analysis team, approximately 85% of ArrayList instances are created at default size so this optimization will be valid for an overwhelming majority of cases. For HashMap, creative use is made of the threshold field to track the requested initial size until the bucket array is needed. On the read side the empty map case is tested with isEmpty(). On the write size a comparison of (table == EMPTY_TABLE) is used to detect the need to inflate the bucket array. In readObject there's a little more work to try to choose an efficient initial capacity. Mike On Mar 26 2013, at 17:25 , Mike Duigou wrote:
Hello all;
This is a review for optimization work that came out of internal analysis of Oracle's Java applications. It's 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. This patch is not a substitute for pre-sizing your collections and maps--doing so will *always* have better results.
This patch extends HashMap and ArrayList to provide special handling for newly created instances that avoids creating the backing array until needed. There is a very small additional cost for detecting when to inflate the map or list that is measurable in interpreted tests but disappears in JITed code.
http://cr.openjdk.java.net/~mduigou/JDK-7143928/0/webrev/
We expect that should this code prove successful in Java 8 it will be backported to Java 7 updates.
The unit test may appear to be somewhat unrelated. It was created after resolving a bug in an early version of this patch to detect the issue encountered (LinkedHashMap.init() was not being called in readObject() when the map was empty).
Mike
Hello all; Last night while pushing another changeset I accidentally pushed a changeset for JKD-7143928. Since the review and testing was not complete on this issue I have backed out that changeset and created a new bug number to continue development. The new webrev to complete the review is: http://cr.openjdk.java.net/~mduigou/JDK-8011200/0/webrev/ It is currently unchanged from the last posted changeset for 7143928. Mike On Apr 1 2013, at 19:00 , Mike Duigou wrote:
Hello all;
I have posted an updated version of the empty ArrayList and HashMap patch.
http://cr.openjdk.java.net/~mduigou/JDK-7143928/1/webrev/
This revised implementation introduces *no new fields* to either class. For ArrayList the lazy allocation of the backing array occurs only if the list is created at default size. According to our performance analysis team, approximately 85% of ArrayList instances are created at default size so this optimization will be valid for an overwhelming majority of cases.
For HashMap, creative use is made of the threshold field to track the requested initial size until the bucket array is needed. On the read side the empty map case is tested with isEmpty(). On the write size a comparison of (table == EMPTY_TABLE) is used to detect the need to inflate the bucket array. In readObject there's a little more work to try to choose an efficient initial capacity.
Mike
On Mar 26 2013, at 17:25 , Mike Duigou wrote:
Hello all;
This is a review for optimization work that came out of internal analysis of Oracle's Java applications. It's 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. This patch is not a substitute for pre-sizing your collections and maps--doing so will *always* have better results.
This patch extends HashMap and ArrayList to provide special handling for newly created instances that avoids creating the backing array until needed. There is a very small additional cost for detecting when to inflate the map or list that is measurable in interpreted tests but disappears in JITed code.
http://cr.openjdk.java.net/~mduigou/JDK-7143928/0/webrev/
We expect that should this code prove successful in Java 8 it will be backported to Java 7 updates.
The unit test may appear to be somewhat unrelated. It was created after resolving a bug in an early version of this patch to detect the issue encountered (LinkedHashMap.init() was not being called in readObject() when the map was empty).
Mike
On 02/04/2013 05:44, Mike Duigou wrote:
Hello all;
Last night while pushing another changeset I accidentally pushed a changeset for JKD-7143928. Since the review and testing was not complete on this issue I have backed out that changeset and created a new bug number to continue development. The new webrev to complete the review is:
http://cr.openjdk.java.net/~mduigou/JDK-8011200/0/webrev/
It is currently unchanged from the last posted changeset for 7143928.
Mike
I skimmed through the webrev as lazily creating the backing arrays will be help in some environments. For ArrayList then it might be good to add a constant DEFAULT_INITIAL_CAPACITY or some such to avoid repeating the specified default. I agree with Martin's comment that ArrayList.clear will now clear elementData.length elements rather than size so I assume you'll address that. I also agree with Martin on keeping the coding style consistent, particularly the missing space in "if(", and missing braces in places such as HashMap.writeObject. For ArrayList.readObject then you read the array length in as "initialCapacity" which I think is a bit confusing given the current semantics. An alternative is to just not change readObject unless there is evidence that it is common to reconstitute empty ArrayLists. For HashMap.indexFor then I assume this isn't an assert because it is used early in the VM startup. This should probably be changed to InternalError and the message needs to be changed too. Do you envisage usage of inflateTable in LinkedHashMap? I'm wondering why it isn't private. HashMap.writeObject - the update to the @serialData text will change the wording emitting in the javadoc. I mention this as I think you are planning to push this to jdk7u at some point. I don't have time to go through the test in detail at this time but it looks like it has the original bug number and I assume that will need to change now. -Alan.
2013/4/1 21:07 -0700, alan.bateman@oracle.com:
...
I also agree with Martin on keeping the coding style consistent, particularly the missing space in "if(", and missing braces in places such as HashMap.writeObject.
On the topic of style, please also change private static final Object EMPTY_ELEMENTDATA[] = new Object[0]; to private static final Object[] EMPTY_ELEMENTDATA = new Object[0]; in HashMap.java. - Mark
On Apr 2 2013, at 04:07 , Alan Bateman wrote:
On 02/04/2013 05:44, Mike Duigou wrote:
Hello all;
Last night while pushing another changeset I accidentally pushed a changeset for JKD-7143928. Since the review and testing was not complete on this issue I have backed out that changeset and created a new bug number to continue development. The new webrev to complete the review is:
http://cr.openjdk.java.net/~mduigou/JDK-8011200/0/webrev/
It is currently unchanged from the last posted changeset for 7143928.
Mike
I skimmed through the webrev as lazily creating the backing arrays will be help in some environments.
For ArrayList.readObject then you read the array length in as "initialCapacity" which I think is a bit confusing given the current semantics. An alternative is to just not change readObject unless there is evidence that it is common to reconstitute empty ArrayLists.
I've gone with making ArrayList.writeObject/readObject behave like clone(). They remain forward and backwards compatible with existing impls.
For HashMap.indexFor then I assume this isn't an assert because it is used early in the VM startup.
Correct.
This should probably be changed to InternalError and the message needs to be changed too.
It will be removed. :-) I had put this in for my testing.
Do you envisage usage of inflateTable in LinkedHashMap? I'm wondering why it isn't private.
I wasn't sure when I wrote it. I will make it private.
HashMap.writeObject - the update to the @serialData text will change the wording emitting in the javadoc.
The "must be a power of 2" is actually an existing but previously undocumented requirement. I will file a CCC case for this.
I mention this as I think you are planning to push this to jdk7u at some point.
Even though it's been a requirement for the life of this class I won't attempt to push this change to jdk7u.
I don't have time to go through the test in detail at this time but it looks like it has the original bug number and I assume that will need to change now.
Correct. It will be changed. Transitioning it now. Mike
Hello again; I have updated the patch with the received review feedback. The revised webrev is here: http://cr.openjdk.java.net/~mduigou/JDK-8011200/1/webrev/ The important changes in this revision: - The behaviour of the readObject/writeObject serialization for both classes now more closely mirrors the behaviour of clone(). For ArrayList this means that the deserialized list has a capacity the same as the size. ie. as if trimToSize() was called. For HashMap, the opposite is true, the capacity is the same as was in effect when the object was serialized. (HashMap also tries to protect itself from nonsensical/harmful input). The implementation changes to serialization preserve forward and backward compatibility--all serialized objects are compatible with all implementations. I will file a spec change request for the addition of ", a power of 2" to the @serialData tag for this existing but previously unstated requirement. - Use of Arrays.fill has been reverted. I did change one fill case so that the loop can be optimized. (size field was being updated with each iteration). I very slightly expanded the docs. This is starting to look like a nice set of changes. Mike On Apr 1 2013, at 21:44 , Mike Duigou wrote:
Hello all;
Last night while pushing another changeset I accidentally pushed a changeset for JKD-7143928. Since the review and testing was not complete on this issue I have backed out that changeset and created a new bug number to continue development. The new webrev to complete the review is:
http://cr.openjdk.java.net/~mduigou/JDK-8011200/0/webrev/
It is currently unchanged from the last posted changeset for 7143928.
Mike
On Apr 1 2013, at 19:00 , Mike Duigou wrote:
Hello all;
I have posted an updated version of the empty ArrayList and HashMap patch.
http://cr.openjdk.java.net/~mduigou/JDK-7143928/1/webrev/
This revised implementation introduces *no new fields* to either class. For ArrayList the lazy allocation of the backing array occurs only if the list is created at default size. According to our performance analysis team, approximately 85% of ArrayList instances are created at default size so this optimization will be valid for an overwhelming majority of cases.
For HashMap, creative use is made of the threshold field to track the requested initial size until the bucket array is needed. On the read side the empty map case is tested with isEmpty(). On the write size a comparison of (table == EMPTY_TABLE) is used to detect the need to inflate the bucket array. In readObject there's a little more work to try to choose an efficient initial capacity.
Mike
On Mar 26 2013, at 17:25 , Mike Duigou wrote:
Hello all;
This is a review for optimization work that came out of internal analysis of Oracle's Java applications. It's 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. This patch is not a substitute for pre-sizing your collections and maps--doing so will *always* have better results.
This patch extends HashMap and ArrayList to provide special handling for newly created instances that avoids creating the backing array until needed. There is a very small additional cost for detecting when to inflate the map or list that is measurable in interpreted tests but disappears in JITed code.
http://cr.openjdk.java.net/~mduigou/JDK-7143928/0/webrev/
We expect that should this code prove successful in Java 8 it will be backported to Java 7 updates.
The unit test may appear to be somewhat unrelated. It was created after resolving a bug in an early version of this patch to detect the issue encountered (LinkedHashMap.init() was not being called in readObject() when the map was empty).
Mike
On 02/04/2013 23:50, Mike Duigou wrote:
Hello again;
I have updated the patch with the received review feedback. The revised webrev is here:
http://cr.openjdk.java.net/~mduigou/JDK-8011200/1/webrev/
The important changes in this revision:
- The behaviour of the readObject/writeObject serialization for both classes now more closely mirrors the behaviour of clone(). For ArrayList this means that the deserialized list has a capacity the same as the size. ie. as if trimToSize() was called. For HashMap, the opposite is true, the capacity is the same as was in effect when the object was serialized. (HashMap also tries to protect itself from nonsensical/harmful input). The implementation changes to serialization preserve forward and backward compatibility--all serialized objects are compatible with all implementations. I will file a spec change request for the addition of ", a power of 2" to the @serialData tag for this existing but previously unstated requirement.
- Use of Arrays.fill has been reverted. I did change one fill case so that the loop can be optimized. (size field was being updated with each iteration). I very slightly expanded the docs.
This is starting to look like a nice set of changes.
Mike This does looks much nicer.
For ArrayList.ensureCapacity then it might be useful to include a comment to make it clear that it's a no-op when the ArrayList is created with the default and ensureCapacity(n), for n < 10. I had to read it a few times to satisfy myself that it's right. One thing that I'm not sure about is HashMap.readObject using the bucket count from the serialized stream. We can't predict all usages of course but this has the potential for the table to be much bigger than we need. Otherwise I think this looks okay to me. I didn't quite get the reason for splitting out the update to the @serialData description but maybe you want to separate the changes to make it easy to backport. -Alan.
A couple small things: HashMap: It might be nice to have a comment or two on the new, dual-purpose of 'threshold': perhaps in the comments for inflateTable(), and/or at the field declaration. ArrayList: Is there an extra set of ()'s around (minCapacity > DEFAULT_CAPACITY) ? Thanks, -Brent On 4/2/13 3:50 PM, Mike Duigou wrote:
Hello again;
I have updated the patch with the received review feedback. The revised webrev is here:
http://cr.openjdk.java.net/~mduigou/JDK-8011200/1/webrev/
The important changes in this revision:
- The behaviour of the readObject/writeObject serialization for both classes now more closely mirrors the behaviour of clone(). For ArrayList this means that the deserialized list has a capacity the same as the size. ie. as if trimToSize() was called. For HashMap, the opposite is true, the capacity is the same as was in effect when the object was serialized. (HashMap also tries to protect itself from nonsensical/harmful input). The implementation changes to serialization preserve forward and backward compatibility--all serialized objects are compatible with all implementations. I will file a spec change request for the addition of ", a power of 2" to the @serialData tag for this existing but previously unstated requirement.
- Use of Arrays.fill has been reverted. I did change one fill case so that the loop can be optimized. (size field was being updated with each iteration). I very slightly expanded the docs.
This is starting to look like a nice set of changes.
Mike
On Apr 1 2013, at 21:44 , Mike Duigou wrote:
Hello all;
Last night while pushing another changeset I accidentally pushed a changeset for JKD-7143928. Since the review and testing was not complete on this issue I have backed out that changeset and created a new bug number to continue development. The new webrev to complete the review is:
http://cr.openjdk.java.net/~mduigou/JDK-8011200/0/webrev/
It is currently unchanged from the last posted changeset for 7143928.
Mike
On Apr 1 2013, at 19:00 , Mike Duigou wrote:
Hello all;
I have posted an updated version of the empty ArrayList and HashMap patch.
http://cr.openjdk.java.net/~mduigou/JDK-7143928/1/webrev/
This revised implementation introduces *no new fields* to either class. For ArrayList the lazy allocation of the backing array occurs only if the list is created at default size. According to our performance analysis team, approximately 85% of ArrayList instances are created at default size so this optimization will be valid for an overwhelming majority of cases.
For HashMap, creative use is made of the threshold field to track the requested initial size until the bucket array is needed. On the read side the empty map case is tested with isEmpty(). On the write size a comparison of (table == EMPTY_TABLE) is used to detect the need to inflate the bucket array. In readObject there's a little more work to try to choose an efficient initial capacity.
Mike
On Mar 26 2013, at 17:25 , Mike Duigou wrote:
Hello all;
This is a review for optimization work that came out of internal analysis of Oracle's Java applications. It's 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. This patch is not a substitute for pre-sizing your collections and maps--doing so will *always* have better results.
This patch extends HashMap and ArrayList to provide special handling for newly created instances that avoids creating the backing array until needed. There is a very small additional cost for detecting when to inflate the map or list that is measurable in interpreted tests but disappears in JITed code.
http://cr.openjdk.java.net/~mduigou/JDK-7143928/0/webrev/
We expect that should this code prove successful in Java 8 it will be backported to Java 7 updates.
The unit test may appear to be somewhat unrelated. It was created after resolving a bug in an early version of this patch to detect the issue encountered (LinkedHashMap.init() was not being called in readObject() when the map was empty).
Mike
On Tue, Apr 2, 2013 at 3:50 PM, Mike Duigou <mike.duigou@oracle.com> wrote:
- T I will file a spec change request for the addition of ", a power of 2" to the @serialData tag for this existing but previously unstated requirement.
Hi Mike, I think changing the serialization spec is a mistake. There are a bunch of collection classes that use power-of-two backing arrays, but it's clearly the intent of the authors that this be an implementation detail. As often happens, implementation details get accidentally exposed ("leaked") in a serial form. Here we see that the size of the backing array is embedded in the serial form. There is an incompatibility between the OpenJDK HashMap implementation and other implementations that don't use power-of-two backing arrays (which may not exist) but the right fix is to make the OpenJDK implementation more resilient to the input serial form. Treat the backing array size as merely a hint. If it's not a power of two, make it so! That is, remove the "previously unstated requirement".
Hello all; Another, and hopefully the final, update to the webrev for this issue. The revised webrev is here: http://cr.openjdk.java.net/~mduigou/JDK-8011200/1/webrev/ The important changes in this revision: - I've removed the serialData change in HashMap. The implementation now reads the capacity and gracefully handles non-power of 2 values. - I'm not entirely convinced that having serialization emulate clone() for capacity handling is the best answer. I might also want to change clone() to size it's result based upon the number of mappings in the source rather its the capacity. Anybody have strong feelings about this to suggest one behaviour is obviously better? Any other final thoughts? Mike On Apr 2 2013, at 15:50 , Mike Duigou wrote:
Hello again;
I have updated the patch with the received review feedback. The revised webrev is here:
http://cr.openjdk.java.net/~mduigou/JDK-8011200/1/webrev/
The important changes in this revision:
- The behaviour of the readObject/writeObject serialization for both classes now more closely mirrors the behaviour of clone(). For ArrayList this means that the deserialized list has a capacity the same as the size. ie. as if trimToSize() was called. For HashMap, the opposite is true, the capacity is the same as was in effect when the object was serialized. (HashMap also tries to protect itself from nonsensical/harmful input). The implementation changes to serialization preserve forward and backward compatibility--all serialized objects are compatible with all implementations. I will file a spec change request for the addition of ", a power of 2" to the @serialData tag for this existing but previously unstated requirement.
- Use of Arrays.fill has been reverted. I did change one fill case so that the loop can be optimized. (size field was being updated with each iteration). I very slightly expanded the docs.
This is starting to look like a nice set of changes.
Mike
On Apr 1 2013, at 21:44 , Mike Duigou wrote:
Hello all;
Last night while pushing another changeset I accidentally pushed a changeset for JKD-7143928. Since the review and testing was not complete on this issue I have backed out that changeset and created a new bug number to continue development. The new webrev to complete the review is:
http://cr.openjdk.java.net/~mduigou/JDK-8011200/0/webrev/
It is currently unchanged from the last posted changeset for 7143928.
Mike
On Apr 1 2013, at 19:00 , Mike Duigou wrote:
Hello all;
I have posted an updated version of the empty ArrayList and HashMap patch.
http://cr.openjdk.java.net/~mduigou/JDK-7143928/1/webrev/
This revised implementation introduces *no new fields* to either class. For ArrayList the lazy allocation of the backing array occurs only if the list is created at default size. According to our performance analysis team, approximately 85% of ArrayList instances are created at default size so this optimization will be valid for an overwhelming majority of cases.
For HashMap, creative use is made of the threshold field to track the requested initial size until the bucket array is needed. On the read side the empty map case is tested with isEmpty(). On the write size a comparison of (table == EMPTY_TABLE) is used to detect the need to inflate the bucket array. In readObject there's a little more work to try to choose an efficient initial capacity.
Mike
On Mar 26 2013, at 17:25 , Mike Duigou wrote:
Hello all;
This is a review for optimization work that came out of internal analysis of Oracle's Java applications. It's 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. This patch is not a substitute for pre-sizing your collections and maps--doing so will *always* have better results.
This patch extends HashMap and ArrayList to provide special handling for newly created instances that avoids creating the backing array until needed. There is a very small additional cost for detecting when to inflate the map or list that is measurable in interpreted tests but disappears in JITed code.
http://cr.openjdk.java.net/~mduigou/JDK-7143928/0/webrev/
We expect that should this code prove successful in Java 8 it will be backported to Java 7 updates.
The unit test may appear to be somewhat unrelated. It was created after resolving a bug in an early version of this patch to detect the issue encountered (LinkedHashMap.init() was not being called in readObject() when the map was empty).
Mike
On 06/04/2013 23:02, Mike Duigou wrote:
Hello all;
Another, and hopefully the final, update to the webrev for this issue. The revised webrev is here:
http://cr.openjdk.java.net/~mduigou/JDK-8011200/1/webrev/
The important changes in this revision:
- I've removed the serialData change in HashMap. The implementation now reads the capacity and gracefully handles non-power of 2 values.
- I'm not entirely convinced that having serialization emulate clone() for capacity handling is the best answer. I might also want to change clone() to size it's result based upon the number of mappings in the source rather its the capacity. Anybody have strong feelings about this to suggest one behaviour is obviously better?
Any other final thoughts?
Mike
I think this is the webrev: http://cr.openjdk.java.net/~mduigou/JDK-8011200/2/webrev/ It's impossible to predict what the usage will be after you reconstitute. Personally I think it's better to leave it as is, meaning the rounded-up size as otherwise you might reconstitute to a capacity that is much more than you might ever need. I didn't notice in the previous revisions but roundUpToPowerOf2 can assign "rounded" twice (it probably doesn't happen when it gets compiled at runtime but still looks a bit odd). The test still have the bug issue number. -Alan
Style: spaces around "=" + private static final int DEFAULT_CAPACITY= 10; --- It's a matter of taste whether to remove the temp var oldCapacity. I believe it was coded intentionally. public void trimToSize() { modCount++; - int oldCapacity = elementData.length; - if (size < oldCapacity) { + if (size < elementData.length) { elementData = Arrays.copyOf(elementData, size); } --- 754 throws java.io.IOException, ClassNotFoundException { 755 elementData = EMPTY_ELEMENTDATA; Your indentation is off. --- Because "threshold" is a serialized field, its javadoc is part of the public interface of this class, and hence cannot refer to implementation details like EMPTY_TABLE. 161 /** 162 * The next size value at which to resize (capacity * load factor). If 163 * table == EMPTY_TABLE then this is the initial capacity at which the 164 * table will be created when inflated. 165 * @serial 166 */ 167 int threshold;** * http://docs.oracle.com/javase/7/docs/api/serialized-form.html#java.util.Hash... * * * --- Consider making roundUpToPowerOf2 public. Best Implementation is not obvious. I would probably write a loop with core x = x & (x - 1) until get to zero. 274 private static int roundUpToPowerOf2(int number) { 275 int rounded = number >= MAXIMUM_CAPACITY 276 ? MAXIMUM_CAPACITY 277 : (rounded = Integer.highestOneBit(number)) != 0 278 ? (Integer.bitCount(number) > 1) ? rounded << 1 : rounded 279 : 1; 280 281 return rounded; 282 } --- I think it's a mistake to "optimize" for the empty case in code like this: 694 public boolean containsValue(Object value) { 695 if (isEmpty()) { 696 return false; 697 } 698
On Apr 8 2013, at 16:03 , Martin Buchholz wrote:
Style: spaces around "=" + private static final int DEFAULT_CAPACITY= 10;
I apologize for these minor style problems in this and my other patches. I am really loathe to run any kind of automated source reformatting tool on JDK source. Unfortunately there are a variety of styles sued within the JDK sources and the value of having minimal diffs is too great to contemplate global restyling. I am happy to correct any style or other errors I make and don't notice myself.
---
It's a matter of taste whether to remove the temp var oldCapacity. I believe it was coded intentionally. public void trimToSize() { modCount++; - int oldCapacity = elementData.length; - if (size < oldCapacity) { + if (size < elementData.length) { elementData = Arrays.copyOf(elementData, size); }
I assumed that oldCapacity was a remnant of a previous implementation prior to the introduction of Arrays.copyOf(). It didn't seem to be worth retaining even for explanatory value.
---
Because "threshold" is a serialized field, its javadoc is part of the public interface of this class, and hence cannot refer to implementation details like EMPTY_TABLE. 161 /** 162 * The next size value at which to resize (capacity * load factor). If 163 * table == EMPTY_TABLE then this is the initial capacity at which the 164 * table will be created when inflated. 165 * @serial 166 */ 167 int threshold; http://docs.oracle.com/javase/7/docs/api/serialized-form.html#java.util.Hash...
---
Consider making roundUpToPowerOf2 public.
I assume you mean as part of some utility class like Integer? Reasonable and increases the chances that some VM engineer will come along and optimize it. Not sure what should be done about negative numbers. This likely comes too late for Java 8 though. (I know I probably don't have time).
Best Implementation is not obvious. I would probably write a loop with core x = x & (x - 1) until get to zero. 274 private static int roundUpToPowerOf2(int number) { 275 int rounded = number >= MAXIMUM_CAPACITY 276 ? MAXIMUM_CAPACITY 277 : (rounded = Integer.highestOneBit(number)) != 0 278 ? (Integer.bitCount(number) > 1) ? rounded << 1 : rounded 279 : 1; 280 281 return rounded; 282 }
The Integer operations are Hotspot intrinsics. This version is coded so that there are no loops. The previous looping implementation was criticized in an earlier review. It may be better to convert this to the Hacker's Delight 3-3 implementation
On Apr 8 2013, at 05:52 , Alan Bateman wrote:
I think this is the webrev:
http://cr.openjdk.java.net/~mduigou/JDK-8011200/2/webrev/
It's impossible to predict what the usage will be after you reconstitute.
I agree completely. We should have a consistent policy for both deserialization and clone().
Personally I think it's better to leave it as is, meaning the rounded-up size as otherwise you might reconstitute to a capacity that is much more than you might ever need.
This is my feeling as well. I especially wonder about the extra space of clone()ed maps. Seems like a good opportunity for savings.
I didn't notice in the previous revisions but roundUpToPowerOf2 can assign "rounded" twice (it probably doesn't happen when it gets compiled at runtime but still looks a bit odd).
All in the name of optimization.
The test still have the bug issue number.
Sorry for not correcting this in earlier revs.
-Alan
Hello all; Another update to the webrev incorporating feedback from Alan and Martin. http://cr.openjdk.java.net/~mduigou/JDK-8011200/3/webrev/ - The key change in this revision is that the capacity of both cloned() and deserialized instances is determined by the number of entries NOT the capacity of the source HashMap. As Alan says, we don't know how the clone or deserialized instance is going to be used. Without maintaining the original user specified initial capacity we're possibly better off not allocating excessive bucket table. Mike On Apr 6 2013, at 15:02 , Mike Duigou wrote:
Hello all;
Another, and hopefully the final, update to the webrev for this issue. The revised webrev is here:
http://cr.openjdk.java.net/~mduigou/JDK-8011200/1/webrev/
The important changes in this revision:
- I've removed the serialData change in HashMap. The implementation now reads the capacity and gracefully handles non-power of 2 values.
- I'm not entirely convinced that having serialization emulate clone() for capacity handling is the best answer. I might also want to change clone() to size it's result based upon the number of mappings in the source rather its the capacity. Anybody have strong feelings about this to suggest one behaviour is obviously better?
Any other final thoughts?
Mike
On Apr 2 2013, at 15:50 , Mike Duigou wrote:
Hello again;
I have updated the patch with the received review feedback. The revised webrev is here:
http://cr.openjdk.java.net/~mduigou/JDK-8011200/1/webrev/
The important changes in this revision:
- The behaviour of the readObject/writeObject serialization for both classes now more closely mirrors the behaviour of clone(). For ArrayList this means that the deserialized list has a capacity the same as the size. ie. as if trimToSize() was called. For HashMap, the opposite is true, the capacity is the same as was in effect when the object was serialized. (HashMap also tries to protect itself from nonsensical/harmful input). The implementation changes to serialization preserve forward and backward compatibility--all serialized objects are compatible with all implementations. I will file a spec change request for the addition of ", a power of 2" to the @serialData tag for this existing but previously unstated requirement.
- Use of Arrays.fill has been reverted. I did change one fill case so that the loop can be optimized. (size field was being updated with each iteration). I very slightly expanded the docs.
This is starting to look like a nice set of changes.
Mike
On Apr 1 2013, at 21:44 , Mike Duigou wrote:
Hello all;
Last night while pushing another changeset I accidentally pushed a changeset for JKD-7143928. Since the review and testing was not complete on this issue I have backed out that changeset and created a new bug number to continue development. The new webrev to complete the review is:
http://cr.openjdk.java.net/~mduigou/JDK-8011200/0/webrev/
It is currently unchanged from the last posted changeset for 7143928.
Mike
On Apr 1 2013, at 19:00 , Mike Duigou wrote:
Hello all;
I have posted an updated version of the empty ArrayList and HashMap patch.
http://cr.openjdk.java.net/~mduigou/JDK-7143928/1/webrev/
This revised implementation introduces *no new fields* to either class. For ArrayList the lazy allocation of the backing array occurs only if the list is created at default size. According to our performance analysis team, approximately 85% of ArrayList instances are created at default size so this optimization will be valid for an overwhelming majority of cases.
For HashMap, creative use is made of the threshold field to track the requested initial size until the bucket array is needed. On the read side the empty map case is tested with isEmpty(). On the write size a comparison of (table == EMPTY_TABLE) is used to detect the need to inflate the bucket array. In readObject there's a little more work to try to choose an efficient initial capacity.
Mike
On Mar 26 2013, at 17:25 , Mike Duigou wrote:
Hello all;
This is a review for optimization work that came out of internal analysis of Oracle's Java applications. It's 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. This patch is not a substitute for pre-sizing your collections and maps--doing so will *always* have better results.
This patch extends HashMap and ArrayList to provide special handling for newly created instances that avoids creating the backing array until needed. There is a very small additional cost for detecting when to inflate the map or list that is measurable in interpreted tests but disappears in JITed code.
http://cr.openjdk.java.net/~mduigou/JDK-7143928/0/webrev/
We expect that should this code prove successful in Java 8 it will be backported to Java 7 updates.
The unit test may appear to be somewhat unrelated. It was created after resolving a bug in an early version of this patch to detect the issue encountered (LinkedHashMap.init() was not being called in readObject() when the map was empty).
Mike
Mike, thanks. I don't see anything wrong in this version, although the ongoing complexification and special-case-ification (with attendant risk of bugs) of ArrayList and HashMap, the two most didactically important classes, continue to bother me. This change continues to feel marginal. Anyways, this is OK with me if it's OK with Alan. The original code that shifts by one every time has a certain elegance, and because it's rare to need more than one doubling, is also hard to beat performance-wise. 546 while (newCapacity < targetCapacity) 547 newCapacity <<= 1; --- should there be an "else" added in the code below? 563 if (table == EMPTY_TABLE) { 564 inflateTable(Math.max((int) (numKeysToBeAdded * loadFactor), threshold)); 565 } 566 567 /* 568 * Expand the map if the map if the number of mappings to be added 569 * is greater than or equal to threshold. This is conservative; the 570 * obvious condition is (m.size() + size) >= threshold, but this 571 * condition could result in a map with twice the appropriate capacity, 572 * if the keys to be added overlap with the keys already in this map. 573 * By using the conservative calculation, we subject ourself 574 * to at most one extra resize. 575 */ 576 if (numKeysToBeAdded > threshold) { --- There are now so many "if (isEmpty())" checks that I wonder again whether it would be better to use a null for the empty table, since null checks are closer to free. --- Style: """ Inflates the table. """ 285 * Inflate the table --- 288 // Find a power of 2 >= initialCapacity There's no "initialCapacity" variable here. On Tue, Apr 9, 2013 at 6:17 PM, Mike Duigou <mike.duigou@oracle.com> wrote:
Hello all;
Another update to the webrev incorporating feedback from Alan and Martin.
http://cr.openjdk.java.net/~mduigou/JDK-8011200/3/webrev/
- The key change in this revision is that the capacity of both cloned() and deserialized instances is determined by the number of entries NOT the capacity of the source HashMap. As Alan says, we don't know how the clone or deserialized instance is going to be used. Without maintaining the original user specified initial capacity we're possibly better off not allocating excessive bucket table.
Mike
On Apr 6 2013, at 15:02 , Mike Duigou wrote:
Hello all;
Another, and hopefully the final, update to the webrev for this issue. The revised webrev is here:
http://cr.openjdk.java.net/~mduigou/JDK-8011200/1/webrev/
The important changes in this revision:
- I've removed the serialData change in HashMap. The implementation now reads the capacity and gracefully handles non-power of 2 values.
- I'm not entirely convinced that having serialization emulate clone() for capacity handling is the best answer. I might also want to change clone() to size it's result based upon the number of mappings in the source rather its the capacity. Anybody have strong feelings about this to suggest one behaviour is obviously better?
Any other final thoughts?
Mike
On Apr 2 2013, at 15:50 , Mike Duigou wrote:
Hello again;
I have updated the patch with the received review feedback. The revised webrev is here:
http://cr.openjdk.java.net/~mduigou/JDK-8011200/1/webrev/
The important changes in this revision:
- The behaviour of the readObject/writeObject serialization for both classes now more closely mirrors the behaviour of clone(). For ArrayList this means that the deserialized list has a capacity the same as the size. ie. as if trimToSize() was called. For HashMap, the opposite is true, the capacity is the same as was in effect when the object was serialized. (HashMap also tries to protect itself from nonsensical/harmful input). The implementation changes to serialization preserve forward and backward compatibility--all serialized objects are compatible with all implementations. I will file a spec change request for the addition of ", a power of 2" to the @serialData tag for this existing but previously unstated requirement.
- Use of Arrays.fill has been reverted. I did change one fill case so that the loop can be optimized. (size field was being updated with each iteration). I very slightly expanded the docs.
This is starting to look like a nice set of changes.
Mike
On Apr 1 2013, at 21:44 , Mike Duigou wrote:
Hello all;
Last night while pushing another changeset I accidentally pushed a changeset for JKD-7143928. Since the review and testing was not complete on this issue I have backed out that changeset and created a new bug number to continue development. The new webrev to complete the review is:
http://cr.openjdk.java.net/~mduigou/JDK-8011200/0/webrev/
It is currently unchanged from the last posted changeset for 7143928.
Mike
On Apr 1 2013, at 19:00 , Mike Duigou wrote:
Hello all;
I have posted an updated version of the empty ArrayList and HashMap patch.
http://cr.openjdk.java.net/~mduigou/JDK-7143928/1/webrev/
This revised implementation introduces *no new fields* to either class. For ArrayList the lazy allocation of the backing array occurs only if the list is created at default size. According to our performance analysis team, approximately 85% of ArrayList instances are created at default size so this optimization will be valid for an overwhelming majority of cases.
For HashMap, creative use is made of the threshold field to track the requested initial size until the bucket array is needed. On the read side the empty map case is tested with isEmpty(). On the write size a comparison of (table == EMPTY_TABLE) is used to detect the need to inflate the bucket array. In readObject there's a little more work to try to choose an efficient initial capacity.
Mike
On Mar 26 2013, at 17:25 , Mike Duigou wrote:
Hello all;
This is a review for optimization work that came out of internal analysis of Oracle's Java applications. It's 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. This patch is not a substitute for pre-sizing your collections and maps--doing so will *always* have better results.
This patch extends HashMap and ArrayList to provide special handling for newly created instances that avoids creating the backing array until needed. There is a very small additional cost for detecting when to inflate the map or list that is measurable in interpreted tests but disappears in JITed code.
http://cr.openjdk.java.net/~mduigou/JDK-7143928/0/webrev/
We expect that should this code prove successful in Java 8 it will be backported to Java 7 updates.
The unit test may appear to be somewhat unrelated. It was created after resolving a bug in an early version of this patch to detect the issue encountered (LinkedHashMap.init() was not being called in readObject() when the map was empty).
Mike
On Apr 9 2013, at 19:56 , Martin Buchholz wrote:
Mike, thanks.
I don't see anything wrong in this version, although the ongoing complexification and special-case-ification (with attendant risk of bugs) of ArrayList and HashMap, the two most didactically important classes, continue to bother me. This change continues to feel marginal.
It was surprising to find just how many ArrayList and HashMap instances were empty and/or never used. Unfortunately it's harder to globally fix applications than it is to and special case code to ArrayList and HashMap.
Anyways, this is OK with me if it's OK with Alan.
The original code that shifts by one every time has a certain elegance, and because it's rare to need more than one doubling, is also hard to beat performance-wise.
546 while (newCapacity < targetCapacity) 547 newCapacity <<= 1; I will restore it.
There are now so many "if (isEmpty())" checks that I wonder again whether it would be better to use a null for the empty table, since null checks are closer to free.
The use of an empty array rather than null was suggested by John Rose who said:
I recommend an empty array rather than null as a sentinel value for two reasons:
1. The JVM prefers to merge null checks into load or store instructions (so-called "implicit null checks") because it removes an explicit branch. But it only does so if the probability of nulls is zero or very low. But using null as a sentinel for common states (e.g., empty collection) defeats this optimization.
2. For power-of-two sized structures (HashMap) we can optimize away an array range check in the presence of a zero-length check.
Since most uses of a variable-sized collection load and test the array length, the sentinel check can easily be overloaded onto this test. If null is not used, then the (safety-mandated) null check is (usually) merged into the load of the length. If the table is power-of-two-sized, then only the zero check remains, and the array range check may be removed. This is thought to be the best code for a frequent load from a possibly-empty collection.
Mike asked, "what about empty collection?" This is a reasonable thing to use, but it has a cost. The JVM uses inline caches and type profiles to simplify its optimized code; these techniques "win" when at a given use point (individual call to Map.get, for example) there is only one class present, even if the interface is totally general. (This is the so-called "monomorphic" case.) If the application uses (say) only HashMaps for both empty and non-empty maps, then this optimization can win big. It can be broken, on the other hand, if the application begins to use one other type for some other case (such as empty maps). In these cases, it is better to overload the "am I empty?" test on some other loaded value, such as a null or (better) an array length.
Mike
I'm willing to accept John as an authority on hotspot optimization. I'm surprised that null checks aren't more close to free in part because recent jsr166 code has been introducing more explicit null checks, sometimes in code where the reference being checked is "known" not to be null. Martin On Wed, Apr 10, 2013 at 11:12 AM, Mike Duigou <mike.duigou@oracle.com>wrote:
On Apr 9 2013, at 19:56 , Martin Buchholz wrote: The use of an empty array rather than null was suggested by John Rose who said:
I recommend an empty array rather than null as a sentinel value for two reasons:
1. The JVM prefers to merge null checks into load or store instructions (so-called "implicit null checks") because it removes an explicit branch. But it only does so if the probability of nulls is zero or very low. But using null as a sentinel for common states (e.g., empty collection) defeats this optimization.
2. For power-of-two sized structures (HashMap) we can optimize away an array range check in the presence of a zero-length check.
Since most uses of a variable-sized collection load and test the array length, the sentinel check can easily be overloaded onto this test. If null is not used, then the (safety-mandated) null check is (usually) merged into the load of the length. If the table is power-of-two-sized, then only the zero check remains, and the array range check may be removed. This is thought to be the best code for a frequent load from a possibly-empty collection.
Mike asked, "what about empty collection?" This is a reasonable thing to use, but it has a cost. The JVM uses inline caches and type profiles to simplify its optimized code; these techniques "win" when at a given use point (individual call to Map.get, for example) there is only one class present, even if the interface is totally general. (This is the so-called "monomorphic" case.) If the application uses (say) only HashMaps for both empty and non-empty maps, then this optimization can win big. It can be broken, on the other hand, if the application begins to use one other type for some other case (such as empty maps). In these cases, it is better to overload the "am I empty?" test on some other loaded value, such as a null or (better) an array length.
Mike
On 04/10/13 17:26, Martin Buchholz wrote:
I'm willing to accept John as an authority on hotspot optimization. I'm surprised that null checks aren't more close to free in part because recent jsr166 code has been introducing more explicit null checks, sometimes in code where the reference being checked is "known" not to be null.
Some are cheap. Some aren't. Always measure. -Doug
On 04/10/2013 11:26 PM, Martin Buchholz wrote:
I'm willing to accept John as an authority on hotspot optimization. I'm surprised that null checks aren't more close to free in part because recent jsr166 code has been introducing more explicit null checks, sometimes in code where the reference being checked is "known" not to be null.
Martin
null check that are never null are free when the interpreter has never (or rarely) sees a null at a specific callsite because in that case, the JIT doesn't generate a null check and let the CPU/MMU do a fault (the VM has a signal handler to be able to come back from death :) If you set a field to null, the profiler will see the null and will not use this optimization, that why in this case, it's better to have an empty array instead of null. BTW, the nullcheck in assembler cost you almost nothing anyway but the jump associated with it has a cost. Modern CPUs do not like to jump. Rémi
On Wed, Apr 10, 2013 at 11:12 AM, Mike Duigou <mike.duigou@oracle.com>wrote:
On Apr 9 2013, at 19:56 , Martin Buchholz wrote: The use of an empty array rather than null was suggested by John Rose who said:
I recommend an empty array rather than null as a sentinel value for two reasons:
1. The JVM prefers to merge null checks into load or store instructions (so-called "implicit null checks") because it removes an explicit branch. But it only does so if the probability of nulls is zero or very low. But using null as a sentinel for common states (e.g., empty collection) defeats this optimization.
2. For power-of-two sized structures (HashMap) we can optimize away an array range check in the presence of a zero-length check.
Since most uses of a variable-sized collection load and test the array length, the sentinel check can easily be overloaded onto this test. If null is not used, then the (safety-mandated) null check is (usually) merged into the load of the length. If the table is power-of-two-sized, then only the zero check remains, and the array range check may be removed. This is thought to be the best code for a frequent load from a possibly-empty collection.
Mike asked, "what about empty collection?" This is a reasonable thing to use, but it has a cost. The JVM uses inline caches and type profiles to simplify its optimized code; these techniques "win" when at a given use point (individual call to Map.get, for example) there is only one class present, even if the interface is totally general. (This is the so-called "monomorphic" case.) If the application uses (say) only HashMaps for both empty and non-empty maps, then this optimization can win big. It can be broken, on the other hand, if the application begins to use one other type for some other case (such as empty maps). In these cases, it is better to overload the "am I empty?" test on some other loaded value, such as a null or (better) an array length.
Mike
The null check jumps should be taken care of by branch prediction; as long as they're predictable, penalty on OOO CPU is minimal. So modern CPUs don't like mispredicted branches I'd say, not just any jump. On Apr 10, 2013 7:23 PM, "Remi Forax" <forax@univ-mlv.fr> wrote:
On 04/10/2013 11:26 PM, Martin Buchholz wrote:
I'm willing to accept John as an authority on hotspot optimization. I'm surprised that null checks aren't more close to free in part because recent jsr166 code has been introducing more explicit null checks, sometimes in code where the reference being checked is "known" not to be null.
Martin
null check that are never null are free when the interpreter has never (or rarely) sees a null at a specific callsite because in that case, the JIT doesn't generate a null check and let the CPU/MMU do a fault (the VM has a signal handler to be able to come back from death :)
If you set a field to null, the profiler will see the null and will not use this optimization, that why in this case, it's better to have an empty array instead of null. BTW, the nullcheck in assembler cost you almost nothing anyway but the jump associated with it has a cost. Modern CPUs do not like to jump.
Rémi
On Wed, Apr 10, 2013 at 11:12 AM, Mike Duigou <mike.duigou@oracle.com
wrote:
On Apr 9 2013, at 19:56 , Martin Buchholz wrote:
The use of an empty array rather than null was suggested by John Rose who said:
I recommend an empty array rather than null as a sentinel value for two reasons:
1. The JVM prefers to merge null checks into load or store instructions (so-called "implicit null checks") because it removes an explicit branch. But it only does so if the probability of nulls is zero or very low. But using null as a sentinel for common states (e.g., empty collection) defeats this optimization.
2. For power-of-two sized structures (HashMap) we can optimize away an array range check in the presence of a zero-length check.
Since most uses of a variable-sized collection load and test the array length, the sentinel check can easily be overloaded onto this test. If null is not used, then the (safety-mandated) null check is (usually) merged into the load of the length. If the table is power-of-two-sized, then only the zero check remains, and the array range check may be removed. This is thought to be the best code for a frequent load from a possibly-empty collection.
Mike asked, "what about empty collection?" This is a reasonable thing to use, but it has a cost. The JVM uses inline caches and type profiles to simplify its optimized code; these techniques "win" when at a given use point (individual call to Map.get, for example) there is only one class present, even if the interface is totally general. (This is the so-called "monomorphic" case.) If the application uses (say) only HashMaps for both empty and non-empty maps, then this optimization can win big. It can be broken, on the other hand, if the application begins to use one other type for some other case (such as empty maps). In these cases, it is better to overload the "am I empty?" test on some other loaded value, such as a null or (better) an array length.
Mike
Whether or not we use null or an empty array as a sentinel value, we will need to make a special check for empty on most operations, and that will not be predictable if empty collection operations are common. The empty collection optimization is a strange sort of compression algorithm.
On 04/11/2013 01:33 AM, Vitaly Davidovich wrote:
The null check jumps should be taken care of by branch prediction; as long as they're predictable, penalty on OOO CPU is minimal. So modern CPUs don't like mispredicted branches I'd say, not just any jump.
yes :) Rémi
On Apr 10, 2013 7:23 PM, "Remi Forax" <forax@univ-mlv.fr <mailto:forax@univ-mlv.fr>> wrote:
On 04/10/2013 11:26 PM, Martin Buchholz wrote:
I'm willing to accept John as an authority on hotspot optimization. I'm surprised that null checks aren't more close to free in part because recent jsr166 code has been introducing more explicit null checks, sometimes in code where the reference being checked is "known" not to be null.
Martin
null check that are never null are free when the interpreter has never (or rarely) sees a null at a specific callsite because in that case, the JIT doesn't generate a null check and let the CPU/MMU do a fault (the VM has a signal handler to be able to come back from death :)
If you set a field to null, the profiler will see the null and will not use this optimization, that why in this case, it's better to have an empty array instead of null. BTW, the nullcheck in assembler cost you almost nothing anyway but the jump associated with it has a cost. Modern CPUs do not like to jump.
Rémi
On Wed, Apr 10, 2013 at 11:12 AM, Mike Duigou <mike.duigou@oracle.com <mailto:mike.duigou@oracle.com>>wrote:
On Apr 9 2013, at 19:56 , Martin Buchholz wrote: The use of an empty array rather than null was suggested by John Rose who said:
I recommend an empty array rather than null as a sentinel value for two reasons:
1. The JVM prefers to merge null checks into load or store instructions (so-called "implicit null checks") because it removes an explicit branch. But it only does so if the probability of nulls is zero or very low. But using null as a sentinel for common states (e.g., empty collection) defeats this optimization.
2. For power-of-two sized structures (HashMap) we can optimize away an array range check in the presence of a zero-length check.
Since most uses of a variable-sized collection load and test the array length, the sentinel check can easily be overloaded onto this test. If null is not used, then the (safety-mandated) null check is (usually) merged into the load of the length. If the table is power-of-two-sized, then only the zero check remains, and the array range check may be removed. This is thought to be the best code for a frequent load from a possibly-empty collection.
Mike asked, "what about empty collection?" This is a reasonable thing to use, but it has a cost. The JVM uses inline caches and type profiles to simplify its optimized code; these techniques "win" when at a given use point (individual call to Map.get, for example) there is only one class present, even if the interface is totally general. (This is the so-called "monomorphic" case.) If the application uses (say) only HashMaps for both empty and non-empty maps, then this optimization can win big. It can be broken, on the other hand, if the application begins to use one other type for some other case (such as empty maps). In these cases, it is better to overload the "am I empty?" test on some other loaded value, such as a null or (better) an array length.
Mike
On 10/04/2013 19:12, Mike Duigou wrote:
On Apr 9 2013, at 19:56 , Martin Buchholz wrote:
Mike, thanks.
I don't see anything wrong in this version, although the ongoing complexification and special-case-ification (with attendant risk of bugs) of ArrayList and HashMap, the two most didactically important classes, continue to bother me. This change continues to feel marginal. It was surprising to find just how many ArrayList and HashMap instances were empty and/or never used. Unfortunately it's harder to globally fix applications than it is to and special case code to ArrayList and HashMap. Right and I wonder if the performance folks could share some of the data that they have gathered on this.
In any case, I think this patch is looking good now, assuming this is the near-to-final version: http://cr.openjdk.java.net/~mduigou/JDK-8011200/4/webrev/ One remaining point that I'm a bit uneasy about is ArrayList.writeObject writing out the size rather than the array length. It is specified to be the array backing the ArrayList. It's now ignored by readObject (which is good) but reconstituting on an older/other JDK release will/may reconstitute to the trimmed size. -Alan.
On Apr 11 2013, at 06:03 , Alan Bateman wrote:
On 10/04/2013 19:12, Mike Duigou wrote:
On Apr 9 2013, at 19:56 , Martin Buchholz wrote:
Mike, thanks.
I don't see anything wrong in this version, although the ongoing complexification and special-case-ification (with attendant risk of bugs) of ArrayList and HashMap, the two most didactically important classes, continue to bother me. This change continues to feel marginal. It was surprising to find just how many ArrayList and HashMap instances were empty and/or never used. Unfortunately it's harder to globally fix applications than it is to and special case code to ArrayList and HashMap. Right and I wonder if the performance folks could share some of the data that they have gathered on this.
I started this review cycle with high level numbers for a wide variety of Java applications that the performance team looked at. Across these applications 1.4%(±2.9%) of HashMaps were forever empty and a similar percentage spent a large portion of their lifetime empty. For ArrayList the numbers were 1.0%(±2.6%) are forever empty and a larger percentage spent much of their life empty. As a percentage of heap space the empty instances account for about 1%. For some applications the numbers are much worse. Of the empty instances 85% were created at default size.
In any case, I think this patch is looking good now, assuming this is the near-to-final version:
Correct. I am running it through final pre-integration tests now. Some performance testing has been done on the second review version of this patch (the last before removing initialCapacity fields unfortunately) which shows no performance regressions across our reference workloads and a few significant improvements (a GC benchmark).
One remaining point that I'm a bit uneasy about is ArrayList.writeObject writing out the size rather than the array length. It is specified to be the array backing the ArrayList. It's now ignored by readObject (which is good) but reconstituting on an older/other JDK release will/may reconstitute to the trimmed size.
It's not harmful that it does so. This effectively forces the trimming behaviour in all deserialization cases. Mike
Overall, this kind of change seems barely worth doing. --- This change: // Let gc do its work - for (int i = 0; i < size; i++) - elementData[i] = null; + Arrays.fill(elementData, null); changes the performance of clear from O(size) to O(capacity), which is bad, and unrelated to the "empty collection optimization". --- + if(elementData == EMPTY_ELEMENTDATA) { Please use standard jdk style - space after keywords such as "if". --- 183 public void ensureCapacity(int minCapacity) { 184 if (minCapacity > 0) 185 ensureExplicitCapacity(minCapacity); 186 } 187 188 private void ensureCapacityInternal(int minCapacity) { 189 if(elementData == EMPTY_ELEMENTDATA) { 190 minCapacity = Math.max(10, minCapacity); 191 } 192 193 ensureExplicitCapacity(minCapacity); 194 } It looks to me like, if the user does x = new ArrayList(); x.ensureCapacity(2); then the capacity will be 2, not 10, an observable change from the previous implementation, and sort-of contradicting the spec of ArrayList() --- 604 Arrays.fill(elementData, newSize, size, null); In performance-critical code I would avoid Arrays.fill because it adds a bit of overhead (unless it's intrinsified, which I don't think it is). --- If we are willing to make small incompatible changes, how about when serializing, storing capacity as the size, so that reconstituted ArrayLists are pre-trimmed to size? --- I still believe that with the help of the gc team, one can cook up a trim-to-size when gc-ing fix, but that's going to be very hard to implement. --- On Mon, Apr 1, 2013 at 7:00 PM, Mike Duigou <mike.duigou@oracle.com> wrote:
Hello all;
I have posted an updated version of the empty ArrayList and HashMap patch.
http://cr.openjdk.java.net/~mduigou/JDK-7143928/1/webrev/
This revised implementation introduces *no new fields* to either class. For ArrayList the lazy allocation of the backing array occurs only if the list is created at default size. According to our performance analysis team, approximately 85% of ArrayList instances are created at default size so this optimization will be valid for an overwhelming majority of cases.
For HashMap, creative use is made of the threshold field to track the requested initial size until the bucket array is needed. On the read side the empty map case is tested with isEmpty(). On the write size a comparison of (table == EMPTY_TABLE) is used to detect the need to inflate the bucket array. In readObject there's a little more work to try to choose an efficient initial capacity.
Mike
On Mar 26 2013, at 17:25 , Mike Duigou wrote:
Hello all;
This is a review for optimization work that came out of internal analysis of Oracle's Java applications. It's 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. This patch is not a substitute for pre-sizing your collections and maps--doing so will *always* have better results.
This patch extends HashMap and ArrayList to provide special handling for newly created instances that avoids creating the backing array until needed. There is a very small additional cost for detecting when to inflate the map or list that is measurable in interpreted tests but disappears in JITed code.
http://cr.openjdk.java.net/~mduigou/JDK-7143928/0/webrev/
We expect that should this code prove successful in Java 8 it will be backported to Java 7 updates.
The unit test may appear to be somewhat unrelated. It was created after resolving a bug in an early version of this patch to detect the issue encountered (LinkedHashMap.init() was not being called in readObject() when the map was empty).
Mike
---
604 Arrays.fill(elementData, newSize, size, null);
In performance-critical code I would avoid Arrays.fill because it adds a bit of overhead (unless it's intrinsified, which I don't think it is).
Last week, I sent few benchmarks I did on array cleaning (zero fill) comparing Arrays.fill, System.arraycopy, Unsafe.setMemory ... Arrays.fill is the winner (always faster than arraycopy which use native code) by 10 - 20% ! I suspect aggressive hotspot optimizations (native code ?) because I agree Arrays.fill looks like a stupid for-loop ! Does somebody have clues explaining the Arrays.fill performance ? Is there an alternative way to clear an array giving the best possible performance (like c memset) ? it could be useful to have in JDK a native array fill implementation (System.fill ?) if it gives better performance. Laurent
On Tue, Apr 2, 2013 at 9:27 AM, Laurent Bourgès <bourges.laurent@gmail.com>wrote:
---
604 Arrays.fill(elementData, newSize, size, null);
In performance-critical code I would avoid Arrays.fill because it adds a bit of overhead (unless it's intrinsified, which I don't think it is).
Last week, I sent few benchmarks I did on array cleaning (zero fill) comparing Arrays.fill, System.arraycopy, Unsafe.setMemory ... Arrays.fill is the winner (always faster than arraycopy which use native code) by 10 - 20% ! I suspect aggressive hotspot optimizations (native code ?) because I agree Arrays.fill looks like a stupid for-loop !
Does somebody have clues explaining the Arrays.fill performance ?
There was at least one round of optimization done by the HotSpot team in mid-2010 - "This adds new logic to recognize fill idioms and convert them into a call to an optimized fill routine. Loop predication creates easily matched loops that are simply replaced with calls to the new assembly stubs. Currently only 1,2 and 4 byte primitive types are supported. Objects and longs/double will be supported in a later putback. Tested with runthese, nsk and ctw plus jbb2005. " see http://openjdk.5641.n7.nabble.com/review-M-for-4809552-Optimize-Arrays-fill-... Looks like the change was part of 6u23 http://download.java.net/jdk6/6u23/promoted/b03/changes/JDK6u23.b03.list.htm... Could not find anything more recent than that (on a quick mail search) Cheers Patrick
Thanks for the research. It seems like hotspot is recognizing and optimizing fill loops, rather than intrinsifying calls to Arrays.fill itself (good!). Anyways, I'd still like the "simple" fill loops in ArrayList to stay unchanged. Using Arrays.fill is only slightly more readable. There would be more of a case for fill if it was an actual array class instance method. On Tue, Apr 2, 2013 at 2:12 AM, Patrick Wright <pdoubleya@gmail.com> wrote:
On Tue, Apr 2, 2013 at 9:27 AM, Laurent Bourgès <bourges.laurent@gmail.com>wrote:
---
604 Arrays.fill(elementData, newSize, size, null);
In performance-critical code I would avoid Arrays.fill because it adds a bit of overhead (unless it's intrinsified, which I don't think it is).
Last week, I sent few benchmarks I did on array cleaning (zero fill) comparing Arrays.fill, System.arraycopy, Unsafe.setMemory ... Arrays.fill is the winner (always faster than arraycopy which use native code) by 10 - 20% ! I suspect aggressive hotspot optimizations (native code ?) because I agree Arrays.fill looks like a stupid for-loop !
Does somebody have clues explaining the Arrays.fill performance ?
There was at least one round of optimization done by the HotSpot team in mid-2010 - "This adds new logic to recognize fill idioms and convert them into a call to an optimized fill routine. Loop predication creates easily matched loops that are simply replaced with calls to the new assembly stubs. Currently only 1,2 and 4 byte primitive types are supported. Objects and longs/double will be supported in a later putback. Tested with runthese, nsk and ctw plus jbb2005. "
see
http://openjdk.5641.n7.nabble.com/review-M-for-4809552-Optimize-Arrays-fill-...
Looks like the change was part of 6u23
http://download.java.net/jdk6/6u23/promoted/b03/changes/JDK6u23.b03.list.htm...
Could not find anything more recent than that (on a quick mail search)
Cheers Patrick
On Apr 2 2013, at 10:55 , Martin Buchholz wrote:
Thanks for the research. It seems like hotspot is recognizing and optimizing fill loops, rather than intrinsifying calls to Arrays.fill itself (good!).
Why wouldn't doing both be better?
Anyways, I'd still like the "simple" fill loops in ArrayList to stay unchanged. Using Arrays.fill is only slightly more readable.
Part of the goal of the change was to make the intent clearer. I'll improve the comments instead.
There would be more of a case for fill if it was an actual array class instance method.
Maybe for Java 9.... Mike
On Tue, Apr 2, 2013 at 2:12 AM, Patrick Wright <pdoubleya@gmail.com> wrote:
On Tue, Apr 2, 2013 at 9:27 AM, Laurent Bourgès <bourges.laurent@gmail.com>wrote:
---
604 Arrays.fill(elementData, newSize, size, null);
In performance-critical code I would avoid Arrays.fill because it adds a bit of overhead (unless it's intrinsified, which I don't think it is).
Last week, I sent few benchmarks I did on array cleaning (zero fill) comparing Arrays.fill, System.arraycopy, Unsafe.setMemory ... Arrays.fill is the winner (always faster than arraycopy which use native code) by 10 - 20% ! I suspect aggressive hotspot optimizations (native code ?) because I agree Arrays.fill looks like a stupid for-loop !
Does somebody have clues explaining the Arrays.fill performance ?
There was at least one round of optimization done by the HotSpot team in mid-2010 - "This adds new logic to recognize fill idioms and convert them into a call to an optimized fill routine. Loop predication creates easily matched loops that are simply replaced with calls to the new assembly stubs. Currently only 1,2 and 4 byte primitive types are supported. Objects and longs/double will be supported in a later putback. Tested with runthese, nsk and ctw plus jbb2005. "
see
http://openjdk.5641.n7.nabble.com/review-M-for-4809552-Optimize-Arrays-fill-...
Looks like the change was part of 6u23
http://download.java.net/jdk6/6u23/promoted/b03/changes/JDK6u23.b03.list.htm...
Could not find anything more recent than that (on a quick mail search)
Cheers Patrick
On Tue, Apr 2, 2013 at 11:24 AM, Mike Duigou <mike.duigou@oracle.com> wrote:
On Apr 2 2013, at 10:55 , Martin Buchholz wrote:
Thanks for the research. It seems like hotspot is recognizing and optimizing fill loops, rather than intrinsifying calls to Arrays.fill itself (good!).
Why wouldn't doing both be better?
If hotspot recognizes and optimizes fill loops, Arrays.fill is optimized "for free".
Anyways, I'd still like the "simple" fill loops in ArrayList to stay unchanged. Using Arrays.fill is only slightly more readable.
Part of the goal of the change was to make the intent clearer. I'll improve the comments instead.
ArrayList is one of those classes that are important for educational reasons. Studying it will be part of many peoples' university education. So I applaud efforts to improve clarity. But I think the fill loops are sufficiently clear as they stand.
Thanks for the pointer. I had remembered reading this changeset and it has motivated to use Arrays.fill but I could not have found it. Mike On Apr 2 2013, at 02:12 , Patrick Wright wrote:
On Tue, Apr 2, 2013 at 9:27 AM, Laurent Bourgès <bourges.laurent@gmail.com>wrote:
---
604 Arrays.fill(elementData, newSize, size, null);
In performance-critical code I would avoid Arrays.fill because it adds a bit of overhead (unless it's intrinsified, which I don't think it is).
Last week, I sent few benchmarks I did on array cleaning (zero fill) comparing Arrays.fill, System.arraycopy, Unsafe.setMemory ... Arrays.fill is the winner (always faster than arraycopy which use native code) by 10 - 20% ! I suspect aggressive hotspot optimizations (native code ?) because I agree Arrays.fill looks like a stupid for-loop !
Does somebody have clues explaining the Arrays.fill performance ?
There was at least one round of optimization done by the HotSpot team in mid-2010 - "This adds new logic to recognize fill idioms and convert them into a call to an optimized fill routine. Loop predication creates easily matched loops that are simply replaced with calls to the new assembly stubs. Currently only 1,2 and 4 byte primitive types are supported. Objects and longs/double will be supported in a later putback. Tested with runthese, nsk and ctw plus jbb2005. "
see http://openjdk.5641.n7.nabble.com/review-M-for-4809552-Optimize-Arrays-fill-...
Looks like the change was part of 6u23 http://download.java.net/jdk6/6u23/promoted/b03/changes/JDK6u23.b03.list.htm...
Could not find anything more recent than that (on a quick mail search)
Cheers Patrick
On Apr 1 2013, at 22:24 , Martin Buchholz wrote: (Other changes accepted as suggested)
If we are willing to make small incompatible changes, how about when serializing, storing capacity as the size, so that reconstituted ArrayLists are pre-trimmed to size?
Yes, I found it strange that clone() returns a trimmed copy and serialization preserved capacity. Recording size as capacity would be a difference but not an incompatibility (objects serialized by both old and new implementations could be deserialized correctly by old and new).
---
I still believe that with the help of the gc team, one can cook up a trim-to-size when gc-ing fix, but that's going to be very hard to implement.
I'm saving my VM RFEs for split arrays, huge arrays, sparse arrays and array pinning. :-) Mike
---
On Mon, Apr 1, 2013 at 7:00 PM, Mike Duigou <mike.duigou@oracle.com> wrote: Hello all;
I have posted an updated version of the empty ArrayList and HashMap patch.
http://cr.openjdk.java.net/~mduigou/JDK-7143928/1/webrev/
This revised implementation introduces *no new fields* to either class. For ArrayList the lazy allocation of the backing array occurs only if the list is created at default size. According to our performance analysis team, approximately 85% of ArrayList instances are created at default size so this optimization will be valid for an overwhelming majority of cases.
For HashMap, creative use is made of the threshold field to track the requested initial size until the bucket array is needed. On the read side the empty map case is tested with isEmpty(). On the write size a comparison of (table == EMPTY_TABLE) is used to detect the need to inflate the bucket array. In readObject there's a little more work to try to choose an efficient initial capacity.
Mike
On Mar 26 2013, at 17:25 , Mike Duigou wrote:
Hello all;
This is a review for optimization work that came out of internal analysis of Oracle's Java applications. It's 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. This patch is not a substitute for pre-sizing your collections and maps--doing so will *always* have better results.
This patch extends HashMap and ArrayList to provide special handling for newly created instances that avoids creating the backing array until needed. There is a very small additional cost for detecting when to inflate the map or list that is measurable in interpreted tests but disappears in JITed code.
http://cr.openjdk.java.net/~mduigou/JDK-7143928/0/webrev/
We expect that should this code prove successful in Java 8 it will be backported to Java 7 updates.
The unit test may appear to be somewhat unrelated. It was created after resolving a bug in an early version of this patch to detect the issue encountered (LinkedHashMap.init() was not being called in readObject() when the map was empty).
Mike
participants (12)
-
Alan Bateman
-
Brent Christian
-
Brian Goetz
-
Doug Lea
-
Laurent Bourgès
-
mark.reinhold＠oracle.com
-
Martin Buchholz
-
Mike Duigou
-
Patrick Wright
-
Peter Levart
-
Remi Forax
-
Vitaly Davidovich