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

Sat Nov 1 17:49:35 UTC 2014

Hi Martin,

On 10/30/2014 07:13 PM, Martin Buchholz wrote:
> Hi Peter!
>
> Thanks for all your hard work.
> Your patch is hard to digest, but some initial comments anyways:
>
> ---
>
> I'm surprised you got this much performance gain loading rt.jar methods.
>
> 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.

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

The question is where to draw the line. I have measured the time with a 
modified 
http://cr.openjdk.java.net/~plevart/jdk9-dev/Class.getMethods/GetAllRtMethods.java 
benchmark that executes with various MAX_ARRAY_SIZE values as it goes 
and results are pretty stable for MAX_ARRAY_SIZE up to about 90, then 
slowly start degrading (these results should not be compared with 
previous runs of this benchmark, since they are performed on a slightly 
slower computer - baseline for MAX_ARRAY_SIZE=-1 would be 0.70 seconds 
on my faster one which I don't have at the moment):

MAX_ARRAY_SIZE=-1: 494141 methods obtained in 0.774282398 seconds; 0 
ARRAY(s), 86614 HashMap(s)
MAX_ARRAY_SIZE=0: 494141 methods obtained in 0.767787858 seconds; 8742 
ARRAY(s), 77872 HashMap(s)
MAX_ARRAY_SIZE=1: 494141 methods obtained in 0.769671542 seconds; 16464 
ARRAY(s), 70150 HashMap(s)
MAX_ARRAY_SIZE=2: 494141 methods obtained in 0.770154629 seconds; 19855 
ARRAY(s), 66759 HashMap(s)
MAX_ARRAY_SIZE=3: 494141 methods obtained in 0.781438807 seconds; 22341 
ARRAY(s), 64273 HashMap(s)
MAX_ARRAY_SIZE=4: 494141 methods obtained in 0.768229468 seconds; 24006 
ARRAY(s), 62608 HashMap(s)
MAX_ARRAY_SIZE=5: 494141 methods obtained in 0.77067988 seconds; 25007 
ARRAY(s), 61607 HashMap(s)
MAX_ARRAY_SIZE=6: 494141 methods obtained in 0.766908937 seconds; 25600 
ARRAY(s), 61014 HashMap(s)
MAX_ARRAY_SIZE=7: 494141 methods obtained in 0.770945373 seconds; 26364 
ARRAY(s), 60250 HashMap(s)
MAX_ARRAY_SIZE=8: 494141 methods obtained in 0.769324065 seconds; 27089 
ARRAY(s), 59525 HashMap(s)
MAX_ARRAY_SIZE=9: 494141 methods obtained in 0.766438124 seconds; 47479 
ARRAY(s), 39135 HashMap(s)
MAX_ARRAY_SIZE=10: 494141 methods obtained in 0.76463966 seconds; 48738 
ARRAY(s), 37876 HashMap(s)
MAX_ARRAY_SIZE=11: 494141 methods obtained in 0.768795889 seconds; 51308 
ARRAY(s), 35306 HashMap(s)
MAX_ARRAY_SIZE=12: 494141 methods obtained in 0.764373936 seconds; 53262 
ARRAY(s), 33352 HashMap(s)
MAX_ARRAY_SIZE=13: 494141 methods obtained in 0.762611993 seconds; 55051 
ARRAY(s), 31563 HashMap(s)
MAX_ARRAY_SIZE=14: 494141 methods obtained in 0.762725072 seconds; 56013 
ARRAY(s), 30601 HashMap(s)
MAX_ARRAY_SIZE=15: 494141 methods obtained in 0.753798798 seconds; 57471 
ARRAY(s), 29143 HashMap(s)
MAX_ARRAY_SIZE=16: 494141 methods obtained in 0.757654008 seconds; 58561 
ARRAY(s), 28053 HashMap(s)
MAX_ARRAY_SIZE=17: 494141 methods obtained in 0.754389446 seconds; 59584 
ARRAY(s), 27030 HashMap(s)
MAX_ARRAY_SIZE=18: 494141 methods obtained in 0.757966162 seconds; 60535 
ARRAY(s), 26079 HashMap(s)
...
...
MAX_ARRAY_SIZE=82: 494141 methods obtained in 0.759516432 seconds; 83375 
ARRAY(s), 3239 HashMap(s)
MAX_ARRAY_SIZE=83: 494141 methods obtained in 0.763177438 seconds; 83406 
ARRAY(s), 3208 HashMap(s)
MAX_ARRAY_SIZE=84: 494141 methods obtained in 0.761280607 seconds; 83425 
ARRAY(s), 3189 HashMap(s)
MAX_ARRAY_SIZE=85: 494141 methods obtained in 0.77047745 seconds; 83444 
ARRAY(s), 3170 HashMap(s)
MAX_ARRAY_SIZE=86: 494141 methods obtained in 0.758688921 seconds; 83486 
ARRAY(s), 3128 HashMap(s)
MAX_ARRAY_SIZE=87: 494141 methods obtained in 0.759290368 seconds; 83500 
ARRAY(s), 3114 HashMap(s)
MAX_ARRAY_SIZE=88: 494141 methods obtained in 0.758998186 seconds; 83518 
ARRAY(s), 3096 HashMap(s)
MAX_ARRAY_SIZE=89: 494141 methods obtained in 0.759510168 seconds; 83581 
ARRAY(s), 3033 HashMap(s)
MAX_ARRAY_SIZE=90: 494141 methods obtained in 0.757445598 seconds; 83594 
ARRAY(s), 3020 HashMap(s)
MAX_ARRAY_SIZE=91: 494141 methods obtained in 0.759975452 seconds; 83617 
ARRAY(s), 2997 HashMap(s)
MAX_ARRAY_SIZE=92: 494141 methods obtained in 0.762257197 seconds; 83635 
ARRAY(s), 2979 HashMap(s)
MAX_ARRAY_SIZE=93: 494141 methods obtained in 0.759114441 seconds; 83702 
ARRAY(s), 2912 HashMap(s)
MAX_ARRAY_SIZE=94: 494141 methods obtained in 0.762578409 seconds; 83709 
ARRAY(s), 2905 HashMap(s)
MAX_ARRAY_SIZE=95: 494141 methods obtained in 0.759205774 seconds; 83724 
ARRAY(s), 2890 HashMap(s)
MAX_ARRAY_SIZE=96: 494141 methods obtained in 0.762559129 seconds; 83739 
ARRAY(s), 2875 HashMap(s)
MAX_ARRAY_SIZE=97: 494141 methods obtained in 0.764749586 seconds; 83754 
ARRAY(s), 2860 HashMap(s)
MAX_ARRAY_SIZE=98: 494141 methods obtained in 0.762137989 seconds; 83762 
ARRAY(s), 2852 HashMap(s)
MAX_ARRAY_SIZE=99: 494141 methods obtained in 0.761563792 seconds; 83886 
ARRAY(s), 2728 HashMap(s)
MAX_ARRAY_SIZE=100: 494141 methods obtained in 0.762560357 seconds; 
83965 ARRAY(s), 2649 HashMap(s)
MAX_ARRAY_SIZE=101: 494141 methods obtained in 0.763043115 seconds; 
83983 ARRAY(s), 2631 HashMap(s)
MAX_ARRAY_SIZE=102: 494141 methods obtained in 0.763149662 seconds; 
84073 ARRAY(s), 2541 HashMap(s)
MAX_ARRAY_SIZE=103: 494141 methods obtained in 0.762778262 seconds; 
84083 ARRAY(s), 2531 HashMap(s)
MAX_ARRAY_SIZE=104: 494141 methods obtained in 0.770542513 seconds; 
84103 ARRAY(s), 2511 HashMap(s)
MAX_ARRAY_SIZE=105: 494141 methods obtained in 0.764989499 seconds; 
84125 ARRAY(s), 2489 HashMap(s)
MAX_ARRAY_SIZE=106: 494141 methods obtained in 0.762698653 seconds; 
84155 ARRAY(s), 2459 HashMap(s)
MAX_ARRAY_SIZE=107: 494141 methods obtained in 0.764577549 seconds; 
84171 ARRAY(s), 2443 HashMap(s)
MAX_ARRAY_SIZE=108: 494141 methods obtained in 0.766050758 seconds; 
84190 ARRAY(s), 2424 HashMap(s)
MAX_ARRAY_SIZE=109: 494141 methods obtained in 0.763050679 seconds; 
84203 ARRAY(s), 2411 HashMap(s)
MAX_ARRAY_SIZE=110: 494141 methods obtained in 0.762198567 seconds; 
84217 ARRAY(s), 2397 HashMap(s)
...
...
MAX_ARRAY_SIZE=435: 494141 methods obtained in 0.92093385 seconds; 86594 
ARRAY(s), 20 HashMap(s)
MAX_ARRAY_SIZE=436: 494141 methods obtained in 0.923851043 seconds; 
86594 ARRAY(s), 20 HashMap(s)
MAX_ARRAY_SIZE=437: 494141 methods obtained in 0.920907745 seconds; 
86594 ARRAY(s), 20 HashMap(s)
MAX_ARRAY_SIZE=438: 494141 methods obtained in 0.92080572 seconds; 86594 
ARRAY(s), 20 HashMap(s)
MAX_ARRAY_SIZE=439: 494141 methods obtained in 0.921864791 seconds; 
86594 ARRAY(s), 20 HashMap(s)
MAX_ARRAY_SIZE=440: 494141 methods obtained in 0.925055685 seconds; 
86594 ARRAY(s), 20 HashMap(s)
MAX_ARRAY_SIZE=441: 494141 methods obtained in 0.921136685 seconds; 
86594 ARRAY(s), 20 HashMap(s)
MAX_ARRAY_SIZE=442: 494141 methods obtained in 0.923417116 seconds; 
86594 ARRAY(s), 20 HashMap(s)
MAX_ARRAY_SIZE=443: 494141 methods obtained in 0.924828923 seconds; 
86594 ARRAY(s), 20 HashMap(s)
MAX_ARRAY_SIZE=444: 494141 methods obtained in 0.92331634 seconds; 86594 
ARRAY(s), 20 HashMap(s)
MAX_ARRAY_SIZE=445: 494141 methods obtained in 0.923586046 seconds; 
86594 ARRAY(s), 20 HashMap(s)
MAX_ARRAY_SIZE=446: 494141 methods obtained in 0.923619987 seconds; 
86594 ARRAY(s), 20 HashMap(s)
MAX_ARRAY_SIZE=447: 494141 methods obtained in 0.925436079 seconds; 
86595 ARRAY(s), 19 HashMap(s)
MAX_ARRAY_SIZE=448: 494141 methods obtained in 0.926022715 seconds; 
86595 ARRAY(s), 19 HashMap(s)
MAX_ARRAY_SIZE=449: 494141 methods obtained in 0.931290541 seconds; 
86595 ARRAY(s), 19 HashMap(s)
MAX_ARRAY_SIZE=450: 494141 methods obtained in 0.926193262 seconds; 
86595 ARRAY(s), 19 HashMap(s)

So for common cases (rt.jar classes), the MAX_ARRAY_SIZE could be quite 
high, but there will always be worst-case scenarios that perform poorly 
with array based implementation. I'll try to spend some time 
constructing some of them and measuring the performance with array based 
implementation.

Array based MethodTable is about 32% better then original MethodArray 
for your ManyMethodsBenchmark, but still O(n^2) of course:

Original code:

Base class load time: 129.14 ms
getDeclaredMethods: Methods: 65521, Total time: 63.59 ms, Time per 
method: 0.0010 ms
getMethods        : Methods: 65530, Total time: 49.37 ms, Time per 
method: 0.0008 ms
Derived class load time: 33869.25 ms
getDeclaredMethods: Methods: 65521, Total time: 33.65 ms, Time per 
method: 0.0005 ms
getMethods        : Methods: 65530, Total time: 8290.76 ms, Time per 
method: 0.1265 ms

Patched (MethodTable with MAX_ARRAY_SIZE=Integer.MAX_VALUE):

Base class load time: 132.17 ms
getDeclaredMethods: Methods: 65521, Total time: 58.55 ms, Time per 
method: 0.0009 ms
getMethods        : Methods: 65530, Total time: 50.58 ms, Time per 
method: 0.0008 ms
Derived class load time: 33735.93 ms
getDeclaredMethods: Methods: 65521, Total time: 32.74 ms, Time per 
method: 0.0005 ms
getMethods        : Methods: 65530, Total time: 5601.14 ms, Time per 
method: 0.0855 ms

> ---
>
> (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?).

We could. Should I prepare a separate webrev for them?

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

Will correct this in next webrev.

Regards, Peter

>
>
> On Thu, Oct 30, 2014 at 9:53 AM, Peter Levart <peter.levart at gmail.com> wrote:
>> 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
>>