Linear implementation of Tarjan's algorithm

[B. Blaser]

I agree with both of you.

To Rémi, It's never easy to choose between readability and absolute
performance, but I agree an inline rewriting would probably be more
appropriate here.

To Maurizio, this wasn't intended to be a major optimization but only
a very small rewriting that might help going faster in some particular
situations.

Cheers,
Bernard


On 22 October 2017 at 22:14, Maurizio Cimadamore
<maurizio.cimadamore at oracle.com> wrote:
> Another thing I'm concerned here is that we're jumping into performance
> fixes w/o any evidence of what the bottlenecks really are. I'm all for
> fixing performance issues (and during JDK 9 we did a lot of work in order to
> resolve the combinatorial explosion of checks in nested method calls). So, I
> think that, before we decide to spend significant cycles on this (and other
> related issues), we should at least come up with reasonable examples which
> demonstrate the bottleneck. In other words, in a world where the average
> inference graph has 4-5 nodes, does it really matter much how the contains()
> method is implemented? And, if you have a 1000 nodes inference-graph, are
> you sure that the main bottleneck is going to be the contains method? After
> having profiled MANY javac runs, I have to admit I have never seen that
> popping up - of course with all the optimizations that went into the
> compiler recently, things might have changed, but I still think that we
> should handle performance-related matters on a more data-driven basis.
>
> Cheers
> Maurizio
>
>
>
> On 22/10/17 19:06, Remi Forax wrote:
>>
>> Please do not add a new class just for that, for a code as simple as this
>> one, you can inline every methods.
>> Also, i think the compiler will create 8 methods for your class HashStack,
>> you should declare the class and all the method package private (or wait for
>> the compiler using the 18.3 as bootstrap JDK).
>>
>> regards,
>> Rémi
>>
>> ----- Mail original -----
>>>
>>> De: "B. Blaser" <bsrbnd at gmail.com>
>>> À: "compiler-dev" <compiler-dev at openjdk.java.net>
>>> Envoyé: Dimanche 22 Octobre 2017 19:36:12
>>> Objet: Linear implementation of Tarjan's algorithm
>>> Hi,
>>>
>>> As briefly mentioned in [1], the current implementation of Tarjan's
>>> algorithm performs a linear scan of the stack while iterating on the
>>> node dependencies which might be avoided...
>>>
>>> Next is an attempt to make the whole implementation more linear using
>>> a 'HashStack' that provides all operations in constant time,
>>> especially 'contains()'.
>>>
>>> What do you think?
>>>
>>> Thanks,
>>> Bernard
>>>
>>>
>>> [1]
>>> http://mail.openjdk.java.net/pipermail/compiler-dev/2017-October/011226.html
>>>
>>>
>>> diff --git
>>> a/src/jdk.compiler/share/classes/com/sun/tools/javac/util/GraphUtils.java
>>> b/src/jdk.compiler/share/classes/com/sun/tools/javac/util/GraphUtils.java
>>> ---
>>> a/src/jdk.compiler/share/classes/com/sun/tools/javac/util/GraphUtils.java
>>> +++
>>> b/src/jdk.compiler/share/classes/com/sun/tools/javac/util/GraphUtils.java
>>> @@ -28,6 +28,7 @@
>>> import java.util.ArrayList;
>>> import java.util.Collection;
>>> import java.util.Properties;
>>> +import java.util.HashSet;
>>>
>>> /** <p><b>This is NOT part of any supported API.
>>>   *  If you write code that depends on this, you do so at your own risk.
>>> @@ -164,7 +165,28 @@
>>>          ListBuffer<List<N>> sccs = new ListBuffer<>();
>>>
>>>          /** Stack of all reacheable nodes from given root. */
>>> -        ListBuffer<N> stack = new ListBuffer<>();
>>> +        HashStack<N> stack = new HashStack<>();
>>> +        //where
>>> +        private static class HashStack<N> {
>>> +            HashSet<N> set = new HashSet<>();
>>> +            List<N> stack = List.nil();
>>> +
>>> +            private void push(N n) {
>>> +                set.add(n);
>>> +                stack = stack.prepend(n);
>>> +            }
>>> +
>>> +            private N pop() {
>>> +                N n = stack.head;
>>> +                set.remove(n);
>>> +                stack = stack.tail;
>>> +                return n;
>>> +            }
>>> +
>>> +            private boolean contains(N n) {
>>> +                return set.contains(n);
>>> +            }
>>> +        }
>>>
>>>          private List<? extends List<? extends N>> findSCC(Iterable<?
>>> extends N> nodes) {
>>>              for (N node : nodes) {
>>> @@ -197,7 +219,7 @@
>>>              n.index = index;
>>>              n.lowlink = index;
>>>              index++;
>>> -            stack.prepend(n);
>>> +            stack.push(n);
>>>              n.active = true;
>>>          }
>>>
>>> @@ -205,7 +227,7 @@
>>>              N n;
>>>              ListBuffer<N> cycle = new ListBuffer<>();
>>>              do {
>>> -                n = stack.remove();
>>> +                n = stack.pop();
>>>                  n.active = false;
>>>                  cycle.add(n);
>>>               } while (n != v);
>
>