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

[Tagir Valeev]

Hello, Claes!

Yes, it's true that CME will not be thrown anymore. Depending on the
concurrent modification kind one might face various ranges of incorrect
behavior, including the AIOOBE, NPE or incorrect array returned. As
Collection spec says [1]:
> In the absence of a stronger guarantee by the implementation, undefined
behavior may result from the invocation of any method on a collection that
is being mutated by another thread

In particular it's never mentioned in HashSet, HashMap or Collection spec
that toArray implements a fail-fast behavior: this is said only about the
iterator() method. Also note that ArrayList and LinkedList toArray
implementation also never throws CME. LinkedHashSet.toArray in my patch is
pretty similar to LinkedList.toArray. So I feel that such change is
perfectly acceptable: toArray method has no moral obligation to fail fast,
and there's no reason why it should be more "robust" for HashSet than for
LinkedList. or ArrayList.

Finally I should note that there are even more unfortunate examples of
behavior during the concurrent modification. In particular, querying a
TreeMap element during the concurrent update may cause an infinite loop
which is usually much more unpleasant than random exception.

With best regards,
Tagir Valeev.

[1]
https://docs.oracle.com/en/java/javase/12/docs/api/java.base/java/util/Collection.html

On Wed, Jun 5, 2019 at 6:32 PM Claes Redestad <claes.redestad at oracle.com>
wrote:

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