Improving compile-time for structure based on implicits resolutions

gistfile1.md

Here is a fast explanation on this study for Freek to improve compile-time:

https://github.com/ProjectSeptemberInc/freek/blob/optim/cop/src/main/scala/CoproductK.scala#L14-L34

In Freek, Higher-Kinded Coproduct was based on Shapeless HList/Coproduct representation like:

sealed trait CoproductK[A] extends Product with Serializable

sealed trait CNilK[A] extends CoproductK[A]

sealed trait ConsK[H[_], L[_] <: CoproductK[_], A] extends CoproductK[A]
final case class Inlk[H[_], T[_] <: CoproductK[_], A](head : H[A]) extends ConsK[H, T, A]
final case class Inrk[H[_], T[_] <: CoproductK[_], A](tail : T[A]) extends ConsK[H, T, A]

So when you build a CoproductK, it looks like:

ConsK[Foo1, ConsK[Foo2, ConsK[Foo3, CNilK]]]

Graphically, it looks like a tree in depth:

     ConsK
    /     \
Foo1       ConsK
          /     \
      Foo2       ConsK
                 /    \
             Foo3     CNilK

If you look at Shapeless, all operations are encoded using typeclass with some implicits. In general when you define one operation, you have a few implicit cases: often, at least, one terminal case based on CNilK and one recursive case based on ConsK.

trait MyOp[C[_] <: CoproductK[_] {
  // do something
}

object MyOp {
  
 implicit def terminal: MyOp[CNilK] = ...
 
 implicit def rec[C[_] <: CoproductK[_]](implicit next: MyOp[C]): MyOp[ConsK[H, C] = ...
}

So when scalac tries to resolve an implicit MyOp for a n-level ConsK[Foo1, ConsK[Foo2, ConsK[Foo3, ...]]], it's going to do 2 x n operations. So the number of implicits grows linearly with the length of the coproduct.

If you test in Scalac, you'll see that compile-time explodes as soon as you have coproduct of more than 5-6 elements.

So how can we try to improve that compile-time? By optimizing the structure for compile-time without losing it's capabilities

The idea is simple: Try to make CoproductK a less high & larger tree and reduce the number of implicit resolutions.

Naturally, in this purpose, we immediately think about kind of B-Tree (of order 3 in our case).

By applying this idea, here is the new representation of CoproductK:

sealed trait CoproductK[A] extends Product with Serializable

sealed trait CNilK[A] extends CoproductK[A]

final case class In1[H[_], A](head: H[A]) extends CoproductK[A]

sealed trait In2[H1[_], H2[_], A] extends CoproductK[A]
final case class In2l[H1[_], H2[_], A](left: H1[A]) extends In2[H1, H2, A] 
final case class In2r[H1[_], H2[_], A](right: H2[A]) extends In2[H1, H2, A]

sealed trait In3[H1[_], H2[_], H3[_], A] extends CoproductK[A]
final case class In3l[H1[_], H2[_], H3[_], A](left: H1[A]) extends In3[H1, H2, H3, A]
final case class In3m[H1[_], H2[_], H3[_], A](middle: H2[A]) extends In3[H1, H2, H3, A]
final case class In3r[H1[_], H2[_], H3[_], A](right: H3[A]) extends In3[H1, H2, H3, A]

sealed trait AppendK[L[_] <: CoproductK[_], R[_] <: CoproductK[_], A] extends CoproductK[A]
final case class Aplk[L[_] <: CoproductK[_], R[_] <: CoproductK[_], A](left: L[A]) extends AppendK[L, R, A]
final case class Aprk[L[_] <: CoproductK[_], R[_] <: CoproductK[_], A](right: R[A]) extends AppendK[L, R, A]

So, a 5-elements Coproduct would look like:

           AppendK
        /          \
     In2            In3
    /   \        /   |   \
Foo1     Foo2  Foo3 Foo4  Foo5

If you need to describe implicits for MyOp, you would write something like:

trait MyOp[C[_] <: CoproductK[_] {
  // do something
}

object MyOp {
 implicit def terminal: MyOp[CNilK] = ...
 
 implicit def in1: MyOp[In1[...]] = ...
 implicit def in2: MyOp[In2[...]] = ...
 implicit def in3: MyOp[In3[...]] = ...
 
 implicit def append: MyOp[AppendK[...]] = ...
}

So you have 5 implicits in this case.

For this kind of Tree containing n elements, the height in best case can be :

height = log2(n+1)

For In1/In2/In3, implicit resolutions is immediate. For AppendK, implicit resolution need to resolve left and right subtree.

The max number of AppendK in a tree is: 2^(height - 1) - 1.

The max number of In1/In2/In3 in a tree is: 2 x height.

So by simplifying a lot, the max number of resolutions is something like log2(n+1) which is far better than n.

There are other improvements possibles in Scalac like the order of implicits and their priorities. But the structure itself already improves naturally compile-time and this idea is really cool IMHO ;)

To show the result of this in reality, here are compile-time before & after:

Older Freek representation

10 elements -> 5s
12 elements -> 10s
14 elements -> 29s
20 elements -> never ends

Optimized Freek

10 elements -> 2s
12 elements -> 3s
14 elements -> 4s
20 elements -> 8s

Have fun...