Extreme compile times in typelevel algorithms when using type aliases

[jdrphillips]

reproduction steps

using Scala 2.13.8 and 2.13.9-bin-f11f1f7,

When performing a typelevel algorithm the compile time performance varies wildly depending on any aliases present. Below is a cut down implementation of Nat and Sum

// Basic Nat
trait Nat
class _0 extends Nat
trait Succ[A <: Nat] extends Nat

object Testing {

  // Alias _0 to something arbitrarily
  type alias0 = _0

  // The numbers I will be using, they are based off the alias:
  type _12 =
  Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[
    alias0
  ]]]]]]]]]]]]

  type _15 =
  Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[
    alias0
  ]]]]]]]]]]]]]]]

  type _27 =
  Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[Succ[
  Succ[Succ[Succ[Succ[Succ[Succ[Succ[
    alias0
  ]]]]]]]]]]]]]]]]]]]]]]]]]]]

  // Boilerplate `Sum` typeclass
  trait Sum[A <: Nat, B <: Nat] {
    type Out <: Nat
  }

  object Sum {
    type Aux[A <: Nat, B <: Nat, Out0 <: Nat] = Sum[A, B] { type Out = Out0 }
    implicit def zeroCase[A <: Nat]: Sum.Aux[A, _0, A] = ???
    implicit def recursive[A <: Nat, B <: Nat](
      implicit sum: Sum[Succ[A], B]
    ): Sum.Aux[A, Succ[B], sum.Out] = ???
  }

  def sum[A <: Nat, B <: Nat](implicit s: Sum[A, B]): s.Out = null.asInstanceOf[s.Out]
}

Use the following as a test-case:

sum[_15, _12]: _27

problem

When calculating sum[_15, _12]: _27 the compiler takes a very, very long time.

• 2.13.8: Cancelled compilation at 300s
• 2.13.9-bin-f11f1f7: 92s

If you replace the definitions of _12 etc with identical ones replacing alias0 with _0, then the compile times suddenly become:

• 2.13.8: < 1s
• 2.13.9-bin-f11f1f7: < 1s

I would expect the behaviour to not differ so greatly depending on a simple alias.

[jdrphillips]

Additional notes:

2.13.9-bin-f11f1f7 is the version which fixes #12489 which is a similar problem (hence the speed up seen).

And you need only replace a single summand's definition to use _0 to see a speed up. Replacing the left hand summand provides the fastest speed up (down to 14s), presumably due to the left-handed nature of the Sum typeclass.

[SethTisue]

perhaps this would interest @joroKr21

[joroKr21]

The fix for #12489 was scala/scala#9886 which is specific to pattern matching. There is no pattern matching here that I can see so the performance improvement must come from somewhere else 🤔