Linear implementation of Tarjan's algorithm

[Maurizio Cimadamore]

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