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

Slow compilation times when inferring type HKT with intersection types #20120

Closed
WojciechMazur opened this issue Apr 8, 2024 · 5 comments · Fixed by #20399
Closed

Slow compilation times when inferring type HKT with intersection types #20120

WojciechMazur opened this issue Apr 8, 2024 · 5 comments · Fixed by #20399
Assignees
@odersky @EugeneFlesselle
Labels
area:typer itype:bug itype:performance
Milestone
3.5.1

Comments

@WojciechMazur
Copy link
Contributor

WojciechMazur commented Apr 8, 2024 •
edited
Loading

Based on usage of Tapir in commercial project. Whenever one of the input/output types in the Endpoint type is contains an intersection type the compilation type are ~4x longer when compared with the same type using tuple instead of intersection type.

In the original project compilation time of single endpoint val could take up to 1s - mostly due to additional implicit search for Codec instances and more complex method signatures. It is a blocker for finishing migration from Scala 2.13 to Scala 3, due to 4x longer compilation times (~90s Scala 2.13, 5 min Scala 3)

Compiler version

Tested only on fork #19897 containing prototype support for -Yprofile-trace. The issue can be observed in original codebase in all Scala 3.3 and 3.4 versions.

Minimized code

To be able to reproduce the compilation times observed in the original project the code cannot be fully minimized. Tapir uses implicits to infer result types for concatenation of input/output parameters, requiring us to include this mechanism in simplified form. Whole code takes ~200 lines of code.
Reordering in/out method calls order can impact compilation times.

repro.zip

// Repro.scala
import scala.concurrent.Future

object Repro {
  trait ApiError
  trait AuthInput
  trait AuthOutput
  trait AuthenticatedRequestContext
  trait ObjectId
  trait Output

  type AuthenticatedEndpoint =
    PartialServerEndpointWithSecurityOutput[
      AuthInput,
      AuthenticatedRequestContext,
      Unit,
      ApiError,
      AuthOutput,
      Unit,
      Any,
      Future
    ]

  class BaseEndpoints {
    val authenticatedEndpoint: AuthenticatedEndpoint = ???
  }

  class Endpoints(val baseEndpoints: BaseEndpoints) extends Tapir {
    def jsonBody[T]: EndpointIO[String] = ???

    trait Foo
    trait Tag[T]

    // Type annotation based on compiler outputs using -Xprint:typer
    val baseEndpointWithIntersection
        : Endpoints.this.baseEndpoints.authenticatedEndpoint.EndpointType[
          AuthInput,
          ObjectId & Foo,
          ApiError,
          Unit,
          Any
        ] = baseEndpoints.authenticatedEndpoint.in(path[ObjectId & Foo]("arg"))

    // Type annotation based on compiler outputs using -Xprint:typer
    val baseEndpointNoIntersection: Endpoints.this.baseEndpoints.authenticatedEndpoint.EndpointType[
      AuthInput,
      (ObjectId, Foo),
      ApiError,
      Unit,
      Any
    ] = baseEndpoints.authenticatedEndpoint.in(path[(ObjectId, Foo)]("arg"))

    def queryString: EndpointInput[String] = ???
    def queryMaybeString: EndpointInput[Option[String]] = ???

    // Takes ~130ms - initial object to enforce classloading so the later measurments can be more
    object T0 {
      val groupCalendarNoLogic =
        baseEndpoints.authenticatedEndpoint
          .in("calendar")
          .in(queryString.and(queryMaybeString))
          .get
          .out(jsonBody[Output])
    }

    // Takes ~260 ms
    object T1 {
      val groupCalendarNoLogic =
        baseEndpointWithIntersection
          .in("calendar")
          .in(queryString.and(queryMaybeString))
          .get
          .out(jsonBody[Output])
    }

    // Takes 34ms
    object T2 {
      val groupCalendarNoLogic =
        baseEndpointNoIntersection
          .in("calendar")
          .in(queryString.and(queryMaybeString))
          .get
          .out(jsonBody[Output])
    }
    // Same as T1, take ~140ms, faster due to caching in compiler + JVM warmup
    object T1Bis {
      val groupCalendarNoLogic =
        baseEndpointWithIntersection
          .in("calendar")
          .in(queryString.and(queryMaybeString))
          .get
          .out(jsonBody[Output])
    }
    // Same as T2, takes ~18ms
    object T2Bis {
      val groupCalendarNoLogic =
        baseEndpointNoIntersection
          .in("calendar")
          .in(queryString.and(queryMaybeString))
          .get
          .out(jsonBody[Output])
    }
  }
}

// api.scala

trait Tapir {
  implicit def stringToPath(s: String): EndpointInput[Unit] = ???
  def path[T](name: String): EndpointInput[T] = ???
  def stringBody: EndpointIO[String] = ???
}

trait EndpointInput[T] {
  def and[U, TU](other: EndpointInput[U])(implicit concat: ParamConcat.Aux[T, U, TU]): EndpointInput[TU]
}

sealed trait EndpointOutput[T] {
  def and[J, IJ](other: EndpointOutput[J])(implicit concat: ParamConcat.Aux[T, J, IJ]): EndpointOutput[IJ] = ???
}

sealed trait EndpointIO[T] extends EndpointInput[T] with EndpointOutput[T] {
  def and[J, IJ](other: EndpointIO[J])(implicit concat: ParamConcat.Aux[T, J, IJ]): EndpointIO[IJ] = ???
}

trait PartialServerEndpointWithSecurityOutput[ SECURITY_INPUT, PRINCIPAL, INPUT, ERROR_OUTPUT, SECURITY_OUTPUT, OUTPUT, -R, F[_]] 
    extends EndpointInputsOps[SECURITY_INPUT, INPUT, ERROR_OUTPUT, OUTPUT, R]
    with EndpointOutputsOps[SECURITY_INPUT, INPUT, ERROR_OUTPUT, OUTPUT, R]
    { outer =>
  override type EndpointType[_A, _I, _E, _O, -_R] =
    PartialServerEndpointWithSecurityOutput[_A, PRINCIPAL, _I, _E, SECURITY_OUTPUT, _O, _R, F]
}

trait EndpointInputsOps[A, I, E, O, -R] {
  type EndpointType[_A, _I, _E, _O, -_R]

  def get: EndpointType[A, I, E, O, R] = ???
  def in[J, IJ](i: EndpointInput[J])(implicit concat: ParamConcat.Aux[I, J, IJ]): EndpointType[A, IJ, E, O, R] = ???
}

trait EndpointOutputsOps[A, I, E, O, -R] {
  type EndpointType[_A, _I, _E, _O, -_R]
  def out[P, OP](i: EndpointOutput[P])(implicit ts: ParamConcat.Aux[O, P, OP]): EndpointType[A, I, E, OP, R] = ???
}
// typelevel.scala
import TupleOps.{AppendOne, FoldLeft}

trait ParamConcat[T, U] { type Out }

object ParamConcat extends LowPriorityTupleConcat3 {
  implicit def concatUnitLeft[U](implicit ua: TupleArity[U]): Aux[Unit, U, U] = ???
}

trait LowPriorityTupleConcat3 extends LowPriorityTupleConcat1 {
  implicit def concatUnitRight[T](implicit ta: TupleArity[T]): Aux[T, Unit, T] = ???
}

trait LowPriorityTupleConcat1 extends LowPriorityTupleConcat0 {
  implicit def concatSingleAndTuple[T, U, TU](implicit tc: TupleOps.JoinAux[Tuple1[T], U, TU], ua: TupleArity[U]): Aux[T, U, TU] = ???
}

trait LowPriorityTupleConcat0 {
  type Aux[T, U, TU] = ParamConcat[T, U] { type Out = TU }
  implicit def concatSingleAndSingle[T, U, TU](implicit tc: TupleOps.JoinAux[Tuple1[T], Tuple1[U], TU]): Aux[T, U, TU] = ???
}

trait TupleArity[T] { def arity: Int} 
object TupleArity extends LowPriorityTupleArity {
  implicit def tupleArity2[A1, A2]: TupleArity[(A1, A2)] = ???
}
trait LowPriorityTupleArity {
  implicit def tupleArity1[A]: TupleArity[A] = ???
}

object TupleOps {
  trait AppendOne[P, S] {
    type Out
    def apply(prefix: P, last: S): Out
  }
  object AppendOne extends TupleAppendOneInstances

  trait FoldLeft[In, T, Op] {
    type Out
    def apply(zero: In, tuple: T): Out
  }
  object FoldLeft extends TupleFoldInstances

  trait Join[P, S] {
    type Out
    def apply(prefix: P, suffix: S): Out
  }
  type JoinAux[P, S, O] = Join[P, S] { type Out = O }
  object Join extends LowLevelJoinImplicits {
    implicit def join0P[T]: JoinAux[Unit, T, T] = ???
    object Fold  {
      implicit def step[T, A](implicit append: AppendOne[T, A]): Case[T, A, Fold.type] { type Out = append.Out } = ???
    }
  }
  sealed abstract class LowLevelJoinImplicits {
    implicit def join[P, S](implicit fold: FoldLeft[P, S, Join.Fold.type]): JoinAux[P, S, fold.Out] = ???
  }
}

sealed trait Case[A, B, Op] { type Out }

abstract class TupleFoldInstances {
  type Aux[In, T, Op, Out0] = FoldLeft[In, T, Op] { type Out = Out0 }

  implicit def t1[In, A, Op](implicit f: Case[In, A, Op]): Aux[In, Tuple1[A], Op, f.Out] = ???
  implicit def t2[In, T1, X, T2, Op](implicit fold: Aux[In, Tuple1[T1], Op, X], f: Case[X, T2, Op]): Aux[In, Tuple2[T1, T2], Op, f.Out] = ???
}

abstract class TupleAppendOneInstances {
  type Aux[P, S, Out0] = AppendOne[P, S] { type Out = Out0 }
  implicit def append1[T1, L]: Aux[Tuple1[T1], L, Tuple2[T1, L]] = ???
  implicit def append2[T1, T2, L]: Aux[Tuple2[T1,T2], L, Tuple3[T1, T2, L]] = ???
  
}

Output

Compilation times based on -Yprofile-trace in Scala 3:
T0 - no intersection type or tuple type, doing classloading: 130ms
T1 / T1Bis - using intersection types - 257ms / 148 ms
T2 / T2Bis - using tuple types - 34 ms / 18 ms

Compilation times based on -Yprofile-trace in Scala 2.13:
T0 - no intersection type or tuple type, doing classloading: 134ms
T1 / T1Bis - using intersection types - 48ms / 40 ms
T2 / T2Bis - using tuple types - 45 ms / 39 ms

Scala 3.5-nightly -Yprofile-trace (modified to show Apply trees)

image
The blank spots after apply x is probably a time spent in type comparer. Async-profiler flamegraph available below

Scala 2.13 -Yprofile-trace

image

Archive below contains original outputs of -Yprofile-trace and flamegraph generated by async-profiler
profiler-outputs.zip

Type presented in presenation compiler

image

Expectation

Intersection types should affect compilation times with no more then 20% overhead.
@WojciechMazur
Copy link
Contributor Author

During the meeting it was mentioned that #19931 might have fixed this issue, however it seems to have no effect on this particular problem - it has no effect when it comes to compilation times

@jchyb jchyb mentioned this issue Apr 16, 2024
Closed
@EugeneFlesselle EugeneFlesselle mentioned this issue Apr 17, 2024
Closed
@odersky
Copy link
Contributor

odersky commented Apr 17, 2024

Intersection types should affect compilation times with no more then 20% overhead.

Intersection types can give a worst case exponential blowup of compilation times. So this is a nice goal, but not an achievable one 😉

@WojciechMazur WojciechMazur mentioned this issue Apr 18, 2024
Closed
@jchyb
Copy link
Contributor

jchyb commented May 12, 2024

I think I reached the end of my abilities here, so I will share my findings so hopefully the next person has an easier time.

  1. The issue is caused by the implicit resolution adding unfulfilled type variables with type bound constraints (>: Repro.ObjectId & Endpoints.this.Foo <: Repro.ObjectId & Endpoints.this.Foo) to typer state in T1 (in T2 they are gc’d when committing that typerState, as the type bounds are not created for the tuple), which later causes typer to take a longer code path like in the variances method, where overall T1 takes around 10x as much time as T2.
  2. I tried to make a quick fix where I remove the bound with equal lo and hi when committing the typer state obtained in the implicit search, but that broke a test where those were added explicitly in the code. It likely breaks other stuff too.
  3. The problematic typer state is generated here in the adapt method when searching for implicits, and the constraint there can look like this (this is the first constraint added when resolving tupleArity[A] for implicit in T1):
uninstantiated variables: J, IJ, J, IJ, J, IJ, A
 constrained types:
  [J, IJ]
    (i: EndpointInput[J])
      (implicit concat:
        ParamConcat.Aux[Repro.ObjectId & Endpoints.this.Foo, J, IJ]):
        Endpoints.this.baseEndpointWithIntersection.EndpointType[
          Repro.AuthInput, IJ, Repro.ApiError, Unit, Any]
  ,
  [J, IJ]
    (i: EndpointInput[J])
      (implicit concat:
        ParamConcat.Aux[Repro.ObjectId & Endpoints.this.Foo, J, IJ]):
        Endpoints.this.baseEndpointWithIntersection.EndpointType[
          Repro.AuthInput, IJ, Repro.ApiError, Unit, Any]
  ,
  [J, IJ]
    (i: EndpointInput[J])
      (implicit concat:
        ParamConcat.Aux[Repro.ObjectId & Endpoints.this.Foo, J, IJ]):
        Endpoints.this.baseEndpointWithIntersection.EndpointType[
          Repro.AuthInput, Repro.ObjectId & Endpoints.this.Foo, Repro.ApiError,
          Unit, Any]#EndpointType[Repro.AuthInput, IJ, Repro.ApiError, Unit, Any
          ]
  ,
  [J, IJ]
    (i: EndpointInput[J])
      (implicit concat:
        ParamConcat.Aux[Repro.ObjectId & Endpoints.this.Foo, J, IJ]):
        Endpoints.this.baseEndpointWithIntersection.EndpointType[
          Repro.AuthInput, Repro.ObjectId & Endpoints.this.Foo, Repro.ApiError,
          Unit, Any]#EndpointType[Repro.AuthInput, IJ, Repro.ApiError, Unit, Any
          ]
  ,
[T](implicit ta: TupleArity[T]): ParamConcat.Aux[T, Unit, T], [A]: TupleArity[A]
 bounds:
     J
     IJ
     J := Unit
     IJ := Repro.ObjectId & Endpoints.this.Foo
     J
     IJ
     J
     IJ
     T := Repro.ObjectId & Endpoints.this.Foo
     A
     >: Repro.ObjectId & Endpoints.this.Foo <: Repro.ObjectId &
      Endpoints.this.Foo
The problematic part is in the list line, if it was `A := Repro.ObjectId & Endpoints.this.Foo` we wouldn’t have the problem. I do not know the exact place where it’s added (this is where I got stuck), but it's in the `adapt` method.

Things I did to make my life easier (maybe they will be useful):

  1. I precompiled scalac -d . Api.scala TypeLevel.scala, so that I could get less printouts from the compiler when compiling scalac -cp /Users/jchyb/Library/Caches/Coursier/v1/https/repo1.maven.org/maven2/org/scala-lang/scala-library/2.13.12/scala-library-2.13.12.jar:/Users/jchyb/workspace/scala3/library/../out/bootstrap/scala3-library-bootstrapped/scala-3.4.2-RC1-bin-SNAPSHOT-nonbootstrapped/scala3-library_3-3.4.2-RC1-bin-SNAPSHOT.jar:. zrepr/Repro.scala

@EugeneFlesselle EugeneFlesselle mentioned this issue May 13, 2024
Merged
EugeneFlesselle added a commit to dotty-staging/dotty that referenced this issue May 15, 2024
@EugeneFlesselle
Do tryReplace using narrowedBounds instead of legalBound
14a6cac 
In scala#20120, we reach constraints with equal bounds that are intersection types,
they are formed from multiple successive calls to `addOneBound`.

We miss the `replace` optimization in this case because
the bounds only become equal progressively, and
we are only checking for equality with the constraint being added.

The second tryReplace after updateEntry and isSub
does not address this specific issue but scala#19955.
EugeneFlesselle added a commit that referenced this issue May 16, 2024
@EugeneFlesselle
Do constraint.replace when addOneBound produces equal bounds
c608177 
as an optimization

In #20120, we reach constraints with equal bounds that are intersection types,
they are formed from multiple successive calls to `addOneBound`.
We miss the `replace` optimization in this case because
the bounds only become equal progressively, and
we are only checking for equality with the constraint being added.

Additionally, we recheck for equal bounds after `constraint.updateEntry`
as checking `isSub` can have narrowed the bounds further.
#19955 is an example where this second optimization applies.

Fix #20120
Close #20208 the original implementation
@WojciechMazur
Copy link
Contributor Author

Thanks to changes in #20399 the compilation times has dropped significantly. In case of original project the compilation times presents as following:

  • Scala 2.13.12: 2min 14s in which typer took 1m 28s
  • Scala 3.5.0-RC1: 7m 26s, in which typer took 6m 06s
  • Scala 3.5.0-RC1-bin-20240516-c608177-NIGHTLY: 2min 44s in which typer took 1min 19s and inlining took 43s

Under -Yprofile-trace I can still find 3 methods that still take long time to compile 2-5s, so there still might be some room for future improvements. I'll try to create a minimisation for these if possible

@rlecomte
Copy link

@WojciechMazur I tried to compile the following code with Scala 3.5.0-RC1-bin-20240516-c608177-NIGHTLY and I got a significant raise of compilation time.

  • Scala 2.13.14: ~1s
  • Scala 3.4.1: ~40s
  • 3.5.0-RC1-bin-20240516-c608177-NIGHTLY: 420s
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 ()
}

@WojciechMazur WojciechMazur mentioned this issue Jun 3, 2024
Closed
@Kordyjan Kordyjan added this to the 3.5.1 milestone Jul 3, 2024
WojciechMazur pushed a commit that referenced this issue Jul 8, 2024
@EugeneFlesselle @WojciechMazur
Do constraint.replace when addOneBound produces equal bounds
e1aeea5 
as an optimization

In #20120, we reach constraints with equal bounds that are intersection types,
they are formed from multiple successive calls to `addOneBound`.
We miss the `replace` optimization in this case because
the bounds only become equal progressively, and
we are only checking for equality with the constraint being added.

Additionally, we recheck for equal bounds after `constraint.updateEntry`
as checking `isSub` can have narrowed the bounds further.
#19955 is an example where this second optimization applies.

Fix #20120
Close #20208 the original implementation
[Cherry-picked c608177]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@odersky odersky

@EugeneFlesselle EugeneFlesselle

Labels
area:typer itype:bug itype:performance
Projects
None yet
Milestone
3.5.1
6 participants
@odersky @rlecomte @Kordyjan @WojciechMazur @EugeneFlesselle @jchyb