Exponential compilation time for List.of(Map.entry) expressions

[Maurizio Cimadamore]

On 21/01/2025 12:38, Dawid Weiss wrote:
>> This is a performance problem for IntelliJ as well. Highlighting becomes slow on such code. Not sure whether it's slower or faster than javac, but it's definitely slow. So technically, it's 'javac + IntelliJ quirks' :-)
> I can add ecj to this: "javac" + "intellij" + "Eclipse ecj" quirks
> because I've tried out of curiosity and ecj also grinds to a halt on
> this pattern.
>
> Oh well, thanks for the interesting discussion. I've learnt something new.

I'm not surprised (but thanks for reporting). In the sense that this is 
not really a "bug" but more of the JLS being defined this way.

As I said, when you have nested method calls, are inference variables 
are accumulated in the outermost call, so that the target-type can 
influence even deeply nested inference variables.

Then we run a process known as "incorporation", where we look at the 
bounds of the inference variables and keep deriving new bounds. For 
instance:

* if an inference variable alpha has bounds alpha <: S and T <: alpha, 
we automatically generate the test T <: S, which might result in 
additional constraints
* if an inference variable beta has two upper bounds like beta <: C<S> 
and beta <: C<T>, we generate the test S == T, which might result in 
additional constraints

All this has to repeat every time a new constraint is added, and until 
no more constraints can be derived. Which is why the cost of the 
algorithm grows exponentially with the number of inference variables.

Consequently, the only hope a compiler has is to cut down on the number 
of required inference variables. We have already implemented, with 
success, logic to detect that e.g. multiple inference variable formed an 
equivalence set (e.g. alpha == beta == gamma) - in which case we can 
safely pick one of them (after, of course, we made sure to copy all the 
bounds from other variables in the set).

In this case the problem has more to do with many inference variables 
having the same constraints (meaning they will be resolved in exactly 
the same way). We are hopeful a some solution for this problem is also 
possible, but this one looks a little harder as we can't rely on 
inference variables being the "same" (because of == constraints). 
Instead we'd have to infer "same-ness" based on some other principle.

Cheers
Maurizio