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

[Maurizio Cimadamore]

Hi,
as Vicente mentioned, this is sadly a known issue. Each call to 
Map.entry adds two inference variables. These variables are all thrown 
into the same cauldron, as the inference engine wants to reason globally 
about them.

We had overcome many similar performance potholes in the past, 
essentially by detecting and pruning away inference variables where e.g. 
X = Y (so we only keep one of them). In this case, unfortunately, 
there's no such equality to detect, and we can't really prune the set of 
inference variables. We have some ideas on how to maybe do it, but they 
are all fairly complex, and the risk of affecting correctness is rather 
high.

In the meantime, there's maybe a workaround for you to try: let's remove 
the generic-ness of Map.Entry from the picture, by declaring a new method:

Map.Entry<String, String> newStringEntry(String key, String val) { 
return Map.entry(key, val); }

Now, call the new method when you build the big list. I believe this 
should bring compilation back to normal times.

Hope this helps.

Maurizio



On 16/01/2025 12:33, Dawid Weiss wrote:
>
> Hello,
>
> I came across an interesting quirk of javac today. I was looking at 
> unusually long compilation times of a bunch of test files. One of 
> those files looks like this:
>
> public class JavacBoom {
>   public void ahem() {
>   List<Map.Entry<String, String>> value =
>         Arrays.asList(
>             Map.entry("key", "value"),
>             Map.entry("key", "value"),
>             Map.entry("key", "value"),
>             ...
>             Map.entry("key", "value"),
>         );
>   }
> }
>
> Nothing special, except value is populated with many, many key-value 
> pairs. I think type inference must have some kind of exponential 
> algorithm in there because here is what it looks like when you 
> increase the number of keys:
>
> count of Map.entry(k,v), real time [seconds] javac JavacBoom
> 1, 0.4
> 10, 0.43
> 100, 1.08
> 200, 3.4
> 300, 10.8
> 400, 22.9
> 500, 50
>
> So if you have 500 entries like the above, it'll take 50 seconds to 
> compile a single ~10k bytes java source input. Here is a github gist 
> with the source code containing 500 entries if you'd like to try locally:
> https://gist.github.com/dweiss/93caf579a89f3dbbfac5c292048e42ad
>
> The compiler points here (roughly, single stack trace).
>
> "main" #1 [1070081] prio=5 os_prio=0 cpu=1687.19ms elapsed=1.76s 
> tid=0x00007de1b802a3f0 nid=1070081 runnable  [0x00007de1bcdfb000]
>    java.lang.Thread.State: RUNNABLE
> at 
> com.sun.tools.javac.code.Type.equalsIgnoreMetadata(jdk.compiler at 23.0.1/Type.java:563)
> at 
> com.sun.tools.javac.code.Types$Subst.visitTypeVar(jdk.compiler at 23.0.1/Types.java:3355)
> at 
> com.sun.tools.javac.code.Types$Subst.visitTypeVar(jdk.compiler at 23.0.1/Types.java:3331)
> at 
> com.sun.tools.javac.code.Type$TypeVar.accept(jdk.compiler at 23.0.1/Type.java:1709)
> at 
> com.sun.tools.javac.code.Types$DefaultTypeVisitor.visit(jdk.compiler at 23.0.1/Types.java:4920)
> at com.sun.tools.javac.code.Type.map(jdk.compiler at 23.0.1/Type.java:319)
> at 
> com.sun.tools.javac.code.Types.subst(jdk.compiler at 23.0.1/Types.java:3328)
> at 
> com.sun.tools.javac.comp.InferenceContext.asUndetVar(jdk.compiler at 23.0.1/InferenceContext.java:206)
> at 
> com.sun.tools.javac.comp.Infer$GraphSolver$InferenceGraph.initNodes(jdk.compiler at 23.0.1/Infer.java:1907)
> at 
> com.sun.tools.javac.comp.Infer$GraphSolver$InferenceGraph.<init>(jdk.compiler at 23.0.1/Infer.java:1852)
> at 
> com.sun.tools.javac.comp.Infer$GraphSolver.solve(jdk.compiler at 23.0.1/Infer.java:1654)
> at 
> com.sun.tools.javac.comp.InferenceContext.solve(jdk.compiler at 23.0.1/InferenceContext.java:487)
> at 
> com.sun.tools.javac.comp.InferenceContext.solve(jdk.compiler at 23.0.1/InferenceContext.java:494)
> at 
> com.sun.tools.javac.comp.Infer.instantiateMethod(jdk.compiler at 23.0.1/Infer.java:211)
> at 
> com.sun.tools.javac.comp.Resolve.rawInstantiate(jdk.compiler at 23.0.1/Resolve.java:619)
> at 
> com.sun.tools.javac.comp.Resolve.selectBest(jdk.compiler at 23.0.1/Resolve.java:1588)
> at 
> com.sun.tools.javac.comp.Resolve.findMethodInScope(jdk.compiler at 23.0.1/Resolve.java:1794)
> at 
> com.sun.tools.javac.comp.Resolve.findMethod(jdk.compiler at 23.0.1/Resolve.java:1865)
> at 
> com.sun.tools.javac.comp.Resolve.findMethod(jdk.compiler at 23.0.1/Resolve.java:1838)
> at 
> com.sun.tools.javac.comp.Resolve$12.doLookup(jdk.compiler at 23.0.1/Resolve.java:2770)
> at 
> com.sun.tools.javac.comp.Resolve$BasicLookupHelper.lookup(jdk.compiler at 23.0.1/Resolve.java:3485)
> at 
> com.sun.tools.javac.comp.Resolve.lookupMethod(jdk.compiler at 23.0.1/Resolve.java:3749)
> at 
> com.sun.tools.javac.comp.Resolve.resolveQualifiedMethod(jdk.compiler at 23.0.1/Resolve.java:2767)
> at 
> com.sun.tools.javac.comp.Resolve.resolveQualifiedMethod(jdk.compiler at 23.0.1/Resolve.java:2761)
> at 
> com.sun.tools.javac.comp.Attr.selectSym(jdk.compiler at 23.0.1/Attr.java:4546)
> at 
> com.sun.tools.javac.comp.Attr.visitSelect(jdk.compiler at 23.0.1/Attr.java:4433)
> at 
> com.sun.tools.javac.tree.JCTree$JCFieldAccess.accept(jdk.compiler at 23.0.1/JCTree.java:2570)
> at 
> com.sun.tools.javac.comp.Attr.attribTree(jdk.compiler at 23.0.1/Attr.java:674)
> at 
> com.sun.tools.javac.comp.Attr.visitApply(jdk.compiler at 23.0.1/Attr.java:2641)
> at 
> com.sun.tools.javac.tree.JCTree$JCMethodInvocation.accept(jdk.compiler at 23.0.1/JCTree.java:1857)
> at 
> com.sun.tools.javac.comp.Attr.attribTree(jdk.compiler at 23.0.1/Attr.java:674)
> at 
> com.sun.tools.javac.comp.Attr.attribExpr(jdk.compiler at 23.0.1/Attr.java:720)
> at 
> com.sun.tools.javac.comp.Attr.visitVarDef(jdk.compiler at 23.0.1/Attr.java:1318)
>
> I don't have the karma to submit jira issues, but I think this can be 
> considered a showstopper?
>
> Dawid