Severe compile performance regression for `Seq.++` chain

[WojciechMazur]

Based on the OpenCB in valerylobachev/data-dictionary-builder - build logs which now timeouts after 2h of compilation.
Discovery of the issue was delayed due to other errors previously reported in this project: #24207 and #24456

Every additional Seq[Message].++ in the chain dramatically increases the time required to compile snippet.

Under scala compile -S 3.7.4 test.scala --server=false all snippets compile in ~4s

Under scala compile -S 3.nightly test.scala --server=false 8th ++ invocation in the chain the performance starts to be easily visible, and starts to double/triple with each addition ++ in the chain

Compiler version

3.8.0-RC2

Last good release: 3.8.0-RC1-bin-20250818-aaa39c5-NIGHTLY
First bad release: 3.8.0-RC1-bin-20250819-1f13619-NIGHTLY
Bisect points to 1f13619 / #23769

Minimized code

trait Item
private def items : Seq[Item] = ???

def Test(): Seq[Item] =
  items ++
    items ++
    items ++
    items ++
    items ++
    items ++
    items ++ // 5s
    items ++ // 5s
    items ++ // 7s
    items ++ // 12s
    // items ++ // 25s
    // items ++ // 64s
    // items ++ // 188s
    items

Output

Expectation

Compille time should be similar as on the Scala 3.7.4

[natsukagami]

Minimal example without touching stdlib (I forgot to turn on CC before :P)

//> using scala 3.8.0-RC1

import language.experimental.captureChecking

trait Item

trait ItOps[+T, +CC[_], +C]:
  def ++[B >: T](other: It[B]^): CC[B]^{this, other}

trait It[+T] extends ItOps[T, It, It[T]]

trait Sq[+T] extends It[T] with ItOps[T, Seq, Seq[T]]

def items: Sq[Item] = ???

@main def main() =
  items ++
    items ++
    items ++
    items ++
    items ++
    items ++
    items ++ // 5s
    items ++ // 5s
    items ++ // 7s
    items ++ // 12s
    // items ++ // 25s
    // items ++ // 64s
    // items ++ // 188s
    items

[noti0na1]

I can confirm this is caused by retains annotation. The annotation and its type is mapped again and again at many places, which leads the slowing down.

[noti0na1]

According the profile I send on slack, the mapping over annotation/annotated types does not look good to me; but I haven't find the core issue.

So far I know, if I skip annotation in IntegrateMap or Substituters.subst or don't map type in TreeTypeMap.transform (not a correct fix), then the compile time can get normal.

[noti0na1]

I think the performance regression is caused by several factors:

• Type mapping on annotations is expensive: we’re not only traversing and transforming the annotation tree itself, but also mapping over the types associated with those trees, and the mapping is repeated multiple times.
• Elements of a retains annotation can widen to another retains annotated type: for example, in a type like CC[B]^{this, other}, the element this can have a skolem type that could be widen to another similarly annotated type. This means that as the ++ chain grows longer, each mapping step becomes more expensive, leading to increasingly worse performance.

Some places I looked at:

• TreeTypeMap.transform -> TreeTypeMap.mapType
• Annotation.mapOver -> TreeAccumulator.mapOver, tm.mapOver
• Substituters.subst -> SubstBindingMap.mapOver

[mbovel]

My understanding was that capture checking annotation should not matter outside of capture checking phases. Therefore, I tried to just skip them when mapping during other phases:

$ git --no-pager diff
...
@@ -7,6 +7,7 @@ import ast.tpd, tpd.*
 import printing.Texts.Text
+import dotty.tools.dotc.cc.{isRetainsLike, isCaptureCheckingOrSetup}
 
 import scala.annotation.internal.sharable
 
@@ -55,7 +56,7 @@ object Annotations {
      */
     def mapWith(tm: TypeMap)(using Context) =
       val args = tpd.allArguments(tree)
-      if args.isEmpty then this
+      if args.isEmpty || skipMap then this
       else
         // Checks if `tm` would result in any change by applying it to types
         // inside the annotations' arguments and checking if the resulting types
@@ -71,6 +72,10 @@ object Annotations {
         else if diff.exists then derivedAnnotation(tm.mapOver(tree))
         else this
 
+    /** Should we skip mapping this annotation? */
+    private def skipMap(using Context) =
+      symbol.isRetainsLike && !isCaptureCheckingOrSetup
+

However, that is too coarse-grained and makes >50 tests fail.

[noti0na1]

We can't simply skip annotations like this in general, since it can contains symbols we want to subst in tress and types.

Even if we can skip just capture annotations, I feel we would trigger the similar performance regression with regular annotations.

[mbovel]

We can't simply skip annotations like this in general, since it can contains symbols we want to subst in tress and types.

But weren't these supposed to be recomputed in the capture checking phase anyway? Apparently not, it seems that phase relies on annotations being correctly mapped during typer already.

Even if we can skip just capture annotations, I feel we would trigger the similar performance regression with regular annotations.

Yeah, you're right. Mapping annotations is known to be slow (mapping trees is orders of magnitude slower than mapping types). But maybe we can at least avoid the exponential blowup.

Still, I would find it nice to guarantee that CC annotations do not impact performance at all when capture checking is not enabled. For example by systematically stripping them when capture checking is disabled:

$ git --no-pager diff
...
 import config.Config
+import config.Feature
 import config.Feature.sourceVersion
 import config.SourceVersion
 import annotation.{tailrec, constructorOnly}
@@ -6483,10 +6484,13 @@ object Types extends TypeUtils {
           mapCapturingType(tp, parent, refs, variance)
 
         case tp @ AnnotatedType(underlying, annot) =>
-          val underlying1 = this(underlying)
-          val annot1 = annot.mapWith(this)
-          if annot1 eq EmptyAnnotation then underlying1
-          else derivedAnnotatedType(tp, underlying1, annot1)
+          if annot.symbol.isRetainsLike && !Feature.ccEnabledSomewhere then
+            this(underlying) // strip retains like annotations unless capture checking is enabled
+          else
+            val underlying1 = this(underlying)
+            val annot1 = annot.mapWith(this)
+            if annot1 eq EmptyAnnotation then underlying1
+            else derivedAnnotatedType(tp, underlying1, annot1)
 
         case _: ThisType

At first sight, only one test fails with the above (tests/run/IArrayOps.scala).