Linear implementation of Tarjan's algorithm

[B. Blaser]

On 23 October 2017 at 17:58, Maurizio Cimadamore
<maurizio.cimadamore at oracle.com> wrote:
> To have a better idea of the kind of performance issues we are having in
> this area, take a look here:
>
> https://bugs.openjdk.java.net/browse/JDK-8152289
>
> I'm slightly pessimistic that any of the performance fixes discussed here in
> the last few weeks would actually make a difference here - the sad reality
> is that the cost of doing incorporation dominates pretty much everything
> else. And the name of the game to address these kind of issues seem to be to
> attempt to reduce the size of the inference graph by finding similarities
> between variables [1]/minimize number of propagation steps as much as
> possible [2], etc.

Of course, 'contains()' isn't the bottleneck here. But with an
'HashStack', this method is up to 10 times faster than with a 'List'
(in this example).

That said, I observed in the light of your comments that a very large
number of same upper bound pairs are checked multiple times. So, I
tried to put them in a cache that is cleared at every upper bound
change, as here under. It seems to be 3-4 times faster than before for
this issue with 60 nodes (on my computer).

What do you think?

Bernard


diff --git a/src/jdk.compiler/share/classes/com/sun/tools/javac/comp/Infer.java
b/src/jdk.compiler/share/classes/com/sun/tools/javac/comp/Infer.java
--- a/src/jdk.compiler/share/classes/com/sun/tools/javac/comp/Infer.java
+++ b/src/jdk.compiler/share/classes/com/sun/tools/javac/comp/Infer.java
@@ -939,13 +939,15 @@
         @Override
         void apply(InferenceContext inferenceContext, Warner warn) {
             List<Type> boundList = uv.getBounds(InferenceBound.UPPER).stream()
+                    .filter(b2 -> t != b2)
+                    .filter(b2 -> !upperBoundCache.contains(new Pair<>(t, b2)))
                     .collect(types.closureCollector(true, types::isSameType));
+
             for (Type b2 : boundList) {
-                if (t == b2) continue;
                     /* This wildcard check is temporary workaround.
This code may need to be
                      * revisited once spec bug JDK-7034922 is fixed.
                      */
-                if (t != b2 && !t.hasTag(WILDCARD) && !b2.hasTag(WILDCARD)) {
+                if (!t.hasTag(WILDCARD) && !b2.hasTag(WILDCARD)) {
                     for (Pair<Type, Type> commonSupers :
getParameterizedSupers(t, b2)) {
                         List<Type> allParamsSuperBound1 =
commonSupers.fst.allparams();
                         List<Type> allParamsSuperBound2 =
commonSupers.snd.allparams();
@@ -964,6 +966,8 @@
                         Assert.check(allParamsSuperBound1.isEmpty()
&& allParamsSuperBound2.isEmpty());
                     }
                 }
+                upperBoundCache.add(new Pair<>(t, b2));
+                upperBoundCache.add(new Pair<>(b2, t));
             }
         }
     }
@@ -1086,6 +1090,7 @@
             }

             if (ib == InferenceBound.UPPER) {
+                upperBoundCache.clear();
                 actions.add(new CheckUpperBounds(uv, t));
             }

@@ -1125,6 +1130,7 @@
             }
         } finally {
             incorporationCache.clear();
+            upperBoundCache.clear();
         }
     }

@@ -1247,6 +1253,7 @@

     /** an incorporation cache keeps track of all executed
incorporation-related operations */
     Map<IncorporationBinaryOp, Boolean> incorporationCache = new HashMap<>();
+    HashSet<Pair<Type, Type>> upperBoundCache = new HashSet<>();

     protected static class BoundFilter implements Filter<Type> {


> [1] - https://bugs.openjdk.java.net/browse/JDK-8046685
> [2] - https://bugs.openjdk.java.net/browse/JDK-8067767
>
> Maurizio