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

[Peter Levart]

On 11/01/2014 06:49 PM, Peter Levart wrote:
>> On 10/30/2014 07:13 PM, Martin Buchholz wrote: 
>> 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.
>
> ...or two data structures. Since I have already arranged so that 
> construction of MethodTable gets an upper limit on the total number of 
> possible Method(s) that can be added to it, we can have two 
> MethodTable implementations and switch based on this number:
>
> http://cr.openjdk.java.net/~plevart/jdk9-dev/Class.getMethods/webrev.05/ 

Hi,

I made some progress on this front. I created new MethodTable 
implementation (the third one) with similar performance as HashMap 
based, but producing half the garbage. I also added some optimizations 
to getMethod(), getMethods() and MethodTable in general that deal with 
special cases / parameter types comparison and have measurable impact on 
performance (for example loading all rt.jar classes and calling 
getMethods() for them):

Original:

19658 classes loaded in 2.003623648 seconds.
494392 methods obtained in 0.932151066 seconds.
494392 methods obtained in 0.968247076 seconds.
494392 methods obtained in 0.989218185 seconds.
494392 methods obtained in 1.018700179 seconds.
494392 methods obtained in 0.945078767 seconds.
494392 methods obtained in 0.930856897 seconds.
494392 methods obtained in 0.905420555 seconds.
494392 methods obtained in 0.89253006 seconds.
494392 methods obtained in 0.914590141 seconds.
494392 methods obtained in 0.891616716 seconds.
494392 methods obtained in 0.891839815 seconds.
494392 methods obtained in 0.892863985 seconds.
494392 methods obtained in 0.960643274 seconds.
494392 methods obtained in 0.959266392 seconds.
494392 methods obtained in 0.894688322 seconds.
494392 methods obtained in 0.892751891 seconds.
494392 methods obtained in 0.912542838 seconds.
494392 methods obtained in 0.912219636 seconds.
494392 methods obtained in 0.895791468 seconds.
494392 methods obtained in 0.891673959 seconds.

Patched:

19658 classes loaded in 2.145270948 seconds.
494398 methods obtained in 0.722630874 seconds.
494398 methods obtained in 0.697521755 seconds.
494398 methods obtained in 0.689642554 seconds.
494398 methods obtained in 0.742724992 seconds.
494398 methods obtained in 0.695693313 seconds.
494398 methods obtained in 0.685169108 seconds.
494398 methods obtained in 0.663012634 seconds.
494398 methods obtained in 0.666446935 seconds.
494398 methods obtained in 0.675662884 seconds.
494398 methods obtained in 0.65369404 seconds.
494398 methods obtained in 0.656608178 seconds.
494398 methods obtained in 0.668384051 seconds.
494398 methods obtained in 0.657548957 seconds.
494398 methods obtained in 0.672332234 seconds.
494398 methods obtained in 0.655699295 seconds.
494398 methods obtained in 0.671819628 seconds.
494398 methods obtained in 0.657232183 seconds.
494398 methods obtained in 0.654462137 seconds.
494398 methods obtained in 0.659630473 seconds.
494398 methods obtained in 0.674219391 seconds.

(the difference in method count is expected - patched code contains new 
methods in existing rt.jar classes ;-)

Here's new webrev:

http://cr.openjdk.java.net/~plevart/jdk9-dev/Class.getMethods/webrev.06/


The optimizations made from webrev.05 are:

- getMethod() skips construction of MethodTable if there are no 
(super)interfaces.
- getMethods() returns just declared public methods if there are no 
superclass and no (super)interfaces.
- comparing method parameter types is optimized by adding two methods to 
Method/LangReflectAccess/ReflectionFactory.

New MethodTable implementation based on a linear-probe hash table is a 
space/garbage improvement. I took IdentityHashMap, removed unneeded 
stuff and modified it's API. The result is a HashArray. It's API is 
similar in function and form to java.util.Map, but doesn't use separate 
keys and values. An element of HashArray is a key and a value at the 
same time. Elements are always non-null, so the method return values are 
unambiguous. As HashArray is a linear-probe hash table and there are no 
Map.Entry objects involved, the underlying data structure is very simple 
and memory efficient. It is just a sparse array of elements with length 
that is always a power of two and larger than 3 * size / 2. It also 
features overriddable element equals/hashCode methods. I made it a 
separate generic class because I think it can find it's usage elsewhere 
(for example as a cannonicalizing cache).

Since HashArray based MethodTable is more space-efficient I moved the 
line between simple array based and HashArray based MethodTable down to 
20 elements to minimize the worst-case scenario effect. Calling 
getMethods() on all rt.jar classes now constructs about 3/4 simple array 
based and 1/4 HashArray based MethodTables.

Here's also Martin's ManyMethodsBenchmark:

Original:

Base class load time: 129.95 ms
getDeclaredMethods: 65521 methods, 36.58 ms total time, 0.0006 ms per method
getMethods        : 65530 methods, 47.43 ms total time, 0.0007 ms per method
Derived class load time: 32216.09 ms
getDeclaredMethods: 65521 methods, 35.05 ms total time, 0.0005 ms per method
getMethods        : 65530 methods, 8068.66 ms total time, 0.1231 ms per 
method


Patched (using HashArray based MethodTable):

Base class load time: 126.00 ms
getDeclaredMethods: 65521 methods, 36.83 ms total time, 0.0006 ms per method
getMethods        : 65530 methods, 45.08 ms total time, 0.0007 ms per method
Derived class load time: 31865.27 ms
getDeclaredMethods: 65521 methods, 35.01 ms total time, 0.0005 ms per method
getMethods        : 65530 methods, 78.05 ms total time, 0.0012 ms per method


All 86 jtreg test in java.lang/Class/ and java/lang/reflect/ still pass.


Regards, Peter