bug
bug copied to clipboard
Extreme compile times in typelevel algorithms when using type aliases
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.
Additional notes:
2.13.9-bin-f11f1f7
is the version which fixes https://github.com/scala/bug/issues/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.
perhaps this would interest @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 🤔