RFR JDK-7143928 : (coll) Optimize for Empty ArrayList and HashMap

Mike Duigou mike.duigou at oracle.com
Thu Mar 28 17:38:44 UTC 2013

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

More information about the core-libs-dev mailing list