Complexity reduction when choosing the best inference leaf to be solved

[Maurizio Cimadamore]

Hi,
I think the affected area is close to this:

https://bugs.openjdk.java.net/browse/JDK-8178150

for which I have a fix in the work which I will submit for review soon.

After that fix is in, we can consider deeper refactorings in the area.

Cheers
Maurizio


On 13/10/17 17:59, B. Blaser wrote:
> 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