Linear implementation of Tarjan's algorithm

[Maurizio Cimadamore]

On 25/10/17 14:41, B. Blaser wrote:
> 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?
Did you try it with the test case in JDK-8152289?

Maurizio
>
> 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