Slow inference with large Maps of literals

[adkian-sifive]

Compiler version

3.4.0, 3.4.1, 3.4.2

Minimized code

I put it in a gist here since the problematic Maps are quite large: https://gist.github.com/adkian-sifive/5c904054f400871f2fe712ab160be1b3

Output

The compiler hangs

Expectation

In this case the compiler should complain about not finding a main method, but it does not do that and just hangs.

[som-snytt]

3.4.2 takes just over two minutes to compile on my old box. (2.13.14 takes a few seconds. IIRC it checks for all the same primitive when lubbing.)

TIL 2.13 does not try to initialize a main-less object. 3.4 does indeed complain.

[adkian-sifive]

Thanks for checking! After retrying with a bit more patience it did indeed complain after around 5 mins on my old potato. Perhaps a performance enhancement opportunity but doesn't seem like a bug...

[jackkoenig]

This does seem like a pretty painful performance issue, is that something the Scala 3 developers track with Github issues?

[som-snytt]

For example #19907

That is already in 3.4.2.

On HEAD, the example is still over a minute (trying it locally, informally).

[jackkoenig]

Thanks for the additional context!

Do you think this is worth re-filing separately as a performance issue?

[som-snytt]

There are a couple of open PRs for performance of calculating intersection types, but I don't know if they will apply here.

It couldn't hurt to reopen this ticket and let normal triage take its course, so I'll do that.

Edit: the ticket was already triaged, so I updated the labels. I may be wrong about what causes the slow-down.

[noti0na1]

The recent performance improvement does not help this example, and I think #20523 slows down a bit further in this case.

The compiling time seems to be increasing linearly by the number of repeating elements.

According to my profile, the increasing part is at the matchArgs of Application when we check repeated arguments:

val typedArgs =
  harmonic(harmonizeArgs, elemFormal) {
    args.map { arg =>
      checkNoVarArg(arg)
      typedArg(arg, elemFormal)
    }
  }
typedArgs.foreach(addArg(_, elemFormal))

Both typeArg and addArg will trigger signifcant amount of type compirsion around constraints.

In this case, the elemFormal is a type variable A, so probably we added too many contains with constant types, like 1 <:< A, which slows down the compiling.

[noti0na1]

Actually, after re-running the test, I find the nightly version is 30% faster than the LTS version on my computer. But it is still much slower than Scala 2.

• Scala 2: 9s
• Scala 3.4.2: ~60s
• Scala 3.6.0-RC1-bin-20240717-45dcb51-NIGHTLY: ~40s

[noti0na1]

With #21223, the compiling time can be reduced to Scala 2 level.