Bugzilla – Full Text Bug Listing
| Summary: | [1.8][inference][performance] Can we cut back on the bounds and constraints generated during inference ? | ||||||
|---|---|---|---|---|---|---|---|
| Product: | [Eclipse Project] JDT | Reporter: | Stephan Herrmann <stephan.herrmann> | ||||
| Component: | Core | Assignee: | Stephan Herrmann <stephan.herrmann> | ||||
| Status: | VERIFIED WONTFIX | QA Contact: | |||||
| Severity: | enhancement | ||||||
| Priority: | P3 | CC: | daniel.dietrich, jarthana, lukas.eder, register.eclipse, srikanth_sankaran | ||||
| Version: | 4.4 | ||||||
| Target Milestone: | 4.8 M6 | ||||||
| Hardware: | PC | ||||||
| OS: | Windows 7 | ||||||
| See Also: | https://bugs.eclipse.org/bugs/show_bug.cgi?id=543480 | ||||||
| Whiteboard: | |||||||
| Attachments: |
|
||||||
|
Description
Stephan Herrmann
Not necessary for 4.4, but some simple improvements may be applied time permitting. I'll work on this one for bug 442245. Can we also get rid of the T#1 <: j.l.O bounds ? What else ? (In reply to Srikanth Sankaran from comment #2) > I'll work on this one for bug 442245. > > Can we also get rid of the T#1 <: j.l.O bounds ? When you try that, please check with 18.1.3., which explicitly adds bounds αl <: Object :) We may have to ensure that each inference variable has at least one bound, not sure. > What else ? We should make sure that adding a redundant type bound does not cause another round of incorporation. Also note that comment 0 speaks of bounds *and* constraints. (In reply to Stephan Herrmann from comment #3) > We may have to ensure that each inference variable has at least one bound, > not sure. http://git.eclipse.org/c/jdt/eclipse.jdt.core.git/commit/?id=550a751ce1bc873d333fa63fec3308d2d2a04ec5 has some improvements in this area. Back to you Stephan for further work. Adjusted target to 4.5. We will use this bug for follow up performance improvements to https://bugs.eclipse.org/bugs/show_bug.cgi?id=442245 Test case is in GRT1_8: testBug442245 ATM, we take ~17 seconds to compile this. In that test case, I am observing several hundreds of thousands constraints being produced, reduced to bounds again in hundreds of thousands a huge majority of which are duplicates. We weed out duplicates by using a Set, but ThreeSets.addBound and its descendants is where 2/3 of the time is now. In https://bugs.eclipse.org/bugs/show_bug.cgi?id=442245, I have tuned the performance of incorporate() itself, we now need to see what we can do to cut the problem size. I don't know how easy/feasible it would be to when we come across a bound T#1 = T#2, to collapse both into a singularity (where they are not mapped directly to type parameters.) and eliminate all traces of one of them. (In reply to Stephan Herrmann from comment #3) > > Can we also get rid of the T#1 <: j.l.O bounds ? > > When you try that, please check with 18.1.3., which explicitly adds bounds > αl <: Object > :) The only side effect to that pedanticism(?)/pedantry(?) appears to be the need to insert a couple of three null guards. See http://git.eclipse.org/c/jdt/eclipse.jdt.core.git/commit/?id=550a751ce1bc873d333fa63fec3308d2d2a04ec5 > We should make sure that adding a redundant type bound does not cause > another round of incorporation. This is already done. Created attachment 247367 [details]
8000+ bound set elements
Are there any obvious categories begging for elimination ?
(In reply to Srikanth Sankaran from comment #5) > I don't know how easy/feasible it would be to when we come across a bound > T#1 = T#2, to collapse both into a singularity (where they are not mapped > directly to type parameters.) and eliminate all traces of one of them. I have been context switching between several bugs and got the information tangled up. This observation above is not pertinent to this bug. The huge majority of bounds on this bug seem to be of the form: Dependency R#1 :> test.Tuples.Tuple13<E1,T2#3,E3,T4#5,T5#6,E6,T7#8,T8#9,T9#10,T10#11,E11,E12,E13> and its variants with different substitutions. (In reply to Srikanth Sankaran from comment #6) > (In reply to Stephan Herrmann from comment #3) > > > > Can we also get rid of the T#1 <: j.l.O bounds ? > > > > When you try that, please check with 18.1.3., which explicitly adds bounds > > αl <: Object > > :) > > The only side effect to that pedanticism(?)/pedantry(?) appears to be the > need > to insert a couple of three null guards. > > See > http://git.eclipse.org/c/jdt/eclipse.jdt.core.git/commit/ > ?id=550a751ce1bc873d333fa63fec3308d2d2a04ec5 note to self: check if in addition to the technical need for null checks Resolution also needs to reinsert the j.l.O bounds to produce valid results in all cases. (In reply to Srikanth Sankaran from comment #6) > (In reply to Stephan Herrmann from comment #3) > > > > Can we also get rid of the T#1 <: j.l.O bounds ? > > > > When you try that, please check with 18.1.3., which explicitly adds bounds > > αl <: Object > > :) > > The only side effect to that pedanticism(?)/pedantry(?) appears to be the > need > to insert a couple of three null guards. > > See > http://git.eclipse.org/c/jdt/eclipse.jdt.core.git/commit/ > ?id=550a751ce1bc873d333fa63fec3308d2d2a04ec5 I just happened to look at the loop at InferenceContext18.java:1015 This might cause havoc if we neither assign zsj.lowerBound nor call zsj.setUpperBounds(). The j.l.O bound would protect us against this situation. When we no longer add that bound we must ensure initialization of CaptureBinding18 assigns all necessary fields (firstBound, superclass, superInterfaces), even without setUpperBounds(). Taking a look at the bounds in the attachment, it looks to me that javac is able to compile it super fast perhaps because they don't implement capture bound incorporation (18.3.2) exactly as per the spec. Recall that they create fresh inference variables only for wildcard type arguments in GA, while we create them for every argument in GA leading to combinatorial explosion. Stephan, if you agree, I can prepare a patch that aligns with what javac is doing. It should be a straightforward change that will eliminate lots of noise bounds. (In reply to Srikanth Sankaran from comment #11) > I can prepare a patch that aligns with what javac > is doing. It should be a straightforward change that will eliminate > lots of noise bounds. Nope, that is not it. For the problem method (where we produce 8000+ bounds), we have an instantiation for R1 very early on: TypeBound R#1 = test.Tuples.Tuple13<E1,E2,E3,E4,E5,E6,E7,E8,E9,E10,E11,E12,E13> I wonder if that would be a legitimate reason to not continue to generate dependencies of the form R#1 :> test.Tuples.Tuple13<E1,T2#3,E3,E4,E5,T6#7,E7,E8,T9#10,T10#11,T11#12,T12#13,E13> Could the new bound serve some useful purpose ? As an aside, the creation of so many bounds would directly result for any verbatim implementation. For faster solutions, we have to implement something different: 18.3.1: α = U and S <: T imply ‹S[α:=U] <: T[α:=U]› Instead of looking at pair wise, when we see a bound of the form: S <: T, we could hypothetically look for every instantiation in the bound set and mass incorporte them producing the minimal set of bounds that would account for every permutation of instantantiations. Not suggesting we do that, just jotting down my thoughts. Too much on my plate for 4.6. Bulk deferral to 4.7 Ran out of time for 4.7. Bulk move to 4.8. No specific actions could be derived from this. (In reply to Stephan Herrmann from comment #16) > No specific actions could be derived from this. Okay, let's close this. Verified for 4.8 M6. |