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

[Claes Redestad]

Hi Tagir,

how will this behave in the face of concurrent modification? I know the
current implementations deals with this in a best-effort kind of way
(since neither impl. is truly thread-safe).

I.e., the toArray methods of AbstractCollection that you're overriding
would catch this in iterator.next() calls and throw a CME, then still
deals with cases where the iterator returns more or fewer elements than
the initial size hint suggested. Without any safeguard, you might end up
with a case where toArray throws an IOOBE when racing with a put, which
seems particularly unfortunate.

With best regards

/Claes

On 2019-06-05 10:19, 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.
>