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

[Paul Sandoz]

Hi Tagir,

Clearly I am a terribly tracker of null values! My apologies for the poor review of that.

Regarding changing sub-map computeIfAbsent and compute behavior, yes that would require a CSR.

Thinking more about this, it may be better to play it safe and retain the current behavior for this issue. We could always follow up with another change if necessary. In that respect +1 to your current patch.

It may be helpful to add a comment in the implementations of computeIfAbsent/compute saying the call to the mapping function when the key is out of range is to preserve the compatibly with the default methods on Map. No need for another review of that if you choose to add it.

Paul.

> On Aug 7, 2020, at 9:58 PM, Tagir Valeev <amaembo at gmail.com> wrote:
> 
> 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.
>>