Complexity reduction when choosing the best inference leaf to be solved

[B. Blaser]

On 4 October 2017 at 01:03, Maurizio Cimadamore
<maurizio.cimadamore at oracle.com> wrote:
> Quick question on (3) - who is using that new 'map' ? Is the plan to replace
> the findNode linear scan with a map lookup? I believe that method is not
> even used inside javac (leftover from previous code which should be
> removed).

The loop in O(n*v) that I'm trying to improve is [loop], see the
replacement in the patch. Note that I removed "findNode()" since it
isn't used and which is replaced by the map if necessary.

> In any case, if the goal is to replace the findNode routine, I guess I'm a
> bit surprise that the data structure is a Map<Type, ArrayList<Node>> rather
> than a Map<Type, Node> - surely we cannot have the same inference variable
> belonging to more than one graph node? In other words, I'd expect the
> elements of conSubGraphHead.data to be disjoint.

That's what I thought, too. But with a "Map<Type, Node>", I was
surprised by a small set of failing tests because of more than one
node per variable. Is there any problem elsewhere?

> On (1) and (2), I'll have to check more closely, but as an high-level
> design, this BestLeafSolver is only called when there's a generic method
> call with one or more functional expressions and one of them is 'stuck' - so
> that some eager inference resolution has to happens, in which case the
> compiler needs to find a way to do 'as less damage as possible'. I'd expect
> this routine to be called rather infrequently, and not to be (too)
> performance sensitive; I don't think it ever appeared in any of the
> profiling runs we took in the past when troubleshooting inference
> performances.

I think some quite simple and frequent cases could be improved by (1),
something like:

public class E {
    interface F<X, Y, Z> { void f(X x, Y y, Z z); }

    <T> T m(T t) { return null; }

    <X, Y, Z, A, B, C, D>
    void n(F<X, Y, Z> f, A a, B b, C c, D d) {}

    void o() {
        n( (x, y, z) -> {}, m(""), m(""), m(""), m(""));
    }
}

Here, when inferring the type of the lambda parameter 'x', we find
immediately an optimal leaf 'X', there's no need neither to loop
through all the other lambda ivars nor through the rest of the graph
nodes, see [loop].

For (2), it's a bit more complex as it would involve an f-bounded type
for 'X' bound to another ivar like 'A' which also depends on 'T' from
argument 'a' (something like "X extends R<X, A>", I think...), but the
optimization is costless and could be useful in some cases.

What do you think?

Bernard

[loop] http://hg.openjdk.java.net/jdk10/master/file/66774e1fc3a7/src/jdk.compiler/share/classes/com/sun/tools/javac/comp/Infer.java#l1409

> Maurizio
>
>
>
>
> On 03/10/17 22:05, B. Blaser wrote:
>>
>> Hi,
>>
>> While exploring the implementation of the inference graph along with
>> the solving system, I noticed that the complexity of the heuristic
>> used to choose the best leaf to be solved could probably be reduced in
>> three ways:
>>
>> 1) When an optimal leaf is found with only one ivar to be solved,
>> there's no need to evaluate other subtrees.
>>
>> 2) When computing a subtree heuristic, if the path being evaluated
>> appears to be worth than the best subtree so far, it isn't necessary
>> to keep on evaluating this possibility.
>>
>> 3) Let 'n' be the number of inference graph nodes and 'v' be the
>> number of variables to be solved (for example when inferring the types
>> of lambda parameters).
>>
>> Retrieving all the nodes of a graph corresponding to a list of
>> inference variables to be solved is currently in O(n*v) in the best
>> case (only one ivar per node). I think this could be achieved in O(v)
>> if the nodes where stored in a map in addition to the ordered list.
>>
>> You'll find in attachment a suggestion of patch for that.
>>
>> What do you think?
>>
>> Thanks,
>> Bernard
>
>