I have observed a pathological case where the same method, inherited through many different interfaces of the same concrete type, can result in a regression in javac performance. The code looks something like this:

final class DaggerComp implements Comp {
  ...
}

interface Comp extends
  A, B, C, D, E, F {}

interface A extends
  A1, A2, A3, A4 {}

interface A1 extends
  A1_1, A1_2, A1_3, A1_4 {}

Where every leaf interface in this tree implements a single type (and possibly others).

etc., to the point where Scope.getSymbolsByName() is returning in the most case 32 values. Here is a histogram mapping of the # of symbols returned mapped to the frequency.

32: 3
29: 1
28: 12
27: 5
25: 3
24:
22: 3
21:
20:
18: 19
18: 19
17: 3
16: 5
15: 13
14: 4
13: 20
12: 1
11: 10
10: 23
9: 31
8: 20
7: 2
6: 24
5: 39
4: 11
3: 23
2: 772
1: 727
0: 55

In aggregate, Check.checkOverrideClashes is taking 40s per build. While the user code is not common, I also believe there is likely to be a fix that can support the complex build that the app requires.

In particular, it seems like most of the time is actually spent in iterator *creation* and updating, and not inside of the actual loop. In the compilation, only 1.5% of the time spent in checkOverrideClashes is spent on MethodSymbol.overrides, and the rest is spent in CompoundIterator.hasNext(). And it seems almost all of that is spent in getSymbolsByName(), though with lambdas and other bizarre generated-name symbols, it's harder to tell.

Inside checkOverrideClashes, there's an inner loop over the same values of the outer loop. I feel like there must be a way to extract that out as a single loop so that this is not quadratic. But perhaps (see further below) that's not actually the main issue.

Below is a sample program that displays this performance regression. Running `test.py <num>` for a number up to 5 is quite fast, but num=6 starts to regress signficantly (checkOverrideClashes is taking ~9s/build on my machine). n=7 seems to time out.

The same real-life build is also showing similar performance problems with Resolve.findInheritedMemberType (57s/build) and Resolve.findField (18s/build) which all seem to be related to the same CompoundIterator/Scope issue, but I haven't been able to devise a sample program that highlights the issue. In total, these 3 methods are taking 115s out of the 164s of the compilation.

Here is the sample program generator:

=====
test.py
=====

import sys

n = int(sys.argv[1])

print """package test;

class Test implements""",

print ", ".join(["I%s" %x for x in range(n)]),
print """{

  @Override
  public void i() {}
}"""

def define_interfaces(count, prefix=""):
  defined = []
  for x in xrange(count):
    new_prefix = prefix + "_" + str(x)
    inner_defined = define_interfaces(count - 1, new_prefix)

    name = "I%s%s" %(x, prefix)

    if len(inner_defined):
      extends_clause = "extends %s " %(", ".join(inner_defined))
    else:
      extends_clause = ""

    print """
      interface %s %s{
        void i();
      }
    """ %(name, extends_clause)
    defined.append(name)

  return defined

define_interfaces(n)