Linear implementation of Tarjan's algorithm

[Maurizio Cimadamore]

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
>