abnormal long compilation time of match over case classes structure

[rssh]

Compiler version

3.1.0-RC2

Minimized example

package ips.clang

trait LongCompilation {

  def toCastExpression(expr: Expression): CastExpression =
    expr match
      case cExpr: CastExpression => cExpr
      case _ => WrappedExpression(expr)

}
sealed trait C_Ast
sealed trait Expression extends C_Ast

sealed trait PrimaryExpression extends PostfixExpression
case class Identifier(value:String)  extends PrimaryExpression
case class IntConstant(value: Int)  extends PrimaryExpression
case class CharConstant(value: Char)  extends PrimaryExpression
case class StringLiteral(value: String) extends PrimaryExpression
case class WrappedExpression(value: Expression)  extends PrimaryExpression
case class GenericSelection( qualifier: PrecAssigmentExpression, associations: List[Int] )

sealed trait PostfixExpression extends UnaryExpression
case class ArrayIndexExpression(base: PostfixExpression, index: Expression) extends PostfixExpression
case class FunctionCallExpression(fun: PostfixExpression, arguments: List[PrecAssigmentExpression]) extends PostfixExpression
case class DotSelectExpression(qualifier: PostfixExpression, select: Identifier) extends PostfixExpression
case class ArrowSelectExpression(qualifier: PostfixExpression, select: Identifier) extends PostfixExpression
case class PostfixIncrementExpression(base: PostfixExpression) extends PostfixExpression
case class PostfixDecrementExpression(base: PostfixExpression) extends PostfixExpression
case class CompoundLiteral(typeName: TypeName, initializers: List[Int]) extends PostfixExpression

sealed trait UnaryExpression extends CastExpression
case class PrefixIncrementExpression(base: UnaryExpression) extends UnaryExpression
case class PrefixDecrementExpression(base: UnaryExpression) extends UnaryExpression
case class UnaryOperatorExpression(op: String, argument: CastExpression) extends UnaryExpression
case class SizeofConstExpression(expression: UnaryExpression) extends UnaryExpression
case class SizeofTypeExpression(typeName: TypeName) extends UnaryExpression
// each AdditionalUnaryExpressionX increase compilation time
sealed trait AdditionalUnaryExpression1 extends UnaryExpression
sealed trait AdditionalUnaryExpression2 extends UnaryExpression
sealed trait AdditionalUnaryExpression3 extends UnaryExpression
sealed trait AdditionalUnaryExpression4 extends UnaryExpression
sealed trait AdditionalUnaryExpression5 extends UnaryExpression

sealed trait CastExpression extends MultiplicativeExpression
case class Cast(typeName: TypeName, argument: CastExpression) extends CastExpression

sealed trait BinaryExpression {
  def op: String
  def frs: Expression
  def snd: Expression
}

sealed trait MultiplicativeExpression extends AdditiveExpression
case class MultiplicativeBinaryExpression(op: String,
                                          frs: MultiplicativeExpression,
                                          snd: CastExpression) extends MultiplicativeExpression
                                                                 with BinaryExpression

sealed trait AdditiveExpression extends ShiftExpression
case class AdditiveBinaryExpression(op: String,
                                    frs: MultiplicativeExpression,
                                    snd: CastExpression) extends MultiplicativeExpression with BinaryExpression

sealed trait ShiftExpression extends RelationalExpression
case class ShiftBinaryExpression(op: String,
      frs: MultiplicativeExpression, snd: CastExpression) extends MultiplicativeExpression with BinaryExpression

sealed trait RelationalExpression extends EqualityExpression
case class RelationalBinaryExpression(op: String,
      frs: RelationalExpression, snd: ShiftExpression) extends RelationalExpression with BinaryExpression

sealed trait EqualityExpression extends PrecAndExpression
case class EqualityBinaryExpression(op: String,
      frs: RelationalExpression, snd: ShiftExpression) extends EqualityExpression with BinaryExpression

sealed trait PrecAndExpression extends PrecExclusiveOrExpression
case class AndBinaryExpression(op: String,
     frs: PrecAndExpression, snd: EqualityExpression) extends PrecAndExpression with BinaryExpression


sealed trait PrecExclusiveOrExpression extends PrecInclusiveOrExpression
case class ExclusiveOrBinaryExpression(
    op: String,
    frs: PrecExclusiveOrExpression,
    snd: PrecAndExpression) extends PrecExclusiveOrExpression with BinaryExpression

sealed trait PrecInclusiveOrExpression extends PrecLogicalAndExpression
case class InclusiveOrBinaryExpression(op: String,
          frs: PrecExclusiveOrExpression,
          snd: PrecAndExpression) extends PrecInclusiveOrExpression with BinaryExpression

sealed trait PrecLogicalAndExpression extends PrecLogicalOrExpression
case class LogicalAndBinaryExpression(op: String,
    frs: PrecLogicalAndExpression,
    snd: PrecInclusiveOrExpression) extends PrecLogicalAndExpression with BinaryExpression

sealed trait PrecLogicalOrExpression extends PrecConditionalExpression
case class LogicalOrBinaryExpression(op: String,
        frs: PrecLogicalAndExpression,
        snd: PrecInclusiveOrExpression) extends PrecLogicalOrExpression with BinaryExpression


sealed trait PrecConditionalExpression extends PrecAssigmentExpression
case class ConditionalExpression(
        cond: PrecLogicalOrExpression,
        frs: Expression,
        snd: PrecConditionalExpression) extends PrecConditionalExpression

sealed trait PrecAssigmentExpression extends Expression
case class AssigmentExpression(
        op: String,
        frs: UnaryExpression,
        snd: PrecAssigmentExpression) extends PrecAssigmentExpression

case class CommaExpression(frs: Expression, snd: Expression) extends Expression
case class CommaExpression2(frs: Expression, snd: Expression) extends Expression

case class Declarator(pointer: Option[Pointer], base: String)
case class TypeName(specifiers: List[DeclarationSpecifier], declarator: Option[AbstractDeclarator])

sealed trait AbstractDeclarator
case class Pointer( typeQual: List[DeclarationSpecifier], pointer: Option[Pointer]) extends AbstractDeclarator

sealed trait DeclarationSpecifier

Output

info] compiling 1 Scala source to /Users/rssh/work/oss/algorithmic-algebras-embedding/target/scala-3.1.0-RC2/classes ...
[success] Total time: 151 s (02:31), completed 20 Sept 2021, 07:38:15

Expectation

compilation speed should be significantly faster.

[rssh]

long-compilation-example.tar.gz

full sbt project

[griggt]

Performance seems to have regressed between 3.0.1 and 3.0.2:

$ time scalac -3.0.1 i13565.scala
real    0m5.204s
user    0m14.325s
sys     0m0.461s

$ time scalac -3.0.2 i13565.scala
real    2m35.770s
user    2m45.828s
sys     0m0.924s

[bishabosha]

I do not think this needs minimisation - it is a stress test (although it should not be stressing)

Although would be good to try and track the growth of the problem over reducing cases

[dwijnand]

Performance seems to have regressed between 3.0.1 and 3.0.2:

$ time scalac -3.0.1 i13565.scala
real    0m5.204s
user    0m14.325s
sys     0m0.461s

$ time scalac -3.0.2 i13565.scala
real    2m35.770s
user    2m45.828s
sys     0m0.924s

I recognise those command line options! 😄

I'm pretty sure #13030 is what changed that.

There's a number of places in the space engine where work is done multiple times, some of which I've removed (in master) while fixing other issues but others where the result is less easily retrainable. Meaning we could memoise them, but then we might start breaching our memory budget. I'll play with the case and see what I can see.

[rssh]

minimization is problematic because we can lose visible slowdown during this. I.e. I'm pretty sure, that with 3 case classes instead of 63 this will be fast. How we can detect a 'minimal limit' when performance difference becomes visible?

[dwijnand]

So 63 classes takes (on your machine) 2:30 minutes. Perhaps we can write out 4 or 5 incremental steps on that (e.g. 8 -> 16 -> 32 -> 64 classes), and assert on by how much compilation speed increases. As in, linear growth rather than exponential, perhaps.