Optimized HashSet.toArray()

[Tagir Valeev]

Hello!

I think that HashSet.toArray(), HashMap.keySet().toArray() and
HashMap.values().toArray() methods are used often enough to deserve a
dedicated optimized implementation. Here's the patch I propose which
is based on KeySet#forEach and AbstractCollection#toArray
implementations:
http://cr.openjdk.java.net/~tvaleev/patches/hashset_toarray/patch.txt

I performed quick JMH test for HashSet.toArray(). The source code is here:
http://cr.openjdk.java.net/~tvaleev/patches/hashset_toarray/jmh/ToArray.java

Result on JDK 11+28 is here:
http://cr.openjdk.java.net/~tvaleev/patches/hashset_toarray/jmh/jmh_toArray_11.txt

Result on JDK 11+28 with patch applied is here
http://cr.openjdk.java.net/~tvaleev/patches/hashset_toarray/jmh/jmh_toArray_11_patched.txt

Summary (non-patched):
Benchmark                  (size)          Score          Error  Units
ToArray.toArray                 0          6,327 ±        0,094  ns/op
ToArray.toArray                 1         55,040 ±        0,389  ns/op
ToArray.toArray                10        112,903 ±        3,571  ns/op
ToArray.toArray              1000      11281,875 ±       74,423  ns/op
ToArray.toArray            100000    2795345,640 ±    57164,196  ns/op
ToArray.toArray          10000000  443763064,267 ± 82551994,563  ns/op
ToArray.toArrayPresized         0          8,244 ±        0,054  ns/op
ToArray.toArrayPresized         1         57,094 ±        0,431  ns/op
ToArray.toArrayPresized        10        105,456 ±        3,831  ns/op
ToArray.toArrayPresized      1000      11935,895 ±      251,150  ns/op
ToArray.toArrayPresized    100000    2771938,363 ±    42917,423  ns/op
ToArray.toArrayPresized  10000000  421335484,317 ± 66222482,723  ns/op
ToArray.toObjectArray           0          8,288 ±        0,060  ns/op
ToArray.toObjectArray           1         49,415 ±        2,454  ns/op
ToArray.toObjectArray          10         94,243 ±        2,346  ns/op
ToArray.toObjectArray        1000      10061,125 ±       77,197  ns/op
ToArray.toObjectArray      100000    2455011,037 ±    86539,734  ns/op
ToArray.toObjectArray    10000000  416595706,650 ± 84619961,188  ns/op

Summary (patched):
Benchmark                  (size)           Score          Error  Units
ToArray.toArray                 0           5,319 ±        0,050  ns/op
ToArray.toArray                 1          22,235 ±        0,365  ns/op
ToArray.toArray                10          57,515 ±        0,687  ns/op
ToArray.toArray              1000        6586,112 ±       71,258  ns/op
ToArray.toArray            100000     1700754,903 ±    41289,676  ns/op
ToArray.toArray          10000000   299815797,250 ± 37778823,759  ns/op
ToArray.toArrayPresized         0           6,689 ±        0,042  ns/op
ToArray.toArrayPresized         1          44,852 ±        0,813  ns/op
ToArray.toArrayPresized        10          66,904 ±        0,748  ns/op
ToArray.toArrayPresized      1000        7839,880 ±       75,954  ns/op
ToArray.toArrayPresized    100000     1605381,429 ±    55070,143  ns/op
ToArray.toArrayPresized  10000000   292954965,933 ± 45912224,761  ns/op
ToArray.toObjectArray           0           6,608 ±        0,049  ns/op
ToArray.toObjectArray           1          28,085 ±        0,326  ns/op
ToArray.toObjectArray          10          58,170 ±        2,716  ns/op
ToArray.toObjectArray        1000        5979,407 ±       55,930  ns/op
ToArray.toObjectArray      100000     1420318,139 ±    27226,724  ns/op
ToArray.toObjectArray    10000000   255417541,372 ± 33366555,142  ns/op

As you can see, the patched version is always faster, sometimes 2x and
even more. Also it doesn't allocate anything except the target array
when necessary (current version allocates an iterator).

If anybody is interested to sponsor this change, I can log a JBS issue
and provide proper webrev for review. Do we need to add new unit-tests
or these methods are covered enough by existing tests?

With best regards,
Tagir Valeev.