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
