Compilation is very slow on some files due to implicit search repeatedly diverging

[kubukoz]

Compiler version

3.1.0 / 3.1.1

Minimized code

// using "org.typelevel" %% "cats-effect-kernel" % "3.3.4"
import cats.effect.kernel.Resource

import cats.syntax.apply.catsSyntaxApply
import cats.Monad

object middlewares {

  def withToken[F[_]: Monad](getToken: F[Unit]): Resource[F, Unit] =
    Resource.eval(getToken) *> Resource.eval(getToken)

}

Expectation

Sub-second recompilation when there are no changes in the file except whitespace.

Reality

It takes 7-8 seconds to compile this file on a fresh JVM. Recompilation also takes nearly as much, and the presentation compiler is affected as well (which is visible when you e.g. attempt to get completions in Metals).

Notes

I think the *> call is the culprit here. Removing it fixes the issue.

Scala 2.13.8 compiles this in 2 seconds with sub-second incremental recompilations.

[smarter]

It looks like the compiler is spending a ton of time doing a bunch of implicit searches which all diverge:

...
diverged: Candidate(TermRef(TermRef(TermRef(ThisType(TypeRef(NoPrefix,module class effect)),object kernel),object Sync),method syncForIorT),1,0)
diverged: Candidate(TermRef(TermRef(TermRef(ThisType(TypeRef(NoPrefix,module class effect)),object kernel),object Sync),method syncForWriterT),1,0)
diverged: Candidate(TermRef(TermRef(TermRef(ThisType(TypeRef(NoPrefix,module class effect)),object kernel),object Sync),method syncForReaderWriterStateT),1,0)
diverged: Candidate(TermRef(TermRef(TermRef(ThisType(TypeRef(NoPrefix,module class effect)),object kernel),object Sync),method syncForIorT),1,0)
diverged: Candidate(TermRef(TermRef(TermRef(ThisType(TypeRef(NoPrefix,module class effect)),object kernel),object Sync),method syncForWriterT),1,0)
diverged: Candidate(TermRef(TermRef(TermRef(ThisType(TypeRef(NoPrefix,module class effect)),object kernel),object Sync),method syncForReaderWriterStateT),1,0)
diverged: Candidate(TermRef(TermRef(TermRef(ThisType(TypeRef(NoPrefix,module class effect)),object kernel),object Sync),method syncForWriterT),1,0)
diverged: Candidate(TermRef(TermRef(TermRef(ThisType(TypeRef(NoPrefix,module class effect)),object kernel),object Sync),method syncForReaderWriterStateT),1,0)
diverged: Candidate(TermRef(TermRef(TermRef(ThisType(TypeRef(NoPrefix,module class effect)),object kernel),object Sync),method syncForEitherT),1,0)
diverged: Candidate(TermRef(TermRef(TermRef(ThisType(TypeRef(NoPrefix,module class effect)),object kernel),object Sync),method syncForOptionT),1,0)
diverged: Candidate(TermRef(TermRef(TermRef(ThisType(TypeRef(NoPrefix,module class effect)),object kernel),object Sync),method syncForOptionT),1,0)
diverged: Candidate(TermRef(TermRef(TermRef(ThisType(TypeRef(NoPrefix,module class effect)),object kernel),object Sync),method syncForKleisli),1,0)
diverged: Candidate(TermRef(TermRef(TermRef(ThisType(TypeRef(NoPrefix,module class effect)),object kernel),object Sync),method syncForEitherT),1,0)
diverged: Candidate(TermRef(TermRef(TermRef(ThisType(TypeRef(NoPrefix,module class effect)),object kernel),object Sync),method syncForStateT),1,0)
diverged: Candidate(TermRef(TermRef(TermRef(ThisType(TypeRef(NoPrefix,module class effect)),object kernel),object Sync),method syncForOptionT),1,0)
diverged: Candidate(TermRef(TermRef(TermRef(ThisType(TypeRef(NoPrefix,module class effect)),object kernel),object Sync),method syncForKleisli),1,0)
diverged: Candidate(TermRef(TermRef(TermRef(ThisType(TypeRef(NoPrefix,module class effect)),object kernel),object Sync),method syncForEitherT),1,0)
diverged: Candidate(TermRef(TermRef(TermRef(ThisType(TypeRef(NoPrefix,module class effect)),object kernel),object Sync),method syncForStateT),1,0)
diverged: Candidate(TermRef(TermRef(TermRef(ThisType(TypeRef(NoPrefix,module class effect)),object kernel),object Sync),method syncForIorT),1,0)
diverged: Candidate(TermRef(TermRef(TermRef(ThisType(TypeRef(NoPrefix,module class effect)),object kernel),object Sync),method syncForWriterT),1,0)
diverged: Candidate(TermRef(TermRef(TermRef(ThisType(TypeRef(NoPrefix,module class effect)),object kernel),object Sync),method syncForReaderWriterStateT),1,0)
diverged: Candidate(TermRef(TermRef(TermRef(ThisType(TypeRef(NoPrefix,module class effect)),object kernel),object Sync),method syncForWriterT),1,0)
diverged: Candidate(TermRef(TermRef(TermRef(ThisType(TypeRef(NoPrefix,module class effect)),object kernel),object Sync),method syncForReaderWriterStateT),1,0)
... continues for thousands lines

I have no idea what these implicits do but they look like:

implicit def syncForOptionT[F[_]](implicit F0: Sync[F]): Sync[OptionT[F, *]] =

So I guess whenever the compiler tries one, to see if it can be applied, it ends up doing a recursive implicit search where all these implicits are again possible candidates, and so we get an exponential blow-up. I think we'll need someone to produce a minimization to figure out if this is a bug in scala 3 or an intentional difference in implicit resolution. See #13838 for a similar case, and in particular in #13838 (comment) @joroKr21 suggested there might be situations where we do implicit search that cannot possibly succeed, I don't know if this is the same issue.

[kubukoz]

Noteworthy: Resource.eval[F, Unit](getToken) is all right. The method doesn't take any implicits... so I assume type inference of eval's type parameters doesn't happen fully before *>'s type parameters are inferred?

[smarter]

@dwijnand removed the itype:bug label

IMO this is a severe enough regression that this qualifies as a bug. Luckily I think I have a fix: #14353

[kubukoz]

Your fix works :) tried with a publishLocal and this compiles much faster now.

[dwijnand]

IMO this is a severe enough regression that this qualifies as a bug.

I consider performance bugs as bugs. But I guess you could argue there are performance enhancements that aren't bugs? Also, I saw that the templates marks crashes as bugs, which seemed redundant to me. Surely all crashes are bugs?!

[smarter]

Yeah our categorization system isn't great.