RFR: 8061950: Class.getMethods() exhibits quadratic time complexity

[Peter Levart]

On 10/31/2014 11:50 AM, Stanimir Simeonoff wrote:
> Hi,
>
> 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.

Regards, Peter

>
> Stanimir
> ---
>
>
>     (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:
>     >
>     >
>     http://cr.openjdk.java.net/~plevart/jdk9-dev/Class.getMethods/webrev.04/
>     <http://cr.openjdk.java.net/%7Eplevart/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 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
>     >
>     http://cr.openjdk.java.net/~plevart/jdk9-dev/Class.getMethods/GetAllRtMethods.java
>     <http://cr.openjdk.java.net/%7Eplevart/jdk9-dev/Class.getMethods/GetAllRtMethods.java>
>     > 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
>     >
>