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

[Peter Levart]

On 12/01/2014 09:09 PM, Martin Buchholz wrote:
> Looking at Peter's work here is still on my long TODO list, but I was
> hoping first to get in my concurrency correctness fixes for core
> reflection, which conflicts slightly...

No problem. I can rebase the patch after your fixes are in.

Regards, Peter

> On Sun, Nov 30, 2014 at 1:48 PM, Peter Levart <peter.levart at gmail.com> wrote:
>> 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
>>>