RFR: 8061950: Class.getMethods() exhibits quadratic time complexity
peter.levart at gmail.com
Sat Nov 1 18:13:28 UTC 2014
On 10/31/2014 11:50 AM, Stanimir Simeonoff wrote:
> Personally I have no objections to the latest webrev.
> It looks like you are creating a more sophisticated data structure
> with more garbage, which won't show up as much on our small-memory
> benchmarks. Which is why I was expecting to have to write an adaptive
> data structure that switches from linear search to hash-based when
> some threshold is exceeded.
> There is a hidden cost in calling Method.getParameterTypes() even with
> linear search. Although it can be optimized to always first check
> Method.getName() for reference equality
> So the new approach creates 2 more short lived objects per Method -
> HashMap.Node and the MethodList. MethodTable.Impl and its underlying
> Object are one time off as they are properly sized.
> I have no objection if the instances die trivially in the young gen.
webrev.02, 04 (and 05) are basically same as garbage is concerned
(webrev.03 is a dead-end):
webrev.02: creates a LinkedHashMap.Entry + Class.MethodList for each Method
webrev.04: creates a HashMap.Entry + MethodTable.MethodNode for each Method
webrev.05: is same as 04 + it contains an array based alternative
MethodTable which doesn't create any additional objects per Method
all approaches create an underlying array.
> A possible optimization would be using a short-circuit in case of no
> interfaces and extending directly java.lang.Object (quite a common
> case). But even then the Object has quite a few public methods
> [getClass(), notify(), notiftyAll(), wait(), wait(long, int),
> wait(long), toString(), hashCode(), equals(Object)], so it requires
> another HashMap and checking how many of them are overridden.
There is a possibility of optimization in Class.getMethod() (single)
when there are no (super)interfaces. And for Class.getMethods() (plural)
when invoked for and interface with no (super)interfaces - just get
declared methods. And of course, the same for Object.class. Any other
class has to combine it's own declared methods with at least Object
methods, to get a compilation of public methods.
> That also reminds me: Object methods should always be cached,
> regardless of the config flag. Object class cannot be redefined and
> the memory is constant.
The flag is not to enable tracking re-definition of classes (even when
cache is used, they get properly tracked as cache is invalidated), but
for memory constrained environments (and useful for testing too). I
don't know if always caching Object methods would help much - perhaps
optimizing getMethods() to only return declared public methods for
Object.class is enough for memory constrained environments, as the
Method objects must always be cloned anyway.
> (The introduction of default methods into openjdk makes method lookup
> even more confusing, and scares me, especially since I am uncertain we
> have enough tests...)
> If your changes to StarInheritance.java are general improvements, we
> could/should just check them in now (TDD?).
> Use javadoc comments /** even for private methods
> + /* This method returns 'root' Constructor object. It MUST be
> copied with ReflectionFactory
> + * before handed to any code outside java.lang.Class or modified.
> + */
> private Constructor<T> getConstructor0(Class<?> parameterTypes,
> The java way is to spell intfcsMethods "interfacesMethods"
> On Thu, Oct 30, 2014 at 9:53 AM, Peter Levart
> <peter.levart at gmail.com <mailto:peter.levart at gmail.com>> wrote:
> > Hi,
> > Here's a patch:
> > for the following issue:
> > https://bugs.openjdk.java.net/browse/JDK-8061950
> > For those following the thread "Loading classes with many
> methods is very
> > expensive", this is a 4th iteration of this patch. I stepped
> back from the
> > approach taken in 3rd webrev and rather refined approach taken
> in 2nd
> > webrev. Instead of using a LinkedHashMap with values being
> linked-lists of
> > nodes holding Method objects with same signature, which couldn't
> be made so
> > that iteration would follow insertion order, I used plain
> HashMap this time.
> > MethodNode(s) holding Method objects form a linked list of those
> sharing the
> > same signature. In addition MethodNode(s) form a separate
> doubly-linked list
> > of all nodes which is used to keep insertion order. The space
> use should be
> > the same as I traded two object pointers in MethodNode for two
> less pointers
> > in HashMap.Entry (vs. LinkedHashMap.Entry that was used before). So
> > insertion order is not tracked by Map but instead by MethodTable
> now. I also
> > track size of MethodTable now so there's no pre-traversing pass
> to allocate
> > Method when requested.
> > This version seems to be the fastest from all tried so far
> (measured by
> > using "-Dsun.reflect.noCaches=true"):
> > Original:
> > 19658 classes loaded in 2.027207954 <tel:2.027207954> seconds.
> > 494392 methods obtained in 0.945519006 seconds.
> > 494392 methods obtained in 0.95250834 seconds.
> > 494392 methods obtained in 0.917841393 seconds.
> > 494392 methods obtained in 0.971922977 seconds.
> > 494392 methods obtained in 0.947145131 seconds.
> > 494392 methods obtained in 0.937122672 seconds.
> > 494392 methods obtained in 0.893975586 seconds.
> > 494392 methods obtained in 0.90307736 seconds.
> > 494392 methods obtained in 0.918782446 seconds.
> > 494392 methods obtained in 0.881968668 seconds.
> > Patched:
> > 19658 classes loaded in 2.034081706 seconds.
> > 494392 methods obtained in 0.8082686 seconds.
> > 494392 methods obtained in 0.743307034 seconds.
> > 494392 methods obtained in 0.751591979 seconds.
> > 494392 methods obtained in 0.726954964 seconds.
> > 494392 methods obtained in 0.761067189 seconds.
> > 494392 methods obtained in 0.70825252 seconds.
> > 494392 methods obtained in 0.696489363 seconds.
> > 494392 methods obtained in 0.692555238 seconds.
> > 494392 methods obtained in 0.695150116 seconds.
> > 494392 methods obtained in 0.697665068 seconds.
> > I also updated the test that checks multiple inheritance of
> abstract methods
> > as I found that my 1st iteration of the algorithm was not
> getting the same
> > results as original code although all jtreg tests were passing.
> I added 4
> > cases that include abstract classes as well as interfaces to the
> mix. Some
> > of them would fail with my 1st version of algorithm.
> > All 86 jtreg tests in java/lang/reflect/ and java/lang/Class/
> pass with this
> > patch applied.
> > Regards, Peter
More information about the core-libs-dev