Performance of Scope.getSymbolsByName()

[Ron Shapiro]

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.



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/343c8009/attachment.html>