RFR: 8293630: Simplify TreeMap.get() with Comparator.naturalOrder() [v4]

[Сергей Цыпанов]

On Mon, 17 Oct 2022 10:19:26 GMT, Сергей Цыпанов <duke at openjdk.org> wrote:

>> 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?
>
> Сергей Цыпанов has updated the pull request incrementally with one additional commit since the last revision:
> 
>   8293630: Inline natural()

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

-------------

PR: https://git.openjdk.org/jdk/pull/9901