Complexity reduction when choosing the best inference leaf to be solved

[B. Blaser]

On 4 October 2017 at 19:29, B. Blaser <bsrbnd at gmail.com> wrote:
> I think one of the failing tests was
> "tools/javac/lambda/8016177/T8016177f.java".
>
> But I tried to re-do the initial fix for point (3) using a
> "LinkedHashMap<Type, Node>" instead of an "ArrayList<Node>", as
> attached, and all "tools/javac/lambda/" are passing successfully!
>
> Now, it should be possible to re-incorporate points (1) and (2) with
> the new version of (3).

Notice also that deleting a node from the graph (which is done at
every solving step [1]) is improved, too.
The list removal being in O(n) vs O(1) for the map as used in the last
patch for point (3).

What do you think?

Bernard


[1] http://hg.openjdk.java.net/jdk10/master/file/d4f959806fe9/src/jdk.compiler/share/classes/com/sun/tools/javac/comp/Infer.java#l1687

> Cheers,
> Bernard
>
>
> On 4 October 2017 at 18:04, Maurizio Cimadamore
> <maurizio.cimadamore at oracle.com> wrote:
>> Ok, I'll add some extra assertions to the code and then check it more
>> closely.
>>
>> There are situations in which type variables are cloned - and sometimes you
>> can have different clones of the same var in the same inference context -
>> e.g. in situation like these
>>
>> g(m(), m())
>>
>> That said, two type var clone should not be .equals, nor ==, so that would
>> not explain as to why multiple nodes containing the 'same' inference vars
>> were found in an inference graph.
>>
>> Maurizio
>>
>>
>>
>> On 04/10/17 16:03, B. Blaser wrote:
>>>
>>> On 4 October 2017 at 13:55, Maurizio Cimadamore
>>> <maurizio.cimadamore at oracle.com> wrote:
>>>>
>>>>
>>>> On 04/10/17 11:08, B. Blaser wrote:
>>>>>
>>>>> 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?
>>>>
>>>> I think we need to look at those tests - do you have a pointer to what
>>>> they
>>>> were?
>>>
>>> I don't remember exactly, but probably in "test/tools/javac/lambda".
>>> My first idea was to replace the node list with a "LinkedHashMap<Type,
>>> Node>" to have both benefits of an ordered list and a map. So, simply
>>> replacing the list by the map and re-running the tests should reveal
>>> the problem (I put an "Assert.check(map.remove(t) != null)" when
>>> removing a node which made some tests fail).
>>>
>>> Bernard
>>>
>>>
>>>> Thanks
>>>> Maurizio
>>
>>