Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
CompTestBenchmark by Aleksey Shipilev
package comp;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.Fork;
import org.openjdk.jmh.annotations.Measurement;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.Setup;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Warmup;
import java.util.Comparator;
import java.util.List;
import java.util.concurrent.TimeUnit;
import java.util.function.Function;
import java.util.function.ToIntFunction;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
@Warmup(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
@Fork(3)
@State(Scope.Thread)
public class FixedCompTestBenchmark {
/*
Benchmark Mode Cnt Score Error Units
FixedCompTestBenchmark.bmCustomComparator thrpt 15 14185.620 ± 119.578 ops/s
FixedCompTestBenchmark.bmJDKComparator thrpt 15 3394.244 ± 28.449 ops/s
FixedCompTestBenchmark.bmNoVTLComparator thrpt 15 6348.175 ± 147.335 ops/s
FixedCompTestBenchmark.bmNoVTLOrAutoBoxingComparator thrpt 15 13020.958 ± 332.037 ops/s
*/
List<MyComparableInt> myComparableList;
@Setup
public void init() {
myComparableList = IntStream.range(0, 1_000)
.mapToObj(i -> new MyComparableInt(i))
.collect(Collectors.toList());
}
/*
-prof stack:
....[Thread state: RUNNABLE]........................................................................
43.1% 43.1% java.util.TimSort.binarySort
15.9% 15.9% java.util.TimSort.mergeLo
10.9% 10.9% java.util.stream.SortedOps$SizedRefSortingSink.end
8.7% 8.7% java.util.TimSort.mergeHi
7.4% 7.4% java.util.TimSort.gallopRight
6.8% 6.8% java.util.TimSort.gallopLeft
3.9% 3.9% java.util.Arrays.sort
1.2% 1.2% java.util.TimSort.sort
1.0% 1.0% java.util.TimSort.mergeAt
0.8% 0.8% java.util.ArrayList.ensureExplicitCapacity
0.2% 0.2% <other>
-prof perfasm:
....[Hottest Methods (after inlining)]..............................................................
31.69% 32.58% java.util.TimSort::sort
15.48% 16.56% java.util.TimSort::mergeLo
9.78% 9.78% <stub: _shouldnotreachhere 233 _shouldnotreachhere>
8.34% 7.99% java.util.stream.ReferencePipeline::collect
6.66% 6.60% java.util.TimSort::mergeLo; java.util.TimSort::gallopRight
6.59% 6.48% java.util.TimSort::gallopLeft
5.93% 6.09% java.util.TimSort::mergeHi
5.32% 5.44% comp.FixedCompTestBenchmark::bmCustomComparator
3.48% 2.76% <kernel>
1.45% 1.02% java.util.ArrayList::ensureExplicitCapacity
0.79% 0.51% java.util.TimSort::mergeAt
0.33% 0.08% SpinPause (libjvm.so)
0.31% 0.19% java.util.ArrayList::grow
0.23% 0.31% vfprintf (libc-2.19.so)
0.15% 0.15% _IO_fwrite (libc-2.19.so)
0.13% 0.03% print_insn (libhsdis-amd64.so)
0.11% 0.25% RelocIterator::initialize(nmethod*, unsigned char*, unsigned char*) (libjvm.so)
0.11% 0.15% StringTable::unlink_or_oops_do(BoolObjectClosure*, OopClosure*, int*, int*) (libjvm.so)
0.11% 0.09% outputStream::update_position(char const*, unsigned long) (libjvm.so)
0.11% 0.20% xmlTextStream::write(char const*, unsigned long) (libjvm.so)
2.91% 1.82% <...other 134 warm methods...>
....................................................................................................
Comparator had inlined, need to look into the hottest regions disassembly to verify what's going
on there.
*/
@Benchmark
public Object bmCustomComparator() {
return myComparableList.stream()
.sorted(MyComparableIntSorter.INSTANCE)
.collect(Collectors.toList());
}
/*
-prof stack:
....[Thread state: RUNNABLE]........................................................................
80.4% 80.4% java.util.Comparator.lambda$comparing$77a9974f$1
7.9% 7.9% java.util.Comparator.lambda$thenComparing$36697e65$1
2.5% 2.5% java.util.TimSort.binarySort
2.3% 2.3% java.util.TimSort.mergeLo
1.4% 1.4% java.util.ArrayList.ensureCapacityInternal
1.2% 1.2% java.util.TimSort.mergeHi
0.8% 0.8% java.util.TimSort.gallopRight
0.6% 0.6% java.util.stream.SortedOps$SizedRefSortingSink.end
0.4% 0.4% java.util.TimSort.minRunLength
0.4% 0.4% java.util.TimSort.mergeAt
2.1% 2.1% <other>
-prof perfasm:
....[Hottest Methods (after inlining)]..............................................................
23.39% 26.28% java.util.Comparator$$Lambda$11::compare
15.60% 14.55% comp.FixedCompTestBenchmark$$Lambda$6::apply; java.util.ArrayList::add
12.07% 10.73% java.util.TimSort::binarySort
9.89% 11.82% comp.FixedCompTestBenchmark$$Lambda$7::apply; java.util.Comparator$$Lambda$10::compare
5.89% 5.57% java.lang.Class::getComponentType; comp.FixedCompTestBenchmark$$Lambda$8::apply
5.39% 4.75% <kernel>
5.32% 5.63% java.util.TimSort::mergeLo
3.38% 2.47% <stub: _shouldnotreachhere 233 _shouldnotreachhere>
2.55% 2.72% java.util.TimSort::gallopRight
2.50% 2.15% java.util.TimSort::gallopLeft
2.43% 2.42% comp.FixedCompTestBenchmark::bmJDKComparator
2.20% 2.09% java.util.TimSort::mergeHi
0.83% 0.95% PhaseIdealLoop::get_late_ctrl(Node*, Node*) (libjvm.so)
0.72% 0.63% java.util.ArrayList::ensureExplicitCapacity
0.42% 0.30% PhaseIdealLoop::dom_depth(Node*) const (libjvm.so)
0.38% 0.39% java.util.stream.SortedOps$SizedRefSortingSink::end
0.30% 0.07% print_insn (libhsdis-amd64.so)
0.26% 0.23% _IO_fwrite (libc-2.19.so)
0.26% 0.17% java.util.TimSort::sort
0.23% 0.22% xmlTextStream::write(char const*, unsigned long) (libjvm.so)
5.88% 4.48% <...other 225 warm methods...>
....................................................................................................
Lots of non-inlined Comparator.apply calls here, need to adjust the inlining policy? This may be
caused by type-recursive inlining?
*/
@Benchmark
public Object bmJDKComparator() {
return myComparableList.stream()
.sorted(comparingusingJDKCode(
MyComparableInt::getA,
MyComparableInt::getB,
MyComparableInt::getC,
MyComparableInt::getD))
.collect(Collectors.toList());
}
/*
-prof stack
....[Thread state: RUNNABLE]........................................................................
41.8% 41.8% java.util.TimSort.binarySort
14.3% 14.3% java.util.TimSort.mergeLo
12.9% 12.9% java.util.TimSort.gallopRight
11.0% 11.0% java.util.TimSort.gallopLeft
9.1% 9.1% java.util.TimSort.mergeHi
4.6% 4.6% java.util.ArrayList.ensureCapacityInternal
2.3% 2.3% java.util.stream.SortedOps$SizedRefSortingSink.end
1.7% 1.7% comp.generated.FixedCompTestBenchmark_bmNoVTLComparator.bmNoVTLComparator_thrpt_jmhStub
0.6% 0.6% java.lang.Integer.valueOf
0.6% 0.6% java.util.TimSort.mergeAt
1.1% 1.1% <other>
-prof perfasm
....[Hottest Regions]...............................................................................
53.04% 59.84% [0x7f1f591eed00:0x7f1f591eefeb] in comp.FixedCompTestBenchmark$$Lambda$10::compare
6.90% 5.84% [0x7f1f5923c150:0x7f1f5923c308] in java.util.TimSort::sort
4.98% 4.70% [0x7f1f59052644:0x7f1f590527c6] in <stub: _shouldnotreachhere 233 _shouldnotreachhere>
4.78% 4.06% [0x7f1f5923c32c:0x7f1f5923c3a9] in java.util.TimSort::sort
4.35% 4.62% [0x7f1f59212df0:0x7f1f59212fb4] in java.util.TimSort::mergeLo
4.34% 4.63% [0x7f1f5924ef20:0x7f1f5924f047] in comp.FixedCompTestBenchmark::bmNoVTLComparator
3.41% 2.95% [0x0:0x0] in <kernel>
3.19% 2.07% [0x7f1f591ef0e5:0x7f1f591ef15d] in comp.FixedCompTestBenchmark$$Lambda$10::compare
1.70% 1.78% [0x7f1f5920ebcb:0x7f1f5920ed81] in java.util.TimSort::mergeHi
1.57% 1.13% [0x7f1f591f5cfc:0x7f1f591f5eac] in java.util.TimSort::gallopLeft
1.35% 0.81% [0x7f1f59243940:0x7f1f59243981] in java.util.ArrayList::ensureExplicitCapacity
1.19% 1.08% [0x7f1f5924ecc0:0x7f1f5924edd2] in comp.FixedCompTestBenchmark::bmNoVTLComparator
0.96% 0.76% [0x7f1f592051c0:0x7f1f59205358] in java.util.ArrayList$ArrayListSpliterator::forEachRemaining; java.util.TimSort::gallopRight
0.62% 0.56% [0x7f1f592053d0:0x7f1f59205448] in java.util.TimSort::gallopRight
0.56% 0.04% [0x7f1f59052442:0x7f1f5905249d] in <stub: _shouldnotreachhere 233 _shouldnotreachhere>
0.25% 0.28% [0x7f1f591f5c40:0x7f1f591f5cda] in java.lang.Class::getComponentType; java.util.TimSort::gallopLeft
0.25% 0.35% [0x7f1f5920eeec:0x7f1f5920f027] in java.util.TimSort::mergeHi
0.25% 0.19% [0x7f1f5923be08:0x7f1f5923bea6] in java.util.TimSort::sort
0.21% 0.29% [0x7f1f6e2c8eff:0x7f1f6e2c8f59] in RelocIterator::initialize(nmethod*, unsigned char*, unsigned char*) (libjvm.so)
0.20% 0.13% [0x7f1f59213281:0x7f1f59213352] in java.util.TimSort::mergeLo
5.79% 3.88% <...other 261 warm regions...>
....................................................................................................
At least one Comparator.compare had not inlined, need to adjust the inlining policy?
*/
@Benchmark
public Object bmNoVTLComparator() {
return myComparableList.stream()
.sorted(comparingUnwindingTheMethodToRemoveVTLs(
MyComparableInt::getA,
MyComparableInt::getB,
MyComparableInt::getC,
MyComparableInt::getD))
.collect(Collectors.toList());
}
/*
-prof stack:
....[Thread state: RUNNABLE]........................................................................
39.9% 39.9% java.util.TimSort.binarySort
15.9% 15.9% java.util.TimSort.mergeLo
10.1% 10.1% java.util.stream.SortedOps$SizedRefSortingSink.end
9.9% 9.9% java.util.TimSort.gallopRight
9.0% 9.0% java.util.TimSort.gallopLeft
6.2% 6.2% java.util.TimSort.mergeHi
2.6% 2.6% java.util.TimSort.sort
1.9% 1.9% java.util.TimSort.minRunLength
1.7% 1.7% java.util.ArrayList.ensureExplicitCapacity
1.1% 1.1% java.util.TimSort.mergeAt
1.7% 1.7% <other>
-prof perfasm:
....[Hottest Regions]...............................................................................
30.88% 30.25% [0x7f0cc5209bbd:0x7f0cc5209ea3] in java.util.TimSort::binarySort
13.20% 14.70% [0x7f0cc51f854c:0x7f0cc51f8780] in java.util.TimSort::mergeLo
7.03% 9.00% [0x7f0cc5052644:0x7f0cc50527c6] in <stub: _shouldnotreachhere 233 _shouldnotreachhere>
6.30% 5.90% [0x7f0cc51f3a44:0x7f0cc51f3e95] in java.util.TimSort::gallopLeft
5.14% 5.31% [0x7f0cc5246600:0x7f0cc5246719] in java.util.stream.ReferencePipeline::collect
4.80% 5.06% [0x7f0cc5203643:0x7f0cc5203872] in java.util.TimSort::mergeHi
4.52% 3.88% [0x0:0x0] in <kernel>
3.80% 4.63% [0x7f0cc523d420:0x7f0cc523d530] in comp.FixedCompTestBenchmark::bmNoVTLOrAutoBoxingComparator
3.50% 3.46% [0x7f0cc51fd12c:0x7f0cc51fd3de] in java.util.TimSort::gallopRight
3.08% 3.16% [0x7f0cc51fce80:0x7f0cc51fd0f7] in java.util.ArrayList$ArrayListSpliterator::forEachRemaining; java.util.TimSort::gallopRight
1.17% 1.24% [0x7f0cc52463b5:0x7f0cc52464bf] in java.util.stream.ReferencePipeline::collect
1.15% 1.36% [0x7f0cc523d1c0:0x7f0cc523d2e0] in comp.FixedCompTestBenchmark::bmNoVTLOrAutoBoxingComparator
1.13% 1.14% [0x7f0cc5236400:0x7f0cc5236485] in java.util.ArrayList::ensureExplicitCapacity
1.11% 1.01% [0x7f0cc51f3940:0x7f0cc51f3a21] in java.util.ArrayList$ArrayListSpliterator::forEachRemaining; java.util.TimSort::gallopLeft
1.04% 0.94% [0x7f0cc51f803e:0x7f0cc51f8256] in java.util.TimSort::mergeLo
1.02% 0.25% [0x7f0cc5052420:0x7f0cc5052490] in <stub: _shouldnotreachhere 233 _shouldnotreachhere>
0.98% 0.75% [0x7f0cc523075c:0x7f0cc523093b] in java.util.TimSort::sort
0.90% 0.79% [0x7f0cc5203899:0x7f0cc5203b26] in java.util.TimSort::mergeHi
0.77% 0.63% [0x7f0cc51f82b7:0x7f0cc51f84d0] in java.util.TimSort::mergeLo
0.62% 0.43% [0x7f0cc52089a0:0x7f0cc5208b57] in java.util.TimSort::mergeAt
7.84% 6.12% <...other 338 warm regions...>
....................................................................................................
Comparator had inlined, need to read the disassembly for the hottest method.
*/
@Benchmark
public Object bmNoVTLOrAutoBoxingComparator() {
return myComparableList.stream()
.sorted(comparingUnwindingTheMethodToRemoveVTLAndNoAutoBoxing(
MyComparableInt::getA,
MyComparableInt::getB,
MyComparableInt::getC,
MyComparableInt::getD))
.collect(Collectors.toList());
}
private static class MyComparableInt {
private int a, b, c, d;
public MyComparableInt(int i) {
a = i % 2;
b = i % 10;
c = i % 1000;
d = i;
}
public int getA() {
return a;
}
public int getB() {
return b;
}
public int getC() {
return c;
}
public int getD() {
return d;
}
}
public enum MyComparableIntSorter implements Comparator<MyComparableInt> {
INSTANCE;
@Override
public int compare(MyComparableInt o1, MyComparableInt o2) {
int comp = Integer.compare(o1.getA(), o2.getA());
if (comp == 0) {
comp = Integer.compare(o1.getB(), o2.getB());
if (comp == 0) {
comp = Integer.compare(o1.getC(), o2.getC());
if (comp == 0) {
comp = Integer.compare(o1.getD(), o2.getD());
}
}
}
return comp;
}
}
public static <T, U extends Comparable<? super U>> Comparator<T> comparingusingJDKCode(
Function<? super T, ? extends U> ke1,
Function<? super T, ? extends U> ke2,
Function<? super T, ? extends U> ke3,
Function<? super T, ? extends U> ke4) {
return Comparator.comparing(ke1).thenComparing(ke2)
.thenComparing(ke3).thenComparing(ke4);
}
public static <T, U extends Comparable<? super U>> Comparator<T>
comparingUnwindingTheMethodToRemoveVTLs(
Function<? super T, ? extends U> ke1,
Function<? super T, ? extends U> ke2,
Function<? super T, ? extends U> ke3,
Function<? super T, ? extends U> ke4) {
return (c1, c2) -> {
int comp = ke1.apply(c1).compareTo(ke1.apply(c2));
if (comp == 0) {
comp = ke2.apply(c1).compareTo(ke2.apply(c2));
if (comp == 0) {
comp = ke3.apply(c1).compareTo(ke3.apply(c2));
if (comp == 0) {
comp = ke4.apply(c1).compareTo(ke4.apply(c2));
}
}
}
return comp;
};
}
public static <T, U extends Comparable<? super U>> Comparator<T>
comparingUnwindingTheMethodToRemoveVTLAndNoAutoBoxing(
ToIntFunction<? super T> ke1,
ToIntFunction<? super T> ke2,
ToIntFunction<? super T> ke3,
ToIntFunction<? super T> ke4) {
return (c1, c2) -> {
int comp = Integer.compare(ke1.applyAsInt(c1), ke1.applyAsInt(c2));
if (comp == 0) {
comp = Integer.compare(ke2.applyAsInt(c1), ke2.applyAsInt(c2));
if (comp == 0) {
comp = Integer.compare(ke3.applyAsInt(c1), ke3.applyAsInt(c2));
if (comp == 0) {
comp = Integer.compare(ke4.applyAsInt(c1), ke4.applyAsInt(c2));
}
}
}
return comp;
};
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.