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

[Tagir Valeev]

Hello, Paul!

Thank you for the review.

> The putIfAbsent and merge implementations result in a change of behavior. For putIfAbsent, a key out-of-range now results in an exception rather than returning null.

No, the semantics is preserved. Before this change, putIfAbsent also
throws for out-of-range key. The default implementation looks like
this:

V v = get(key); // always returns null for out-of-range key
if (v == null) { // if is always visited
    v = put(key, value); // put always throws for out-of-range key
}
return v;

The following test confirms that the behavior is preserved:

var map = IntStream.range(1, 10).boxed()
    .collect(Collectors.toMap(x -> x, String::valueOf, (a, b) -> a,
TreeMap::new));
var subMap = map.subMap(1, 5);
subMap.putIfAbsent(6, "6");

> For merge, if the new value is null, then remove is called which also returns null for a key out-of-range.

The new value in merge cannot be null, both by Map::merge spec (@param
value the non-null value to be merged...) and by implementation
(Objects.requireNonNull(value) is called). The remapping function is
never called for out-of-range key because the old value is always
null. Thus the 'remove' call is unreachable for out-of-range key and
my patch preserves this behavior.

> I am inclined to also change the behavior of other modification methods, compute and computeIfAbsent, to always throw if the key is out-of-range, rather than check the result of the mapping function. i.e. an out-of-range key is never passed to the mapping function.
>
> That’s a wider change in behavior but I suspect one that has minimal impact. (In hindsight if we were implementing these methods when we added the defaults in 8 I would like to think this is the behavior we, or at least I :-), would of implemented.)

I believe this change would require CSR, right?

With best regards,
Tagir Valeev.

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