RFR JDK-8225339 Optimize HashMap.keySet()/HashMap.values()/HashSet toArray() methods

[Roger Riggs]

Hi Tagir,

A few comments:

HashMap:

927: Can keysToArray() be 'final'?

953, 954, 1003:  Please put the body of the methods on a separate line 
and separate methods with a blank line to keep it from all running together.

HashSet:

362, 366, Add @Override

LinkedHashMap:

565, 566: Please put the body of the methods on a separate line and 
separate methods with a blank line to keep it from all running together.

And its worth generating the javadoc and checking it appears unchanged.

ToArray test:

The other tests in that directory put the main() method first and work 
down to the individual test methods.
Please re-order.

Thanks, Roger



On 06/05/2019 04:19 AM, Tagir Valeev wrote:
> Hello!
>
> Please review the specialized implementation of toArray method in
> (Linked)HashMap/HashSet:
> https://bugs.openjdk.java.net/browse/JDK-8225339
> http://cr.openjdk.java.net/~tvaleev/webrev/8225339/r1/
>
> Here's shortened benchmark output for keySet().toArray() ( KeySetToArray  )
> and keySet().toArray(new String[0]) (KeySetToArrayTyped):
> Benchmark               (mapType)  (size)      C2-orig  C2-patched
> Graal-orig Graal-patched
> KeySetToArray             HashMap       0        7.504       7.267
> 13.195         6.404
> KeySetToArray             HashMap       1       43.222      27.720
> 50.093        26.623
> KeySetToArray             HashMap      10      101.087      51.778
>   116.605        59.520
> KeySetToArray             HashMap    1000     8546.031    4008.694
>   11216.667      5726.983
> KeySetToArray             HashMap  100000  1619722.598  574863.302
>   1467273.538    910837.681
> KeySetToArray       LinkedHashMap       0        7.830       6.479
> 12.944         6.187
> KeySetToArray       LinkedHashMap       1       18.644       9.369
> 18.499        10.375
> KeySetToArray       LinkedHashMap      10       57.622      32.903
> 71.410        37.072
> KeySetToArray       LinkedHashMap    1000     5041.059    4563.318
> 6020.531      4348.969
> KeySetToArray       LinkedHashMap  100000   949706.126  737959.825
> 873106.291    839018.677
> KeySetToArrayTyped        HashMap       0        5.578       5.112
> 16.265         4.860
> KeySetToArrayTyped        HashMap       1       42.162      21.757
> 54.329        29.137
> KeySetToArrayTyped        HashMap      10       99.719      47.455
>   126.767        63.958
> KeySetToArrayTyped        HashMap    1000    10961.851    4251.996
>   11908.622      5760.225
> KeySetToArrayTyped        HashMap  100000  1647795.795  759171.750
>   1601851.965    915145.116
> KeySetToArrayTyped  LinkedHashMap       0        5.531       4.928
> 12.524         5.090
> KeySetToArrayTyped  LinkedHashMap       1       22.017      10.534
> 26.641        15.983
> KeySetToArrayTyped  LinkedHashMap      10       64.832      36.017
> 88.757        41.172
> KeySetToArrayTyped  LinkedHashMap    1000     5265.125    4492.492
> 6979.131      4394.444
> KeySetToArrayTyped  LinkedHashMap  100000  1003702.468  818225.090
> 985088.932    809797.822
>
> For values().toArray() the results are very similar. Complete JMH output is
> here:
> http://cr.openjdk.java.net/~tvaleev/jmh/JDK-8225339/
> Benchmark source is included into the patch
>
> As you can see, speedup is observed in every test. For HashMap it's about
> 2x, for LinkedHashMap it's usually smaller (presumably because the
> LinkedHashIterator state is simpler than HashIterator).
>
> I also added some unit-tests for toArray methods (HashMap/ToArray.java). I
> put it inside HashMap folder as most of changes are in HashMap class. As
> this patch should preserve the semantics, unit-tests pass on both
> non-patched and patched version.
>
> With best regards,
> Tagir Valeev.