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

[Tagir Valeev]

Hello!


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

Seems I was wrong here: JavaDoc for JDK is generated with
--override-methods=summary option, so the resulting spec should not be
different.
I will try to generate it before and after applying the patch.


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