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

[Tagir Valeev]

Hello, Roger!

Thank you for review.

HashMap:
>
> 927: Can keysToArray() be 'final'?
>

No, it's overridden in LinkedHashMap (where it's declared as final).
HashSet.toArray calls this method, and LinkedHashSet behavior should be
different (order should be preserved), so it's overridden.

Other suggestions are accepted in the new webrev:
http://cr.openjdk.java.net/~tvaleev/webrev/8225339/r2/


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

The doc will change for HashSet and LinkedHashSet as currently it says that
toArray methods are inherited from AbstractCollection which is not true
anymore.
For HashMap/LinkedHashMap doc should not change. I will post a specdiff to
CSR [1] once I figure out how to generate it. I searched over OpenJDK wiki,
but found no clue how to do it. Could anybody help me?

With best regards,
Tagir Valeev.

[1] https://bugs.openjdk.java.net/browse/JDK-8225393


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