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

[Paul Sandoz]

Hi Tagir,

Thanks for your measured patience. I will take a look.

Paul.

> On Jul 26, 2020, at 9:04 AM, Tagir Valeev <amaembo at gmail.com> wrote:
> 
> 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.