# Inlining Arrays of Lambdas

**URL:** <https://discuss.kotlinlang.org/t/inlining-arrays-of-lambdas/18249>\
**Category:** Language Design\
**Created:** [June 27, 2020, 6:48am UTC](https://discuss.kotlinlang.org/t/inlining-arrays-of-lambdas/18249 "2020-06-27T06:48:53Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![derektom14](https://sea1.discourse-cdn.com/flex019/user_avatar/discuss.kotlinlang.org/derektom14/32/7411_2.png) [@derektom14](https://discuss.kotlinlang.org/u/derektom14)\
**Post date:** [June 27, 2020, 6:48am UTC](https://discuss.kotlinlang.org/t/inlining-arrays-of-lambdas/18249/1 "2020-06-27T06:48:53Z")

</div>

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:

```auto
val comparatorLambdas = compareBy<Data>({ it.a }, { it.b }, { it.c }, { it.d })

```

Alternatively, you could list the properties in a `compareBy`/`thenBy` chain:

```auto
val comparatorChain = compareBy<Data> { it.a }
            .thenBy { it.b }
            .thenBy { it.c }
            .thenBy { it.d }

```

Or, you could construct the comparator entirely manually:

```auto
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:

```auto
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 `Comparator`s, 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:

```auto
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:

```auto
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](https://discuss.kotlinlang.org/t/sequences-and-inlined-lambdas/17228), 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.)

---

<div class="post-metadata">

**Author:** ![fvasco](https://sea1.discourse-cdn.com/flex019/user_avatar/discuss.kotlinlang.org/fvasco/32/1961_2.png) [@fvasco](https://discuss.kotlinlang.org/u/fvasco)\
**Post date:** [June 27, 2020, 5:37pm UTC](https://discuss.kotlinlang.org/t/inlining-arrays-of-lambdas/18249/2 "2020-06-27T17:37:50Z")

</div>

Hi, @derektom14,  
it looks interesting to me, can you provide a reproducer using different data size?

Maybe it is possible to change the actual `compareBy` with something like:

```nohighlight
fun <T> compareBy(vararg selectors: (T) -> Comparable<*>?): Comparator<T> =
        selectors.drop(1).fold(compareBy(selectors.first())) { c, s -> c.thenBy(s) }

```

What do you think?

---

<div class="post-metadata">

**Author:** ![derektom14](https://sea1.discourse-cdn.com/flex019/user_avatar/discuss.kotlinlang.org/derektom14/32/7411_2.png) [@derektom14](https://discuss.kotlinlang.org/u/derektom14)\
**Post date:** [June 27, 2020, 9:59pm UTC](https://discuss.kotlinlang.org/t/inlining-arrays-of-lambdas/18249/3 "2020-06-27T21:59:04Z")

</div>

That method is effectively the same as `comparatorChain`, except that you’re no longer inlining the lambdas, so the performance is instead the same as `comparatorLambdas`:

```auto
Benchmark (N) Mode Cnt Score Error Units
ComparatorBenchmarkHelper.sortChain 100000 avgt 10 38.646 ± 2.322 ms/op
ComparatorBenchmarkHelper.sortEfficient 100000 avgt 10 28.239 ± 2.376 ms/op
ComparatorBenchmarkHelper.sortLambdas 100000 avgt 10 87.527 ± 4.053 ms/op
ComparatorBenchmarkHelper.sortLambdasAlt 100000 avgt 10 84.818 ± 4.888 ms/op

```

I can add different sizes, but I don’t expect it to tell much of a different story, as each run will still take roughly `n log(n)` comparisons, so all of the times should increase while maintaining the same relative values.

---

<div class="post-metadata">

**Author:** ![derektom14](https://sea1.discourse-cdn.com/flex019/user_avatar/discuss.kotlinlang.org/derektom14/32/7411_2.png) [@derektom14](https://discuss.kotlinlang.org/u/derektom14)\
**Post date:** [June 27, 2020, 10:24pm UTC](https://discuss.kotlinlang.org/t/inlining-arrays-of-lambdas/18249/4 "2020-06-27T22:24:41Z")

</div>

Here are the benchmarks with varying values of N:

```auto
Benchmark (N) Mode Cnt Score Error Units
ComparatorBenchmarkHelper.sortChain 1000 avgt 10 0.223 ± 0.003 ms/op
ComparatorBenchmarkHelper.sortChain 10000 avgt 10 2.972 ± 0.035 ms/op
ComparatorBenchmarkHelper.sortChain 100000 avgt 10 38.040 ± 1.075 ms/op
ComparatorBenchmarkHelper.sortEfficient 1000 avgt 10 0.165 ± 0.004 ms/op
ComparatorBenchmarkHelper.sortEfficient 10000 avgt 10 2.176 ± 0.036 ms/op
ComparatorBenchmarkHelper.sortEfficient 100000 avgt 10 27.268 ± 0.215 ms/op
ComparatorBenchmarkHelper.sortLambdas 1000 avgt 10 0.470 ± 0.043 ms/op
ComparatorBenchmarkHelper.sortLambdas 10000 avgt 10 6.672 ± 0.736 ms/op
ComparatorBenchmarkHelper.sortLambdas 100000 avgt 10 99.819 ± 22.008 ms/op

```

The order remains clear.

---

<div class="post-metadata">

**Author:** ![fvasco](https://sea1.discourse-cdn.com/flex019/user_avatar/discuss.kotlinlang.org/fvasco/32/1961_2.png) [@fvasco](https://discuss.kotlinlang.org/u/fvasco)\
**Post date:** [June 28, 2020, 7:07am UTC](https://discuss.kotlinlang.org/t/inlining-arrays-of-lambdas/18249/5 "2020-06-28T07:07:28Z")

</div>

Hi, @derektom14,  
did you understand why `sortLambdasAlt` is so different from `sortChain`.  
What you effectively measured?  
Can you share your code?

---

<div class="post-metadata">

**Author:** ![derektom14](https://sea1.discourse-cdn.com/flex019/user_avatar/discuss.kotlinlang.org/derektom14/32/7411_2.png) [@derektom14](https://discuss.kotlinlang.org/u/derektom14)\
**Post date:** [June 28, 2020, 8:26am UTC](https://discuss.kotlinlang.org/t/inlining-arrays-of-lambdas/18249/6 "2020-06-28T08:26:34Z")

</div>

The reason is due to inlining. The chain relies on two methods, `compareBy` and `thenBy`:

```auto
@kotlin.internal.InlineOnly
public inline fun <T> compareBy(crossinline selector: (T) -> Comparable<*>?): Comparator<T> =
    Comparator { a, b -> compareValuesBy(a, b, selector) }

@kotlin.internal.InlineOnly
public inline fun <T> Comparator<T>.thenBy(crossinline selector: (T) -> Comparable<*>?): Comparator<T> =
    Comparator { a, b ->
        val previousCompare = this@thenBy.compare(a, b)
        if (previousCompare != 0) previousCompare else compareValuesBy(a, b, selector)
    }

```

When the lambdas are inlined, their invocations no longer require a virtual call.

However, in your alternative, you are using a `vararg` of lambdas, and as the topic of this thread points out, those can’t be inlined. Therefore, you end up creating multiple lambda objects, and for each step in the chain, a virtual call must be made by the `selector` for each parameter.

This exact phenomenon is covered in [this Medium article](https://medium.com/tompee/idiomatic-kotlin-inline-functions-e39b2f90a291).