Community
Participate
Working Groups
Created attachment 270851 [details] Eclipse project containing everything needed to reproduce the problem Java 8 closures can easily be nested to define treelike data structures. I noticed slow compilation time in one of our projects and simplified it as much as possible to isolate the problem. Here is an example showing closures that are nested 3 levels deep: public class Test3 { public Test3 child(Consumer<Test3> object) { return null; } public Consumer<Test3> test() { return level1 -> level1.child(level2 -> level2.child(level3 -> level3.child(null))); } } The code above compiles in less than 10ms (measured using org.eclipse.jdt.core/debug/builder/stats=true) But as nesting level is increased, compilation time increases exponentially: Level 10: ~150ms Level 11: ~300ms Level 12: ~600ms Level 13: 1100ms Level 14: 2200ms Level 15: 4200ms Level 16: 8400ms This behavior can be reproduced with the attached eclipse project. It contains Test16.java and the code generator that created Test16.java.
Here is the output from JDT debug logging: >FULL BUILD STATS for: Reproducer > compiled 97 lines in 8354ms:11.6lines/s > parse: 3 ms (0.0%), resolve: 8346 ms (99.9%), analyze: 1 ms (0.0%), generate: 2 ms (0.0%)
Generally, such characteristics come to no surprise. The intrinsic complexity of type inference grows in what intuitively I would call an exponential scale. And your measurements confirm that resolve (which includes inference) is the expensive part. It would be interesting to know if lambda nesting is still so expensive when you use explicit types (for lambda arguments).
I know too little about the underlying type inference to rely on my intuition to decide wether O(2^N) could be considered expected/acceptable here. But I do know that compilation time only grows perfectly linear with javac in this specific sample. Here is a comparison of compilation times: N=20: javac 30ms, eclipse 140s N=50: javac 50ms, eclipse estimated around 4000 years N=100: javac 100ms N=200: javac 200ms N=300: javac stackoverflow So I don't think that the intrinsic complexity of the problem can explain the O(2^N) here.
While you're measuring this issue, could you please provide data also for this: (In reply to Stephan Herrmann from comment #2) > It would be interesting to know if lambda nesting is still so expensive when > you use explicit types (for lambda arguments).
On a different note, what is the deepest nesting level that you have seen in "real" production code?
The deepest nesting level that was still in our code base when I started investigating the problem was 15. We had 2 closures at this level so compilation time for those roughly 30 lines of Java code was more than 8 seconds. As is expected, developers started to rewrite deeply nested code to workaround the problem in Eclipse. However we still have a small project with only a few hundred files that currently takes 60s to compile in Eclipse and less than 1s with javac.
Compilation is still as expensive when using types on each level like this: level4.child((Test16 level5) ->
The problem disappears when using inner classes like this on each level: level4.child(new Consumer<Test16>() { public void accept(Test16 level5) {
The 4000 years of compilation time for level 50 seem to be true only when memory is almost unlimited. Here are the top 10 consuming objects before OutOfMemoryError is thrown: C:\WINDOWS\system32>jmap -histo:live 8684 num #instances #bytes class name ---------------------------------------------- 1: 1702338 245136672 org.eclipse.jdt.internal.compiler.ast.LambdaExpression 2: 6617956 244438336 [C 3: 1702433 190672496 org.eclipse.jdt.internal.compiler.ast.MessageSend 4: 1701789 190600368 org.eclipse.jdt.internal.compiler.lookup.MethodScope 5: 1705426 122790672 org.eclipse.jdt.internal.compiler.lookup.MethodBinding 6: 5111467 122692536 [Lorg.eclipse.jdt.internal.compiler.lookup.TypeBinding; 7: 1702402 122572944 org.eclipse.jdt.internal.compiler.ast.Argument 8: 1701620 122516640 org.eclipse.jdt.internal.compiler.lookup.LocalVariableBinding 9: 1702441 108956224 org.eclipse.jdt.internal.compiler.ast.SingleNameReference 10: 1701903 81775416 [J
(In reply to Markus Gaisbauer from comment #9) > The 4000 years of compilation time for level 50 seem to be true only when > memory is almost unlimited. I still don't believe that 50 levels of nesting is in any way relevant :) 15 already sounds like an extremely complex style of code, if you ask me. The other details, in particular in comment 7 and comment 8 are, however, very useful. Thanks.
Retested for kicks in JDT 3.18.100.v20190916-1045. Recompilation time for the attached file (Test16.java): * ecj 1.8 • 11 seconds * ecj 12 • 11 seconds Hardware: MacBook Pro (13-inch, Early 2011) 2.3 GHz Intel Core i5
This bug hasn't had any activity in quite some time. Maybe the problem got resolved, was a duplicate of something else, or became less pressing for some reason - or maybe it's still relevant but just hasn't been looked at yet. If you have further information on the current state of the bug, please add it. The information can be, for example, that the problem still occurs, that you still want the feature, that more information is needed, or that the bug is (for whatever reason) no longer relevant. -- The automated Eclipse Genie.