Linear implementation of Tarjan's algorithm

[B. Blaser]

On 25 October 2017 at 18:16, Maurizio Cimadamore
<maurizio.cimadamore at oracle.com> wrote:
>
>
> 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?

Yes, with 20/60/100 points (the gain is different but always appreciable).
Of course, only the cache is important (the gain with 'contains()' is
only of some milliseconds).

Bernard


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