Slow compilation with chained dependent match types #14903
Comments
|
A simple guess would be that the result of the first step is a The root cause would be how implicits and type matches combine in this case. Would that make sense? |
|
I have the same intuition. I would say the problem here is that match types are reduced too lazily. |
|
Here's a simpler example, it's not even about the wrapping type class but it seems to depend just on the number of patterns in the match: trait Wrapper[T] {
type Out
}
type Func[T] =
T match {
case String => Long
case Long => Int
case Int => Float
case Float => Double
case Double => Unit
case Unit => String
}
implicit def infer[A]: Wrapper[One[A]] { type Out = Func[A] } = ???
trait One[A] {
def use(implicit w: Wrapper[One[A]]): One[w.Out]
}
val x: One[Long] = null
x.use.use.use.use.use.use.use |
|
@jrudolph I think that makes sense. We do cache match type reduction, but we have to be very conservative in order to be sound, which means that we have to invalidate caches in many situations. It seems that applies here. /cc @OlivierBlanvillain maybe he can shed some more light on the matter. But it's good that |
|
Thanks, @odersky. Speaking of caches, WeakHashSet related code turns up with > 7 % in profiling of this case. In particular, the |
|
The WeakHashSet is the set of all cached types. That's a different cache actually. A high profiling count could point to a problem in the implementation of that cache. Maybe @smarter could take a look at it, he converted our type tables to weak hash sets. It's also an indication that we generate a lot of different types. Would be interesting to find out what they are. |
|
In fact it's something else. We generate millions of fresh match types, all of the form: ?1.Out match {
case String => Long
case Long => Int
case Int => Float
case Float => Double
case Double => Unit
case Unit => String
}Since every match type is fresh, it needs to be reduced from scratch, so the cache is populated but never looked up. The problem is that the skolem type ?1 is not cached and that means every type containing it is not cached either. |
In fact I could not reproduce that. I hangs for me also with |
Skolem types were not cached, which means that any type containing a skolem type was not cached either. This meant that the same match type with a skolem type as selector was created many times instead of once, so its reduction was not cached either. We now cache skolem types. It's a bet that in practice few skolem types are created and that therefore the hashtable pollution with skolemtypes is less of a problem than the potential problem of losing identity of types containing skolem types. Fixes scala#14903
|
It seems that caching skolem types solves the problem. But I note that the original code has an error. See the test file in the PR. |
I don't know, but that design was imported wholesale from Scala 2 where it survived many years of optimization work, and using it in Scala 3 did not lead to slowdowns compared to a regular HashMap, cf #12935 |
It compiles fine for me on 3.1.1 and 3.1.2 when using implicit transparent inline def tailSwitch... |
|
I get a hanged compiler when I run that code from main. And with the changes in the PR I get: Correction: It did not hang in main (with |
|
Indeed. This looks like a regression between main and 3.1.2 then. |
|
@prolativ Can we find out what was the commit that regressed? And, is the error legit or wrong? |
|
3.1.3-RC1-bin-20220404-ad2553d-NIGHTLY is the first nightly that doesn't compile quickly with |
|
I guess #13780 is a likely candidate. The question still remains whether the error is legit or not. |
|
For anyone looking into this, note that the error message doesn't give enough information because it talks about skolems without giving their underlying type, this happened before and in #13491 (comment) I gave a way to workaround this:
(I didn't make a PR for that because it can lead to the same skolem being explained multiple times so something a bit more clever is needed) |
|
In d1957e5, the test case for #13491 was changed as follow: --- tests/pos/13491.scala
+++ tests/pos/13491.scala
@@ -86,7 +86,8 @@ object Rule {
type RuleN[+L <: HList] = Rule[HNil, L]
def rule[I <: HList, O <: HList](r: Rule[I, O]): Rule[I, O] = ???
- implicit def valueMap[T](m: Map[String, T])(implicit h: HListable[T]): RuleN[h.Out] = ???
+
+ implicit def valueMap[T, Out0 <: HList](m: Map[String, T])(implicit h: HListable[T] { type Out = Out0 }): RuleN[Out0] = ???
}
object Test {If I apply the same kind of change to the test case in this issue, it works too (and it doesn't lead to slow compilation on master anymore since skolems aren't involved): diff --git tests/neg/i14903.scala tests/neg/i14903.scala
index cd61a12e858..cfd9fd6d546 100644
--- tests/neg/i14903.scala
+++ tests/pos/i14903.scala
@@ -43,10 +43,10 @@ object TailSwitch:
* Rule popping I from stack and pushing back O
*/
sealed class Rule[-I <: HList, +O <: HList]:
- def ~[I2 <: HList, O2 <: HList](that: Rule[I2, O2])(implicit
- i: TailSwitch[I2, O @uncheckedVariance, I @uncheckedVariance],
- o: TailSwitch[O @uncheckedVariance, I2, O2]
- ): Rule[i.Out, o.Out] = ???
+ def ~[I2 <: HList, O2 <: HList, Out0 <: HList, Out1 <: HList](that: Rule[I2, O2])(implicit
+ i: TailSwitch[I2, O @uncheckedVariance, I @uncheckedVariance] { type Out = Out0 },
+ o: TailSwitch[O @uncheckedVariance, I2, O2] { type Out = Out1 }
+ ): Rule[Out0, Out1] = ???
object Test:
def dot = new Rule[HNil, HNil] {} |
|
@jrudolph does the proposed change to ~ in my previous comment work for parboiled2? |
I can definitely try. Would it have to stay that way or just to check that it would be a suitable workaround for the issue for the time being? |
|
Seems like it would have to be that way, unless there's a chance the compiler could accept this code without breaking soundness /cc @OlivierBlanvillain |
Doing it in that one place doesn't seem to be enough. I would imagine that it will break things at other places as well as this kind of pattern is used in many more places. Which kind of usages are fine and which are going to break with 3.1.3? |
Unclear so far, I've opened #14987 as an alternative fix which if backported would avoid breaking anything hopefully. |
Previously, when reducing `a.T` we checked if the type of `a` was a subtype of `RefinedType(.., T, TypeAlias(...))`, now we extend this check to handle refinements where the `info` is a `TypeBounds` where both bounds are equal. This solves two big issues at once: - We can restore tests/pos/13491.scala to its original form from before scala#13780. The check for abstract types introduced by scala#13780 for soundness reasons is no longer hit because the type selection is reduced before we get to that point. This is important because parboiled2 relies on this and is therefore currently broken on 3.1.3-RC1 and main (sirthias/parboiled2#365). - This fixes scala#14903 (slow compilation issue affecting parboiled2) without caching skolems (as in the alternative fix scala#14909). Again, this is due to the type containing skolem being reducible to a simpler type and therefore cacheable.
Skolem types were not cached, which means that any type containing a skolem type was not cached either. This meant that the same match type with a skolem type as selector was created many times instead of once, so its reduction was not cached either. We now cache skolem types. It's a bet that in practice few skolem types are created and that therefore the hashtable pollution with skolemtypes is less of a problem than the potential problem of losing identity of types containing skolem types. Fixes scala#14903
Previously, when reducing `a.T` we checked if the type of `a` was a subtype of `RefinedType(.., T, TypeAlias(...))`, now we extend this check to handle refinements where the `info` is a `TypeBounds` where both bounds are equal. This solves two big issues at once: - We can restore tests/pos/13491.scala to its original form from before scala#13780. The check for abstract types introduced by scala#13780 for soundness reasons is no longer hit because the type selection is reduced before we get to that point. This is important because parboiled2 relies on this and is therefore currently broken on 3.1.3-RC1 and main (sirthias/parboiled2#365). - This fixes scala#14903 (slow compilation issue affecting parboiled2) without caching skolems (as in the alternative fix scala#14909). Again, this is due to the type containing skolem being reducible to a simpler type and therefore cacheable.
Skolem types were not cached, which means that any type containing a skolem type was not cached either. This meant that the same match type with a skolem type as selector was created many times instead of once, so its reduction was not cached either. We now cache skolem types. It's a bet that in practice few skolem types are created and that therefore the hashtable pollution with skolemtypes is less of a problem than the potential problem of losing identity of types containing skolem types. This was originally motivated by scala#14903 but that ended up being fixed in a different way. It still seems like a good idea to do this since it matches what we do for type variables.
Skolem types were not cached, which means that any type containing a skolem type was not cached either. This meant that the same match type with a skolem type as selector was created many times instead of once, so its reduction was not cached either. We now cache skolem types. It's a bet that in practice few skolem types are created and that therefore the hashtable pollution with skolemtypes is less of a problem than the potential problem of losing identity of types containing skolem types. This was originally motivated by scala#14903 but that ended up being fixed in a different way. It still seems like a good idea to do this since it matches what we do for type variables.
Compiler version
3.1.2
Minimized code
I encountered the problem while trying to migrate a part of akka-http (forked from parboiled2) to Scala 3.
Output
This does compile although the compilation is very slow and making
pattereven slightly more complex makes the compilation time much longer. It turns out that the compilation time strongly depends on how thetailSwitchinstance is defined.If it's just an
implicit deforgiventhen the compilation takes about 3.5 minutes. Forinline givenit's 2 minutes. Luckily there seems to be a workaround for the problem, which is usingtransparent inline given- then the code compiles in less than a second.Expectation
The compilation should be as fast as for
transparent inline givenfor all other cases as the types are given very explicitly here andtransparentdoesn't seem to narrow the type.The text was updated successfully, but these errors were encountered: