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

[Peter Levart]

Hi Joel,

I managed to find some time to create some tests for this patch:

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

Both MethodTable and HashArray unit tests are provided. I had to create 
a special TestProxy to access package-private classes from the tests.

There are no changes to j.l.Class or j.l.r.Method from webrev.06 (I just 
re-based them to current tip).

I also included the patch to StarInheritance test that I forgot to 
include in webrev.06.

Comments inline...

On 11/13/2014 10:39 AM, Joel Borggrén-Franck wrote:
> Hi Peter,
>
> As always, thanks for taking a look at this,
>
> This is quite big so in order to make this more approachable perhaps you can split the patch up into a series? If you start with creating the MethodTable interface, adding tests for how the interface should behave and refactored the current MethodArray into implementing that interface while also changing the lookup logic that would be easier to review.

Well, there's not much to refactor in MethodArray when implementing 
MethodTable. They are two entirely different APIs with entirely 
different implementations.

> Then you could add different implementations of MethodTable (with additional unit tests) as follow up patches.

You can view the MethodTable.SimpleArrayImpl as the basic implementation 
of the MethodTable API  and a replacement for MethodArray. 
MethodTable.HashArrayImpl is the alternative implementation for bigger 
sizes. The same unit tests are executed against both implementations.

> I am a bit concerned about the size and scope of the implementations. In general I would prefer if you targeted these to the precise need of core reflection today. If you want to expand these to general purpose data structures (even internal ones) I think that is a larger effort.

I stripped HashArray and only left those methods that are needed to 
implement MethodTable API and execute the tests.

> In general I think the changes to Class are sound, but there is a slight change in the default method pruning. The call to removeLessSpecifics was deliberately placed at the end, so that all default methods would be present (the algorithm is sensitive to the order of pair vise comparisons). Since we add methods in a deterministic order, I think consolidate() as you go should result in the same set of methods, but I haven’t 100% convinced myself of this just yet.

I think it results in the same methods. I haven't yet found an example 
where it would result in different set of methods. All JDK classes 
return same methods with current implementation as with patched one.

> Have you double checked that all methods returning root Method/Ctors are private?

I checked all usages of private methods that I have changed and are now 
returning root objects and made sure those are copied before being 
exposed to the outside or being modified.

Regards, Peter

> On 5 nov 2014, at 17:58, Peter Levart <peter.levart at gmail.com> wrote:
>
>> 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.
>>
> HashArray.java:
>
> I was hoping for a decent set of unit tests for the new HashArray<T> data structure. I think it is reasonable to test the corner cases/non-trivial areas of the table (closeDeletion(), rezise() etc). Perhaps also run these over the simple implementation. Also, please document thread safety (there is none IFAICT it should just be noted).
>
> Instead of using inheritance to change the behavior of equals() and hash() you could give it two lambdas at table creation time, a ToIntFunction<T> for hash() and a BiPredicate<T,T> for equals(). Might not give you the performance we need though.
>
> Note that the file doesn’t actually compile in jdk9/dev, you have two unchecked casts and we build with -Werror.
>
> MethodTable.java
>
> HashMapImpl is missing serialVersionUID, but it looks like this class won’t be needed at all.
>
>
>> 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.
>>
> I have seen discussion about allocation, should we measure and compare? You can probably use the Hotspot impl of ThreadMXBean to get the allocation in the tread.
>
> Also, it might be time to fix the boolean parameters:
>
> 2741         Method[] declaredMethods = privateGetDeclaredMethods(true);
> 2742         Class<?> superclass = getSuperclass();
> 2743         Class<?>[] interfaces = getInterfaces(false);
>
> Perhaps just add boolean constants somewhere so that it is easier to decode.
>
> 2741         Method[] declaredMethods = privateGetDeclaredMethods(PUBLIC_METHOD_ONLY);
> 2742         Class<?> superclass = getSuperclass();
> 2743         Class<?>[] interfaces = getInterfaces(NO_COPY_RESULT);
>
> or so.
>
> HashArray.java:
>
> 155         if (lookupObj == null) throw new NullPointerException();
>
> use Objects.requreNonNull() ?
>
> cheers
> /Joel
>