Linear implementation of Tarjan's algorithm

[Maurizio Cimadamore]

On 25/10/17 17:34, B. Blaser wrote:
> 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).
Could you post some before/after times please?

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