Exponential growth of compilation time with number of inferred types of List element
#19907
Comments
WojciechMazur
changed the title
Lit element types
WojciechMazur
changed the title
Lit element typesList element
SethTisue
changed the title
List elementList element
|
@WojciechMazur can you try to minimise this? |
|
also somewhat reminiscent of scala/bug#10908, which also links to a number of similar bugs — I don't know if there's anything to be learned from them as the Scala 3 typer internals are so different |
|
The issue seems to be mostly related to number of member types, there needs to be at least 2 different member types (can be Int and Unit), these seem to have the biggest impact on compilation time. Number of member types has no effect on Scala 2.13 compilation time Generator for safe-contained minimisation: import scala.util.Random
val random = Random(19907)
// We need to have at least 2 member types of different types
val paramTypes = Array("Int", "Unit" /*, "String", "Float", "Long" */)
def nextParam = paramTypes(random.between(0, paramTypes.length))
@main def GenSources(instances: Int, memberTypes: Int, hintType: Boolean) =
System.err.println(s"Size=$instances, memberTypes=$memberTypes")
val EndpointType = s"ServerEndpoint[Any, Option]"
val instanceNames = List.tabulate(instances)(n => s"instance$n")
def delimited(seq: Seq[String]) = if seq.isEmpty then "" else seq.mkString("", ", ", ",")
val instanceDefs = instanceNames.map { routeName =>
s"""\n val $routeName = ServerEndpoint[${delimited(List.fill(memberTypes)(nextParam))} Any, Option]"""
}
val paramTypes = delimited(0.until(memberTypes).map(n => s"_T$n"))
val maybeHint = if hintType then s"[$EndpointType]" else ""
val code = s"""
abstract class ServerEndpoint[-R, F[_]] {
${0.until(memberTypes).map(n => s"type T$n").mkString("\n ")}
}
object ServerEndpoint {
type Full[$paramTypes -R, F[_]] =
ServerEndpoint[R, F] { ${0.until(memberTypes).map(n => s"\n type T$n = _T$n").mkString}
}
def apply[$paramTypes R, F[_]]: ServerEndpoint.Full[$paramTypes R, F] = ???
}
object Test {
type Route = ServerEndpoint[Any, Option]
def routes: List[$EndpointType] = { ${instanceDefs.mkString("")}
List${maybeHint}(${instanceNames.mkString(", ")})
}
}
"""
println(code)Run using Results for 1000 insances with 1-3 member types: > scala-cli run genSources.scala -- 1000 1 false | time scala-cli compile - --server=false -S 3
Size=1000, memberTypes=1
scala-cli compile - --server=false -S 3 10.65s user 0.41s system 313% cpu 3.528 total
> scala-cli run genSources.scala -- 1000 2 false | time scala-cli compile - --server=false -S 3
Size=1000, memberTypes=2
scala-cli compile - --server=false -S 3 14.12s user 0.42s system 227% cpu 6.387 total
> scala-cli run genSources.scala -- 1000 3 false | time scala-cli compile - --server=false -S 3
Size=1000, memberTypes=3
scala-cli compile - --server=false -S 3 36.90s user 0.43s system 129% cpu 28.795 total |
|
It would be good to get a self-contained minimization. I tried to run the script but got: ~/workspace/dotty/tests/new> scala-cli run GenSources.scala -- 100 false | scala-cli compile -O -Ystop-after:typer Also, there's still an external reference to sttp. This makes it too hard to debug for me. |
|
@noti0na1 Maybe you can give it a try? |
|
|
@odersky The generator in #19907 (comment) is self contained, it does not depend on anything. It has different inputs then the original generator, try with |
|
With the 
Interpolating tvars on the It tries to |
|
Thanks for the analysis @noti0na1. So, the generator generates a lot of different types for the arguments of a long |
|
why would |
In Tapir routes (original code) there are 5 member types, typically at least 3 of them would be different:
A quick way to test how |
|
OK, but then that does not correspond to the generated code, which has many more unique member types. EDIT: I think I misunderstood. So there are different combinations of member types in ServerEndPoint, and ServerEndPoints were the list arguments? The question is how many unique ServerEndPoint combinations are there? |
|
In the original code we had a What I've missed before is that fact that each ServerEndpoint also defines it's parametrized self type - all the types but So I guess this additional |
|
I think it's probably the 140 that matters here. Forming least upper bounds is quadratic in the number of unique types, and @noti0na1's profile shows that it is indeed the merge function that takes the most time. The other elements would matter insofar as it takes more time to compare complicated types than simple ones, but this should be a constant factor. |
|
Some things we could consider:
|
Replace mergeIfSuper by a different algorithm that is more efficient. We drop or-summands in both arguments of a lub that are subsumed by the other. This avoids expensive recursive calls to lub or expensive comparisons with union types on the right. I tested the previous performance regression #19907 with the new algorithm, and without the changes in #19995 that avoid a slow lub. Where previously it took minutes it now compiles fast. Specifically, we get for i19907_slow_1000_3.scala: 2.9s with the optimizations in #19995, 3.3s with just this PR. And for i19907_slow_1000_4.scala: 3.9s with the optimizations in #19995, 4.5s with just this PR. So the optimizations in #19995 are much less critical now since lubs are much faster. Still, it's probably worthwhile to leave them in in case there is a humongous program that stresses lubs even more.
When creating list using local values without declared types the compilation time can grow exponentially when infered types are complex. Upon creating
List(...)compiler seems to be stuckTypeComparerfor long time.Compiler version
3.3.3
Minimized code
Not yet minimised, reproduction using source generator:
tl;dr
We generate N Tapir routes without declaring explicitly their type (each of them should infer to
ServerEndpoint[Any, Future]We combine all the N routes into a List.
hintTypeparameter controls if we'd combine them usingList[ServerEndpoint[Any, Future](route1, route2, ...)orList(route1, route2, ...)in which case the compile time skyrocketsRun using
Measures
Hinted
List[T](...)Infered `List(...)
Thread stacktrace
Collected when compiler was stuck in calculating type of infered elements.
The text was updated successfully, but these errors were encountered: