Suppose you want to sort a list of objects by certain values in order:
data class Data(val a: Boolean, val b: Boolean, val c: Boolean, val d: Int)
The easiest way to do it is to just list the properties you want to sort by in lambdas:
val comparatorLambdas = compareBy<Data>({ it.a }, { it.b }, { it.c }, { it.d })
Alternatively, you could list the properties in a compareBy/thenBy chain:
val comparatorChain = compareBy<Data> { it.a }
.thenBy { it.b }
.thenBy { it.c }
.thenBy { it.d }
Or, you could construct the comparator entirely manually:
private inline fun Int.ifDiff(onDiff: (Int) -> Unit) = if (this != 0) onDiff(this) else Unit
val comparatorManual = object : Comparator<Data> {
override fun compare(o1: Data, o2: Data): Int {
o1.a.compareTo(o2.a).ifDiff { return it }
o1.b.compareTo(o2.b).ifDiff { return it }
o1.c.compareTo(o2.c).ifDiff { return it }
o1.d.compareTo(o2.d).let { return it }
}
}
How efficient is each comparator? Let’s look at a benchmark of using each one to sort an array of 100,000 elements:
Benchmark (N) Mode Cnt Score Error Units
ComparatorBenchmarkHelper.sortChain 100000 avgt 10 37.531 ± 1.532 ms/op
ComparatorBenchmarkHelper.sortManual 100000 avgt 10 26.763 ± 0.257 ms/op
ComparatorBenchmarkHelper.sortLambdas 100000 avgt 10 93.089 ± 3.965 ms/op
We see that sortLambdas is incredibly slow compared to sortChain and sortManual, with sortManual being clearly the fastest. Why? Because sortChain creates nested Comparators, leading to multiple virtual calls, and sortLambdas has an array of lambdas, leading to an iteration as well as multiple virtual calls.
This would be much improved if it were possible to inline a vararg of lambdas. Take the above compareBy call, which uses this method:
public fun <T> compareBy(vararg selectors: (T) -> Comparable<*>?): Comparator<T> {
require(selectors.size > 0)
return Comparator { a, b -> compareValuesByImpl(a, b, selectors) }
}
Inlining compareValuesByImpl, we would get:
public fun <T> compareBy(vararg selectors: (T) -> Comparable<*>?): Comparator<T> {
require(selectors.size > 0)
return Comparator { a, b ->
for (fn in selectors) {
val v1 = fn(a)
val v2 = fn(b)
val diff = compareValues(v1, v2)
if (diff != 0) return diff
}
return 0
}
}
If we were able to inline selectors, a compiler would be able to resolve the require at compilation time, and from there, it could unroll the loop and inline each lambda, effectively becoming comparatorManual (except that compareValues also does unnecessary null checks, which an inlining compiler could know to eliminate on non-null values).
(This is a bit similar to my prior topic on Sequences and Inlined Lambdas, and would be one of the optimizations that its concepts would create. This one happens to be more immediately apparent, as a Comparator can easily become a major part of code execution when sorting large lists, so it’s important that they be as efficient as possible, and existing vararg compareBy as simply intolerable performance.)