Linear implementation of Tarjan's algorithm

[B. Blaser]

I think both solutions are slightly different.

Given 'P1 <: Comparable<P1>', 'P2 <: Comparable<P2>' and 'P1.tsym == P2.tsym':

* with your suggestion 'same(P1, P2) = false'
* with my suggestion 'same(P1, P2) = true'

So, it depends what we are expecting loose-same-type to do. But, as it
seems that loose-same-type should use the type symbol not to distinct
clones, I think the second suggestion would make more sense.

That said, the performance problem starts in 'Types.lub()' which uses
loose-same-type. Fortunately, with the current impl or with your
suggestion 'same(P1, P2) = false' which is what we are expecting in
'lub()' (I think) even if causing a performance problem. But 'same(P1,
P2)' currently doesn't return 'false' for the good reason (because of
the bug in loose-same-type instead of checking if 'P1 == P2').

So, we have to decide what 'loose-same-type' should really do to
choose between the two suggestions and eventually fix 'Types.lub()'
(and other places) to use strict-same-type instead, if necessary.

What do you think?

Bernard


On 3 November 2017 at 15:00, Maurizio Cimadamore
<maurizio.cimadamore at oracle.com> wrote:
> Or, in terms of Prolog, add a clause to your definitions (and probably some
> 'cuts' ;-)):
>
> same(P, P).
>
>
> Maurizio
>
>
> On 03/11/17 13:57, Maurizio Cimadamore wrote:
>>
>> I agree that it's a bug in the loose check not to consider if tv1 == tv2.
>> But that should be added to the sameTypeVars() predicate, not done by
>> tweaking the behavior in the cache. In other words:
>>
>> class LooseSameTypeVisitor extends SameTypeVisitor {
>>
>>             @Override
>>             boolean sameTypeVars(TypeVar tv1, TypeVar tv2) {
>>                 return tv1 == tv2 ||
>>                     (tv1.tsym == tv2.tsym && checkSameBounds(tv1, tv2));
>>             }
>>
>> }
>>
>>
>> This should make the loose check a proper superset of the strict check.
>>
>> But I bet that this doesn't help the performance problem, which is
>> probably triggered by clones of the same var, not just by == instances. Am I
>> right?
>>
>> Maurizio
>>
>>
>> On 03/11/17 13:17, B. Blaser wrote:
>>>
>>> On 3 November 2017 at 02:58, Maurizio Cimadamore
>>> <maurizio.cimadamore at oracle.com> wrote:
>>>>
>>>>
>>>> On 02/11/17 23:26, B. Blaser wrote:
>>>>>
>>>>> Of course, it will still require some optimization to be sub-second
>>>>> (as you said), but this simple correction could do half of the job.
>>>>
>>>> Hi Bernard,
>>>> unfortunately this optimization is unsound - there's no way to prove
>>>> that P
>>>> <: Comparable<P> is the same as P' <: Comparable<P'>, because of the
>>>> f-bound. That's why the cache is there - it's not an optimization, is
>>>> something that prevents javac from doing the same check over and over
>>>> again.
>>>>
>>>> When such a loop occurs, the right thing to do is to say 'false', as it
>>>> is
>>>> not possible to prove that the bounds are indeed the same.
>>>
>>> If we want to prove that "P <: Comparable<P>" is the same type as "P'
>>> <: Comparable<P'>", we have to do something like the following lines
>>> of Prolog:
>>>
>>> % same(P1, P2) :- samesym(P1, P2), samebounds(comparable(P1),
>>> comparable(P2)).
>>> % samebounds(comparable(P1), comparable(P2)) :- samesym(P1, P2),
>>> cache(comparable(P1), comparable(P2)).
>>>
>>> To prove 'same(P1, P2)', we have to know about 'samesym(P1, P2)' and
>>> 'cache(comparable(P1), comparable(P2))'.
>>> Looking at the implementation, we find that 'samesym(P1, P2)' is given
>>> by 'P1.tsym == P2.tsym' and 'cache(comparable(P1), comparable(P2))'
>>> currently returns 'false'.
>>>
>>> Now, we can look at the truth table for 'samesym()' and 'cache()':
>>>
>>> % samesym(P1, P2) :- true.
>>> % cache(comparable(P1), comparable(P2)) :- true.
>>> %
>>> % ?- same(P1, P2).
>>> % true.
>>>
>>> % samesym(P1, P2) :- true.
>>> % cache(comparable(P1), comparable(P2)) :- false.
>>> %
>>> % ?- same(P1, P2).
>>> % false.
>>>
>>> % samesym(P1, P2) :- false.
>>> % cache(comparable(P1), comparable(P2)) :- true.
>>> %
>>> % ?- same(P1, P2).
>>> % false.
>>>
>>> % samesym(P1, P2) :- false.
>>> % cache(comparable(P1), comparable(P2)) :- false.
>>> %
>>> % ?- same(P1, P2).
>>> % false.
>>>
>>> We see that the only way to prove that 'same(P1, P2) = true' is to
>>> postulate that 'cache(...) = true' which is what I suggested.
>>>
>>> If we make the opposite hypothesis that 'cache(...) = false', which is
>>> currently done, we will never be able to prove that 'same(P, P) =
>>> true'... but the strict comparison would do that successfully!
>>>
>>> What do you think (for the rest, I agree with you)?
>>>
>>> Bernard
>>>
>>>
>>>> Note that the
>>>> fact that the two variables are clones is largely irrelevant here - we
>>>> clone
>>>> new tvars every time we check a new instance of the same generic method
>>>> call/diamond constructor - so in a way these are all different variables
>>>> which just happen to have the same name/same set of initial (declared)
>>>> bounds.
>>>>
>>>> Moreover, the 'loose' type equality test is an artifact of the past - it
>>>> was
>>>> introduced because the strict behavior (which was the default in 6) was,
>>>> well, sometimes too strict - essentially, if bounds of a type variable
>>>> are
>>>> replaced for other type variables (e.g. replace U in the bound of 'Z
>>>> extends
>>>> List<U>'), javac creates a different type-variable with the replaced
>>>> bound.
>>>> If you performed the same replacement twice on the original variable,
>>>> the
>>>> resulting replaced vars would not be deemed 'equals' by javac, which is
>>>> why
>>>> this looser behavior was added. Some more comments are added here:
>>>>
>>>>
>>>> http://hg.openjdk.java.net/jdk7/jdk7/langtools/file/tip/src/share/classes/com/sun/tools/javac/code/Types.java#l632
>>>>
>>>> These changes have been added as a consequence of the fixes for:
>>>>
>>>> https://bugs.openjdk.java.net/browse/JDK-6729401
>>>>
>>>> Now, all this is relatively ancient history, which predates the Java 8
>>>> changes - in fact, this 'legacy' loose behavior, is very problematic -
>>>> it's
>>>> completely outside the spec, and, in the general case with fbounds, it
>>>> cannot even be proven to always complete (which is why the cache is
>>>> there).
>>>> During 8, I sidestepped this issue by adding the 'strict' type equality
>>>> check, which should become the 'standard' - but, as I there was only so
>>>> much
>>>> code I could rewrite in one shot (:-)), I added the new routine beside
>>>> the
>>>> old one, instead of having the new routine completely replacing the old
>>>> one
>>>> (and deal with the compatibility fallout).
>>>>
>>>> I think the time is come that we do a bit of spring cleaning in the
>>>> area,
>>>> and get rid of the legacy (and unsound) loose check, and see where we're
>>>> at.
>>>>
>>>> That said, speaking of inference performances, if we ever move the
>>>> entire
>>>> code base to use the strict equality check, your proposed optimization
>>>> would
>>>> not even apply - in a way your optimization is exploiting the fact that
>>>> that
>>>> particular check is using the loose check instead of the strict one -
>>>> with
>>>> the strict one, two different type var instances (no matter if they are
>>>> clones, and even have same bounds) will still be deemed different.
>>>>
>>>> I still stand by my earlier analysis that the particular issue
>>>> highlighted
>>>> in 8152289 is not something that needs to be addressed by looking at the
>>>> profiler. While you can make the bottleneck smaller and smaller, you
>>>> still
>>>> have an underlying behavior that doesn't scale with the number of nested
>>>> calls - with increasing values of N, you do 10, 100, 1000, 10000, 1000
>>>> ....00000 checks - so no matter how fast the rewritten logic is, you can
>>>> always add a bunch new nested call to bring the compilation time more or
>>>> less in time to what it was before the fix.
>>>>
>>>> The real fix is to find a way so that the incorporation machinery
>>>> doesn't
>>>> have to actually perform a number of steps that is exponential in the
>>>> number
>>>> of the type variables involved, and to detect patterns that can be
>>>> exploited
>>>> in order to reduce the complexity of the incorporation step.
>>>>
>>>> Thanks
>>>> Maurizio
>>
>>
>