Performance regression in 16463.scala

[kubukoz]

Compiler version

3.2.1

Minimized code

//> using scala "3.2.1"

import scala.compiletime.ops.int._

object TupleOps {
  import Tuple._

  type Reduce[T <: NonEmptyTuple, F[_, _]] =
    Fold[Tuple.Tail[T], Tuple.Head[T], F]

  type Maximum[T <: NonEmptyTuple] = Reduce[
    T,
    [A, B] =>> (A, B) match {
      case (Int, Int) => A Max B
    }
  ]

  type IndexOfRec[T <: Tuple, Elem, I <: Int] = Tuple.Elem[T, I] match {
    case Elem => I
    case _    => IndexOfRec[T, Elem, I + 1]
  }

  type IndexOf[T <: Tuple, Elem] = IndexOfRec[T, Elem, 0]

  type DropLargest[T <: NonEmptyTuple] =
    T IndexOf Maximum[T] match {
      case Int =>
        (
          (T Take (T IndexOf Maximum[T])) Concat
          (T Drop ((T IndexOf Maximum[T]) + 1))
        ) *: EmptyTuple
    }

  type BubbleSort[T <: Tuple] = T match {
    case EmptyTuple => EmptyTuple
    case NonEmptyTuple =>
      BubbleSort[DropLargest[T]] Concat (Maximum[T] *: EmptyTuple)
  }
}

object demo extends App {
  println(compiletime.constValue[TupleOps.BubbleSort[(1, 2)]])
}

Output

Compiles forever. I'm able to get it to terminate with a recursion overflow if I specify really low stack, e.g. -Xss256K:

scala-cli compile . --bloop-java-opt -Xss256K
Starting compilation server
Compiling project (Scala 3.2.1, JVM)
dotty.tools.dotc.core.RecursionOverflow:
Error compiling project (Scala 3.2.1, JVM)
dotty.tools.dotc.core.RecursionOverflow:
Error: Unexpected error when compiling project_f0e8bc45bf: ''
Compilation failed

Expectation

Successfully compiles or fails compilation in a couple seconds at most

[kubukoz]

OK, I found the infinite recursion:

BubbleSort[DropLargest[T]]

This recurses forever because DropLargest always returns a 1-tuple. If I simplify that to a direct recursion on BubbleSort[T], the output is clearer about that:

[error] ./main.scala:16:34: Recursion limit exceeded.
[error] Maybe there is an illegal cyclic reference?
[error] If that's not the case, you could also try to increase the stacksize using the -Xss JVM option.
[error] For the unprocessed stack trace, compile with -Yno-decode-stacktraces.
[error] A recurring operation is (inner to outer):
[error]
[error]   normalizing ((1 : Int), (2 : Int)) match ...
[error]   normalizing ((1 : Int), (2 : Int)) match ...
[error]   normalizing ((1 : Int), (2 : Int)) match ...
[error]   normalizing ((1 : Int), (2 : Int)) match ...
[error]   normalizing ((1 : Int), (2 : Int)) match ...
[error]   normalizing ((1 : Int), (2 : Int)) match ...
[error]   normalizing ((1 : Int), (2 : Int)) match ...
[error]   normalizing ((1 : Int), (2 : Int)) match ...
[error]   normalizing ((1 : Int), (2 : Int)) match ...
[error]   normalizing ((1 : Int), (2 : Int)) match ...
...

so I guess it's more of a reporting issue than correctness.

[mbovel]

With the latest Scala version, a recursion limit error is displayed for your test case:

-- Error: tests/neg/16463.scala:42:33 ----------------------------------------------------------------------------------
42 |  println(compiletime.constValue[TupleOps.BubbleSort[(1, 2)]]) // error: Recursion limit exceeded
   |                                 ^
   |                 Recursion limit exceeded.
   |                 Maybe there is an illegal cyclic reference?
   |                 If that's not the case, you could also try to increase the stacksize using the -Xss JVM option.
   |                 For the unprocessed stack trace, compile with -Yno-decode-stacktraces.
   |                 A recurring operation is (inner to outer):
   |
   |                   reduce type  EmptyTuple *: EmptyTuple match ...
   |                   reduce type  EmptyTuple *: EmptyTuple match ...
   |                   reduce type  EmptyTuple *: EmptyTuple match ...
   |                   reduce type  EmptyTuple *: EmptyTuple match ...
   |                   reduce type  EmptyTuple *: EmptyTuple match ...
   |                   reduce type  EmptyTuple *: EmptyTuple match ...
   |                   reduce type  EmptyTuple *: EmptyTuple match ...
   |                   reduce type  EmptyTuple *: EmptyTuple match ...
   |                   reduce type  EmptyTuple *: EmptyTuple match ...
   |                   reduce type  EmptyTuple *: EmptyTuple match ...
   |                   ...
   |
   |                   reduce type  EmptyTuple *: EmptyTuple match ...
   |                   reduce type  EmptyTuple *: EmptyTuple match ...
   |                   reduce type  EmptyTuple *: EmptyTuple match ...
   |                   reduce type  EmptyTuple *: EmptyTuple match ...
   |                   reduce type  EmptyTuple *: EmptyTuple match ...
   |                   reduce type  EmptyTuple *: EmptyTuple match ...
   |                   reduce type  EmptyTuple *: EmptyTuple match ...
   |                   reduce type  EmptyTuple *: EmptyTuple match ...
   |                   reduce type  ((1 : Int) *: EmptyTuple.type) *: EmptyTuple match ...
   |                   reduce type  ((1 : Int), (2 : Int)) match ...

Is this what you expected @kubukoz?

[kubukoz]

@mbovel yeah, that's a bit better 😅

wondering how much stack I'd need to give it to actually see a result though. Can you set JVM flags for the compiler with scala-cli? (presumably it'd only work with --server=off)

[EugeneFlesselle]

The test now takes 201s before reporting an error, Vs 1s when #20269 was merged, so there's been a performance regression since then somewhere.

[mbovel]

Please dismiss my previous comments, I actually was able to reproduce on 3.6.0-RC1-bin-20241003-a672e05-NIGHTLY.

[mbovel]

Strange, I am again not able to reproduce the >200 s compilation time today. That is surprising, given that I was able to get this slow compilation time on Friday on the same setup. Not sure what could have changed in-between.

What I am able to observe today though is an apparent performance degradation between f2829c3fab and ab48a55a1a, for the snippet from this issue:

➜  ~ time scala compile -S 3.6.0-RC1-bin-20240703-75a15c2-NIGHTLY --server=false -Wconf:any:silent 16463.scala
scala compile -S 3.6.0-RC1-bin-20240703-75a15c2-NIGHTLY --server=false    4.41s user 0.39s system 212% cpu 2.258 total

➜  ~ time scala compile -S 3.6.0-RC1-bin-20240705-ab48a55-NIGHTLY --server=false -Wconf:any:silent 16463.scala
scala compile -S 3.6.0-RC1-bin-20240705-ab48a55-NIGHTLY --server=false    7.63s user 0.55s system 229% cpu 3.569 total

➜  ~/dotty git:(f2829c3fab) sbt publishLocal
➜  ~ time scala compile -S 3.6.0-RC1-bin-SNAPSHOT --server=false -Wconf:any:silent 16463.scala
scala compile -S 3.6.0-RC1-bin-SNAPSHOT --server=false -Wconf:any:silent   4.47s user 0.44s system 219% cpu 2.238 total

➜  ~/dotty git:(ab48a55a1a) sbt publishLocal
➜  ~ time scala compile -S 3.6.0-RC1-bin-SNAPSHOT --server=false -Wconf:any:silent 16463.scala
scala compile -S 3.6.0-RC1-bin-SNAPSHOT --server=false -Wconf:any:silent   7.46s user 0.54s system 220% cpu 3.621 total

[mbovel]

By the way, here is the correct version (*: EmptyTuple deleted in BubbleSort):

import scala.compiletime.ops.int.*

object TupleOps:
  import Tuple.*

  type Reduce[T <: NonEmptyTuple, F[_, _]] =
    Fold[Tuple.Tail[T], Tuple.Head[T], F]

  infix type Maximum[T <: NonEmptyTuple] = Reduce[
    T,
    [A, B] =>> (A, B) match
      case (Int, Int) => Max[A, B]
  ]

  type IndexOfRec[T <: Tuple, Elem, I <: Int] = Tuple.Elem[T, I] match
    case Elem => I
    case _    => IndexOfRec[T, Elem, I + 1]

  infix type IndexOf[T <: Tuple, Elem] = IndexOfRec[T, Elem, 0]

  type DropLargest[T <: NonEmptyTuple] =
    T IndexOf Maximum[T] match
      case Int =>
        Concat[Take[T, (T IndexOf Maximum[T])], Drop[T, (T IndexOf Maximum[T]) + 1]]

  type BubbleSort[T <: Tuple] = T match
    case EmptyTuple => EmptyTuple
    case NonEmptyTuple =>
      Concat[BubbleSort[DropLargest[T]], (Maximum[T] *: EmptyTuple)]

@main def main =
  println(compiletime.constValueTuple[(TupleOps.BubbleSort[(2, 3, 5, 4, 1)])])
  // (1,2,3,4,5)

I will add it as a benchmark.

[mbovel]

Not sure what could have changed in-between.

It seems I only get the > 200 s compilation time when compiling the incorrect version via Bloop.

➜  ~/scala-snippets-6 jps -q | xargs kill -9
➜  ~/scala-snippets-6 rm -rf .scala-build         
➜  ~/scala-snippets-6 time scala compile --server=false -S 3.6.0-RC1-bin-20241003-a672e05-NIGHTLY 16463.scala
scala compile --server=false -S 3.6.0-RC1-bin-20241003-a672e05-NIGHTLY   10.86s user 0.96s system 204% cpu 5.767 total
➜  ~/scala-snippets-6 time scala compile -S 3.6.0-RC1-bin-20241003-a672e05-NIGHTLY 16463.scala   
^Cscala compile -S 3.6.0-RC1-bin-20241003-a672e05-NIGHTLY 16463.scala  0.43s user 0.23s system 0% cpu 2:23.80 total
➜  ~/scala-snippets-6 time scala compile -S 3.6.0-RC1-bin-20241003-a672e05-NIGHTLY 16463.scala
Deduplicating compilation of scala-snippets-6_55f1e8bb20-10ab6c2095 from bsp client 'scala-cli 1.4.3' (since 3m 37.858s)
Compiling project (Scala 3.6.0-RC1-bin-20241003-a672e05-NIGHTLY, JVM (17))
Compilation cancelled (Scala 3.6.0-RC1-bin-20241003-a672e05-NIGHTLY, JVM (17))
Warning: Disconnecting from deduplication of ongoing compilation for 'scala-snippets-6_55f1e8bb20-10ab6c2095'
No progress update for 30 seconds caused bloop to cancel compilation and schedule a new compile.

Compiling project (Scala 3.6.0-RC1-bin-20241003-a672e05-NIGHTLY, JVM (17))