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

Fri Jan 17 08:00:23 UTC 2025

Hello!

There's a simpler workaround. No need to declare a method, you can just add
explicit type arguments to Arrays.asList call:

    List<Map.Entry<String, String>> value =
            Arrays.<Map.Entry<String, String>>asList(
                    Map.entry("key", "value"),
                    Map.entry("key", "value"),
                    ...
                    Map.entry("key", "value"),
                    Map.entry("key", "value")
                    );

Now, Arrays.asList becomes a standalone call, and instead of having a
single huge inference session, one has many small sessions, and the
compilation is fast again.

This problem is old and well-known. IntelliJ IDEA even has an inspection
for it since ages. It's called "Javac quirks" [1], and we provide a
quick-fix that adds explicit type arguments when the number of inference
variables exceeds some threshold. Probably thanks to this, the OpenJDK
project receives much fewer complaints about this problem than it could be
:-)

With best regards,
Tagir Valeev

[1] https://www.jetbrains.com/help/inspectopedia/JavacQuirks.html

On Thu, Jan 16, 2025 at 11:29 PM Maurizio Cimadamore <
maurizio.cimadamore at oracle.com> wrote:

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