Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Regression of compilation times in the Scala Next line for large intersection type / for-comprehension blocks #20516

Closed
WojciechMazur opened this issue Jun 3, 2024 · 4 comments
Closed

Regression of compilation times in the Scala Next line for large intersection type / for-comprehension blocks #20516

WojciechMazur opened this issue Jun 3, 2024 · 4 comments
Assignees
@noti0na1
Labels
area:typer itype:performance regression This worked in a previous version but doesn't anymore

Comments

@WojciechMazur
Copy link
Contributor

The compilation of following code inflicts a significant raise of compilation time in the last Scala 3 versions

  • Scala 2.13.14: ~1s
  • Scala 3.3.3: ~2s
  • Scala 3.4.2: ~18s
  • Scala 3.5.0-RC1: ~203s
  • 3.5.1-RC1-bin-20240530-01b404f-NIGHTLY: ~210s
object Main {
  trait A {}
  trait B {}
  trait C {}
  trait D {}
  trait E {}
  trait F {}
  trait G {}
  trait H {}
  trait I {}
  trait J {}
  trait K {}
  trait L {}
  trait M {}
  trait N {}
  trait O {}
  trait P {}
  trait Q {}
  trait R {}
  trait S {}
  trait T {}
  trait U {}
  trait V {}
  trait W {}
  trait X {}
  trait Y {}
  trait Z {}

  type AlphabeticServices = A & B & C & D & E & F & G & H & I & J & K & L & M & N & O & P & Q & R & S & T & U & V & W & X & Y & Z

  type EnvOutA = B & C & D & E & F & G & H & I & J & K & L & M & N & O & P & Q & R & S & T & U & V & W & X & Y & Z
  type EnvOutB = A & C & D & E & F & G & H & I & J & K & L & M & N & O & P & Q & R & S & T & U & V & W & X & Y & Z
  type EnvOutC = A & B & D & E & F & G & H & I & J & K & L & M & N & O & P & Q & R & S & T & U & V & W & X & Y & Z
  type EnvOutD = A & B & C & E & F & G & H & I & J & K & L & M & N & O & P & Q & R & S & T & U & V & W & X & Y & Z
  type EnvOutE = A & B & C & D & F & G & H & I & J & K & L & M & N & O & P & Q & R & S & T & U & V & W & X & Y & Z
  type EnvOutF = A & B & C & D & E & G & H & I & J & K & L & M & N & O & P & Q & R & S & T & U & V & W & X & Y & Z
  type EnvOutG = A & B & C & D & E & F & H & I & J & K & L & M & N & O & P & Q & R & S & T & U & V & W & X & Y & Z
  type EnvOutH = A & B & C & D & E & F & G & I & J & K & L & M & N & O & P & Q & R & S & T & U & V & W & X & Y & Z
  type EnvOutI = A & B & C & D & E & F & G & H & J & K & L & M & N & O & P & Q & R & S & T & U & V & W & X & Y & Z
  type EnvOutJ = A & B & C & D & E & F & G & H & I & K & L & M & N & O & P & Q & R & S & T & U & V & W & X & Y & Z
  type EnvOutK = A & B & C & D & E & F & G & H & I & J & L & M & N & O & P & Q & R & S & T & U & V & W & X & Y & Z
  type EnvOutL = A & B & C & D & E & F & G & H & I & J & K & M & N & O & P & Q & R & S & T & U & V & W & X & Y & Z
  type EnvOutM = A & B & C & D & E & F & G & H & I & J & K & L & N & O & P & Q & R & S & T & U & V & W & X & Y & Z
  type EnvOutN = A & B & C & D & E & F & G & H & I & J & K & L & M & O & P & Q & R & S & T & U & V & W & X & Y & Z
  type EnvOutO = A & B & C & D & E & F & G & H & I & J & K & L & M & N & P & Q & R & S & T & U & V & W & X & Y & Z
  type EnvOutP = A & B & C & D & E & F & G & H & I & J & K & L & M & N & O & Q & R & S & T & U & V & W & X & Y & Z
  type EnvOutQ = A & B & C & D & E & F & G & H & I & J & K & L & M & N & O & P & R & S & T & U & V & W & X & Y & Z
  type EnvOutR = A & B & C & D & E & F & G & H & I & J & K & L & M & N & O & P & Q & S & T & U & V & W & X & Y & Z
  type EnvOutS = A & B & C & D & E & F & G & H & I & J & K & L & M & N & O & P & Q & R & T & U & V & W & X & Y & Z
  type EnvOutT = A & B & C & D & E & F & G & H & I & J & K & L & M & N & O & P & Q & R & S & U & V & W & X & Y & Z
  type EnvOutU = A & B & C & D & E & F & G & H & I & J & K & L & M & N & O & P & Q & R & S & T & V & W & X & Y & Z
  type EnvOutV = A & B & C & D & E & F & G & H & I & J & K & L & M & N & O & P & Q & R & S & T & U & W & X & Y & Z
  type EnvOutW = A & B & C & D & E & F & G & H & I & J & K & L & M & N & O & P & Q & R & S & T & U & V & X & Y & Z
  type EnvOutX = A & B & C & D & E & F & G & H & I & J & K & L & M & N & O & P & Q & R & S & T & U & V & W & Y & Z
  type EnvOutY = A & B & C & D & E & F & G & H & I & J & K & L & M & N & O & P & Q & R & S & T & U & V & W & X & Z
  type EnvOutZ = A & B & C & D & E & F & G & H & I & J & K & L & M & N & O & P & Q & R & S & T & U & V & W & X & Y

  trait Reader[-E, A] {
    def map[B](f: A => B): Reader[E, B] = ???
    def flatMap[E2 <: E, B](f: A => Reader[E2, B]): Reader[E2, B] = ???
  }

  def e1: Reader[EnvOutA, Unit] = ???
  def e2: Reader[EnvOutB, Unit] = ???
  def e3: Reader[EnvOutC, Unit] = ???
  def e4: Reader[EnvOutD, Unit] = ???
  def e5: Reader[EnvOutE, Unit] = ???
  def e6: Reader[EnvOutF, Unit] = ???
  def e7: Reader[EnvOutG, Unit] = ???
  def e8: Reader[EnvOutH, Unit] = ???
  def e9: Reader[EnvOutI, Unit] = ???
  def e10: Reader[EnvOutJ, Unit] = ???
  def e11: Reader[EnvOutK, Unit] = ???
  def e12: Reader[EnvOutL, Unit] = ???
  def e13: Reader[EnvOutM, Unit] = ???
  def e14: Reader[EnvOutN, Unit] = ???
  def e15: Reader[EnvOutO, Unit] = ???
  def e16: Reader[EnvOutP, Unit] = ???
  def e17: Reader[EnvOutQ, Unit] = ???
  def e18: Reader[EnvOutR, Unit] = ???
  def e19: Reader[EnvOutS, Unit] = ???
  def e20: Reader[EnvOutT, Unit] = ???
  def e21: Reader[EnvOutU, Unit] = ???
  def e22: Reader[EnvOutV, Unit] = ???
  def e23: Reader[EnvOutW, Unit] = ???
  def e24: Reader[EnvOutX, Unit] = ???
  def e25: Reader[EnvOutY, Unit] = ???
  def e26: Reader[EnvOutZ, Unit] = ???

  def program: Reader[AlphabeticServices, Unit] = for {
        //1
    _ <- e1
    _ <- e2
    _ <- e3
    _ <- e4
    _ <- e5
    _ <- e6
    _ <- e7
    _ <- e8
    _ <- e8
    _ <- e9
    _ <- e10
    _ <- e11
    _ <- e12
    _ <- e13
    _ <- e14
    _ <- e15
    _ <- e16
    _ <- e17
    _ <- e18
    _ <- e19
    _ <- e20
    _ <- e21
    _ <- e22
    _ <- e23
    _ <- e24
    _ <- e25
    _ <- e26
    //2
    _ <- e1
    _ <- e2
    _ <- e3
    _ <- e4
    _ <- e5
    _ <- e6
    _ <- e7
    _ <- e8
    _ <- e8
    _ <- e9
    _ <- e10
    _ <- e11
    _ <- e12
    _ <- e13
    _ <- e14
    _ <- e15
    _ <- e16
    _ <- e17
    _ <- e18
    _ <- e19
    _ <- e20
    _ <- e21
    _ <- e22
    _ <- e23
    _ <- e24
    _ <- e25
    _ <- e26
    //3
    _ <- e1
    _ <- e2
    _ <- e3
    _ <- e4
    _ <- e5
    _ <- e6
    _ <- e7
    _ <- e8
    _ <- e8
    _ <- e9
    _ <- e10
    _ <- e11
    _ <- e12
    _ <- e13
    _ <- e14
    _ <- e15
    _ <- e16
    _ <- e17
    _ <- e18
    _ <- e19
    _ <- e20
    _ <- e21
    _ <- e22
    _ <- e23
    _ <- e24
    _ <- e25
    _ <- e26
    //4
    _ <- e1
    _ <- e2
    _ <- e3
    _ <- e4
    _ <- e5
    _ <- e6
    _ <- e7
    _ <- e8
    _ <- e8
    _ <- e9
    _ <- e10
    _ <- e11
    _ <- e12
    _ <- e13
    _ <- e14
    _ <- e15
    _ <- e16
    _ <- e17
    _ <- e18
    _ <- e19
    _ <- e20
    _ <- e21
    _ <- e22
    _ <- e23
    _ <- e24
    _ <- e25
    _ <- e26
    } yield ()
}

Originally posted by @rlecomte in #20120 (comment)
@WojciechMazur WojciechMazur added area:typer itype:performance regression This worked in a previous version but doesn't anymore labels Jun 3, 2024
@WojciechMazur
Copy link
Contributor Author

Bisect points to 9c80a7c as the latest, the most significant change

@noti0na1
Copy link
Member

noti0na1 commented Jun 3, 2024

It seems that a large intersection type is inferred for the first type argument of flatMap: EnvOutA & EnvOutB & EnvOutC & ....
However, before 3.5, the inferred type is EnvOutA & EnvOutB, which should cover the intersection of all alphabetic types A & B & C & ....

@noti0na1
Copy link
Member

noti0na1 commented Jun 3, 2024

This issue is caused by the new dropIfSuper.

We know EnvOutC = A & B & D & ... is a super type of EnvOutA & EnvOutB, but EnvOutA is not a subtype of EnvOutC, same with EnvOutB.

We want dropIfSuper(EnvOutC, EnvOutA & EnvOutB) to return NoType, but inside the body, EnvOutC is a type alias, so tp match ... does not go to the AndType case.
Then, it tries to compare isSuperOf(EnvOutA) or isSuperOf(EnvOutB). In both cases, the results are clearly false.

Before 3.5, dropIfSuper checks the subtype of two arguments directly at first, hence it can avoid this issue.

cc @odersky

@noti0na1 noti0na1 mentioned this issue Jun 4, 2024
Merged
noti0na1 added a commit that referenced this issue Jun 19, 2024
@noti0na1
Fall back to direct subtype comparison at the end in dropIfSuper and …
1f00e4a 
…dropIfSub (#20523)

Improve compiling in #20516.

We need to be careful to check branches of AndTypes and OrTypes in
correct order, see discussion in issue #20516.

Fall back to direct subtype comparison at the end in dropIfSuper and
dropIfSub.

We may need to improve subtype checking for large intersections further
to be able to fully test the example.
@Gedochao
Copy link
Contributor

Addressed in #20523. Closing this.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@noti0na1 noti0na1

Labels
area:typer itype:performance regression This worked in a previous version but doesn't anymore
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@noti0na1 @Gedochao @WojciechMazur