Last active
October 21, 2016 12:56
-
-
Save danielshaya/9ded4b5bff2c89807d4a to your computer and use it in GitHub Desktop.
Comparing sorting implementations
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package comp; | |
import org.openjdk.jmh.annotations.Benchmark; | |
import org.openjdk.jmh.annotations.Scope; | |
import org.openjdk.jmh.annotations.Setup; | |
import org.openjdk.jmh.annotations.State; | |
import org.openjdk.jmh.runner.Runner; | |
import org.openjdk.jmh.runner.RunnerException; | |
import org.openjdk.jmh.runner.options.Options; | |
import org.openjdk.jmh.runner.options.OptionsBuilder; | |
import java.util.Comparator; | |
import java.util.List; | |
import java.util.function.Function; | |
import java.util.function.ToIntFunction; | |
import java.util.stream.Collectors; | |
import java.util.stream.IntStream; | |
@State(Scope.Thread) | |
public class CompTestBenchmark { | |
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 = compare(ke1.apply(c1), ke1.apply(c2)); | |
if (comp == 0) { | |
comp = compare(ke2.apply(c1), ke2.apply(c2)); | |
if (comp == 0) { | |
comp = compare(ke3.apply(c1), ke3.apply(c2)); | |
if (comp == 0) { | |
comp = compare(ke4.apply(c1), 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 = compareInt(ke1.applyAsInt(c1), ke1.applyAsInt(c2)); | |
if (comp == 0) { | |
comp = compareInt(ke2.applyAsInt(c1), ke2.applyAsInt(c2)); | |
if (comp == 0) { | |
comp = compareInt(ke3.applyAsInt(c1), ke3.applyAsInt(c2)); | |
if (comp == 0) { | |
comp = compareInt(ke4.applyAsInt(c1), ke4.applyAsInt(c2)); | |
} | |
} | |
} | |
return comp; | |
}; | |
} | |
private static <U extends Comparable<? super U>> int compare(U a, U b) { | |
return a.compareTo(b); | |
} | |
private static int compareInt(int a, int b) { | |
return Integer.compare(a, b); | |
} | |
List<MyComparableInt> myComparableList; | |
@Setup | |
public void init() { | |
//Create the list of objects to sort | |
myComparableList = IntStream.range(0, 1_000) | |
.mapToObj(i -> new MyComparableInt(i)) | |
.collect(Collectors.toList()); | |
} | |
@Benchmark | |
public void bmCustomComparator(){ | |
Comparator customComparator = MyComparableIntSorter.INSTANCE; | |
run(myComparableList, 5, customComparator, "custom comparator"); | |
} | |
@Benchmark | |
public void bmJDKComparator(){ | |
Comparator jdkComparator = comparingusingJDKCode( | |
MyComparableInt::getA, | |
MyComparableInt::getB, | |
MyComparableInt::getC, | |
MyComparableInt::getD); | |
run(myComparableList, 5, jdkComparator, "jdk comparator"); | |
} | |
@Benchmark | |
public void bmNoVTLComparator(){ | |
Comparator noVTLComparator = comparingUnwindingTheMethodToRemoveVTLs( | |
MyComparableInt::getA, | |
MyComparableInt::getB, | |
MyComparableInt::getC, | |
MyComparableInt::getD); | |
run(myComparableList, 5, noVTLComparator, "method unwinding (reduce virtual table lookups) comparator"); | |
} | |
@Benchmark | |
public void bmNoVTLOrAutoBoxingComparator(){ | |
Comparator noVTLOrAutoBoxingComparator = comparingUnwindingTheMethodToRemoveVTLAndNoAutoBoxing( | |
MyComparableInt::getA, | |
MyComparableInt::getB, | |
MyComparableInt::getC, | |
MyComparableInt::getD); | |
run(myComparableList, 5, noVTLOrAutoBoxingComparator, "method unwinding and remove autoboxing comparator"); | |
} | |
private void run(List<MyComparableInt> list, int runs, Comparator<MyComparableInt> comparator, String message){ | |
for(int i=0; i<runs; i++){ | |
List<MyComparableInt> mySortedList = list.stream() | |
.sorted(comparator) | |
.collect(Collectors.toList()); | |
} | |
} | |
public static void main(String[] args) throws RunnerException { | |
Options opt = new OptionsBuilder() | |
.include(CompTestBenchmark.class.getSimpleName()) | |
.forks(1) | |
.build(); | |
new Runner(opt).run(); | |
} | |
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; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment