On Mon, 17 Oct 2022 10:19:26 GMT, Сергей Цыпанов <d...@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
