Complexity reduction when choosing the best inference leaf to be solved

[B. Blaser]

On 13 October 2017 at 14:31, Vicente Romero <vicente.romero at oracle.com> wrote:
>
>
>> On 10/13/2017 05:08 AM, Maurizio Cimadamore wrote:
>>
>>
>> But I think there's only _one_ minimal answer. So, the way I see the javac
>> implementation, is that the BestLeafSolver is a big workaround to the fact
>> that we need to be able to solve a 'subset' of the inference graph. But this
>> can be achieved in many different ways - and the approach implemented right
>> now (which predates the spec text) is probably more general than it needs
>> to.
>>
>> I think a very simple BestLeafSolver would simply 'skip' all the inference
>> graph nodes which cannot influence any of the nodes containing at least one
>> variable in the target set, and will keep going until all variables in such
>> set are solved. I don' think such an algorithm would require any tracking of
>> cost, paths and such.
>>
>>
> well I think that there are two parts here, one is finding that minimal set
> that could be done using a simple flood fill algorithm in the graph, just
> connectivity matters.

This seems not to be needed as all the subtrees matching the variables
in the list will have to be solved.
We can simply peek the first one.

> But then once we have the subset, we have to find a
> resolution order right? After the application of the Tarjan algo for
> strongly connected components, the graph is already topologically sorted.
> The subset found in step 1 will also be sorted we can follow that order.

Once we have selected a subtree matching one of the variables in the
list (pt 3), we can simply solve all the subtree leaf by leaf. As
leaves aren't inter-dependent, the order we solve them doesn't matter
I think.

Please take a look at the suggested implementation in attachment.
It seems to give quite good results.

What do you think?
Bernard


>> Maurizio
>
>
> Vicente
-------------- next part --------------
A non-text attachment was scrubbed...
Name: InferenceGraph_lazy.patch
Type: text/x-patch
Size: 8959 bytes
Desc: not available
URL: <http://mail.openjdk.java.net/pipermail/compiler-dev/attachments/20171013/01f736a4/InferenceGraph_lazy-0001.patch>