Performance of Scope.getSymbolsByName()

[Maurizio Cimadamore]

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 
> <mailto: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
>     <mailto: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 <mailto: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/3fdb2b96/attachment-0001.html>