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

[Michal Vala]

thank you Roger, I've added jmh benchmark. see new webrev in reply to Martin's 
review.


On 12/12/18 4:45 AM, Roger Riggs wrote:
> Hi,
> 
> fyi, jmh tests appropriate for JDK apis are located in the test/micro/... 
> directories.
> 
> The benchmarks are built with:
>    % make build-microbenchmark
> 
> The results are in the build/<platform>/images/test/micro/benchmarks.jar
> 
> $.02, Roger
> 
> On 12/11/2018 A 9:55 PM, Martin Buchholz wrote:
>> Hi Michal, pleased to meet you.  I'll be your sponsor.
>>
>> The test will need a legal header, presumably similar to others authored by
>> redhatters.
>>
>> It is now possible to check in jmh microbenchmarks (but I've never done so
>> myself).
>>
>> The current coding style is non-standard, but deliberate; avoid gratuitous
>> changes like
>> -                Node<K,V> e;
>> +                Node<K, V> e;
>>
>> As author of concurrent/ConcurrentHashMap/WhiteBox.java ...
>> - I thought you'd need a @modules ... did this test actually pass?
>> - you should have some kind of @summary that includes the word "whitebox"
>> - why not "throws ReflectiveOperationException" ?
>> - your reviewer is a bit on the autistic side, so please change /** to /*
>> on the @test comment (it's not javadoc!)
>>
>>
>> On Tue, Dec 11, 2018 at 11:06 AM Michal Vala <mvala at redhat.com> wrote:
>>
>>> Hi,
>>>
>>> I've been looking into this bug in HashMap where resize() is called
>>> multiple
>>> times when putting whole map into another.
>>>
>>> I come up with following patch:
>>> http://cr.openjdk.java.net/~mvala/jdk/jdk/JDK-8210280/webrev.00/
>>>
>>> I've tried to do it as little invasive as possible. New resize(int) method
>>> is
>>> called just from putMapEntries for now. Notice that method is called with
>>> size
>>> of the new map. I was experimenting with calling it with 'size()+s', but
>>> this
>>> leads to unwanted space allocation when inserted map rewrites a lot of
>>> existing
>>> keys.
>>>
>>> I've benchmarked this with adding 10millions elements into existing map
>>> and it
>>> gets ~50% improvement:
>>>
>>> unpatched
>>> Benchmark                Mode  Cnt  Score   Error  Units
>>> MyBenchmark.testMethod  thrpt   10  1.248 ± 0.058  ops/s
>>>
>>> patched
>>> Benchmark                Mode  Cnt  Score   Error  Units
>>> MyBenchmark.testMethod  thrpt   10  1.872 ± 0.109  ops/s
>>>
>>> public class MyBenchmark {
>>>       static Map<Integer, Integer> mapTocopy = IntStream.range(1,
>>> 10_000_000).boxed().collect(Collectors.toMap(k -> k,
>>>               k -> k));
>>>
>>>       @Benchmark
>>>       public int testMethod() {
>>>           var map = new HashMap<Integer, Integer>();
>>>           map.put(-5, -5);
>>>           map.putAll(mapTocopy);
>>>           return map.size();
>>>       }
>>> }
>>>
>>> Any ideas for missed corner-cases or some good tests?
>>>
>>> -- 
>>> Michal Vala
>>> OpenJDK QE
>>> Red Hat Czech
>>>
> 

-- 
Michal Vala
OpenJDK QE
Red Hat Czech