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

[Martin Buchholz]

My ancient benchmark
test/jdk/java/util/Collection/IteratorMicroBenchmark.java
compares many toArray implementations, but none for Set or Map, and I feel
a little guilty about that (but I've been reluctant to give up the extra
testing for collections with duplicates)

(I used that benchmark to validate similar optimizations.)

On Wed, Jun 5, 2019 at 1:21 AM Tagir Valeev <amaembo at gmail.com> 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.
>