Linear implementation of Tarjan's algorithm

[B. Blaser]

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

On a quite slow CPU (before -> after):
* 20 points - 13s -> 6s
* 60 points - 90s -> 24s
* 100 points - 551s -> 110s

Bernard

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