RFR(s): 8176894 Provide specialized implementation for default methods putIfAbsent, computeIfAbsent, computeIfPresent, compute, merge in TreeMap

[Sergey Kuksenko]

Thanks! Looks good.

The only I have comments for added microbenchmark:

* Keys and values should be preallocated in setup. We want to measure TreeMap, not boxing. I'd prefer to see preallocated array of keys.

* What is the reason to have "shuffled" parameter? Random keys distribution is more preferable.

* pairs of similar operations looks weird. I mean code like this:
            bh.consume(map.put(key, key));
            bh.consume(map.put(key, key));
   The second put has advantage due to the fact that all required data is in CPU cache already. If we want to take into account operations over existing keys - it would be better to have two keys in the preallocated array. If array of keys is shuffled -> put operations for equal keys won't be following as sequentially. I think it will be closer to real behavior.
  
* general notice about random keys. Typically I use the following scheme:

@Param("0")
long seed;

@Setup()
public void setup() {
    Random rnd = seed==0 ? new Random() : new Random(seed);
    // use rnd for generating data
}

In default case we always generates random data and cover quite nice distribution of really random cases. But if we found some "bad" behavior in some cases or we want to fix sequence of out tree modifications - we always may setup seed parameter as we wish and make it fixed.

On 10/13/19 2:51 AM, Tagir Valeev wrote:
> Hello!
>
> Please review the updated patch (no sponsorship is necessary; review only):
> https://cr.openjdk.java.net/~tvaleev/webrev/8176894/r3/
> https://bugs.openjdk.java.net/browse/JDK-8176894
>
> The difference from the previous version [1] is minimal: I just
> noticed that the specification for computeIfAbsent should say
> "mapping" instead of "remapping", so I fixed the spec. No changes in
> code/tests.
>
> Also please review the associated CSR:
> https://bugs.openjdk.java.net/browse/JDK-8227666
> I updated it, according to Joe Darcy's comments.
>
> An additional explanation and background is copied below from my
> original e-mail [2] for your convenience:
>
> The patch was originally submitted by Sergey Kuksenko in March 2017 and
> reviewed by some people:
> http://mail.openjdk.java.net/pipermail/core-libs-dev/2017-March/046825.html
> The latest patch submitted by Sergey is here:
> http://cr.openjdk.java.net/~skuksenko/corelibs/utils/8176894/webrev.01/
>
> I asked Sergey why it was abandoned. Seems there were no particular reason
> and Sergey asked if I could pick up this work. I will be happy to finish it.
>
> Here's the list of differences between the latest Sergey patch and my patch:
> - A bug is fixed in putIfAbsent implementation. TreeMap.java, lines 576 and
> 596:  `|| oldValue == null` condition added (the null value should be
> overwritten no matter what)
> - A testcase is added to cover this problem (InPlaceOpsCollisions.java,
> also checks HashMap and LinkedHashMap). Not sure if it's the best place for
> such test though. Probably a separate file would be better?
> - TreeMap.merge() implementation is added.
> - TreeMap is added to the FunctionalCMEs.java test (btw this file copyright
> says that it's a subject to Classpath exception which is probably wrong?)
> - Simple microbenchmark is added: TreeMapUpdate.java
>
> My quick benchmarking shows that optimized version is indeed faster for the
> most of the tests and no regression is observed for put() method. Here's
> raw results of jdk13-ea+26 and jdk13-ea+26+patch if anybody is interested.
> http://cr.openjdk.java.net/~tvaleev/jmh/JDK-8176894/
>
> With best regards,
> Tagir Valeev.
>
> [1] https://cr.openjdk.java.net/~tvaleev/webrev/8176894/r2/
> [2] https://mail.openjdk.java.net/pipermail/core-libs-dev/2019-July/061309.html