Complexity reduction when choosing the best inference leaf to be solved

[Maurizio Cimadamore]

On 12/10/17 20:04, Vicente Romero wrote:
> This is my interpretation of this problem and how I think we should 
> discuss if this interpretation is correct, or if there is a better 
> one, before considering optimizing the current implementation which 
> doesn't fit very well into any of these descriptions strategies.
I think your interpretation of the problem is correct. This is the dual 
of the max flow problem, with some variations (as you note). I'm not 
sure about the aggressive strategy you propose; it seems like it could 
get fooled quite easily if a flow with an high overall cost is 'hidden' 
behind a leaf with an initial very low cost. As per your point (2), yes 
it will typically be the case that the var to instantiate is not a leaf, 
which is why we try to come up with the best set of variables to 
instantiate eagerly - knowing that each (redundant) eager instantiation 
could potentially lead to spurious error messages.

That said, this part is outside the spec - as section 18.5.2.2 says this:

"1 A subset of constraints is selected in C, satisfying the property 
that, for each constraint, no input variable can influence an output 
variable of another constraint in C. The terms /input variable/ and 
/output variable/ are defined below. An inference variable α /can 
influence/ an inference variable β if α depends on the resolution of β 
(§18.4 
<https://docs.oracle.com/javase/specs/jls/se9/html/jls-18.html#jls-18.4>), 
or vice versa; or if there exists a third inference variable γ such that 
α can influence γ and γ can influence β.

2 The selected constraint(s) are removed from C.

3 The input variables α1, ..., αm of all the selected constraint(s) are 
resolved.""

Here javac is playing some tricks that are totally outside of the spec - 
note that the spec requires that all input inference variables in the 
node to be unstuck should be solved at once - but that's not what javac 
does - as javac calls solveAny to do the heuristic trick:

http://hg.openjdk.java.net/jdk10/master/file/tip/src/jdk.compiler/share/classes/com/sun/tools/javac/comp/DeferredAttr.java#l635

I think that, instead of investing resources on making these tricks more 
optimal, we should probably try to bring the compiler closer to what the 
spec has to say in this matter (or at least try and see what breaks, if 
anything).

Cheers
Maurizio





-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/compiler-dev/attachments/20171012/51cd2b55/attachment.html>