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

[Vicente Romero]

HI Dawid,

this looks like another instance of [1], is this something affecting 
test cases or production code?

Thanks,
Vicente

[1] https://bugs.openjdk.org/browse/JDK-8302292


On 1/16/25 07: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