RFR: 8061950: Class.getMethods() exhibits quadratic time complexity
stanimir at riflexo.com
Fri Oct 31 10:50:31 UTC 2014
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.
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.
That also reminds me: Object methods should always be cached, regardless of
the config flag. Object class cannot be redefined and the memory is
> (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>
> > Hi,
> > Here's a patch:
> > http://cr.openjdk.java.net/~plevart/jdk9-dev/Class.getMethods/webrev.04/
> > 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
> > approach taken in 3rd webrev and rather refined approach taken in 2nd
> > webrev. Instead of using a LinkedHashMap with values being linked-lists
> > nodes holding Method objects with same signature, which couldn't be made
> > that iteration would follow insertion order, I used plain HashMap this
> > MethodNode(s) holding Method objects form a linked list of those sharing
> > same signature. In addition MethodNode(s) form a separate doubly-linked
> > of all nodes which is used to keep insertion order. The space use should
> > the same as I traded two object pointers in MethodNode for two less
> > in HashMap.Entry (vs. LinkedHashMap.Entry that was used before). So
> > insertion order is not tracked by Map but instead by MethodTable now. I
> > track size of MethodTable now so there's no pre-traversing pass to
> > 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 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
> > as I found that my 1st iteration of the algorithm was not getting the
> > 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.
> > of them would fail with my 1st version of algorithm.
> > All 86 jtreg tests in java/lang/reflect/ and java/lang/Class/ pass with
> > patch applied.
> > Regards, Peter
More information about the core-libs-dev