Linear implementation of Tarjan's algorithm

[B. Blaser]

Hi Maurizio,

On 25 October 2017 at 22:16, Maurizio Cimadamore
<maurizio.cimadamore at oracle.com> wrote:
> Thanks for testing - I imagined something similar - our target here is what
> is said in the bug report:
>
> "In JDK 7, compilation takes less than a second." (this is with 100 points).
>
> Your tests show that the smaller the inference graph, the smaller the gain
> (you start from 2x, and you end with 5x). But for bigger graphs, these kind
> of improvements are not going to cut it (still 2mins against <1s in JDK 7).
>
> And, if you fix this at a deeper level, so that the incorporation has to do
> less work, then you go back to subsecond compilation, in which case the
> contribution of your optimization is likely to be negligible.
>
> So, I don't want to sound overly critical (I realize I can sound that way
> sometimes) - you did a great experiment, and it's showing some good numbers
> - but the real problem here is that in JDK 7, _no matter how many nodes you
> had_ compilation always stayed subsecond. So, when I see a compilation time
> that increase depending on how many nested call you add, I worry - because,
> no matter how you optimize, you can always add few extra nodes and go back
> being as slow as you were (or more!) before the optimization.
>
> During JDK 9 we did a great job at optimizing this pattern:
>
> m1(m2(m3 .... mN() ) ) ) )
>
> I think it's time we do something similar for
>
> m(g1(), g2(), ... gN())
>
> Note that when we made incorporation smart enough to detect the first case,
> all other performance related concerns became negligible - I'm hoping we can
> pull a similar trick here (and we have few ideas on how to do that).

I perhaps found why a large number of same upper bounds are checked
multiple times, which seems to be one of the bottlenecks in
JDK-8152289. This is probably because 'Types.isSameType()' doesn't
work properly with recursive types.

Consider two clones of the same type variable 'P extends
Comparable<P>'. 'LooseSameTypeVisitor.checkSameBounds()' will
currently return 'false' when the upper bound of 'P' is recursively
checked (see [1]) which will then make
'LooseSameTypeVisitor.sameTypeVars()' return 'false' (see [2]).

I think 'LooseSameTypeVisitor.checkSameBounds()' should return 'true'
within recursive calls because only the root of recursion is able to
effectively check the bounds.

Fixing this little bug, as below, gives roughly the same results as
previously when using a cache (from 2x to 5x faster than initially).

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.

What do you think?

Thanks,
Bernard


[1] http://hg.openjdk.java.net/jdk10/master/file/6d0e943bcd24/src/jdk.compiler/share/classes/com/sun/tools/javac/code/Types.java#l1452

[2] http://hg.openjdk.java.net/jdk10/master/file/6d0e943bcd24/src/jdk.compiler/share/classes/com/sun/tools/javac/code/Types.java#l1432

diff --git a/src/jdk.compiler/share/classes/com/sun/tools/javac/code/Types.java
b/src/jdk.compiler/share/classes/com/sun/tools/javac/code/Types.java
--- a/src/jdk.compiler/share/classes/com/sun/tools/javac/code/Types.java
+++ b/src/jdk.compiler/share/classes/com/sun/tools/javac/code/Types.java
@@ -1449,7 +1449,7 @@
                         cache.remove(p);
                     }
                 } else {
-                    return false;
+                    return true;
                 }
             }
         };

> Cheers
> Maurizio