Linear implementation of Tarjan's algorithm
Maurizio Cimadamore
maurizio.cimadamore at oracle.com
Wed Oct 25 16:51:34 UTC 2017
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
>>
More information about the compiler-dev
mailing list