JDK-8210280 - Unnecessary reallocation when invoking HashMap.putAll()

[Michal Vala]

All tests I've run passed, benchmarks show ~15% performance boost for 
putAllWithBigMapToNonEmptyMap.

On 12/17/18 7:32 AM, Michal Vala wrote:
> Hi,
> 
> thanks Doug, this is nice reduction.
> 
> Here's the new webrev: 
> http://cr.openjdk.java.net/~mvala/jdk/jdk/JDK-8210280/webrev.03/
> 
> Just a nitpick, issue is in using linked-list in buckets. The same is used for 
> both HashMap and LinkedHashMap, so mentioning just LinkedHashMap might be 
> confising. I've updated the comment s/LinkedHashMap/linked-list buckets/.
> 
> I'm just running tier1 tests and benchmarks.
> 
> On 12/16/18 3:23 PM, Doug Lea wrote:
>>
>> On 12/14/18 1:37 AM, Michal Vala wrote:
>>> Thanks Martin for finding this serious issue and the testcase.
>>>
>>
>> Sorry that I wasn't paying attention to this and so forced Martin to
>> discover the hard way that because of LinkeHashMap, you can't skip
>> doubling steps (at least not without a lot of rework). Also, the
>> documentation should have mentioned this. A simpler way to reduce
>> overhead in the case at hand is just to loop in putMapEntries:
>>
>> --- HashMap.java.~1.9.~    2018-11-11 15:43:24.982878495 -0500
>> +++ HashMap.java    2018-12-16 09:05:48.924727867 -0500
>> @@ -502,8 +502,13 @@
>>                   if (t > threshold)
>>                       threshold = tableSizeFor(t);
>>               }
>> -            else if (s > threshold)
>> -                resize();
>> +            else {
>> +                // Because of LinkedHashMap constraints, we cannot
>> +                // expand all at once, but can reduce total resize
>> +                // effort by repeated doubling now vs later
>> +                while (table.length <  MAXIMUM_CAPACITY && s > threshold)
>> +                    resize();
>> +            }
>>               for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
>>                   K key = e.getKey();
>>                   V value = e.getValue();
>>
> 

-- 
Michal Vala
OpenJDK QE
Red Hat Czech