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

Thu Nov 6 07:36:27 UTC 2014

Hi Stanimir,

On 11/05/2014 07:27 PM, Stanimir Simeonoff wrote:
> A very small issue:
>
> MethodTable.java:
>
>   697                     while (i < hwm && next == null) next = methods[i++];
>
>
> In my opinion the condition should be while (next == null && i < hwm) as next
> will be non-null on each invocation of next() and generally it's more
> likely to exit the loop.

You're right, the conditions order should be reversed as the (i < hwm) 
is less likely than (next == null).

> I suppose HashMapImpl is unused .

That's right. If HashArrayImpl turns out to be an acceptable solution, 
I'll remove HashMapImpl.

>
> HashArray.java:
>    82             Integer.highestOneBit(expectedMaxSize + (expectedMaxSize << 1))
>
>
> This effectively multiples expectedMaxSize by 3, I guess you meant >>
> instead.

The intention of capacity(int expectedMaxSize) is to return the smallest 
power of 2 number that is greater than 3 * expectedMaxSize / 2.

The method is copied from IdentityHashMap, so I'm sure it does it right ;-)

> Perhaps extra a method about effective capacity?

Don't know what you mean by effective capacity? The capacity() is meant 
to size the initial array. And it behaves correctly even for large 
requested expectedMaxSize values that would cause an overflow in naively 
written code.

>
> I will take a deeper look a bit later.

Thanks.

Regards, Peter

>
> Stanimir
>
>
> On Wed, Nov 5, 2014 at 6:58 PM, Peter Levart <peter.levart at gmail.com> wrote:
>
>> 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
>>
>>