8293630: Simplify TreeMap.get() with Comparator.naturalOrder()

[stsypanov]

We can use Comparator.naturalOrder() for cases when a TreeMap instance is constructed without comparator. This allows to squash two branches in TreeMap.get() into one.

P.S. I think the comment of TreeMap.getEntryUsingComparator() is outdated. Should we also change it?

---

Progress

• [ ] Change must be properly reviewed (1 review required, with at least 1 Reviewer)
• [x] Change must not contain extraneous whitespace
• [x] Commit message must refer to an issue

Issue

• JDK-8293630: Simplify TreeMap.get() with Comparator.naturalOrder()

Reviewing

Using git

Checkout this PR locally:
$ git fetch https://git.openjdk.org/jdk pull/9901/head:pull/9901
$ git checkout pull/9901

Update a local copy of the PR:
$ git checkout pull/9901
$ git pull https://git.openjdk.org/jdk pull/9901/head

Using Skara CLI tools

Checkout this PR locally:
$ git pr checkout 9901

View PR using the GUI difftool:
$ git pr show -t 9901

Using diff file

Download this PR as a diff file:
https://git.openjdk.org/jdk/pull/9901.diff

[bridgekeeper[bot]]

:wave: Welcome back stsypanov! A progress list of the required criteria for merging this PR into master will be added to the body of your pull request. There are additional pull request commands available for use with this pull request.

[openjdk[bot]]

@stsypanov The following label will be automatically applied to this pull request:

• core-libs

When this pull request is ready to be reviewed, an "RFR" email will be sent to the corresponding mailing list. If you would like to change these labels, use the /label pull request command.

[openjdk[bot]]

⚠️ @stsypanov This pull request contains merges that bring in commits not present in the target repository. Since this is not a "merge style" pull request, these changes will be squashed when this pull request in integrated. If this is your intention, then please ignore this message. If you want to preserve the commit structure, you must change the title of this pull request to Merge <project>:<branch> where <project> is the name of another project in the OpenJDK organization (for example Merge jdk:master).

[mlbridge[bot]]

Webrevs

• 04: Full - Incremental (ca1d40b6)
• 03: Full - Incremental (ae6e2320)
• 02: Full - Incremental (a55957e9)
• 01: Full - Incremental (ab4cfa2c)
• 00: Full (259348a7)

[bridgekeeper[bot]]

@stsypanov This pull request has been inactive for more than 4 weeks and will be automatically closed if another 4 weeks passes without any activity. To avoid this, simply add a new comment to the pull request. Feel free to ask for assistance if you need help with progressing this pull request towards integration!

[stsypanov]

Let's wait

[amaembo]

I saw this code many times and always thought that it exists for performance purposes, to avoid extra indirection via likely megamorphic naturalOrder comparator which will slow down the operations on common path. I think such a simplification could be accepted only if accompanied by a properly written benchmark (which actually emulates megamorphic callsite) which shows no performance regression.

[stsypanov]

@amaembo you mean we should have a benchmark measuring a TreeMap.get() with lots of implementations of Comparators or Comparables?

[amaembo]

@stsypanov all operations involving the code paths touched by your refactorings. Well, get() is the most interesting one. Comparable.naturalOrder() should be actually used in many other contexts (e.g., in setup phase of the benchmark) often enough to pollute the type profile. Well, probably there are some compiler control options to automate this but I'm not aware. I would also check inlining log to ensure whether comparator is devirtualized and inlined or not. If inlined, then it's unlikely that you've polluted the type profile successfully.

[stsypanov]

For the benchmark

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Warmup(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 15, time = 2, timeUnit = TimeUnit.SECONDS)
@Fork(10)
@State(Scope.Thread)
public class TreeMapGet {

    @Param({"10", "100", "1000", "10000"})
    public int size;

    @Param({"true", "false"})
    public boolean comparator;

    private TreeMap<Integer, Integer> map;
    private Integer[] keys;

    @Setup(Level.Iteration)
    public void setUp() {
        map = comparator ? new TreeMap<>(Comparator.reverseOrder()) : new TreeMap<>();
        keys = IntStream.range(0, size).boxed().toArray(Integer[]::new);
        Collections.reverse(Arrays.asList(keys));
        for (Integer key : keys) {
            map.put(key, key);
        }
    }

    @Benchmark
    public void get(Blackhole bh) {
        var keys = this.keys;
        var map = this.map;
        for (Integer key : keys) {
            bh.consume(map.get(key));
        }
    }
}

I got these results:

baseline

Benchmark       (comparator)  (size)  Mode  Cnt       Score      Error  Units
TreeMapGet.get          true      10  avgt  150      69.170 ±    0.886  ns/op
TreeMapGet.get          true     100  avgt  150    1369.488 ±   36.312  ns/op
TreeMapGet.get          true    1000  avgt  150   31462.583 ±  261.650  ns/op
TreeMapGet.get          true   10000  avgt  150  490948.456 ± 3395.402  ns/op
TreeMapGet.get         false      10  avgt  150      69.625 ±    0.975  ns/op
TreeMapGet.get         false     100  avgt  150    1076.163 ±   30.976  ns/op
TreeMapGet.get         false    1000  avgt  150   36528.309 ±  140.245  ns/op
TreeMapGet.get         false   10000  avgt  150  422948.634 ±  976.892  ns/op

patch

Benchmark       (comparator)  (size)  Mode  Cnt       Score      Error  Units
TreeMapGet.get          true      10  avgt  150      68.814 ±    1.221  ns/op
TreeMapGet.get          true     100  avgt  150    1280.799 ±   34.319  ns/op
TreeMapGet.get          true    1000  avgt  150   31530.447 ±  329.406  ns/op
TreeMapGet.get          true   10000  avgt  150  435109.171 ± 1807.717  ns/op
TreeMapGet.get         false      10  avgt  150      65.646 ±    0.124  ns/op
TreeMapGet.get         false     100  avgt  150    1083.535 ±   23.545  ns/op
TreeMapGet.get         false    1000  avgt  150   36299.345 ±  494.126  ns/op
TreeMapGet.get         false   10000  avgt  150  444266.085 ± 2315.616  ns/op

For benchmark

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Warmup(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 15, time = 2, timeUnit = TimeUnit.SECONDS)
@Fork(10)
@State(Scope.Thread)
public class TreeMapEntrySetStream {

    @Param({"10", "100", "1000", "10000"})
    public int size;

    @Param({"true", "false"})
    public boolean comparator;

    private TreeMap<Integer, Integer> map;

    @Setup(Level.Iteration)
    public void setUp() {
        map = comparator ? new TreeMap<>(Comparator.reverseOrder()) : new TreeMap<>();
        var keys = IntStream.range(0, size).boxed().toArray(Integer[]::new);
        Collections.reverse(Arrays.asList(keys));
        for (Integer key : keys) {
            map.put(key, key);
        }
    }

    @Benchmark
    public void get(Blackhole bh) {
        var map = this.map;
        map.entrySet().stream().forEach(bh::consume);
    }
}

results are the following:

baseline

Benchmark                  (comparator)  (size)  Mode  Cnt      Score     Error  Units
TreeMapEntrySetStream.get          true      10  avgt  150     32.714 ±   0.117  ns/op
TreeMapEntrySetStream.get          true     100  avgt  150    271.825 ±   0.596  ns/op
TreeMapEntrySetStream.get          true    1000  avgt  150   3267.876 ±  42.650  ns/op
TreeMapEntrySetStream.get          true   10000  avgt  150  43207.384 ± 457.110  ns/op
TreeMapEntrySetStream.get         false      10  avgt  150     30.863 ±   0.071  ns/op
TreeMapEntrySetStream.get         false     100  avgt  150    259.394 ±   0.493  ns/op
TreeMapEntrySetStream.get         false    1000  avgt  150   3362.446 ±  44.108  ns/op
TreeMapEntrySetStream.get         false   10000  avgt  150  42190.313 ± 421.604  ns/op

patch

Benchmark                  (comparator)  (size)  Mode  Cnt      Score     Error  Units
TreeMapEntrySetStream.get          true      10  avgt  150     30.856 ±   0.112  ns/op
TreeMapEntrySetStream.get          true     100  avgt  150    270.719 ±   0.504  ns/op
TreeMapEntrySetStream.get          true    1000  avgt  150   3278.241 ±  41.304  ns/op
TreeMapEntrySetStream.get          true   10000  avgt  150  42549.518 ± 427.607  ns/op
TreeMapEntrySetStream.get         false      10  avgt  150     31.780 ±   0.092  ns/op
TreeMapEntrySetStream.get         false     100  avgt  150    252.551 ±   0.414  ns/op
TreeMapEntrySetStream.get         false    1000  avgt  150   3359.962 ±  44.337  ns/op
TreeMapEntrySetStream.get         false   10000  avgt  150  41613.570 ± 381.721  ns/op

[bridgekeeper[bot]]

@stsypanov This pull request has been inactive for more than 4 weeks and will be automatically closed if another 4 weeks passes without any activity. To avoid this, simply add a new comment to the pull request. Feel free to ask for assistance if you need help with progressing this pull request towards integration!

[bridgekeeper[bot]]

@stsypanov This pull request has been inactive for more than 8 weeks and will now be automatically closed. If you would like to continue working on this pull request in the future, feel free to reopen it! This can be done using the /open pull request command.