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

[Tagir Valeev]

Hello!

A gentle ping: please review
https://bugs.openjdk.java.net/browse/JDK-8244288
http://cr.openjdk.java.net/~tvaleev/webrev/8244288/r1/
The details are listed below.

With best regards,
Tagir Valeev.

On Sun, May 3, 2020 at 4:36 PM Tagir Valeev <amaembo at gmail.com> wrote:
>
> 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.