Exponential growth in compilation time

[scabug]

There seems to be an exponential growth in compilation time when type expression complexity increases linearly. The following code example takes a very long time to compile. It needs to be compiled with "-Yrecursion 10" compiler option. When changing T1 to "_4#Add[_0]" for example, the compilation time is reasonable.

object MInts {
  sealed trait MInt {
    type Add[N <: MInt] <: MInt
    type Suc <: MInt
  }

  final class _0 extends MInt {
    type Add[N <: MInt] = N
    type Suc = Succ[_0]
  }

  final class Succ[P <: MInt] extends MInt {
    type Add[N <: MInt] = P#Add[N]#Suc
    type Suc = Succ[Succ[P]]
  }

  type _1 = Succ[_0]
  type _2 = Succ[_1]
  type _3 = Succ[_2]
  type _4 = Succ[_3]
  type _5 = Succ[_4]
  type _6 = Succ[_5]
  type _7 = Succ[_6]
  type _8 = Succ[_7]
  type _9 = Succ[_8]

  // Anything above _6 increases compile time a lot
  type T1 = _9#Add[_0]
}

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-1327?orig=1 Reporter: @jesnor

[scabug]

Geoffrey Alan Washburn (washburn) said: It is unclear to me that this can really be considered a defect unless you are aware of a different type inference/checking algorithm for Scala we could be using that would fall into a better complexity class. Not to mention that the -Y compiler options are called "private" for a reason.

If you know a specific way to address this problem, submit a patch or a SIP, but I think it is likely that fixing this would require a significant re-engineering of the compiler that we probably won't consider until we have worked out the theory of a solution that doesn't require a recursion depth hack.

[scabug]

@jesnor said: Well, it's a defect in the sense that the compiler becomes unusable for compiling certain valid Scala code. It's not a defect in the sense that it violates the language specification.

The example is really simple and no type inference is needed, the type path is straight forward to evaluate. So I was hoping it would just require an easy optimization fix in the type checker, but if it's, like you say (and I doubt), an inherent property of the type checking algorithm that the time to type check code like this grows exponentially (or similar), then, as you say, it would require a much larger modification.

[scabug]

@mcdirmid said: Here be dragons.

There are much easier ways to do a denial of service (DOS) attack on the type inference component; e.g., create a list with 100 explicit elements in one expression that is assigned to a type inferred val! In my experience, we shouldn't worry about these too much unless they occur in the path of reasonable normal programming.

[scabug]

Geoffrey Alan Washburn (washburn) said: But your code is technically not a valid Scala program because you are using an undocumented escape hatch to typecheck a program that is normally disallowed.

Do you have a particular reason you doubt that this is an inherent result of the typechecking algorithm? There are already parts of the typechecker that are known to be quadratic (or even cubic if I am remembering correctly) so it wouldn't surprise me that allowing arbitrary computation at the type level would lead to exponential behavior.

In any event, I will assign this to Martin who knows more about how type inference and checking are implemented and can make a final determination.

[scabug]

@odersky said: I can't do anything about this without a diagnosis where the exponential behavior comes from. So either we bury it or someone (Geoffrey?) does that analysis.

[scabug]

@jesnor said: Replying to [comment:4 washburn]:

Do you have a particular reason you doubt that this is an inherent result of the typechecking algorithm? There are already parts of the typechecker that are known to be quadratic (or even cubic if I am remembering correctly) so it wouldn't surprise me that allowing arbitrary computation at the type level would lead to exponential behavior.

I'm not familiar with the details of the typechecking algorithm or the implementation in the compiler. But the type evaluation is this example is really straight forward and I find it hard to see how a well designed typechecking algorithm would take such a long time to finish, thus my guesstimate is that there is some problem in the implementation. All I'm suggesting is that the compilation is profiled and if a hotspot is identified it's analyzed to see if an optimization can easily be applied.

Replying to [comment:3 mcdirmid]: It's hard to define what will "occur in the path of reasonable normal programming". I agree that code like this doesn't occur in any Scala application today because it wasn't possible to compile it before Geoffrey added the recursion option. However, there are useful applications for code like this, for example units or compile time checking of integer bounds. So, if there is good compiler support for this, it will be used in "normal programming".

[scabug]

Geoffrey Alan Washburn (washburn) said: While it may look like straightforward code, it is not generally desirable to add too many heuristics to the algorithm to accommodate special cases.

I had thought about emphasizing this earlier, but I thought it wouldn't be necessary: -Yrecursion is a hack intended entirely for experimental purposes. In particular it is useful to have around if we or other researchers wish to experiment with programs that a less restrictive typechecking algorithm would allow. It should not be used for production code and as a "private" compiler option we make no guarantees it will be available in the future. So no, this will probably not be "normal" code for quite some time.

Maybe if we can work out a better typechecking algorithm that does not require specifying a recursion depth we will make that the default. However, I seem to be the only person interested in such a research project, and I am already completely overloaded with more fundamental research.

If you really want to be able to use this functionality in production programs sooner than that, I recommend you write a SIP describing a proposed language extension.

[scabug]

@odersky said: Milestone postponed deleted

[scabug]

Geoffrey Alan Washburn (washburn) said: Reassigning to scala_community as it is unlikely I will ever fix this issue.

[scabug]

Lars Hupel (larsrh) said: Is this still an issue with 2.8? I took the example and pasted it into the repl, and the compilation time seems ok (less than 5 seconds). As far as I can see, this ticket could be closed.

[scabug]

@paulp said: Even if it's not fixed according to whatever metric, it is in the category of tickets we should be closing as too vague. We must cull mercilessly so the important ones are not lost in the noise.