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

[Peter Levart]

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 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 
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 
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