Linear implementation of Tarjan's algorithm

[Maurizio Cimadamore]

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