RFR: JDK-8244288 Specialized implementations for putIfAbsent, merge, compute* methods in TreeMap derived maps

[Tagir Valeev]

Hello!

Please review the following change:
https://bugs.openjdk.java.net/browse/JDK-8244288
http://cr.openjdk.java.net/~tvaleev/webrev/8244288/r1/

We already implemented putIfAbsent, merge, computeIfAbsent,
computeIfPresent, and compute for TreeMap class (see JDK-8176894).
However, default implementations of these methods are still used for
TreeMap derived maps, such as descendingMap(), tailMap(), headMap()
and subMap(). The implementation is pretty straightforward, just a
range-check+delegation for each of these methods inside the
TreeMap.NavigableSubMap (+32 lines in TreeMap.java). Care should be
taken to avoid throwing IAE from compute* methods if the key is
outside of the range but we don't actually add the entry. This mimics
the previous behavior and also consistent with other modification
methods like Map.remove (we don't throw from remove if the key is out
of range, simply do nothing).

To cover these changes with tests, I added new
TreeMap().descendingMap() to
InPlaceOpsCollisions.nullValueFriendlyMaps and
MapWithCollisionsProviders.makeMapsMoreTypes. This map should behave
like a normal Map modulo iteration order but implementation goes
through NavigableSubMap. Also, I added more adders to
LockStep::randomAdder (lines 572+) to cover new methods, as well as
some more throws IAE asserts around line 806. At the same time, I took
the liberty to modernize this test:
- Convert all the raw-types to properly parameterized (using 'var' for
local vars where resulting type is long)
- Convert MapFrobber and SetFrobber to interfaces, and convert all the
implementations to lambdas (automatic conversion via IntelliJ IDEA +
rename of conflicting parameter names)
- Use for-each loop instead of indexed for loop where possible
- 'elts' array was created in two places but unused afterward. I added
size assert to these arrays to use it at least somehow (though
probably content should be checked as well).
- Use Comparator.naturalOrder() instead of manually written one in
comparator() methods (should not affect the testing in any way as it's
only used directly, not passed e.g. to TreeMap constructor).
- Use Objects.equals inside LockStep#equal
- Inverted 'if' at line 299 to avoid empty block.
If the cleanup really complicates the review I can post the cleanup as
a separate changeset. Though it should not be very problematic as the
actual changes are quite compact (as said above, near lines 572 and
806)

I also improved the previously added benchmark TreeMapUpdate to check
descendingMap and tailMap cases to confirm the hypothesis that the
change improves the performance of derived maps. This is indeed the
case. E.g. merge test yields (comparator = false, size = 1000) for
unpatched JDK:

(benchmark)                 (mode) (prefill)    Score      Error  Units
TreeMapUpdate.merge        TreeMap   true   63589,075 ± 1028,065  ns/op
TreeMapUpdate.merge        TreeMap  false   65414,367 ± 1011,442  ns/op
TreeMapUpdate.merge  descendingMap   true  121501,618 ± 1849,108  ns/op
TreeMapUpdate.merge  descendingMap  false   95913,212 ± 2854,063  ns/op
TreeMapUpdate.merge        tailMap   true  126657,309 ± 4467,733  ns/op
TreeMapUpdate.merge        tailMap  false   93448,840 ± 1359,392  ns/op

As you can see, the merge on derived maps is significantly slower.
After the patch is applied the results are much better:

(benchmark)                 (mode)  (prefill)     Score      Error  Units
TreeMapUpdate.merge        TreeMap       true 64059,189 ±  808,230  ns/op
TreeMapUpdate.merge        TreeMap      false 65156,912 ± 1229,965  ns/op
TreeMapUpdate.merge  descendingMap       true 69938,131 ± 1697,357  ns/op
TreeMapUpdate.merge  descendingMap      false 67783,829 ±  263,061  ns/op
TreeMapUpdate.merge        tailMap       true 71079,529 ±  841,738  ns/op
TreeMapUpdate.merge        tailMap      false 68577,169 ± 1196,758  ns/op

I don't think this requires a CSR, as the changed class is
package-private, so it cannot be extended by clients.

With best regards,
Tagir Valeev.