Exponential compilation time for List.of(Map.entry) expressions
Vicente Romero
vicente.romero at oracle.com
Thu Jan 16 14:56:54 UTC 2025
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
More information about the compiler-dev
mailing list