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

[Stanimir Simeonoff]

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.
I suppose HashMapImpl is unused .

HashArray.java:
  82             Integer.highestOneBit(expectedMaxSize + (expectedMaxSize << 1))


This effectively multiples expectedMaxSize by 3, I guess you meant >>
instead.
Perhaps extra a method about effective capacity?

I will take a deeper look a bit later.

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