Compilation time regression when using subtyping of union type in enum type parameter

[bilki]

Compiler version

3.3.5 | 3.3.6

Minimized code

case class C01(name: String, age: Int, isAdult: Boolean)
case class C02(name: String, age: Int, isAdult: Boolean)
case class C03(name: String, age: Int, isAdult: Boolean)
case class C04(name: String, age: Int, isAdult: Boolean)
case class C05(name: String, age: Int, isAdult: Boolean)
case class C06(name: String, age: Int, isAdult: Boolean)
case class C07(name: String, age: Int, isAdult: Boolean)
case class C08(name: String, age: Int, isAdult: Boolean)
case class C09(name: String, age: Int, isAdult: Boolean)
case class C10(name: String, age: Int, isAdult: Boolean)
case class C11(name: String, age: Int, isAdult: Boolean)
case class C12(name: String, age: Int, isAdult: Boolean)
case class C13(name: String, age: Int, isAdult: Boolean)
case class C14(name: String, age: Int, isAdult: Boolean)
case class C15(name: String, age: Int, isAdult: Boolean)
case class C16(name: String, age: Int, isAdult: Boolean)
case class C17(name: String, age: Int, isAdult: Boolean)
case class C18(name: String, age: Int, isAdult: Boolean)
case class C19(name: String, age: Int, isAdult: Boolean)
case class C20(name: String, age: Int, isAdult: Boolean)
case class C21(name: String, age: Int, isAdult: Boolean)
case class C22(name: String, age: Int, isAdult: Boolean)
case class C23(name: String, age: Int, isAdult: Boolean)
case class C24(name: String, age: Int, isAdult: Boolean)
case class C25(name: String, age: Int, isAdult: Boolean)
case class C26(name: String, age: Int, isAdult: Boolean)
case class C27(name: String, age: Int, isAdult: Boolean)
case class C28(name: String, age: Int, isAdult: Boolean)
case class C29(name: String, age: Int, isAdult: Boolean)
case class C30(name: String, age: Int, isAdult: Boolean)
case class C31(name: String, age: Int, isAdult: Boolean)
case class C32(name: String, age: Int, isAdult: Boolean)
case class C33(name: String, age: Int, isAdult: Boolean)
case class C34(name: String, age: Int, isAdult: Boolean)
case class C35(name: String, age: Int, isAdult: Boolean)
case class C36(name: String, age: Int, isAdult: Boolean)
case class C37(name: String, age: Int, isAdult: Boolean)
case class C38(name: String, age: Int, isAdult: Boolean)
case class C39(name: String, age: Int, isAdult: Boolean)
case class C40(name: String, age: Int, isAdult: Boolean)

type CUnion =
  C01 | C02 | C03 | C04 | C05 | C06 | C07 | C08 | C09 | C10 | C11 | C12 | C13 | C14 | C15
  | C16 | C17 | C18 | C19 | C20 | C21 | C22 | C23 | C24 | C25 | C26 | C27 | C28 | C29 | C30
  | C31 | C32 | C33 | C34 | C35 | C36 | C37 | C38 | C39 | C40

enum EnumWithUnionSubtyping[A <: CUnion]:
  case First(one: String)
  case Second(two: String)
  case Third(three: String)
  case Fourth(four: String)
  case Fifth(five: String)
  case Sixth(six: String)
  case Seventh(seven: String)

@main def hello(): Unit =
  val c10 = C10(name = "bla", age = 10, isAdult = false)
  println(c10)

Output

[success] Total time: 8 s, completed 27 feb 2025, 16:37:27

Expectation

After updating from 3.3.4 to 3.3.5 we've noticed a huge increase in compilation times for one scenario similar to the one I'm showing above. Since it looks like it is also happening in 3.3.6, and the profile tracer is being ported back, I've used that version (3.3.6-RC1-bin-20250219-7fb2a9d-NIGHTLY) to generate a trace file (pasted below as an image as well) for the minimized code.

My guess is the posttyper phase of the compiler is taking way more time than it used to. I say guess because for 3.3.4 I don't have any profile traces, but compilation time is under 1s for this exact same code.

Also, after running a few experiments: the more cases we add to EnumWithUnionSubtyping, the longer it takes to compile, provided the CUnion contains enough members (e.g. using 10 member types compilation time is more reasonable). If we swap the enum for a sealed trait, the same happens.

In our real-life scenario we have 30+ members, and four cases inside the enum, of course a bit more complex than the scenario above.

It doesn't seem to be impacting 3.6.3 fwiw.

tracefile.json

[noti0na1]

The current nightly version (3.7.0-RC1-bin-20250226-399d008-NIGHTLY) does not have the performance issue.

Happened between:

3.3.5-RC1-bin-20241203-6ba335a-NIGHTLY
3.3.5-RC1-bin-20241204-5f2d7ef-NIGHTLY

cc @WojciechMazur

[WojciechMazur]

The bisect points to #22108 - df0bb26 to be exact but the presentation-compiler was failing to compile with previous revisions of that backport PR

[Gedochao]

The bisect points to #22108 - df0bb26 to be exact but the presentation-compiler was failing to compile with previous revisions of that backport PR

@dwijnand @kasiaMarek @rochala would you be able to take a look at the backport PR? It seems some modifications had to be made when porting the original PR, maybe we can pinpoint what is causing the performance regression in LTS.

[kasiaMarek]

would you be able to take a look at the backport PR?

I don't have much of an insight here, I can't say I understood the changes that @dwijnand made in type inference to make the Metals feature work. But if he's too busy I can try to dig into this.

[kasiaMarek]

It seems that using ExplainingTypeComparer is simply expensive in some cases. Specifically calling show many times on long types like with this union, the string like below is constructed about 40 times in this example:

On main it was fix in edd40bc.

[Gedochao]

Right... and the backport of #21583 to LTS was rejected.
Not sure if we'll be able to fix it then...
@tgodzik @WojciechMazur thoughts? is this a case of won't fix?

[noti0na1]

I think we should be able to backport if we remove the cc stuff from the PR?

[kasiaMarek]

@Gedochao it is just about that single commit, which can be backported without any issues. It comes down to moving isSubType(tp1, tp2) out of TypeComparer.explaining{ }. It is a sort of partial revert of df0bb26.

[tgodzik]

Thanks @kasiaMarek for finding this one, I will backport this as soon as the current batch is done.

[dwijnand]

@Gedochao it is just about that single commit, which can be backported without any issues. It comes down to moving isSubType(tp1, tp2) out of TypeComparer.explaining{ }. It is a sort of partial revert of df0bb26.

👍🏼 Just cherry-picking edd40bc should do the trick.

[tgodzik]

Will test it in scala#142

[tgodzik]

You can test it under 3.3.6-RC1-bin-20250312-fb2c793-NIGHTLY, it should be faster, but not sure if enough, it's under 2 seconds on my machine.

[tgodzik]

Interestingly this is faster than 3.7.0-RC1, so there might be room for improvement in the Next too.

[bilki]

3.3.6-RC1-bin-20250312-fb2c793-NIGHTLY

Tested on both this minimized code sample, and the real-life scenario that was impacted by this issue.

It works way much faster than 3.3.5, I'd say it is on par with 3.3.4 👍