Performance of Scope.getSymbolsByName()

Tue May 21 16:39:15 UTC 2019

Are the checks of the inner loop symmetrical?

Currently it's checking mi against (m0..n - mi). This second webrev below
would check it against just (m0..i-1), which albeit still n^2, it divides
by a factor of 2.

(sorry if the subscripting here doesn't display correctly)

http://cr.openjdk.java.net/~ronsh/8224161/webrev.01/

This feels conceptually logical to me, but I'm not seeing a
measurable change by it. It looks a little bit cleaner to me, but I'm fine
with either webrev given the benefits they both bring.

I can take a look in another thread about speeding up CompoundScope
iteration.

On Tue, May 21, 2019 at 8:05 AM Maurizio Cimadamore <
maurizio.cimadamore at oracle.com> wrote:

>
> On 21/05/2019 12:16, Ron Shapiro wrote:
>
> I still think that something to optimize the actual ScopeImpl Iterable is
> a worthwhile endeavor, as that would alleviate the need to materialize here
> (and solve hopefully the other issues I'm seeing), but I was having trouble
> figuring out how to do that. This may be a good interim option without much
> cost.
>
> Sure - I'm not opposed to optimizing the iteration process - I was
> expressing my skepticism w.r.t. making checkOverrideClash simpler/non
> quadratic.
>
> Maurizio
>
>
>
>
> On Tue, May 21, 2019, 5:59 AM Maurizio Cimadamore <
> maurizio.cimadamore at oracle.com> wrote:
>
>> I think your fix is a good one. We spent some cycles optimizing this, a
>> bit odd we have missed this :-)
>>
>> I'm very skeptical you can collapse into a single loop, as this implement
>> the logic in JLS 8.4.8.3 [1] which, as you can see, is inherently quadratic
>> (for each method, we have to scan all methods with same name in supertypes
>> to see if there is an override clash). The algorithm that was there before
>> wasn't - and it lead to the wrong answers in tricky cases - so while you
>> can get 80% there with a non-quadratic algorithm, you will miss issues by
>> doing so.
>>
>> One thing that would help would be, instead, to limit the analysis only
>> in cases where it adds value - for instance, if your hierarchy is just
>> non-generic classes (as in your example), then there's no way for you to
>> accidentally override a 'bridge' method, since no bridges will be
>> generated! But when looking at this, I couldn't find great ways to detect
>> these conditions w/o spending more time than the check itself.
>>
>> [1] -
>> https://docs.oracle.com/javase/specs/jls/se12/html/jls-8.html#jls-8.4.8.3
>>
>> Maurizio
>> On 20/05/2019 21:58, Ron Shapiro wrote:
>>
>> In the real world example, I'm seeing the 40s that was previously spent
>> in Check.checkOverrideClashes drop to to 9.5s when using this patch. Of
>> that 9.5, 8.9 is spent in iterating through the CompoundIterator and
>> calling getSymbolsByName.
>>
>> On Mon, May 20, 2019 at 4:34 PM Ron Shapiro <ronshapiro at google.com>
>> wrote:
>>
>>> This patch, which materializes the duplicate outer and inner Iterables
>>> first into a list. It removes the entire section of the CompoundIterator
>>> iteration from the profile.
>>>
>>> webrev:
>>> http://cr.openjdk.java.net/~ronsh/8224161/webrev.00/src/jdk.compiler/share/classes/com/sun/tools/javac/comp/Check.java.sdiff.html
>>>
>>> I'm not sure it's the absolutely correct solution as it possibly masks
>>> an underlying issue.
>>>
>>> I'm still seeing some time spent in MethodSymbol.overrides,
>>> Types.isSubSignature, and Types.memberType, all of which happen in the
>>> inner loop. If we can remove those and collapse the nested loops into one,
>>> then this solution isn't necessary and it would also solve that performance
>>> issue.
>>>
>>> On Fri, May 17, 2019 at 5:55 PM Ron Shapiro <ronshapiro at google.com>
>>> wrote:
>>>
>>>> I still have more to investigate to fully wrap my head around it, but I
>>>> finally found a sample program that exhibits this. Filed a bug here:
>>>> https://bugs.openjdk.java.net/browse/JDK-8224161
>>>>
>>>> On Fri, May 17, 2019 at 11:21 AM Jan Lahoda <jan.lahoda at oracle.com>
>>>> wrote:
>>>>
>>>>> Hi Ron,
>>>>>
>>>>> I am afraid it is hard to guess what is the problem without some
>>>>> testcase. So, at least to me, having a sample would be helpful.
>>>>>
>>>>> Thanks,
>>>>>      Jan
>>>>>
>>>>> On 17. 05. 19 0:41, Ron Shapiro wrote:
>>>>> > Hi,
>>>>> >
>>>>> > I'm observing a particularly bizarre compilation. It's a single file
>>>>> > with annotation processing, and the type that is being compiled and
>>>>> > processed has ~1000 declared and inherited methods combined. The
>>>>> total
>>>>> > compilation is 3 minutes, but 65% of the entire compilation is spent
>>>>> in
>>>>> > 3 methods:
>>>>> > Check.checkOverrideClashes(), Resolve.findInheritedMemberType(),
>>>>> > and Resolve.findField().
>>>>> >
>>>>> > Looking at profiles, it looks like getSymbolsByName() is the major
>>>>> > culprit here. I initially thought the reason was that there were far
>>>>> too
>>>>> > many overloads (this type had >600 overloads...) and that that was
>>>>> > causing a bad regression for the pseudo-hashmap that ScopeImpl uses.
>>>>> > However, renaming the methods did not alleviate the build pain and
>>>>> these
>>>>> > methods continue to be taking long amounts of time.
>>>>> >
>>>>> > I was wondering what could be done to improve the performance of
>>>>> this
>>>>> > code. It seemed to me that something like a Map<Name, List<Symbol>>
>>>>> > could be a reasonable+modern replacement for this table, which would
>>>>> > naturally have a fast getSymbolsForName() implementation. I'm having
>>>>> > some trouble implementing it correctly, and I believe it's partially
>>>>> > related to not fully understanding some of the semantics of the
>>>>> class.
>>>>> >
>>>>> > Does what I wrote make sense to anyone, and maybe spark a lightbulb?
>>>>> >
>>>>> > I'm trying to put together a repro in case that helps, but I'm not
>>>>> 100%
>>>>> > sure I even understand what the regression case is.
>>>>> >
>>>>> > Thanks for you help!
>>>>>
>>>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.openjdk.java.net/pipermail/compiler-dev/attachments/20190521/3a9bcd7a/attachment-0001.html>