[prev in list] [next in list] [prev in thread] [next in thread]
List: openjdk-compiler-dev
Subject: Re: Linear implementation of Tarjan's algorithm
From: Maurizio Cimadamore <maurizio.cimadamore () oracle ! com>
Date: 2017-10-25 20:16:51
Message-ID: 7ba40e17-cb0b-1641-9e49-5391f55bae1c () oracle ! com
[Download RAW message or body]
Thanks for testing - I imagined something similar - our target here is
what is said in the bug report:
"In JDK 7, compilation takes less than a second." (this is with 100 points).
Your tests show that the smaller the inference graph, the smaller the
gain (you start from 2x, and you end with 5x). But for bigger graphs,
these kind of improvements are not going to cut it (still 2mins against
<1s in JDK 7).
And, if you fix this at a deeper level, so that the incorporation has to
do less work, then you go back to subsecond compilation, in which case
the contribution of your optimization is likely to be negligible.
So, I don't want to sound overly critical (I realize I can sound that
way sometimes) - you did a great experiment, and it's showing some good
numbers - but the real problem here is that in JDK 7, _no matter how
many nodes you had_ compilation always stayed subsecond. So, when I see
a compilation time that increase depending on how many nested call you
add, I worry - because, no matter how you optimize, you can always add
few extra nodes and go back being as slow as you were (or more!) before
the optimization.
During JDK 9 we did a great job at optimizing this pattern:
m1(m2(m3 .... mN() ) ) ) )
I think it's time we do something similar for
m(g1(), g2(), ... gN())
Note that when we made incorporation smart enough to detect the first
case, all other performance related concerns became negligible - I'm
hoping we can pull a similar trick here (and we have few ideas on how to
do that).
Cheers
Maurizio
On 25/10/17 18:45, B. Blaser wrote:
> On 25 October 2017 at 18:51, Maurizio Cimadamore
> <maurizio.cimadamore@oracle.com> wrote:
>>
>> On 25/10/17 17:34, B. Blaser wrote:
>>> On 25 October 2017 at 18:16, Maurizio Cimadamore
>>> <maurizio.cimadamore@oracle.com> wrote:
>>>>
>>>> On 25/10/17 14:41, B. Blaser wrote:
>>>>> On 23 October 2017 at 17:58, Maurizio Cimadamore
>>>>> <maurizio.cimadamore@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
>>>>
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic