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

[Dawid Weiss]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.openjdk.org/pipermail/compiler-dev/attachments/20250116/12a4d158/attachment.htm>