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

[Tagir Valeev]

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.