Community
Participate
Working Groups
Created attachment 277162 [details] Java Mission Control allocation overview Try compiling the following class in Eclipse using Java 11 and normal memory settings: // --------------------------------------------------------------- package test; import static test.Import.f; import static test.Import.s; import java.util.Collection; import java.util.function.Consumer; public class Test { J j; I i; void m() { j.b(i -> { var m = i.m(s( f(1).x(1), f(2).x(2), f(3).x(3), f(4).x(4), f(5).x(5), f(6).x(6), f(7).x(7), f(8).x(8), f(9).x(9), f(10).x(10), f(11).x(11), f(12).x(12) )); System.out.println(m); }); } } class Import { static <T> F1<T> f(T t) { return null; } static S1<RX> s(F4<?>... t) { return null; } static S1<RX> s(Collection<? extends F4<?>> t) { return null; } static <T1> S1<R1<T1>> s(F4<T1> t1) { return null; } static <T1, T2> S1<R2<T1, T2>> s(F4<T1> t1, F4<T2> t2) { return null; } static <T1, T2, T3> S1<R3<T1, T2, T3>> s(F4<T1> t1, F4<T2> t2, F4<T3> t3) { return null; } static <T1, T2, T3, T4> S1<R4<T1, T2, T3, T4>> s(F4<T1> t1, F4<T2> t2, F4<T3> t3, F4<T4> t4) { return null; } static <T1, T2, T3, T4, T5> S1<R5<T1, T2, T3, T4, T5>> s(F4<T1> t1, F4<T2> t2, F4<T3> t3, F4<T4> t4, F4<T5> t5) { return null; } static <T1, T2, T3, T4, T5, T6> S1<R6<T1, T2, T3, T4, T5, T6>> s(F4<T1> t1, F4<T2> t2, F4<T3> t3, F4<T4> t4, F4<T5> t5, F4<T6> t6) { return null; } static <T1, T2, T3, T4, T5, T6, T7> S1<R7<T1, T2, T3, T4, T5, T6, T7>> s(F4<T1> t1, F4<T2> t2, F4<T3> t3, F4<T4> t4, F4<T5> t5, F4<T6> t6, F4<T7> t7) { return null; } static <T1, T2, T3, T4, T5, T6, T7, T8> S1<R8<T1, T2, T3, T4, T5, T6, T7, T8>> s(F4<T1> t1, F4<T2> t2, F4<T3> t3, F4<T4> t4, F4<T5> t5, F4<T6> t6, F4<T7> t7, F4<T8> t8) { return null; } static <T1, T2, T3, T4, T5, T6, T7, T8, T9> S1<R9<T1, T2, T3, T4, T5, T6, T7, T8, T9>> s(F4<T1> t1, F4<T2> t2, F4<T3> t3, F4<T4> t4, F4<T5> t5, F4<T6> t6, F4<T7> t7, F4<T8> t8, F4<T9> t9) { return null; } static <T1, T2, T3, T4, T5, T6, T7, T8, T9, T10> S1<R10<T1, T2, T3, T4, T5, T6, T7, T8, T9, T10>> s(F4<T1> t1, F4<T2> t2, F4<T3> t3, F4<T4> t4, F4<T5> t5, F4<T6> t6, F4<T7> t7, F4<T8> t8, F4<T9> t9, F4<T10> t10) { return null; } static <T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11> S1<R11<T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11>> s(F4<T1> t1, F4<T2> t2, F4<T3> t3, F4<T4> t4, F4<T5> t5, F4<T6> t6, F4<T7> t7, F4<T8> t8, F4<T9> t9, F4<T10> t10, F4<T11> t11) { return null; } static <T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12> S1<R12<T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12>> s(F4<T1> t1, F4<T2> t2, F4<T3> t3, F4<T4> t4, F4<T5> t5, F4<T6> t6, F4<T7> t7, F4<T8> t8, F4<T9> t9, F4<T10> t10, F4<T11> t11, F4<T12> t12) { return null; } } interface F1<T> extends F2<T> {} interface F2<T> extends F3<T> { F3<T> x(F3<T> f3); F3<T> x(T f3); } interface F3<T> extends F4<T> {} interface F4<T> {} interface J { void b(Consumer<I> consumer); } interface I { <R extends RX> R m(S7<R> s4); } interface S1<R extends RX> extends S2<R> {} interface S2<R extends RX> extends S3<R> {} interface S3<R extends RX> extends S4<R> {} interface S4<R extends RX> extends S5<R> {} interface S5<R extends RX> extends S6<R> {} interface S6<R extends RX> extends S7<R> {} interface S7<R extends RX> {} interface RX {} interface R1<T1> extends RX {} interface R2<T1, T2> extends RX {} interface R3<T1, T2, T3> extends RX {} interface R4<T1, T2, T3, T4> extends RX {} interface R5<T1, T2, T3, T4, T5> extends RX {} interface R6<T1, T2, T3, T4, T5, T6> extends RX {} interface R7<T1, T2, T3, T4, T5, T6, T7> extends RX {} interface R8<T1, T2, T3, T4, T5, T6, T7, T8> extends RX {} interface R9<T1, T2, T3, T4, T5, T6, T7, T8, T9> extends RX {} interface R10<T1, T2, T3, T4, T5, T6, T7, T8, T9, T10> extends RX {} interface R11<T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11> extends RX {} interface R12<T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12> extends RX {} // --------------------------------------------------------------- The compiler runs forever until it reaches a result. A JMC/JFR session seems to reveal an excessive amount of allocations of these types (100s of GB for a single compilation!): Class Max Live Count Max Live Size Live Size Increase Total Allocation Est. TLAB Allocation Total Allocation Outside TLABs org.eclipse.jdt.internal.compiler.lookup.ConstraintTypeFormula 1.07840158144E11 B 1.07840158144E11 B org.eclipse.jdt.internal.compiler.lookup.TypeBound 8.8232580912E10 B 8.8232580912E10 B org.eclipse.jdt.internal.compiler.lookup.ConstraintFormula[] 1.5996216536E10 B 1.5996216536E10 B In these methods: ConstraintTypeFormula org.eclipse.jdt.internal.compiler.lookup.ConstraintTypeFormula.create(TypeBinding, TypeBinding, int, boolean) Object org.eclipse.jdt.internal.compiler.lookup.ConstraintTypeFormula.reduceTypeEquality(TypeBinding, InferenceContext18) A workaround seems to be to prevent one of the inline calls and assign the intermediate type to a local variable // --------------------------------------------------------------- package test; import static test.Import.f; import static test.Import.s; import java.util.Collection; import java.util.function.Consumer; public class Test { J j; I i; void m() { j.b(i -> { // Local variable assignment here, as a workaround var s = s( f(1).x(1), f(2).x(2), f(3).x(3), f(4).x(4), f(5).x(5), f(6).x(6), f(7).x(7), f(8).x(8), f(9).x(9), f(10).x(10), f(11).x(11), f(12).x(12) ); var m = i.m(s); System.out.println(m); }); } } class Import { static <T> F1<T> f(T t) { return null; } static S1<RX> s(F4<?>... t) { return null; } static S1<RX> s(Collection<? extends F4<?>> t) { return null; } static <T1> S1<R1<T1>> s(F4<T1> t1) { return null; } static <T1, T2> S1<R2<T1, T2>> s(F4<T1> t1, F4<T2> t2) { return null; } static <T1, T2, T3> S1<R3<T1, T2, T3>> s(F4<T1> t1, F4<T2> t2, F4<T3> t3) { return null; } static <T1, T2, T3, T4> S1<R4<T1, T2, T3, T4>> s(F4<T1> t1, F4<T2> t2, F4<T3> t3, F4<T4> t4) { return null; } static <T1, T2, T3, T4, T5> S1<R5<T1, T2, T3, T4, T5>> s(F4<T1> t1, F4<T2> t2, F4<T3> t3, F4<T4> t4, F4<T5> t5) { return null; } static <T1, T2, T3, T4, T5, T6> S1<R6<T1, T2, T3, T4, T5, T6>> s(F4<T1> t1, F4<T2> t2, F4<T3> t3, F4<T4> t4, F4<T5> t5, F4<T6> t6) { return null; } static <T1, T2, T3, T4, T5, T6, T7> S1<R7<T1, T2, T3, T4, T5, T6, T7>> s(F4<T1> t1, F4<T2> t2, F4<T3> t3, F4<T4> t4, F4<T5> t5, F4<T6> t6, F4<T7> t7) { return null; } static <T1, T2, T3, T4, T5, T6, T7, T8> S1<R8<T1, T2, T3, T4, T5, T6, T7, T8>> s(F4<T1> t1, F4<T2> t2, F4<T3> t3, F4<T4> t4, F4<T5> t5, F4<T6> t6, F4<T7> t7, F4<T8> t8) { return null; } static <T1, T2, T3, T4, T5, T6, T7, T8, T9> S1<R9<T1, T2, T3, T4, T5, T6, T7, T8, T9>> s(F4<T1> t1, F4<T2> t2, F4<T3> t3, F4<T4> t4, F4<T5> t5, F4<T6> t6, F4<T7> t7, F4<T8> t8, F4<T9> t9) { return null; } static <T1, T2, T3, T4, T5, T6, T7, T8, T9, T10> S1<R10<T1, T2, T3, T4, T5, T6, T7, T8, T9, T10>> s(F4<T1> t1, F4<T2> t2, F4<T3> t3, F4<T4> t4, F4<T5> t5, F4<T6> t6, F4<T7> t7, F4<T8> t8, F4<T9> t9, F4<T10> t10) { return null; } static <T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11> S1<R11<T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11>> s(F4<T1> t1, F4<T2> t2, F4<T3> t3, F4<T4> t4, F4<T5> t5, F4<T6> t6, F4<T7> t7, F4<T8> t8, F4<T9> t9, F4<T10> t10, F4<T11> t11) { return null; } static <T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12> S1<R12<T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12>> s(F4<T1> t1, F4<T2> t2, F4<T3> t3, F4<T4> t4, F4<T5> t5, F4<T6> t6, F4<T7> t7, F4<T8> t8, F4<T9> t9, F4<T10> t10, F4<T11> t11, F4<T12> t12) { return null; } } interface F1<T> extends F2<T> {} interface F2<T> extends F3<T> { F3<T> x(F3<T> f3); F3<T> x(T f3); } interface F3<T> extends F4<T> {} interface F4<T> {} interface J { void b(Consumer<I> consumer); } interface I { <R extends RX> R m(S7<R> s4); } interface S1<R extends RX> extends S2<R> {} interface S2<R extends RX> extends S3<R> {} interface S3<R extends RX> extends S4<R> {} interface S4<R extends RX> extends S5<R> {} interface S5<R extends RX> extends S6<R> {} interface S6<R extends RX> extends S7<R> {} interface S7<R extends RX> {} interface RX {} interface R1<T1> extends RX {} interface R2<T1, T2> extends RX {} interface R3<T1, T2, T3> extends RX {} interface R4<T1, T2, T3, T4> extends RX {} interface R5<T1, T2, T3, T4, T5> extends RX {} interface R6<T1, T2, T3, T4, T5, T6> extends RX {} interface R7<T1, T2, T3, T4, T5, T6, T7> extends RX {} interface R8<T1, T2, T3, T4, T5, T6, T7, T8> extends RX {} interface R9<T1, T2, T3, T4, T5, T6, T7, T8, T9> extends RX {} interface R10<T1, T2, T3, T4, T5, T6, T7, T8, T9, T10> extends RX {} interface R11<T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11> extends RX {} interface R12<T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12> extends RX {} // --------------------------------------------------------------- This is a significant bug for users of tuple libraries, including e.g.: - jOOQ - jOOλ - Vavr - Possibly others This problem is exceptionally significant when writing the code elsewhere, e.g. outside of Eclipse, and then loading the code in Eclipse. It is very difficult to track down and to assign the right local variable as a workaround, as every compilation run takes forever. There seems to be a threshold in the number of generics / overloads. Remove R8-R12 as well as the relevant overloads of s() and arguments to the call to s(), and the problem does not manifest itself as severely as in the above example.
Is this a regression in 4.10? Can you also try with 4.11 nightly builds?
(In reply to Lukas Eder from comment #0) > In these methods: > > ConstraintTypeFormula > org.eclipse.jdt.internal.compiler.lookup.ConstraintTypeFormula. > create(TypeBinding, TypeBinding, int, boolean) > Object > org.eclipse.jdt.internal.compiler.lookup.ConstraintTypeFormula. > reduceTypeEquality(TypeBinding, InferenceContext18) Just from looking at these code locations, it's hard to believe we do anything unnecessary, because those code regions are basically "verbatim copies" of JLS. From a quick look at the example program it just opens a huge combinatorial space which needs to be explored in full. If we see call chains into these locations, maybe we can identify entire invocations of type inference which are redundant or otherwise unnecessary. As you mention Java 11, are you saying that giving a specific type instead of 'var' performs significantly better? What happens if i.m(..) is invoked as a standalone expression, i.e., not assigned to any variable? If 'var' is worse than unassigned, than we'd have to check if local variable type inference invokes unnecessary type inference of the RHS.
(In reply to Andrey Loskutov from comment #1) > Is this a regression in 4.10? I have vague memories of this having been there in 4.9, but not as bad as it is now > Can you also try with 4.11 nightly builds? I might, later this week (In reply to Stephan Herrmann from comment #2) > (In reply to Lukas Eder from comment #0) > > In these methods: > > > > ConstraintTypeFormula > > org.eclipse.jdt.internal.compiler.lookup.ConstraintTypeFormula. > > create(TypeBinding, TypeBinding, int, boolean) > > Object > > org.eclipse.jdt.internal.compiler.lookup.ConstraintTypeFormula. > > reduceTypeEquality(TypeBinding, InferenceContext18) > > Just from looking at these code locations, it's hard to believe we do > anything unnecessary, because those code regions are basically "verbatim > copies" of JLS. javac has no problems at all compiling this, and by consequence, neither does IntelliJ... > From a quick look at the example program it just opens a huge combinatorial > space which needs to be explored in full. Why? > If we see call chains into these locations, maybe we can identify entire > invocations of type inference which are redundant or otherwise unnecessary. I will try again later this week, providing the call chains > As you mention Java 11, are you saying that giving a specific type instead > of 'var' performs significantly better? This (Java 11) is just additional info that might help reproduce the issue. I haven't tried all combinations of Java versions and language features. It took quite a while to produce a relatively minimal example that helps reproduce this. > What happens if i.m(..) is invoked as a standalone expression, i.e., not > assigned to any variable? If 'var' is worse than unassigned, than we'd have > to check if local variable type inference invokes unnecessary type inference > of the RHS. I don't think using var is relevant. I've seen it with other assignment types. I will try again later this week. If I find some time, I'll create a more minimal example to reproduce this problem. As I said, it took long enough to find this one :-)
(In reply to Lukas Eder from comment #3) > (In reply to Andrey Loskutov from comment #1) > > Can you also try with 4.11 nightly builds? Yes, can still reproduce this with Build id: I20190115-1800 > (In reply to Stephan Herrmann from comment #2) > > (In reply to Lukas Eder from comment #0) > > If we see call chains into these locations, maybe we can identify entire > > invocations of type inference which are redundant or otherwise unnecessary. Here you go. For ConstraintTypeFormula allocations: ConstraintTypeFormula org.eclipse.jdt.internal.compiler.lookup.ConstraintTypeFormula.create(TypeBinding, TypeBinding, int, boolean) 221111 Object org.eclipse.jdt.internal.compiler.lookup.ConstraintTypeFormula.reduceTypeEquality(TypeBinding, InferenceContext18) 205996 Object org.eclipse.jdt.internal.compiler.lookup.ConstraintTypeFormula.reduce(InferenceContext18) 205996 boolean org.eclipse.jdt.internal.compiler.lookup.BoundSet.reduceOneConstraint(InferenceContext18, ConstraintFormula) 205996 boolean org.eclipse.jdt.internal.compiler.lookup.BoundSet.incorporate(InferenceContext18, TypeBound[], TypeBound[]) 205996 boolean org.eclipse.jdt.internal.compiler.lookup.BoundSet.incorporate(InferenceContext18) 205996 BoundSet org.eclipse.jdt.internal.compiler.lookup.InferenceContext18.solve(boolean) 205996 MethodBinding org.eclipse.jdt.internal.compiler.lookup.ParameterizedGenericMethodBinding.computeCompatibleMethod18(MethodBinding, TypeBinding[], Scope, InvocationSite) 205996 MethodBinding org.eclipse.jdt.internal.compiler.lookup.ParameterizedGenericMethodBinding.computeCompatibleMethod(MethodBinding, TypeBinding[], Scope, InvocationSite) 205996 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.computeCompatibleMethod(MethodBinding, TypeBinding[], InvocationSite, boolean) 205996 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.computeCompatibleMethod(MethodBinding, TypeBinding[], InvocationSite) 205996 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.findMethod0(ReferenceBinding, char[], TypeBinding[], InvocationSite, boolean) 205996 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.findMethod(ReferenceBinding, char[], TypeBinding[], InvocationSite, boolean) 205996 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.getMethod(TypeBinding, char[], TypeBinding[], InvocationSite) 205996 TypeBinding org.eclipse.jdt.internal.compiler.ast.MessageSend.findMethodBinding(BlockScope) 205996 TypeBinding org.eclipse.jdt.internal.compiler.ast.MessageSend.resolveType(BlockScope) 205996 void org.eclipse.jdt.internal.compiler.ast.LocalDeclaration.resolve(BlockScope) 205996 void org.eclipse.jdt.internal.compiler.ast.Block.resolve(BlockScope) 205996 TypeBinding org.eclipse.jdt.internal.compiler.ast.LambdaExpression.resolveType(BlockScope, boolean) 205996 LambdaExpression org.eclipse.jdt.internal.compiler.ast.LambdaExpression.cachedResolvedCopy(TypeBinding, boolean, boolean, InferenceContext18) 115512 boolean org.eclipse.jdt.internal.compiler.ast.LambdaExpression.isCompatibleWith(TypeBinding, Scope) 115512 boolean org.eclipse.jdt.internal.compiler.lookup.PolyTypeBinding.isCompatibleWith(TypeBinding, Scope) 115512 int org.eclipse.jdt.internal.compiler.lookup.Scope.parameterCompatibilityLevel(TypeBinding, TypeBinding, LookupEnvironment, boolean) 115512 int org.eclipse.jdt.internal.compiler.lookup.Scope.parameterCompatibilityLevel(MethodBinding, TypeBinding[], boolean) 115512 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.computeCompatibleMethod(MethodBinding, TypeBinding[], InvocationSite, boolean) 115512 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.computeCompatibleMethod(MethodBinding, TypeBinding[], InvocationSite) 115512 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.findMethod0(ReferenceBinding, char[], TypeBinding[], InvocationSite, boolean) 115512 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.findMethod(ReferenceBinding, char[], TypeBinding[], InvocationSite, boolean) 115512 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.getMethod(TypeBinding, char[], TypeBinding[], InvocationSite) 115512 TypeBinding org.eclipse.jdt.internal.compiler.ast.MessageSend.findMethodBinding(BlockScope) 115512 TypeBinding org.eclipse.jdt.internal.compiler.ast.MessageSend.resolveType(BlockScope) 115512 void org.eclipse.jdt.internal.compiler.ast.Expression.resolve(BlockScope) 115512 void org.eclipse.jdt.internal.compiler.ast.AbstractMethodDeclaration.resolveStatements() 115512 void org.eclipse.jdt.internal.compiler.ast.MethodDeclaration.resolveStatements() 115512 void org.eclipse.jdt.internal.compiler.ast.AbstractMethodDeclaration.resolve(ClassScope) 115512 void org.eclipse.jdt.internal.compiler.ast.TypeDeclaration.resolve() 115512 void org.eclipse.jdt.internal.compiler.ast.TypeDeclaration.resolve(CompilationUnitScope) 115512 void org.eclipse.jdt.internal.compiler.ast.CompilationUnitDeclaration.resolve() 115512 CompilationUnitDeclaration org.eclipse.jdt.internal.compiler.Compiler.resolve(CompilationUnitDeclaration, ICompilationUnit, boolean, boolean, boolean) 38859 void org.eclipse.jdt.internal.compiler.Compiler.process(CompilationUnitDeclaration, int) 38133 CompilationUnitDeclaration org.eclipse.jdt.core.dom.CompilationUnitResolver.resolve(CompilationUnitDeclaration, ICompilationUnit, NodeSearcher, boolean, boolean, boolean) 19520 void org.eclipse.jdt.internal.core.search.indexing.SourceIndexer.resolveDocument() 19000 void org.eclipse.jdt.internal.compiler.ast.ASTNode.resolvePolyExpressionArguments(Invocation, MethodBinding, TypeBinding[], BlockScope) 90484 TypeBinding org.eclipse.jdt.internal.compiler.ast.MessageSend.findMethodBinding(BlockScope) 90484 TypeBinding org.eclipse.jdt.internal.compiler.ast.MessageSend.resolveType(BlockScope) 90484 void org.eclipse.jdt.internal.compiler.ast.Expression.resolve(BlockScope) 90484 void org.eclipse.jdt.internal.compiler.ast.AbstractMethodDeclaration.resolveStatements() 90484 void org.eclipse.jdt.internal.compiler.ast.MethodDeclaration.resolveStatements() 90484 void org.eclipse.jdt.internal.compiler.ast.AbstractMethodDeclaration.resolve(ClassScope) 90484 void org.eclipse.jdt.internal.compiler.ast.TypeDeclaration.resolve() 90484 void org.eclipse.jdt.internal.compiler.ast.TypeDeclaration.resolve(CompilationUnitScope) 90484 void org.eclipse.jdt.internal.compiler.ast.CompilationUnitDeclaration.resolve() 90484 void org.eclipse.jdt.internal.compiler.Compiler.process(CompilationUnitDeclaration, int) 38377 CompilationUnitDeclaration org.eclipse.jdt.internal.compiler.Compiler.resolve(CompilationUnitDeclaration, ICompilationUnit, boolean, boolean, boolean) 21667 void org.eclipse.jdt.internal.core.search.indexing.SourceIndexer.resolveDocument() 21466 CompilationUnitDeclaration org.eclipse.jdt.core.dom.CompilationUnitResolver.resolve(CompilationUnitDeclaration, ICompilationUnit, NodeSearcher, boolean, boolean, boolean) 8974 ConstraintTypeFormula org.eclipse.jdt.internal.compiler.lookup.BoundSet.combineSameSame(TypeBound, TypeBound) 14888 boolean org.eclipse.jdt.internal.compiler.lookup.BoundSet.incorporate(InferenceContext18, TypeBound[], TypeBound[]) 14888 boolean org.eclipse.jdt.internal.compiler.lookup.BoundSet.incorporate(InferenceContext18) 14888 BoundSet org.eclipse.jdt.internal.compiler.lookup.InferenceContext18.solve(boolean) 14888 MethodBinding org.eclipse.jdt.internal.compiler.lookup.ParameterizedGenericMethodBinding.computeCompatibleMethod18(MethodBinding, TypeBinding[], Scope, InvocationSite) 14888 MethodBinding org.eclipse.jdt.internal.compiler.lookup.ParameterizedGenericMethodBinding.computeCompatibleMethod(MethodBinding, TypeBinding[], Scope, InvocationSite) 14888 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.computeCompatibleMethod(MethodBinding, TypeBinding[], InvocationSite, boolean) 14888 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.computeCompatibleMethod(MethodBinding, TypeBinding[], InvocationSite) 14888 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.findMethod0(ReferenceBinding, char[], TypeBinding[], InvocationSite, boolean) 14888 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.findMethod(ReferenceBinding, char[], TypeBinding[], InvocationSite, boolean) 14888 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.getMethod(TypeBinding, char[], TypeBinding[], InvocationSite) 14888 TypeBinding org.eclipse.jdt.internal.compiler.ast.MessageSend.findMethodBinding(BlockScope) 14888 TypeBinding org.eclipse.jdt.internal.compiler.ast.MessageSend.resolveType(BlockScope) 14888 void org.eclipse.jdt.internal.compiler.ast.LocalDeclaration.resolve(BlockScope) 14888 void org.eclipse.jdt.internal.compiler.ast.Block.resolve(BlockScope) 14888 TypeBinding org.eclipse.jdt.internal.compiler.ast.LambdaExpression.resolveType(BlockScope, boolean) 14888 LambdaExpression org.eclipse.jdt.internal.compiler.ast.LambdaExpression.cachedResolvedCopy(TypeBinding, boolean, boolean, InferenceContext18) 8377 void org.eclipse.jdt.internal.compiler.ast.ASTNode.resolvePolyExpressionArguments(Invocation, MethodBinding, TypeBinding[], BlockScope) 6511 For TypeBound allocations: Object org.eclipse.jdt.internal.compiler.lookup.ConstraintTypeFormula.reduceTypeEquality(TypeBinding, InferenceContext18) 186274 Object org.eclipse.jdt.internal.compiler.lookup.ConstraintTypeFormula.reduce(InferenceContext18) 186274 boolean org.eclipse.jdt.internal.compiler.lookup.BoundSet.reduceOneConstraint(InferenceContext18, ConstraintFormula) 186274 boolean org.eclipse.jdt.internal.compiler.lookup.BoundSet.reduceOneConstraint(InferenceContext18, ConstraintFormula) 186203 boolean org.eclipse.jdt.internal.compiler.lookup.BoundSet.incorporate(InferenceContext18, TypeBound[], TypeBound[]) 186203 boolean org.eclipse.jdt.internal.compiler.lookup.BoundSet.incorporate(InferenceContext18) 186203 BoundSet org.eclipse.jdt.internal.compiler.lookup.InferenceContext18.solve(boolean) 186203 MethodBinding org.eclipse.jdt.internal.compiler.lookup.ParameterizedGenericMethodBinding.computeCompatibleMethod18(MethodBinding, TypeBinding[], Scope, InvocationSite) 186203 MethodBinding org.eclipse.jdt.internal.compiler.lookup.ParameterizedGenericMethodBinding.computeCompatibleMethod(MethodBinding, TypeBinding[], Scope, InvocationSite) 186203 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.computeCompatibleMethod(MethodBinding, TypeBinding[], InvocationSite, boolean) 186203 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.computeCompatibleMethod(MethodBinding, TypeBinding[], InvocationSite) 186203 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.findMethod0(ReferenceBinding, char[], TypeBinding[], InvocationSite, boolean) 186203 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.findMethod(ReferenceBinding, char[], TypeBinding[], InvocationSite, boolean) 186203 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.getMethod(TypeBinding, char[], TypeBinding[], InvocationSite) 186203 TypeBinding org.eclipse.jdt.internal.compiler.ast.MessageSend.findMethodBinding(BlockScope) 186203 TypeBinding org.eclipse.jdt.internal.compiler.ast.MessageSend.resolveType(BlockScope) 186203 void org.eclipse.jdt.internal.compiler.ast.LocalDeclaration.resolve(BlockScope) 186203 void org.eclipse.jdt.internal.compiler.ast.Block.resolve(BlockScope) 186203 TypeBinding org.eclipse.jdt.internal.compiler.ast.LambdaExpression.resolveType(BlockScope, boolean) 186203 LambdaExpression org.eclipse.jdt.internal.compiler.ast.LambdaExpression.cachedResolvedCopy(TypeBinding, boolean, boolean, InferenceContext18) 104191 boolean org.eclipse.jdt.internal.compiler.ast.LambdaExpression.isCompatibleWith(TypeBinding, Scope) 104191 boolean org.eclipse.jdt.internal.compiler.lookup.PolyTypeBinding.isCompatibleWith(TypeBinding, Scope) 104191 int org.eclipse.jdt.internal.compiler.lookup.Scope.parameterCompatibilityLevel(TypeBinding, TypeBinding, LookupEnvironment, boolean) 104191 int org.eclipse.jdt.internal.compiler.lookup.Scope.parameterCompatibilityLevel(MethodBinding, TypeBinding[], boolean) 104191 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.computeCompatibleMethod(MethodBinding, TypeBinding[], InvocationSite, boolean) 104191 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.computeCompatibleMethod(MethodBinding, TypeBinding[], InvocationSite) 104191 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.findMethod0(ReferenceBinding, char[], TypeBinding[], InvocationSite, boolean) 104191 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.findMethod(ReferenceBinding, char[], TypeBinding[], InvocationSite, boolean) 104191 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.getMethod(TypeBinding, char[], TypeBinding[], InvocationSite) 104191 TypeBinding org.eclipse.jdt.internal.compiler.ast.MessageSend.findMethodBinding(BlockScope) 104191 TypeBinding org.eclipse.jdt.internal.compiler.ast.MessageSend.resolveType(BlockScope) 104191 void org.eclipse.jdt.internal.compiler.ast.Expression.resolve(BlockScope) 104191 void org.eclipse.jdt.internal.compiler.ast.AbstractMethodDeclaration.resolveStatements() 104191 void org.eclipse.jdt.internal.compiler.ast.MethodDeclaration.resolveStatements() 104191 void org.eclipse.jdt.internal.compiler.ast.AbstractMethodDeclaration.resolve(ClassScope) 104191 void org.eclipse.jdt.internal.compiler.ast.TypeDeclaration.resolve() 104191 void org.eclipse.jdt.internal.compiler.ast.TypeDeclaration.resolve(CompilationUnitScope) 104191 void org.eclipse.jdt.internal.compiler.ast.CompilationUnitDeclaration.resolve() 104191 CompilationUnitDeclaration org.eclipse.jdt.internal.compiler.Compiler.resolve(CompilationUnitDeclaration, ICompilationUnit, boolean, boolean, boolean) 35243 void org.eclipse.jdt.internal.compiler.Compiler.process(CompilationUnitDeclaration, int) 34316 CompilationUnitDeclaration org.eclipse.jdt.core.dom.CompilationUnitResolver.resolve(CompilationUnitDeclaration, ICompilationUnit, NodeSearcher, boolean, boolean, boolean) 17572 void org.eclipse.jdt.internal.core.search.indexing.SourceIndexer.resolveDocument() 17060 void org.eclipse.jdt.internal.compiler.ast.ASTNode.resolvePolyExpressionArguments(Invocation, MethodBinding, TypeBinding[], BlockScope) 82012 TypeBinding org.eclipse.jdt.internal.compiler.ast.MessageSend.findMethodBinding(BlockScope) 82012 TypeBinding org.eclipse.jdt.internal.compiler.ast.MessageSend.resolveType(BlockScope) 82012 void org.eclipse.jdt.internal.compiler.ast.Expression.resolve(BlockScope) 82012 void org.eclipse.jdt.internal.compiler.ast.AbstractMethodDeclaration.resolveStatements() 82012 void org.eclipse.jdt.internal.compiler.ast.MethodDeclaration.resolveStatements() 82012 void org.eclipse.jdt.internal.compiler.ast.AbstractMethodDeclaration.resolve(ClassScope) 82012 void org.eclipse.jdt.internal.compiler.ast.TypeDeclaration.resolve() 82012 void org.eclipse.jdt.internal.compiler.ast.TypeDeclaration.resolve(CompilationUnitScope) 82012 void org.eclipse.jdt.internal.compiler.ast.CompilationUnitDeclaration.resolve() 82012 void org.eclipse.jdt.internal.compiler.Compiler.process(CompilationUnitDeclaration, int) 34133 CompilationUnitDeclaration org.eclipse.jdt.internal.compiler.Compiler.resolve(CompilationUnitDeclaration, ICompilationUnit, boolean, boolean, boolean) 20155 void org.eclipse.jdt.internal.core.search.indexing.SourceIndexer.resolveDocument() 18757 CompilationUnitDeclaration org.eclipse.jdt.core.dom.CompilationUnitResolver.resolve(CompilationUnitDeclaration, ICompilationUnit, NodeSearcher, boolean, boolean, boolean) 8967 > > As you mention Java 11, are you saying that giving a specific type instead > > of 'var' performs significantly better? > > This (Java 11) is just additional info that might help reproduce the issue. > I haven't tried all combinations of Java versions and language features. It > took quite a while to produce a relatively minimal example that helps > reproduce this. var doesn't seem to have anything to do with this. In fact, the assignment is irrelevant. Here's a more minimal complete verifiable example: // --------------------------------------------------------------- package test; public class Test2 { void test() { m(s( // f(1), // f(2), f(3), f(4), f(5), f(6), f(7), f(8), f(9), f(10), f(11), f(12) )); } static <R> R m(S<R> s) { return null; } static <T> F<T> f(T t) { return null; } static <T1> S<R1<T1>> s(F<T1> t1) { return null; } static <T1, T2> S<R2<T1, T2>> s(F<T1> t1, F<T2> t2) { return null; } static <T1, T2, T3> S<R3<T1, T2, T3>> s(F<T1> t1, F<T2> t2, F<T3> t3) { return null; } static <T1, T2, T3, T4> S<R4<T1, T2, T3, T4>> s(F<T1> t1, F<T2> t2, F<T3> t3, F<T4> t4) { return null; } static <T1, T2, T3, T4, T5> S<R5<T1, T2, T3, T4, T5>> s(F<T1> t1, F<T2> t2, F<T3> t3, F<T4> t4, F<T5> t5) { return null; } static <T1, T2, T3, T4, T5, T6> S<R6<T1, T2, T3, T4, T5, T6>> s(F<T1> t1, F<T2> t2, F<T3> t3, F<T4> t4, F<T5> t5, F<T6> t6) { return null; } static <T1, T2, T3, T4, T5, T6, T7> S<R7<T1, T2, T3, T4, T5, T6, T7>> s(F<T1> t1, F<T2> t2, F<T3> t3, F<T4> t4, F<T5> t5, F<T6> t6, F<T7> t7) { return null; } static <T1, T2, T3, T4, T5, T6, T7, T8> S<R8<T1, T2, T3, T4, T5, T6, T7, T8>> s(F<T1> t1, F<T2> t2, F<T3> t3, F<T4> t4, F<T5> t5, F<T6> t6, F<T7> t7, F<T8> t8) { return null; } static <T1, T2, T3, T4, T5, T6, T7, T8, T9> S<R9<T1, T2, T3, T4, T5, T6, T7, T8, T9>> s(F<T1> t1, F<T2> t2, F<T3> t3, F<T4> t4, F<T5> t5, F<T6> t6, F<T7> t7, F<T8> t8, F<T9> t9) { return null; } static <T1, T2, T3, T4, T5, T6, T7, T8, T9, T10> S<R10<T1, T2, T3, T4, T5, T6, T7, T8, T9, T10>> s(F<T1> t1, F<T2> t2, F<T3> t3, F<T4> t4, F<T5> t5, F<T6> t6, F<T7> t7, F<T8> t8, F<T9> t9, F<T10> t10) { return null; } static <T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11> S<R11<T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11>> s(F<T1> t1, F<T2> t2, F<T3> t3, F<T4> t4, F<T5> t5, F<T6> t6, F<T7> t7, F<T8> t8, F<T9> t9, F<T10> t10, F<T11> t11) { return null; } static <T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12> S<R12<T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12>> s(F<T1> t1, F<T2> t2, F<T3> t3, F<T4> t4, F<T5> t5, F<T6> t6, F<T7> t7, F<T8> t8, F<T9> t9, F<T10> t10, F<T11> t11, F<T12> t12) { return null; } } interface F<T> {} interface S<R> {} interface R1<T1> {} interface R2<T1, T2> {} interface R3<T1, T2, T3> {} interface R4<T1, T2, T3, T4> {} interface R5<T1, T2, T3, T4, T5> {} interface R6<T1, T2, T3, T4, T5, T6> {} interface R7<T1, T2, T3, T4, T5, T6, T7> {} interface R8<T1, T2, T3, T4, T5, T6, T7, T8> {} interface R9<T1, T2, T3, T4, T5, T6, T7, T8, T9> {} interface R10<T1, T2, T3, T4, T5, T6, T7, T8, T9, T10> {} interface R11<T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11> {} interface R12<T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12> {} // --------------------------------------------------------------- I've commented two arguments to the call to s() to speed up things (significantly!). You can uncomment to see really bad performance. It does seem to behave with O(2^n) complexity, given that one additional argument changes performance so much. The new call stacks are, for ConstraintTypeFormula: ConstraintTypeFormula org.eclipse.jdt.internal.compiler.lookup.ConstraintTypeFormula.create(TypeBinding, TypeBinding, int, boolean) 261419 Object org.eclipse.jdt.internal.compiler.lookup.ConstraintTypeFormula.reduceTypeEquality(TypeBinding, InferenceContext18) 235159 Object org.eclipse.jdt.internal.compiler.lookup.ConstraintTypeFormula.reduce(InferenceContext18) 235159 boolean org.eclipse.jdt.internal.compiler.lookup.BoundSet.reduceOneConstraint(InferenceContext18, ConstraintFormula) 235159 boolean org.eclipse.jdt.internal.compiler.lookup.BoundSet.incorporate(InferenceContext18, TypeBound[], TypeBound[]) 235159 boolean org.eclipse.jdt.internal.compiler.lookup.BoundSet.incorporate(InferenceContext18) 235159 BoundSet org.eclipse.jdt.internal.compiler.lookup.InferenceContext18.resolve(InferenceVariable[]) 235159 BoundSet org.eclipse.jdt.internal.compiler.lookup.InferenceContext18.solve(boolean) 235159 MethodBinding org.eclipse.jdt.internal.compiler.lookup.ParameterizedGenericMethodBinding.computeCompatibleMethod18(MethodBinding, TypeBinding[], Scope, InvocationSite) 185160 MethodBinding org.eclipse.jdt.internal.compiler.lookup.ParameterizedGenericMethodBinding.computeCompatibleMethod(MethodBinding, TypeBinding[], Scope, InvocationSite) 185160 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.computeCompatibleMethod(MethodBinding, TypeBinding[], InvocationSite, boolean) 185160 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.computeCompatibleMethod(MethodBinding, TypeBinding[], InvocationSite) 185160 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.findMethod0(ReferenceBinding, char[], TypeBinding[], InvocationSite, boolean) 185160 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.findMethod(ReferenceBinding, char[], TypeBinding[], InvocationSite, boolean) 185160 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.getImplicitMethod(char[], TypeBinding[], InvocationSite) 185160 TypeBinding org.eclipse.jdt.internal.compiler.ast.MessageSend.findMethodBinding(BlockScope) 132915 TypeBinding org.eclipse.jdt.internal.compiler.ast.MessageSend.resolveType(BlockScope) 132915 void org.eclipse.jdt.internal.compiler.ast.Expression.resolve(BlockScope) 132915 void org.eclipse.jdt.internal.compiler.ast.AbstractMethodDeclaration.resolveStatements() 132915 void org.eclipse.jdt.internal.compiler.ast.MethodDeclaration.resolveStatements() 132915 void org.eclipse.jdt.internal.compiler.ast.AbstractMethodDeclaration.resolve(ClassScope) 132915 void org.eclipse.jdt.internal.compiler.ast.TypeDeclaration.resolve() 132915 void org.eclipse.jdt.internal.compiler.ast.TypeDeclaration.resolve(CompilationUnitScope) 132915 void org.eclipse.jdt.internal.compiler.ast.CompilationUnitDeclaration.resolve() 132915 CompilationUnitDeclaration org.eclipse.jdt.core.dom.CompilationUnitResolver.resolve(CompilationUnitDeclaration, ICompilationUnit, NodeSearcher, boolean, boolean, boolean) 101463 CompilationUnitDeclaration org.eclipse.jdt.internal.compiler.Compiler.resolve(CompilationUnitDeclaration, ICompilationUnit, boolean, boolean, boolean) 18386 void org.eclipse.jdt.internal.compiler.Compiler.process(CompilationUnitDeclaration, int) 13066 TypeBinding org.eclipse.jdt.internal.compiler.ast.MessageSend.resolveType(BlockScope) 52245 BoundSet org.eclipse.jdt.internal.compiler.lookup.InferenceContext18.solve() 49999 BoundSet org.eclipse.jdt.internal.compiler.lookup.InferenceContext18.inferInvocationType(TypeBinding, InvocationSite, MethodBinding) 49999 MethodBinding org.eclipse.jdt.internal.compiler.lookup.ParameterizedGenericMethodBinding.computeCompatibleMethod18(MethodBinding, TypeBinding[], Scope, InvocationSite) 49999 MethodBinding org.eclipse.jdt.internal.compiler.lookup.ParameterizedGenericMethodBinding.computeCompatibleMethod(MethodBinding, TypeBinding[], Scope, InvocationSite) 49999 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.computeCompatibleMethod(MethodBinding, TypeBinding[], InvocationSite, boolean) 49999 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.computeCompatibleMethod(MethodBinding, TypeBinding[], InvocationSite) 49999 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.findMethod0(ReferenceBinding, char[], TypeBinding[], InvocationSite, boolean) 49999 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.findMethod(ReferenceBinding, char[], TypeBinding[], InvocationSite, boolean) 49999 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.getImplicitMethod(char[], TypeBinding[], InvocationSite) 49999 TypeBinding org.eclipse.jdt.internal.compiler.ast.MessageSend.findMethodBinding(BlockScope) 49999 TypeBinding org.eclipse.jdt.internal.compiler.ast.MessageSend.resolveType(BlockScope) 49999 void org.eclipse.jdt.internal.compiler.ast.Expression.resolve(BlockScope) 49999 void org.eclipse.jdt.internal.compiler.ast.AbstractMethodDeclaration.resolveStatements() 49999 void org.eclipse.jdt.internal.compiler.ast.MethodDeclaration.resolveStatements() 49999 void org.eclipse.jdt.internal.compiler.ast.AbstractMethodDeclaration.resolve(ClassScope) 49999 void org.eclipse.jdt.internal.compiler.ast.TypeDeclaration.resolve() 49999 void org.eclipse.jdt.internal.compiler.ast.TypeDeclaration.resolve(CompilationUnitScope) 49999 void org.eclipse.jdt.internal.compiler.ast.CompilationUnitDeclaration.resolve() 49999 CompilationUnitDeclaration org.eclipse.jdt.core.dom.CompilationUnitResolver.resolve(CompilationUnitDeclaration, ICompilationUnit, NodeSearcher, boolean, boolean, boolean) 18759 CompilationUnitDeclaration org.eclipse.jdt.internal.compiler.Compiler.resolve(CompilationUnitDeclaration, ICompilationUnit, boolean, boolean, boolean) 18341 void org.eclipse.jdt.internal.compiler.Compiler.process(CompilationUnitDeclaration, int) 12899 ConstraintTypeFormula org.eclipse.jdt.internal.compiler.lookup.BoundSet.combineSameSame(TypeBound, TypeBound) 24384 For TypeBound: Object org.eclipse.jdt.internal.compiler.lookup.ConstraintTypeFormula.reduceTypeEquality(TypeBinding, InferenceContext18) 228777 Object org.eclipse.jdt.internal.compiler.lookup.ConstraintTypeFormula.reduce(InferenceContext18) 228777 boolean org.eclipse.jdt.internal.compiler.lookup.BoundSet.reduceOneConstraint(InferenceContext18, ConstraintFormula) 228777 boolean org.eclipse.jdt.internal.compiler.lookup.BoundSet.reduceOneConstraint(InferenceContext18, ConstraintFormula) 227552 boolean org.eclipse.jdt.internal.compiler.lookup.BoundSet.incorporate(InferenceContext18, TypeBound[], TypeBound[]) 227550 boolean org.eclipse.jdt.internal.compiler.lookup.BoundSet.incorporate(InferenceContext18) 227550 BoundSet org.eclipse.jdt.internal.compiler.lookup.InferenceContext18.resolve(InferenceVariable[]) 227550 BoundSet org.eclipse.jdt.internal.compiler.lookup.InferenceContext18.solve(boolean) 227550 MethodBinding org.eclipse.jdt.internal.compiler.lookup.ParameterizedGenericMethodBinding.computeCompatibleMethod18(MethodBinding, TypeBinding[], Scope, InvocationSite) 180428 MethodBinding org.eclipse.jdt.internal.compiler.lookup.ParameterizedGenericMethodBinding.computeCompatibleMethod(MethodBinding, TypeBinding[], Scope, InvocationSite) 180428 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.computeCompatibleMethod(MethodBinding, TypeBinding[], InvocationSite, boolean) 180428 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.computeCompatibleMethod(MethodBinding, TypeBinding[], InvocationSite) 180428 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.findMethod0(ReferenceBinding, char[], TypeBinding[], InvocationSite, boolean) 180428 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.findMethod(ReferenceBinding, char[], TypeBinding[], InvocationSite, boolean) 180428 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.getImplicitMethod(char[], TypeBinding[], InvocationSite) 180428 TypeBinding org.eclipse.jdt.internal.compiler.ast.MessageSend.findMethodBinding(BlockScope) 129609 TypeBinding org.eclipse.jdt.internal.compiler.ast.MessageSend.resolveType(BlockScope) 129609 void org.eclipse.jdt.internal.compiler.ast.Expression.resolve(BlockScope) 129609 void org.eclipse.jdt.internal.compiler.ast.AbstractMethodDeclaration.resolveStatements() 129609 void org.eclipse.jdt.internal.compiler.ast.MethodDeclaration.resolveStatements() 129609 void org.eclipse.jdt.internal.compiler.ast.AbstractMethodDeclaration.resolve(ClassScope) 129609 void org.eclipse.jdt.internal.compiler.ast.TypeDeclaration.resolve() 129609 void org.eclipse.jdt.internal.compiler.ast.TypeDeclaration.resolve(CompilationUnitScope) 129609 void org.eclipse.jdt.internal.compiler.ast.CompilationUnitDeclaration.resolve() 129609 CompilationUnitDeclaration org.eclipse.jdt.core.dom.CompilationUnitResolver.resolve(CompilationUnitDeclaration, ICompilationUnit, NodeSearcher, boolean, boolean, boolean) 100156 CompilationUnitDeclaration org.eclipse.jdt.core.dom.CompilationUnitResolver.resolve(ICompilationUnit, IJavaProject, List, NodeSearcher, Map, WorkingCopyOwner, int, IProgressMonitor) 100156 ASTNode org.eclipse.jdt.core.dom.ASTParser.internalCreateAST(IProgressMonitor) 100156 ASTNode org.eclipse.jdt.core.dom.ASTParser.createAST(IProgressMonitor) 100156 void org.eclipse.jdt.core.manipulation.CoreASTProvider$1.run() 100156 void org.eclipse.core.runtime.SafeRunner.run(ISafeRunnable) 100156 CompilationUnit org.eclipse.jdt.core.manipulation.CoreASTProvider.createAST(ITypeRoot, IProgressMonitor) 100156 CompilationUnit org.eclipse.jdt.core.manipulation.CoreASTProvider.getAST(ITypeRoot, CoreASTProvider$WAIT_FLAG, IProgressMonitor) 100156 CompilationUnit org.eclipse.jdt.core.manipulation.CoreASTProvider.getAST(ITypeRoot, CoreASTProvider$WAIT_FLAG, IProgressMonitor) 50825 CompilationUnit org.eclipse.jdt.core.manipulation.SharedASTProviderCore.getAST(ITypeRoot, SharedASTProviderCore$WAIT_FLAG, IProgressMonitor) 49331 CompilationUnitDeclaration org.eclipse.jdt.internal.compiler.Compiler.resolve(CompilationUnitDeclaration, ICompilationUnit, boolean, boolean, boolean) 17369 void org.eclipse.jdt.internal.compiler.Compiler.process(CompilationUnitDeclaration, int) 12084 TypeBinding org.eclipse.jdt.internal.compiler.ast.MessageSend.resolveType(BlockScope) 50819 void org.eclipse.jdt.internal.compiler.ast.Expression.resolve(BlockScope) 50819 void org.eclipse.jdt.internal.compiler.ast.AbstractMethodDeclaration.resolveStatements() 50819 void org.eclipse.jdt.internal.compiler.ast.MethodDeclaration.resolveStatements() 50819 void org.eclipse.jdt.internal.compiler.ast.AbstractMethodDeclaration.resolve(ClassScope) 50819 void org.eclipse.jdt.internal.compiler.ast.TypeDeclaration.resolve() 50819 void org.eclipse.jdt.internal.compiler.ast.TypeDeclaration.resolve(CompilationUnitScope) 50819 void org.eclipse.jdt.internal.compiler.ast.CompilationUnitDeclaration.resolve() 50819 CompilationUnitDeclaration org.eclipse.jdt.core.dom.CompilationUnitResolver.resolve(CompilationUnitDeclaration, ICompilationUnit, NodeSearcher, boolean, boolean, boolean) 36609 CompilationUnitDeclaration org.eclipse.jdt.internal.compiler.Compiler.resolve(CompilationUnitDeclaration, ICompilationUnit, boolean, boolean, boolean) 14210 BoundSet org.eclipse.jdt.internal.compiler.lookup.InferenceContext18.solve() 47122 BoundSet org.eclipse.jdt.internal.compiler.lookup.InferenceContext18.inferInvocationType(TypeBinding, InvocationSite, MethodBinding) 47122 MethodBinding org.eclipse.jdt.internal.compiler.lookup.ParameterizedGenericMethodBinding.computeCompatibleMethod18(MethodBinding, TypeBinding[], Scope, InvocationSite) 47122 MethodBinding org.eclipse.jdt.internal.compiler.lookup.ParameterizedGenericMethodBinding.computeCompatibleMethod(MethodBinding, TypeBinding[], Scope, InvocationSite) 47122 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.computeCompatibleMethod(MethodBinding, TypeBinding[], InvocationSite, boolean) 47122 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.computeCompatibleMethod(MethodBinding, TypeBinding[], InvocationSite) 47122 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.findMethod0(ReferenceBinding, char[], TypeBinding[], InvocationSite, boolean) 47122 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.findMethod(ReferenceBinding, char[], TypeBinding[], InvocationSite, boolean) 47122 MethodBinding org.eclipse.jdt.internal.compiler.lookup.Scope.getImplicitMethod(char[], TypeBinding[], InvocationSite) 47122 TypeBinding org.eclipse.jdt.internal.compiler.ast.MessageSend.findMethodBinding(BlockScope) 47122 TypeBinding org.eclipse.jdt.internal.compiler.ast.MessageSend.resolveType(BlockScope) 47122 void org.eclipse.jdt.internal.compiler.ast.Expression.resolve(BlockScope) 47122 void org.eclipse.jdt.internal.compiler.ast.AbstractMethodDeclaration.resolveStatements() 47122 void org.eclipse.jdt.internal.compiler.ast.MethodDeclaration.resolveStatements() 47122 void org.eclipse.jdt.internal.compiler.ast.AbstractMethodDeclaration.resolve(ClassScope) 47122 void org.eclipse.jdt.internal.compiler.ast.TypeDeclaration.resolve() 47122 void org.eclipse.jdt.internal.compiler.ast.TypeDeclaration.resolve(CompilationUnitScope) 47122 void org.eclipse.jdt.internal.compiler.ast.CompilationUnitDeclaration.resolve() 47122 CompilationUnitDeclaration org.eclipse.jdt.core.dom.CompilationUnitResolver.resolve(CompilationUnitDeclaration, ICompilationUnit, NodeSearcher, boolean, boolean, boolean) 17834 CompilationUnitDeclaration org.eclipse.jdt.internal.compiler.Compiler.resolve(CompilationUnitDeclaration, ICompilationUnit, boolean, boolean, boolean) 17191 void org.eclipse.jdt.internal.compiler.Compiler.process(CompilationUnitDeclaration, int) 12097 Let me know if you need any additional information.
Created attachment 277655 [details] visualvm snapshot when compiling Test2 from comment 4 with 6 invocations of f(T)
Created attachment 277656 [details] Trace of BoundSet for Test2 from comment 4 with 1 invocation of f(T)
Created attachment 277657 [details] Trace of incorporation for Test2 from comment 4 with 2 invocations of f(T)
Created attachment 277658 [details] Trace of BoundSet for Test2 from comment 4 with 3 invocations of f(T)
tl;dr/conclusion ---------------- This bug seems to be a reincarnation of bug 430404 which has status verified wontfix: BoundSet.incorporate(InferenceContext18,TypeBound[],TypeBound[]) performs a pair-wise comparison of all elements of the passed arrays and these arrays can be quite huge. So performance improvements might be found by either reducing the size of the arrays or avoiding pair-wise comparisons. I'll try stuff in these two directions if no one else comes up with better alternatives :-). https://bugs.eclipse.org/bugs/show_bug.cgi?id=430404#c13 has an idea for a solution. Maybe some form of indexing (e.g. by inference variable) would also help avoid pair-wise comparisons. at length --------- I'm also reporting how I arrived at the conclusion so others can verify them. I welcome that, but am ok if that happens later (or not) since I guess many are busy with the 2019-03 release (thanks for that!). Thanks, Lukas, for the reduced Test2 example program from comment #4! (And also for pointing out performance issues for quite some time!) Rough Performance ----------------- I also looked at how the compiler behaves for the Test2 program. Like Lukas, I created variants differed by the number of invocations of f(T) by commenting some of these invocations. All numbers are milliseconds. The code was compiled 6 times in a loop. 10 invocations: 6556, 4533, 3920, 3941, 3934, 4610 9 invocations: 3206, 1270, 998, 912, 950, 892 8 invocations: 2076, 900, 615, 479, 384, 511 7 invocations: 1802, 520, 467, 238, 414, 340 6 invocations: 2165, 331, 308, 357, 244, 231 5 invocations: 1684, 306, 364, 303, 191, 324 ... 2 invocations: 2009, 346, 366, 214, 268, 182 1 invocation: 1885, 418, 253, 296, 348, 253 I.e. complexity seems to be > O(n). Profiling --------- I then used VisualVM to perform CPU profiling for the org.eclipse.jdt.internal.compiler.lookup package for variants of Test2 with 1 to 6 invocations of f(T). See attachment 277655 [details] for a the VisualVM snapshot for one compiler run for the variant with 6 calls. For 6 calls, there are the following top 10 hotspots by self-time (self-time and invocations are shown) 1. 84ms 58,505x ConstraintTypeFormula.reduceTypeEquality(...) 2. 47ms 128,563x TypeBound.equals(Object) 3. 44ms 323,853x TypeBinding.equalsEquals(...) 4. 36ms 58,612x BoundSet.reduceOneConstraint(...) 5. 29ms 102x BoundSet.incorporate(InferenceContext18, TypeBound[], TypeBound[]) 6. 28ms 67,094x String.charAt(int) 7. 26ms 38,663x BoundSet.addBound(...) 8. 25ms 55,449x ReferenceBinding.isProperType(boolean) 9. 21ms 58,593x ConstraintTypeFormula.reduce(...) 10. 16ms 18,737x HashMap$TreeNode.find(int, Object, Class) I.e. there are methods within the compiler implementation that are invoked *very* often and these methods are among the "hottest". Looking at the forward calls (showing total time in ms, the fraction of it in % and invocation count below) in the dominant "Compiler Processing Task" thread for Test 2 with 6 calls, which VisualVM sorts by total time (descending), there is a first branch in PGMB.computeCompatibleMethod(...) that invokes both IC18.solve(boolean) and IC18.inferInvocationType(...). The latter indirectly invokes IC18.solve(boolean), though, spending almost all computation there: ParameterizedGenericMethodBinding.computeCompatibleMethod18(...) 1,574ms 97% 8x InferenceContext18.solve(boolean) 861ms 53% 8x InferenceContext18.inferInvocationType(...) 632ms 39% 1x InferenceContext18.solve() 611ms 37% 1x InferenceContext18.solve(boolean) 611ms 37% 1x Hence I continued analysis for the first invocation of IC18.solve(boolean) from within PGMB.computeCompatibleMethod(...) only (invocations with negligible durations are omitted): InferenceContext18.solve(boolean) 861ms 53% 8x InferenceContext18.resolve(...) 842ms 52% 8x BoundSet.incorporate(InferenceContext18) 793ms 48% 18x BoundSet.incorporate(InferenceContext18, TypeBound[], TypeBound[]) 792ms 48% 60x BoundSet.reduceOneConstraint(...) 531ms 32% 5,136x BoundSet.combineSameSame(...) 145ms 9% 6,876x ConstraintTypeFormula.equalsEquals(...) 67ms 4% 21,796x BoundSet.combineSameSubSuper(...) 27ms 1% 2,100x One can see that while BoundSet.incorporate(InferenceContext18, TypeBound[], TypeBound[]) is invoked only 60 times, the four methods it invokes are invoked way more often, so this method could be a source of above-linear time complexity. Looking at the code, it contains a nested loop over arrays of type bounds. It will be interesting to find out how large these arrays are. Looking back at the hotspots, the forwards calls from BoundSet.incorporate(IC18, TB[], TB[]) only explain invocations of two hot methods: 4. 36ms 58,612x BoundSet.reduceOneConstraint(...) 5. 29ms 102x BoundSet.incorporate(...) I assume that the following hot methods are too low a level to analyze further: 6. 28ms 67,094x String.charAt(int) 10. 16ms 18,737x HashMap$TreeNode.find(int, Object, Class) The other hot methods might be interesting when looking at the reverse calls provided by VisualVM to figure out which other methods invoke them: 1. 84ms 58,505x ConstraintTypeFormula.reduceTypeEquality(...) is invoked by CTF.reduce(...), see below 2. 47ms 128,563x TypeBound.equals(Object) is mainly invoked by BoundSet.addBound(...), see below 3. 44ms 323,853x TypeBinding.equalsEquals(...) is mainly invoked by TypeBound.equals(Object), see above, and ConstraintTypeFormula.equalsEquals(...) already mentioned in the forward calls above 7. 26ms 38,663x BoundSet.addBound(...) is mainly invoked by BoundSet.reduceOneConstraint(...) already mentioned in the forward calls above 8. 25ms 55,449x ReferenceBinding.isProperType(boolean) is very often invoked indirectly by the methods mentioned in the forward calls above 9. 21ms 58,593x ConstraintTypeFormula.reduce(...) is mainly invoked by BoundSet.reduceOneConstraint(...) already mentioned in the forward calls above So the forward calls made by BoundSet.incorporate(IC18, TB[], TB[]) contained (indirect) invocations of the top 10 hot methods and the method contains a nested loop over arrays which might lead to the above-linear computational complexity. I.e. BoundSet.incorporate(IC18, TB[], TB[]) might be the sole source of the >O(n) complexity observed. "Log Tracing" ------------- I then added print statements to get debug output while compiling the variants with different numbers of invocations of f(T) to figure out how large the arrays passed to BoundSet.incorporate(IC18, TB[], TB[]) are and how quickly they grow. Below numbers are the maxima for the lengths of the arrays "first" and "next" passed to BS.incorporate(IC18, TB[], TB[]) and the maximum products of these lengths that occur during a single compiler run for each variant. invocations, first.length <=, next.length <=, first.length*next.length <= 10, 561, 513, 287,793 9, 300, 257, 77,100 ... 3, 18, 5, 100 2, 11, 3, 49 1, 5, 4, 16 I.e. the input arrays grow quite large, as does the products of their lengths, also confirming >O(n) complexity. I then looked at git blame (maybe a bit late ...): The current implementation of BoundSet.incorporate(...) was implemented for bug 442245 where the previous implementation of this method did not complete. It was noted in https://bugs.eclipse.org/bugs/show_bug.cgi?id=442245#c20 that the complexity is now "O(2MN) where M is the size of new bounds added and N is set of all bounds". Further optimization was deferred to bug 430404 but was not actually performed. In https://bugs.eclipse.org/bugs/show_bug.cgi?id=430404#c13 Srikanth Sankaran suggested to move from pair-wise incorporation to mass-incorporation to reduce the number of intermediate type bounds that get generated. So to avoid the (impact of the) above-linear complexity, one could (A) reduce input size or (B) avoid full (pair-wise) execution of nested loop. Because I have no idea what is actually happening, I added more debug output and compiled variants of Test2 with 1, 2 and 3 calls of f(T) - see attachment 277656 [details], attachment 277657 [details], and attachment 277658 [details]. Some observations: * The number of invocations of IC18.resolve(IV[]) - that eventually invokes BS.incorporate(...) grows linearly only * For BoundSet.incorporate(IC18,TB[] first, TB[] next) * first and next, individually, contain no duplicates * BoundSet.incorporate(IC18) contains a line "if (!incorporate(context, freshBounds, freshBounds))" so at times first==next, i.e. every element is duplicated for that call. Given that incorporate(IC18,first,next) internally performs a swap to do both first[i] vs. next[j] and next[j] vs. first[i], this might be a source for a minor optimization. * The final number of incorporated bounds passed to BS.incorporate(IC18,TB[],TB[]) grows with > O(n) for n being the number of invocations of f(T): 5 invocations: 40 type bounds 4 invocations: 27 type bounds 3 invocations: 18 type bounds 2 invocations: 11 type bounds 1 invocation: 5 type bounds * In the compilation of the variant with 3 invocations of f(T) it can be seen that many intermediate type bounds are created for R#6: Dependency R#6 = R3<T1#3,T2#4,T3#5>, Dependency R#6 = R3<T1#3,T2#4,java.lang.Integer>, Dependency R#6 = R3<T1#3,java.lang.Integer,T3#5>, Dependency R#6 = R3<T1#3,java.lang.Integer,java.lang.Integer>, Dependency R#6 = R3<java.lang.Integer,T2#4,T3#5>, Dependency R#6 = R3<java.lang.Integer,T2#4,java.lang.Integer>, Dependency R#6 = R3<java.lang.Integer,java.lang.Integer,T3#5>, TypeBound R#6 = R3<java.lang.Integer,java.lang.Integer,java.lang.Integer> Looking at the trace this seems to happen because the inference variables are applied one after the other. The proposal of Srikanth Sankaran https://bugs.eclipse.org/bugs/show_bug.cgi?id=430404#c13 to apply the inference variables in one run might help reduce the number of type bounds and also the number of times the compiler iterates over them. I'll continue in the directions mentioned in the beginning.
I prepared a commit and would like to push it to Gerrit. I pulled and merged master a couple of days before, though. Now when I try to push to Gerrit, Gerrit complains that I should sign off this commit. What's the best way to sign off a commit that is not the last one?
(In reply to Sebastian Lohmeier from comment #10) > I prepared a commit and would like to push it to Gerrit. I pulled and merged > master a couple of days before, though. Now when I try to push to Gerrit, > Gerrit complains that I should sign off this commit. What's the best way to > sign off a commit that is not the last one? Don't merge, but rebase. (Or, as you have already merged, just reset the master to your commit, then rebase on origin/master) Then just amend your commit (in the git staging view, click on the little icon with the icon in the commit message section) without changing anything than the commit message. The sign-off can be easily added by clicking the button with the pen (next to the amend button )
(In reply to Till Brychcy from comment #11) > [...] click on the little > icon with the icon [...] Should have been "... click on the little icon with the _arrow_ ..."
New Gerrit change created: https://git.eclipse.org/r/139807
Thanks for your help, Till! I worked out an optimization along the lines of Srikanth Sankaran's proposal https://bugs.eclipse.org/bugs/show_bug.cgi?id=430404#c13 . Instead of incorporating the type arguments of parameterized depedencies one by one, they are incorporated at once - but only if there are proper types for all inference variables in all type arguments of a parameterized dependency. I'd appreciate if the attached Gerrit gets reviewed soon :-). The existing tests helped a lot! I also added two more tests to ensure a roughly linear time complexity of the solution. I'd be especially happy for comments on the tests, e.g.: * Is there a better class to put the test methods into? * Should the tests be put into the performance tests project instead? If so: into which class? I did not run the existing performance tests. Can they be easily run locally? It would be interesting to see if the optimization affects the non-optimized cases negatively. Is there a history of performance data available from Jenkins? Is there anything special about building the org.eclipse.jdt.core plug-in locally or can I just build it using mvn clean verify and install it in my Eclipse instance? Thanks!
I found a case for which my previous modification of InferenceContext18.resolve(...) yielts a NullPointerException during byte code generation. I therefore updated the Gerrit change, keeping only the modification of BoundSet which still solves the performance problem that this issue is about.
I'm slightly alerted by the approaching deadline for 2019-06 M2 and would like to raise awareness of this issue again and would appreciate a review. After fixing this issue, I'm currently starting Eclipse from Eclipse to be able to benefit from the improvements that I've made, but the Tycho builds in my build pipeline do (of course) use an old version of jdt that is still super slow at compiling these complex generics. I am therefore highly interested in this issue being fixed very soon so it makes its way into Tycho eventually. Since the problem covered in this issue (and its predecessor 430404) is over 5 years old and covers a complex case of a basic feature of Java, I hope everybody agrees that the proposed solution - if agreed to fit / made fit - should make it into the 2019-06 release and committers are jointly working towards that goal - also to encourage further contributions. Thank you!
Sorry, I was away from type inference for a visit in bug 546352, so this complex change will not make it into M2, but M3 should be feasible.
@Sebastian, first of all: compliments! It's been a while since anybody dove into type inference as deeply as you are doing here. Some highlevel questions regarding the strategy: Are you aware that incorporation actually serves two opposite purposes? (1) Find solutions by instantiating inference variables (indirectly via new constraints, then bounds) (2) Find contradictions leading to failure of type inference To me it looks like the proposed change has a bias towards (1), so my question is: can you demonstrate that all contradictions contained in a bound set are actually discovered? (see all the cases where ConstraintFormula.reduce() answers ReductionResult.FALSE). I was first alerted in this direction when I saw some "or" logic in both isSeenParameterizedDependency() and incorporateIntoParameterizedDependencyIfAllArgumentsAreProperTypes() (first try boundI, else boundJ). In particular, I don't see how isSeenParameterizedDependency() for one bound allows us to skip the other bound. Perhaps boundS already has a solution (that's what isSeen.. may be telling us), but perhaps combining boundS with boundT reveals the incompatibility we need to know about? Next I wonder how the change impacts the performance of "normal"/"simple" programs, i.e., those where performance is fine already today. The change incurs some constant efforts, which obviously pays off in complex cases, but it would not be prudent to penalize the millions of lines that do not have this problem. I first idea about fine tuning: doesn't getProperTypes() basically do the same as if we where asking BoundSet.getInstantiation() (and placing the result into a Map<InferenceVariable,TypeBinding> instead of using TypeBounds downstream)? Can you make any statements about the simple-case performance? Once general questions are settled, and we go into polish phase, I'll ask you to remove unused parameters (like the 'context' parameter you are passing through several layers :) ). Also a trivial method like isSeenParameterizedDependency() doesn't add any value, IMHO. I also dropped a specific/local question into the gerrit.
Thanks for reviewing, Stephan! An initial remark about (my) human memory: I kind of enjoy reasoning about code, but >= 1 month after writing it, it gets quite hard to recall the reasoning I had in mind when writing the code. So if it is possible to start reviewing such code earlier, that would make reasoning and contributing a lot easier. (In reply to Stephan Herrmann from comment #18) > Some highlevel questions regarding the strategy: > > Are you aware that incorporation actually serves two opposite purposes? > (1) Find solutions by instantiating inference variables > (indirectly via new constraints, then bounds) > (2) Find contradictions leading to failure of type inference > > To me it looks like the proposed change has a bias towards (1), so my > question is: can you demonstrate that all contradictions contained in a > bound set are actually discovered? (see all the cases where > ConstraintFormula.reduce() answers ReductionResult.FALSE). Yes, it's true that I focused on finding new instantiations. However, I tried to create a minimal change. My assumption is that (2), i.e. reduction, happens via the BoundSet.reduceOneConstraint(...) invocations within BoundSet.incorporate(IC18,TB[],TB[]). Because - in incorporate(...) - I only modified code before the reduceOneConstraint(...) invocations, I merely modify the input to these invocations but I do not skip any of these invocations. The constraints that are generated after the optimization are the same as the final constraint that was generated by the previous code - the optimization omits the intermediate constraints. E.g. the following constraints were generated by the unoptimized code: Dependency R#6 = R3<T1#3,T2#4,T3#5>, Dependency R#6 = R3<T1#3,T2#4,java.lang.Integer>, Dependency R#6 = R3<T1#3,java.lang.Integer,T3#5>, Dependency R#6 = R3<T1#3,java.lang.Integer,java.lang.Integer>, Dependency R#6 = R3<java.lang.Integer,T2#4,T3#5>, Dependency R#6 = R3<java.lang.Integer,T2#4,java.lang.Integer>, Dependency R#6 = R3<java.lang.Integer,java.lang.Integer,T3#5>, TypeBound R#6 = R3<java.lang.Integer,java.lang.Integer,java.lang.Integer> The optimized code only generates the final constraint from above, namely TypeBound R#6 = R3<java.lang.Integer,java.lang.Integer,java.lang.Integer> As long as all contradictions appear in the final constraint, they should be uncovered by the optimized code. I recall that during development some of the existing tests were failing. Among them were tests that expected compiler errors to be generated due to unmet constraints. Do you know which of the existing tests test such errors? > I was first alerted in this direction when I saw some "or" logic in both > isSeenParameterizedDependency() and > incorporateIntoParameterizedDependencyIfAllArgumentsAreProperTypes() (first > try boundI, else boundJ). I'll try to explain. These methods are overloaded: they either take 1 or 2 bounds (I assume that you saw that, I just need it to structure my argument). The variants of isSeen...(...) and incorporateInto...(...) with 1 bound are invoked from combineSameSubSuper(...) and from the variants with 2 bounds. The optimization generally operates on a single bound: it checks whether it is a parameterized dependency - if that is the case and there are proper types for all type parameters, it incorporates all type arguments. While combineSameSubSuper(...) receives 2 bounds (boundS and boundT), only boundT is used for isSeen...(...) et al. because that is the bound that does not use ReductionResult.SAME. The parameter boundS of combineSameSubSuper(...), which has ReductionResult.SAME, is not passed to isSeen...(...) because if it is a parameterized dependency for which at least one proper type argument is available, both would be passed to an invocation of combineSameSame(...) - which even happens earlier in the switch in incorporate(IC18,TB[],TB[]). The variants of isSeen(...) and incorporateInto...(...) with 2 bounds are only invoked from combineSameSame(...). Both bounds given to combineSameSame(...) can be parameterized dependencies so both are tried - in the same order - in the two-argument variants of isSeen...(...), isParameterizedDependency(...) and incorporateInto...(...). I'll go on about this in the next paragraph. > In particular, I don't see how isSeenParameterizedDependency() for one bound > allows us to skip the other bound. Perhaps boundS already has a solution > (that's what isSeen.. may be telling us), but perhaps combining boundS with > boundT reveals the incompatibility we need to know about? It could be that we have a differing understanding of the code. If that's the case the code should be rewritten to yield one understanding. BoundS and boundT are not combined - or to be more precise: they are not combined via the references passed to these methods. When isSeenParameterizedDependency(boundS) returns true, it will already have been tried to incorporate all available bounds (from first and next - that include the value in boundT) that qualify as arguments to the parameterized dependency boundS into boundS. Actually, if boundS is a parameterized dependency, isSeen...(...), isParameterizedDependency(...) and incorporateInto...(...), will not attempt to handle boundT. That will happen after boundS and boundT have been swapped - incorporate(IC18,TB[],TB[]) has a nested loop to perform pair-wise comparison and the pairs are also swapped. If you have ideas for structuring the optimization in a better way, please share them! > Next I wonder how the change impacts the performance of "normal"/"simple" > programs, i.e., those where performance is fine already today. > [...] > Can you make any statements about the simple-case performance? From working with the optimized version for the last couple of weeks I can only tell that the simple cases do not perform as badly as the complex cases did before, i.e. overall I see a grave performance improvement. I did not collect any numbers, though. Are there any existing performance tests for JDT that I could use? Are there any longer-term performance statistics for JDT to use for comparison? > Once general questions are settled, and we go into polish phase, I'll ask > you to remove unused parameters (like the 'context' parameter you are > passing through several layers :) ). Also a trivial method like > isSeenParameterizedDependency() doesn't add any value, IMHO. Oh, thanks for hinting at the redundant context parameter! :-) Yeah, I like to create 1 line methods. We can inline that one eventually, no problem.
(In reply to Sebastian Lohmeier from comment #19) > An initial remark about (my) human memory: I kind of enjoy reasoning about > code, but >= 1 month after writing it, it gets quite hard to recall the > reasoning I had in mind when writing the code. Be assured: if this code goes in, I will ask you similar questions 3 and 5 years from now ;p (this is one of the reasons why I put more explanations into bugzilla then some peers: to help my future-self to grok what I wrote...) (don't worry, I've taken the point you were making here) Serious answers will follow in a day or two.
Thought experiment (not sure if possible in code, please prove that it is not). Assume: combineSameSame() is invoked with boundS and boundT of such content that when combining both bounds a new constraint is generated, which would reduce to FALSE. (do we agree on the meaning of "combine"?) Look into the invocation isSeenParameterizedDependency(boundS, boundT, seenParameterizedDependencies) (bounds are now called boundI and boundJ :) ). Assume: isSeenParameterizedDependency(boundI, seenParameterizedDependencies) returns true, hence the method returns true without evaluating the second operand. At this point you haven't even looked at boundJ aka boundT. How do you know that it is compatible with boundI? Assume further that boundI and boundJ both contain the same inference variable T#0 in some position, which no longer occurs in the final bound created by simultaneous incorporation for all type parameters. Couldn't it happen, that the combination of boundI and boundJ is unsatisfiable, but after eliminating T#0 this incompatibility is no longer visible? So, question again: why is it OK to ignore boundJ inside isSeenParameterizedDependency(TypeBound, TypeBound, List<TypeBound>)? Here I'm not saying I've found a bug, I see a fair chance that you can prove my worries to be wrong / unfounded. Please do so :)
Putting aside my role as devil's advocate, I wonder if we couldn't even go one step further, but first let's go two steps back: A simple example of the game of contradictions could be: String <: T#0 T#0 <: S#1 S#1 <: Object only by carefully combining all three type bounds, we finally arrive at String <: Object which is FALSE. Once we have SAME bounds (aka instantiations), we could perhaps side step the complex rules of computing new constraints from each pair of type bounds. Instantiations should be amenable to simple substitution, in every position. So if we have s.t. like this: T#0 = Number T#0 <: S#1 R#2 <: G<T#0> Would we miss any opportunity to derive further (meaningful) constraints if we directly substitute to have instead the following? T#0 = Number Number <: S#1 R#2 <: G<Number> It's of course essential to keep the "T#0 = Number" bound, so that every future occurrence of T#0 in any type bound will be checked for compatibility with this instantiation. WDYT? How does this relate to the solution proposed in gerrit? I believe the gerrit is a special case of the above: if all ivar type arguments in a parameterized type have instantiations, then we can go to the fully instantiated type in one step. But we could use a similar short cut also in many other situations (e.g., if only a subset of ivar type arguments has an instantiation). The trick would be to perform substitution "in-place", i.e., to update existing type bounds. So instead of adding more bounds we would eliminate ivars from existing bounds, which should dramatically cut down the number of constraints created during incorporation. Unless I'm missing something, this more radical solution could also be argued in a much simpler way.
(In reply to Stephan Herrmann from comment #21) Maybe that's the problem with the way the optimization is implemented: it is not actually concerned with the combination of arbitrary arguments to combineSameSame(...) but rather handles cases where boundS or boundT is a parameterized dependency and then only indirectly combines the other given bound with the parameterized dependency when the other given bound is an instantiation of a parameter of the parameterized dependency. The question is then whether inserting an instantiation of a parameter into a parameterized dependency can create a contradiction. Can you come up with an example for such a contradiction? Regarding boundT not being handled in combineSameSame(...) when boundS makes the method return I'm tempted to repeat my reply to this question from comment 19 :-): >> Actually, if boundS is a parameterized dependency, isSeen...(...), >> isParameterizedDependency(...) and incorporateInto...(...), will not attempt >> to handle boundT. That will happen after boundS and boundT have been swapped >> - incorporate(IC18,TB[],TB[]) has a nested loop to perform pair-wise >> comparison and the pairs are also swapped. But I agree that the logic of combineSameSame(...) would better be easily comprehensible without looking at its invoking methods.
(In reply to Stephan Herrmann from comment #22) > Once we have SAME bounds (aka instantiations), we could perhaps side step > the complex rules of computing new constraints from each pair of type > bounds. Instantiations should be amenable to simple substitution, in every > position. > > It's of course essential to keep the "T#0 = Number" bound, so that every > future occurrence of T#0 in any type bound will be checked for compatibility > with this instantiation. > > WDYT? Yup, that sounds plausible. (Writing with a weak brain at 10:45 pm after thinking about comment 21 and comment 22 for a while.) > The trick would be to perform substitution "in-place", i.e., to update > existing type bounds. So instead of adding more bounds we would eliminate > ivars from existing bounds, which should dramatically cut down the number of > constraints created during incorporation. Oh yeah, that's a great idea! Is that safe? I.e. are no type bounds shared between bound sets or are at least bound sets not shared between other objects (so type bounds could be replaced in bound sets)? Can you recall whether it was a deliberate decision to keep the old type bounds from before instantiation after instantiation was performed? If you cannot easily think of such a case and mutating type bounds is fine, I volunteer to try out this option and see what the tests say about it. > Unless I'm missing something, this more radical solution could also be > argued in a much simpler way. I agree! It would fit way better with the existing logic of combineSameSame(...) and combineSameSubSuper(...).
(In reply to Sebastian Lohmeier from comment #24) > (In reply to Stephan Herrmann from comment #22) > > Once we have SAME bounds (aka instantiations), we could perhaps side step > > the complex rules of computing new constraints from each pair of type > > bounds. Instantiations should be amenable to simple substitution, in every > > position. > > > > It's of course essential to keep the "T#0 = Number" bound, so that every > > future occurrence of T#0 in any type bound will be checked for compatibility > > with this instantiation. > > > > WDYT? > > Yup, that sounds plausible. (Writing with a weak brain at 10:45 pm after > thinking about comment 21 and comment 22 for a while.) > > > The trick would be to perform substitution "in-place", i.e., to update > > existing type bounds. So instead of adding more bounds we would eliminate > > ivars from existing bounds, which should dramatically cut down the number of > > constraints created during incorporation. > > Oh yeah, that's a great idea! > > Is that safe? I.e. are no type bounds shared between bound sets or are at > least bound sets not shared between other objects (so type bounds could be > replaced in bound sets)? Now that you're asking: a literal "in-place" modification might indeed cause trouble. See that we have method copy() to create various snapshots (as semi-shallow copies). Working on a copy should never affect the original. So, the replacement would require a bit more leg work ... > Can you recall whether it was a deliberate decision to keep the old type > bounds from before instantiation after instantiation was performed? This part is very close to JLS, and JLS only speaks of adding bounds, never of removing :) > If you > cannot easily think of such a case and mutating type bounds is fine, I > volunteer to try out this option and see what the tests say about it. Mh, what seemed easy at the conceptual level, still needs a good technical design. I guess instead of in-place update, replacing a TypeBound with a more-instantiated copy is the best option. Since ThreeSets *is* actually copied during BoundSet.copy(), this guy can be safely updated. When replacing a TypeBound also fields (un)incorporatedBounds need to be updated. Another question is: when to perform this substitution. E.g.: we could do the following after each iteration of incorporate: collect all instantiated ivars to create an InferenceSubstitution. Iterate all bounds to see if this substitution modifies any types, if so replace the old bound with a more-instantiated bound. Or: whenever an ivar is instantiated, find all affected type bounds and replace them. Or ... If you have an idea to approach this experiment this would be very welcome!
Let me ask: did my recent comments discourage you, or do you accept the new challenge? :) If needed I could spend a bit of time on experiments during the weekend, but obviously there's plenty of other bugs crying to be fixed ... Or should we focus on the current patch (for now) and just close up the discussion of why it should be safe?
(In reply to Stephan Herrmann from comment #26) Sorry, I was at a conference and we decided to party instead of reading e-mails in the evening :-). I prefer the new approach you proposed over the existing patch. I'll give it a try tomorrow and am going to report on the outcomes/get back with questions. I can also continue working on it during the weekend so you can focus on the other open issues :-).
I looked a bit around in the code and thought about the two options that you outlined in comment 25: ##### option "in-iteration": "after each iteration of incorporate: collect all instantiated ivars to create an InferenceSubstitution. Iterate all bounds to see if this substitution modifies any types, if so replace the old bound with a more-instantiated bound." I'd prefer to do this in BS.incorporate(IC18) instead of BS.incorporate(IC18,TB[],TB[]) because the values passed to BS.incorporate(IC18,TB[],TB[]) are hard to update because of the nested loop over them. BS.incorporate(IC18) on the other hand does not iterate over the values that are updated. I'll try to use BoundSet.unincorporatedBounds to find (new) instantiated inference variables - only the bounds in there are candidates for new instantiated inference variables. Substitution would need to be performed at the beginning of the while loop, because IC18.resolve(...) might already have added uninstantiated bounds before it invokes BS.incorporate(IC18). Performing substituion in BS.incorporate(IC18) instead of BS.incorporate(IC18,TB[],TB[]) should be fine. There might be multiple type bounds created in multiple interations of BS.incorporate(IC18,TB[],TB[]). It will be interesting to create a test case where different instantiations of the same IV are created. Substitution should not attempt to substitute them into each other because I guess that would miss a chance to detect a contradiction. So the new substitution method in BoundSet ("substituteUsesOfInstantiations" might be a good name) would 1. identify those bounds in BoundSet.uninstantiatedBounds that instantiate IVs 2. Perform substitution on the type bounds in BoundSet.instantiatedBounds and BoundSet.boundsPerVariable and add new bounds to BoundSet.mostRecentBounds as well (boundsPerVariable should contain empty sets for the instaniated inference variables afterwards) 3. leave BoundSet.uninstantiatedBounds unchanged so the instantiations are recorded for future incorporation (although that should not be necessary because instantiated IVs do not contain any other type variables and all occurrences of the instantiated IV have been replaced) ##### option "in-add": "whenever an ivar is instantiated, find all affected type bounds and replace them." BoundSet.addBound(...) already checks whether a new bound is an instantiation and invokes ThreeSets.setInstantiation(...). So adding the substitution to this method would be suitable because instantiation-related logic would be locally close then. BS.addBound(...) is also invoked from IC18.resolve(...), so only one spot is required to handle instantiations coming from there. There are problems though: the name BS.addBound(...) does not really hint at the fact that other bounds are replaced by adding a bound, also addBound would need to update the first, next, boundI and boundJ variables in BoundSet.incorporate(IC18,TB[],TB[]) would be very unexpected to readers of the code and not elegantly implementable. So I'm deferring this option. So I'll proceed with programming the first option tomorrow. What do you think?
Good & bad news: I implemented the substitution of instantiated inference variables by their proper types, but this is not sufficient to solve the combinatorial explosion for generic types because generic types may have type arguments that are resolved to proper types in more than one step and hence incorporation will still create further type bounds. In the Gerrit patch this is the case for GenericTypeTest.testBug543480WithSameSubSuperOptimization() where there are type bounds Dependency E#2 :> Type1<T1#3,T2#4> TypeBound T1#3 = T1 TypeBound T2#4 = T2 I.e. even with substitution of instantiated IVs it is still necessary to defer incorporation into parameterized dependencies until instantiations of all type arguments are available. I'll review the solution from the Gerrit patch and will try to rewrite it so it better fits with the current implementation of BS.combineSameSame(...) and BS.combineSameSubSuper(...) and to avoid hiding other incorporations.
Thanks for keeping me posted. Seeing that the new experiment is not sufficient indicates that I probably haven't grasped the full story. Since M3 is closing now, and big/risky changes should not be done in the release-candidate phase I propose we postpone this to 4.13 (September) - which doesn't mean to stop now, quite the contrary: if we steadily converge on an agreement, then it would be good to release this *early* during 4.13 to enable some more testing before release. In case you are saying you are abandoning the current experiment, could you please upload it to a fresh gerrit anyway? I would still like to observe the remaining problem you saw. thanks.
New Gerrit change created: https://git.eclipse.org/r/142458
Jupp, moving to 4.13 is fine with me for the reasons you give. I uploaded my implementation trial for the new approach to https://git.eclipse.org/r/#/c/142458/ so you can have a look. I managed to get back to my original optimization and refactor the code so I'm not hijacking BS.combineSameSame(...) and BS.combineSameSubSuper(...) in unforseen ways anymore. There are two test failures in GenericTypeTest with this variant also that I'll analyze in the coming days and let you know of the results.
(In reply to Sebastian Lohmeier from comment #32) > Jupp, moving to 4.13 is fine with me for the reasons you give. I uploaded my > implementation trial for the new approach to > https://git.eclipse.org/r/#/c/142458/ so you can have a look. Thanks. I'll abort that build once it starts, because I need another patch in that queue built, will re-trigger later. > I managed to get back to my original optimization and refactor the code so > I'm not hijacking BS.combineSameSame(...) and BS.combineSameSubSuper(...) in > unforseen ways anymore. There are two test failures in GenericTypeTest with > this variant also that I'll analyze in the coming days and let you know of > the results. I'm looking forward to it.
(In reply to Sebastian Lohmeier from comment #23) > Regarding boundT not being handled in combineSameSame(...) when boundS makes > the method return I'm tempted to repeat my reply to this question from > comment 19 :-): That would mean we are stuck in our discussion. Let me try to illustrate why comment 19 didn't convince me: (In reply to Sebastian Lohmeier from comment #19) > Yes, it's true that I focused on finding new instantiations. However, I > tried to create a minimal change. My assumption is that (2), i.e. reduction, > happens via the BoundSet.reduceOneConstraint(...) invocations within > BoundSet.incorporate(IC18,TB[],TB[]). Because - in incorporate(...) - I only > modified code before the reduceOneConstraint(...) invocations, I merely > modify the input to these invocations but I do not skip any of these > invocations. I see code in your patch, which causes newConstraint to be null, to the effect that reduceOneConstraint() is skipped. My point is, if instead of skipping, newConstraint would result as a non-satisfiable constraint, then inference would need to fail. IOW, not creating a constraint can potentially cause an accept, where fail is mandated. > The constraints that are generated after the optimization are > the same as the final constraint that was generated by the previous code - > the optimization omits the intermediate constraints. E.g. the following > constraints were generated by the unoptimized code: For the example this is true. What I'm looking for is an explanation why this will *always* be the case. > > I was first alerted in this direction when I saw some "or" logic in both > > isSeenParameterizedDependency() and > > incorporateIntoParameterizedDependencyIfAllArgumentsAreProperTypes() (first > > try boundI, else boundJ). > > [...] > The variants of isSeen(...) and incorporateInto...(...) with 2 bounds are > only invoked from combineSameSame(...). Both bounds given to > combineSameSame(...) can be parameterized dependencies so both are tried - > in the same order - in the two-argument variants of isSeen...(...), > isParameterizedDependency(...) and incorporateInto...(...). "both are tried"? No. Look at isSeenParameterizedDependency(TypeBound boundI, TypeBound boundJ, List<TypeBound> seen...): If isSeenParameterizedDependency(boundI, seenParameterizedDependencies) == true then you haven't looked at boundJ but already return, causing combineSameSame() to return null. > > In particular, I don't see how isSeenParameterizedDependency() for one bound > > allows us to skip the other bound. Perhaps boundS already has a solution > > (that's what isSeen.. may be telling us), but perhaps combining boundS with > > boundT reveals the incompatibility we need to know about? So, you need to argue, how just from looking at boundI (aka boundS) you know that combining this bound with the other bound (boundj / boundT) can never produces a necessary constraint. I haven't yet looked at the effect of isParameterizedDependency() at the same level of detail. > It could be that we have a differing understanding of the code. If that's > the case the code should be rewritten to yield one understanding. BoundS and > boundT are not combined - or to be more precise: they are not combined via > the references passed to these methods. By "combine" I mean, that from looking at both bounds in combination a new constraint is generated. What does "combine" mean to you? > When > isSeenParameterizedDependency(boundS) returns true, it will already have > been tried to incorporate all available bounds (from first and next - that > include the value in boundT) that qualify as arguments to the parameterized > dependency boundS into boundS. I don't follow, please elaborate, why this should be the case.
Thanks Stephan, I'll reply tomorrow!
I added patch set 5 to https://git.eclipse.org/r/139807 - i.e. I adapted the original optimization by moving the optimization further down the call chain to eliminate the OR logic. I also removed the caching in seenParameterizedDependencies. Tests are green. To test the performance (also for the non-optimized cases) I ran 2x GenericTypeTest and JDTCoreTests without the two new performance tests that explicitly target the optimization. Results were GenericTypeTest unoptimized: 1. run: 345 sec, 2. run: 343 sec optimized: 1. run: 346 sec, 2. run: 345 sec JDTCoreTests unoptimized: 1. run: 4232 sec, 2. run: 4252 sec optimized: 1. run: 4251 sec, 2. run: 4199 sec Let me know if you have better ideas for evaluating the performance overhead of the optimized BoundSet for code that does not trigger the optimization. I also removed 1-line methods and the unused "context" parameter. I will now look into comment 34 to see if the argument applies to patch set 5, too and reply then.
(In reply to Stephan Herrmann from comment #34) Below I did not delete any of your points but instead state why I assume that they can be dropped because of the new code structure in patch set 5 in https://git.eclipse.org/r/139807 so we do not lose track of any of your points. > (In reply to Sebastian Lohmeier from comment #23) > > Regarding boundT not being handled in combineSameSame(...) when boundS makes > > the method return I'm tempted to repeat my reply to this question from > > comment 19 :-): > > That would mean we are stuck in our discussion. > > Let me try to illustrate why comment 19 didn't convince me: > > (In reply to Sebastian Lohmeier from comment #19) > > Yes, it's true that I focused on finding new instantiations. However, I > > tried to create a minimal change. My assumption is that (2), i.e. reduction, > > happens via the BoundSet.reduceOneConstraint(...) invocations within > > BoundSet.incorporate(IC18,TB[],TB[]). Because - in incorporate(...) - I only > > modified code before the reduceOneConstraint(...) invocations, I merely > > modify the input to these invocations but I do not skip any of these > > invocations. > > I see code in your patch, which causes newConstraint to be null, to the > effect that reduceOneConstraint() is skipped. > > My point is, if instead of skipping, newConstraint would result as a > non-satisfiable constraint, then inference would need to fail. IOW, not > creating a constraint can potentially cause an accept, where fail is > mandated. In patch set 5, there are the following cases in which null is returned to the effect that newConstraint is null: * combineWithProperTypes(...) returns null if the set of proper types for all of the IVs of the parameterized dependency is empty. This could be the case if the parameterized dependency has 0 inference variables on its right-hand side. If that were a valid parameterized dependency, incorporating nothing into it would not yield a new constraint. Hence null is returned instead of creating a new constraint. * incorporateIntoParameterizedDependencyIfAllArgumentsAreProperTypes(...) returns null, if at least one IV has no proper type yet. I discuss this case below. * The methods that collect the proper types for all IVs return null in various occasions but merely provide the all-or-nothing-logic that causes incorporateIntoParameterizedDependencyIfAllArgumentsAreProperTypes(...) to return either null or a ConstraintTypeFormula. > > The constraints that are generated after the optimization are > > the same as the final constraint that was generated by the previous code - > > the optimization omits the intermediate constraints. E.g. the following > > constraints were generated by the unoptimized code: > > For the example this is true. What I'm looking for is an explanation why > this will *always* be the case. The new code structure makes it easier to find an explanation why that will always be the case. I'll provide an explanation for combineSameSameWithProperType(...). The explanation for combineSameSubSuperWithProperType(...) should be analogous. The optimization applies to combineSameSameWithProperType(...) when boundT is a parameterized dependency. In patch set 5, the code that would have been applied previously follows after the optimized code: if (u.isProperType(true)) { // incorporate u=boundLeft.right into boundRight.right [...] } // do not incorporate, if u=boundLeft.right is not a proper type. return null; Initially, parameterized dependencies have only inference variables on their right-hand side. Before the optimization, only inference variables that have a proper type are incorporated into the parameterized dependency (or other type bounds with inference variables) - one by one. After the optimization, incorporation of proper types for IVs is postponed until all of proper types are available for all of those IVs are available. I do not see any way in which incorporation of a proper type of an IV into a parameterized dependency can lead to a contradiction. And I do not see why that would change through mass-incorporation. (There can of course be incorporation that involves the same IV in other dependencies that can cause contradictions.) What is different after the optimization is when only some IVs of a parameterized dependency have a proper type and others do not: with the optimization no IV will be replaced at all while before the optimization some IVs will have been replaced by proper types. This does not seem to have an effect though: Both with and without the optimization I get the error message "Type mismatch: cannot convert from Foo<Object,Integer,ArrayList<Integer>> to Foo<Integer,String,List<String>>" in the UI at "create(new ArrayList<Integer>())" on line 5 when editing the following code in an Eclipse instance started from the Eclipse with the modified compiler: 1: import java.util.ArrayList; 2: import java.util.List; 3: public class Foo<A, B, C extends List<B>> { 4: public static void foo() { 5: final Foo<Integer,String, List<String>> foo = create(new ArrayList<Integer>()); 6: } 7: public static <A, B, C extends List<B>> Foo<A, B, C> create(C c) { 8: return new Foo<>(); 9: } 10:} > > > I was first alerted in this direction when I saw some "or" logic in both > > > isSeenParameterizedDependency() and > > > incorporateIntoParameterizedDependencyIfAllArgumentsAreProperTypes() (first > > > try boundI, else boundJ). > > > > [...] > > The variants of isSeen(...) and incorporateInto...(...) with 2 bounds are > > only invoked from combineSameSame(...). Both bounds given to > > combineSameSame(...) can be parameterized dependencies so both are tried - > > in the same order - in the two-argument variants of isSeen...(...), > > isParameterizedDependency(...) and incorporateInto...(...). > > "both are tried"? > No. Look at isSeenParameterizedDependency(TypeBound boundI, TypeBound > boundJ, List<TypeBound> seen...): > > If isSeenParameterizedDependency(boundI, seenParameterizedDependencies) == > true then you haven't looked at boundJ but already return, causing > combineSameSame() to return null. Does not apply anymore with patch set 5 since isSeenParameterizedDependency(...) has been removed. > > > In particular, I don't see how isSeenParameterizedDependency() for one bound > > > allows us to skip the other bound. Perhaps boundS already has a solution > > > (that's what isSeen.. may be telling us), but perhaps combining boundS with > > > boundT reveals the incompatibility we need to know about? > > > So, you need to argue, how just from looking at boundI (aka boundS) you know > that combining this bound with the other bound (boundj / boundT) can never > produces a necessary constraint. > > I haven't yet looked at the effect of isParameterizedDependency() at the > same level of detail. Does not apply anymore with patch set 5 since isSeenParameterizedDependency(...) has been removed and because isParameterizedDependency(...) has no variant with a logical OR anymore. > > It could be that we have a differing understanding of the code. If that's > > the case the code should be rewritten to yield one understanding. BoundS and > > boundT are not combined - or to be more precise: they are not combined via > > the references passed to these methods. > > By "combine" I mean, that from looking at both bounds in combination a new > constraint is generated. What does "combine" mean to you? This point originated in comment 19 and was rooted in isSeenParameterizedDependency(...) skipping one of the two bounds. Since isSeenParameterizedDependency(...) and other spots with OR logic have been removed I can now agree on your understanding of "combine". > > When > > isSeenParameterizedDependency(boundS) returns true, it will already have > > been tried to incorporate all available bounds (from first and next - that > > include the value in boundT) that qualify as arguments to the parameterized > > dependency boundS into boundS. > > I don't follow, please elaborate, why this should be the case. Does not apply anymore with patch set 5 since isSeenParameterizedDependency(...) has been removed.
With patch set 5 and comment 37 (thanks Sebastian!) we have new chances of agreeing on the strategy. Since I was asked whether this could still make it into RC1: Do we have a volunteer committer for the additional code review (need s.o. with good understanding of JLS §18.3 and vicinity)? Otherwise I would rather spend my RC1 time on other bugs that are already scheduled for RC1.
(In reply to Stephan Herrmann from comment #38) > With patch set 5 and comment 37 (thanks Sebastian!) we have new chances of > agreeing on the strategy. Since I was asked whether this could still make it > into RC1: > > Do we have a volunteer committer for the additional code review (need s.o. > with good understanding of JLS §18.3 and vicinity)? > > Otherwise I would rather spend my RC1 time on other bugs that are already > scheduled for RC1. Let's target this for 4.13.
Now would be a good time for a vacation or a review :-) What do you think, Stephan? ;-)
Sorry, I was detained by bug 547181 (correctness beats performance). With that bug approaching resolution, I started to look back to this bug. Before I go deeper: where exactly should I look? https://git.eclipse.org/r/142458 is the one that felt easier to argue why it is correct, but that change causes regressions (some in GenericTypeTest and even more in GenericsRegressionTest_1_8). Did you have a look at a possible cause for those regressions? If a technical issue of how substitution / copying is done, how hard would it be to fix it? If you're confident that the change is technically sound, then this would be alarming, as it means that our argumentation is unsound. Or have you abandoned that idea altogether (why?) and only https://git.eclipse.org/r/139807 is on the table?
FWIW, the 'regression' in GenericTypeTest.test1142 led me to filing bug 549025
Yet another idea, if we are not able to totally dispel doubts about correctness, but tests are green and performance gain is evident, then we may want to think of a back door: use an 'undocumented' system property to disable the optimization. In that case, even if it introduces a regression in some special case we could ask users to disable the optimization for the dual benefit of easy checking if indeed the optimization is to blame and providing a workaround until we fixed it. How difficult would that be?
(In reply to Stephan Herrmann from comment #41) > [...] > Before I go deeper: where exactly should I look? > > https://git.eclipse.org/r/142458 is the one that felt easier to argue why it > is correct, but that change causes regressions (some in GenericTypeTest and > even more in GenericsRegressionTest_1_8). Did you have a look at a possible > cause for those regressions? If a technical issue of how substitution / > copying is done, how hard would it be to fix it? If you're confident that > the change is technically sound, then this would be alarming, as it means > that our argumentation is unsound. > > Or have you abandoned that idea altogether (why?) and only > https://git.eclipse.org/r/139807 is on the table? I abandoned https://git.eclipse.org/r/142458 so far because it is not able to cover all relevant cases - GenericTypeTest.testBug543480WithSameSubSuperOptimization() is red right now, see comment 29 . I.e. this implementation of our argument does not cover all cases. Because that problem is not fixed - and I did not find a way to fix it, I also did not look into the regressions (GenericTypeTest.test1142() and GenericTypeTest. test268798a() and those in GenericsRegressionTest1_8). Looking at comment 28 and comment 29, I can see that the implementation in https://git.eclipse.org/r/142458 is only one implementation of two different ideas. So there might be further implementations for both ideas. However, https://git.eclipse.org/r/139807 now has an implementation that removed the OR conditions as discussed in comments 37 and 38 - tests are green also. I'd therefore propose that you review https://git.eclipse.org/r/139807 . (In reply to Stephan Herrmann from comment #43) > Yet another idea, if we are not able to totally dispel doubts about > correctness, but tests are green and performance gain is evident, then we > may want to think of a back door: use an 'undocumented' system property to > disable the optimization. > [...] > How difficult would that be? That should be doable with little effort. Thanks!
I dropped a few comments in gerrit. Overall impression: I now think the optimization is "morally OK", even though we don't have a formal argument to back it in JLS terms. I'd be willing to release the change after these modifications: - change of assert utility in test - addition of a back door switch (see comment 43) - rebased and +1 from jenkins The "Polish" item in gerrit is optional / can be handled later as well. Note: tomorrow is last day of development for 4.13 M1.
Adjusted the target to 4.13 M3 but hope we can contribute the fix to SimRel already at M2.
*** Bug 549657 has been marked as a duplicate of this bug. ***
I'm sorry for the delay. I now replied to the comments in Gerrit and updated the Gerrit patch set according to comment 45. Please have a look, Stephan. Thanks!
Gerrit change https://git.eclipse.org/r/139807 was merged to [master]. Commit: http://git.eclipse.org/c/jdt/eclipse.jdt.core.git/commit/?id=372c6048cc1b21d8a4ceb948bf5eaecaa40576c9
(In reply to Eclipse Genie from comment #49) > Gerrit change https://git.eclipse.org/r/139807 was merged to [master]. > Commit: > http://git.eclipse.org/c/jdt/eclipse.jdt.core.git/commit/ > ?id=372c6048cc1b21d8a4ceb948bf5eaecaa40576c9 Released for 4.13 M3 Thanks, Sebastian, for your substantial effort.
Yay, I'm happy we fixed this! Thank you, Stephan and everybody who contributed along the way!
Verified for Eclipse 2019-09 (4.13) M3 with Build id: I20190820-1800 (In reply to Sebastian Lohmeier from comment #51) > Yay, I'm happy we fixed this! Thanks Sebastian for this great effort sustained across the releases! I am marking this as greatfix as well as noteworthy. >Thank you, Stephan and everybody who > contributed along the way! True! Thanks Stephan for the careful analysis and continous feedback through complation and thanks to all who contributed to this.
*** Bug 543100 has been marked as a duplicate of this bug. ***
The newly added tests are failing in our BETA builds: https://download.eclipse.org/eclipse/downloads/drops4/Y20190916-0900/testresults/html/org.eclipse.jdt.core.tests.compiler_ep413Y-unit-cen64-gtk3-java11_linux.gtk.x86_64_11.html They do pass locally on my machine. I haven't yet looked at the tests. Any possibility that this is due to lesser machines being used for our Y builds?
(In reply to Jay Arthanareeswaran from comment #54) > The newly added tests are failing in our BETA builds: > > https://download.eclipse.org/eclipse/downloads/drops4/Y20190916-0900/testresults/html/org.eclipse.jdt.core.tests.compiler_ep413Y-unit-cen64-gtk3-java11_linux.gtk.x86_64_11.html > > > They do pass locally on my machine. I haven't yet looked at the tests. Any > possibility that this is due to lesser machines being used for our Y builds? These are failing in our I builds as well: https://download.eclipse.org/eclipse/downloads/drops4/I20190916-1045/testResults.php
(In reply to Jay Arthanareeswaran from comment #55) > (In reply to Jay Arthanareeswaran from comment #54) > > The newly added tests are failing in our BETA builds: > > > > https://download.eclipse.org/eclipse/downloads/drops4/Y20190916-0900/testresults/html/org.eclipse.jdt.core.tests.compiler_ep413Y-unit-cen64-gtk3-java11_linux.gtk.x86_64_11.html > > > > > > They do pass locally on my machine. I haven't yet looked at the tests. Any > > possibility that this is due to lesser machines being used for our Y builds? > > These are failing in our I builds as well: > > https://download.eclipse.org/eclipse/downloads/drops4/I20190916-1045/ > testResults.php Message is: testBug543480BasedOnTest2FromComment4ToSameSameOptimization - 11 Failure 192 should be less than 10.0x the compile time of 11 Let's keep an eye on this. If failures appear frequently, we will have to further relax the threshold.
Hm, collecting some of the failures: * 415 should be less than 10.0x the compile time of 11 [1] * 192 should be less than 10.0x the compile time of 11 [2] * 51 should be less than 10.0x the compile time of 5 [3] the factor would have to be increased from 10 to up to 40. That's more than I expected. I'll have a look at the test reports within the next days. Either the optimization is ineffective or the performance cannot be tested on the test machines. [1] https://download.eclipse.org/eclipse/downloads/drops4/Y20190916-0900/testresults/html/org.eclipse.jdt.core.tests.compiler_ep413Y-unit-cen64-gtk3-java11_linux.gtk.x86_64_11.html [2] https://download.eclipse.org/eclipse/downloads/drops4/I20190916-1045/testresults/html/org.eclipse.jdt.core.tests.compiler_ep413I-unit-cen64-gtk3-java11_linux.gtk.x86_64_11.html#org.eclipse.jdt.core.tests.compiler.regression [3] https://download.eclipse.org/eclipse/downloads/drops4/I20190916-1045/testresults/html/org.eclipse.jdt.core.tests.compiler_ep413I-unit-cen64-gtk3-java12_linux.gtk.x86_64_12.html
The test failure did not occur again during I builds between I20190916-1800 and I20190921-1800. I'll have a look again next week.
(In reply to Sebastian Lohmeier from comment #58) > The test failure did not occur again during I builds between I20190916-1800 > and I20190921-1800. I'll have a look again next week. thanks!
The test failure *did* occur again twice during I builds between I20190922-1800 and I20190928-1800: for two builds on I20190928-1800 [1] [2]. I see a number of options: (1) Do nothing. + Keeps the test. - Flaky tests are annoying because they make it hard to interpret CI results. (2) Improve the error message to make clear the test failures are from a flaky performance test. + Keeps the test. + This will make it easier to interpret the test details. - This will still make it hard to interpret the summarized CI results that don't mention the failed test. (3) Increase the threshold, as Stephan suggested. + Keeps the test. - How high should we set the threshold then? Do we risk to miss a performance regression when the threshold is "too" high? (4) Add @Ignore to the tests or disable them otherwise in CI. + Keeps the test so it can be run locally by developers. - Tests that aren't run continuously cannot uncover regressions. (5) Remove the tests. This is actually my favourite option: I don't typically write time-based assertions in tests because they lead to flaky tests. I only did that here because I could not come up with a better approach. What I would have liked to assert is the number of TypeBounds created during type inference, but I guess I did not do that because I was not easily able to create a unit test for it that does not start with Java source and the tests that start with Java source don't provide access to the TypeBounds (that was my impression, at least). So I'd prefer to remove the flaky performance tests. The original commit message should still make it clear that the changes are performance-related and if one would like to test this again, the original commit would also have the tests available. What do you think? [1] https://download.eclipse.org/eclipse/downloads/drops4/I20190928-1800/testresults/html/org.eclipse.jdt.core.tests.compiler_ep414I-unit-cen64-gtk3-java11_linux.gtk.x86_64_11.html [2] https://download.eclipse.org/eclipse/downloads/drops4/I20190928-1800/testresults/html/org.eclipse.jdt.core.tests.compiler_ep414I-unit-cen64-gtk3-java12_linux.gtk.x86_64_12.html
(In reply to Sebastian Lohmeier from comment #60) > I see a number of options: > > (1) Do nothing. > + Keeps the test. > - Flaky tests are annoying because they make it hard to interpret CI results. > > (2) Improve the error message to make clear the test failures are from a > flaky performance test. > + Keeps the test. > + This will make it easier to interpret the test details. > - This will still make it hard to interpret the summarized CI results that > don't mention the failed test. > > (3) Increase the threshold, as Stephan suggested. > + Keeps the test. > - How high should we set the threshold then? Do we risk to miss a > performance regression when the threshold is "too" high? > > (4) Add @Ignore to the tests or disable them otherwise in CI. > + Keeps the test so it can be run locally by developers. > - Tests that aren't run continuously cannot uncover regressions. > > (5) Remove the tests. > > What do you think? I'm in favor of 3, and if not agreed by all, then 4. Tests failed again on Java 11 + 12 (but fine on 8), see 197 should be less than 10.0x the compile time of 7 https://download.eclipse.org/eclipse/downloads/drops4/I20191002-0100/testresults/html/org.eclipse.jdt.core.tests.compiler_ep414I-unit-cen64-gtk3-java11_linux.gtk.x86_64_11.html 51 should be less than 10.0x the compile time of 4 https://download.eclipse.org/eclipse/downloads/drops4/I20191002-0100/testresults/html/org.eclipse.jdt.core.tests.compiler_ep414I-unit-cen64-gtk3-java12_linux.gtk.x86_64_12.html
couple more ideas: Since we are observing fluctuations of speed in quick succession, can we reduce that noise by one or both of: - explicit System.gc() before each measurement - performing each compilation 10x in a loop and use some math to ignore outliers If that bears fruit, then we can happily keep the tests, perhaps still with slightly increased threshold. As a plan B I would suggest to add test-only API to indeed measure the number of bounds created, even during a full compilation.
New Gerrit change created: https://git.eclipse.org/r/150662
Thanks for your input, Andrey and Stephan! I followed Stephan's suggestion and now run GC, draw 10 samples, and ignore the 2 lowest and 2 highest compile times as they are potential outliers. If the test fails, averages and all numbers are contained in the error message so we get numbers to aid in tuning the tests. Please have a look at the Gerrit patch!
Please follow up on this with a new bug report.
Oh, yes: Bug 551899
