JDK-8227666 : Provide specialized implementation for default methods putIfAbsent, computeIfAbsent, computeIfPresent, compute, merge in TreeMap
  • Type: CSR
  • Component: core-libs
  • Sub-Component: java.util:collections
  • Priority: P4
  • Status: Closed
  • Resolution: Approved
  • Fix Versions: 15
  • Submitted: 2019-07-15
  • Updated: 2020-05-31
  • Resolved: 2020-03-07
Related Reports
CSR :  
Description
Summary
-------

Specialized implementations of the `TreeMap` methods `putIfAbsent`, `computeIfAbsent`, `computeIfPresent`, `compute`, and `merge` are introduced.

Problem
-------

Default implementations of the `putIfAbsent`, `computeIfAbsent`, `computeIfPresent`, `compute`, and `merge` methods provided by `AbstractMap` delegate to the `get`, `put`, and `remove` methods, which may require traversing the tree twice. An optimized implementation can traverse the tree only once. This can provide a noticeable speedup, especially if the comparison method is expensive.

Solution
--------

Provide optimized implementations for these methods, similar to `HashMap`.

Specification
-------------
* As `TreeMap` now overrides the methods `putIfAbsent`, `computeIfAbsent`, `computeIfPresent`, `compute`, and `merge`, the `implSpec` section specified for the corresponding default methods in the `Map` interface is no longer relevant to `TreeMap` methods.

* The specification for the `TreeMap` method `computeIfAbsent` now additionally covers the concurrent update policy, as follows:

```
     * <p>This method will, on a best-effort basis, throw a
     * {@link ConcurrentModificationException} if it is detected that the
     * mapping function modifies this map during computation.
     *
     * @throws ConcurrentModificationException if it is detected that the
     * mapping function modified this map
```

* The specifications for the `TreeMap` methods `computeIfPresent`, `compute`, and `merge` now additionally cover the concurrent update policy, as follows:

```
     * <p>This method will, on a best-effort basis, throw a
     * {@link ConcurrentModificationException} if it is detected that the
     * remapping function modifies this map during computation.
     *
     * @throws ConcurrentModificationException if it is detected that the
     * remapping function modified this map
```

These additions are exactly copied from the specification of the corresponding `HashMap` methods.

Comments
Moving to Approved.
07-03-2020

I'm ok with this proceeding as it stands.
07-03-2020

[~tvaleev], when you and [~smarks] agree to proceed, please Finalize the request to request the second phase of CSR review.
06-03-2020

So is any action required from my side? Stuart's argument sounds reasonable.
06-03-2020

I've been thinking about the use of `@implSpec` here, and I've come to the conclusion that we do **not** want to use it in this case. (Good question though Joe, thanks for raising it.) I owe a writeup on `@implSpec`. Briefly though, it's used to impose requirements on the method implementation in **this** class, and its primary use is for subclassers who need to determine whether they can inherit the method or whether they need to override it, and if they do, what behaviors they can rely on if they were to call `super.method()`. In general we don't guarantee release-to-release compatibility for subclasses of the concrete collections implementations. For example, people have subclassed and overridden methods of `ArrayList` in order to get a `List` that has different behavior. Historically they've been broken every time we've rearranged something in the implementation. By contrast, we **do** guarantee compatibility for implementations of interfaces that inherit/use default methods, and for subclasses of the `AbstractX` family of collections. Those are cases where we want to use `@implSpec`. Based on this, I do not think we want to start providing information for subclassers of `TreeMap`, as we don't guarantee anything in particular about the behaviors of its methods, beyond conforming to the contracts in the interfaces.
02-03-2020

[~tvaleev], I suggest starting with the implSpec tags in the Abstract* classes in java.util, AbstractCollection, AbstractList, AbstractMap, etc. HTH
25-02-2020

Thank you for moving this forward! > Would the new text "This method will, on a best-effort basis, throw a {@link ConcurrentModificationException}..." be better as an @implSpec tag? Note that we also have a `@throws` tag now. I'm not sure whether it's ok if the throws tag describes the exception that is described in implSpec. Or probably we should remove the throws tag if we move this text under the implSpec? > As TreeMap is a non-final class, are there any self-use aspects of the implementation that should be documented on the behalf of subclassers? Are there any examples showing how and where it could be written?
23-02-2020

I'm advancing this request to the intermediate Provisional state since I have a few questions. Once the questions are answered, I anticipate the request can quickly be moved to approved, possibly with some modifications. Would the new text "This method will, on a best-effort basis, throw a {@link ConcurrentModificationException}..." be better as an @implSpec tag? As TreeMap is a non-final class, are there any self-use aspects of the implementation that should be documented on the behalf of subclassers? The same question apply to the existing specs for the overridden methods in HashMap. If it is decided HashMap changes are needed, I'd be fine with that work being done under another bug.
22-02-2020

[~tvaleev] I've done an editing pass and have added myself as a reviewer. Since this has languished so long I took the liberty of moving it forward to the Finalized state. (To do so I had to temporarily assign it to myself.) Sorry for the delays with this.
22-02-2020

Thank you Joe. I updated the description above to reflect the spec changes. Is it better now?
13-10-2019

Looking at the webrev, http://cr.openjdk.java.net/~tvaleev/webrev/8176894/r2/ I believe the CSR involves some spec changes, for the concept of "spec" used in the CSR. For example, the putIfAbsent default method defined in java.util.Map states: "If the specified key is not already associated with a value (or is mapped to null) associates it with the given value and returns null, else returns the current value." An implSpec tag then describes how the implementation works in terms of self-use of other methods on Map and gives disclaimers about concurrency, etc. The altered self-use, if any, different concurrency properties, etc. should be considered part of the specification and included in the CSR. For example, the computeIfAbsent update: 612 /** 613 * {@inheritDoc} 614 * 615 * <p>This method will, on a best-effort basis, throw a 616 * {@link ConcurrentModificationException} if it is detected that the 617 * remapping function modifies this map during computation. 618 * 619 * @throws ConcurrentModificationException if it is detected that the 620 * remapping function modified this map 621 */ 622 @Override 623 public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) { includes a spec change that should be reviewed in the CSR. HTH
23-09-2019