Complexity reduction when choosing the best inference leaf to be solved

[B. Blaser]

Hi,

On 5 October 2017 at 20:26, B. Blaser <bsrbnd at gmail.com> wrote:
> On 5 October 2017 at 16:28, Vicente Romero <vicente.romero at oracle.com> wrote:
>>
>>
>> On 10/05/2017 04:32 AM, Maurizio Cimadamore wrote:
>>>
>>> Please, send me a patch with all your fixed, including the new version of
>>> (3) and I'll take a look/run some tests.
>>
>>
>> +1 yes please share the last full version
>
> Here it is, in attachment.
>
> Note that there's another possibility for pt (2), using "return
> noPath" instead of "throw", but I think this would probably be slower.
>
> I did only some quick tests with this last full version, so please let
> me know if you encounter any problem with it.
>
> I think the example I gave previously is really faster with (1) and
> (3); we pick immediately, in O(1), 'X' then 'Y' and finally 'Z'.

Here are two more examples showing the benefits of pt (2), this time.
The first one uses 'T' via the actual arguments of 'n()' to build
nodes with multiple ivars and the second one uses 'List<T>' to build
dependent nodes of single ivar.

When inferring the type of the lambda parameters in the example below,
we first try the non-optimal node [T, B] of size 2. Then we try node
[C] of size 1 but depending on [T, A] and [T, B]. When examining the
first dependency [T, A] we can immediately conclude that this
possibility is worse than the best known so far, discarding it with
the first 'throw' and without evaluating the second dependency [T, B]:

import java.util.Map;
import java.util.List;
import java.util.function.BiConsumer;

public class H {
    <T> T m(T t) { return t; }

    <A, B, C extends Map<A, B>> void n(BiConsumer<B, C> f, A a, B b, C c) {}

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

This next example shows another benefit of pt (2) when inferring the
type of the lambda parameters. We first examine node [B] which depends
on [T] having then a full cost of 2. Then, we start evaluating [C]
which depends on [A] + [T] and [B] + [T]. When computing the full cost
of [A], we can immediately discard this possibility (via the second
'throw'), the latter being worse than the best known so far:

public class H {
    <T> List<T> m(T t) { return null; }

    <A, B, C extends Map<A, B>> void n(BiConsumer<B, C> f, A a, B b, C c) {}

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

Cheers,
Bernard


> Please let me know about the test results.
>
> Cheers,
> Bernard
>
>>> Cheers
>>> Maurizio
>>
>>
>> Vicente