RFR: 8061950: Class.getMethods() exhibits quadratic time complexity
Peter Levart
peter.levart at gmail.com
Sun Mar 29 11:44:53 UTC 2015
Hi,
I'd like to resurrect a patch I did a couple of months ago. Here's a
rebased webrev (no changes from webrev.07):
http://cr.openjdk.java.net/~plevart/jdk9-dev/Class.getMethods/webrev.08/
Regards, Peter
On 03/23/2015 11:42 PM, Martin Buchholz wrote:
> So Peter, ... time to rebase one of your getMethods patches?
>
> On Mon, Dec 1, 2014 at 2:09 PM, Peter Levart <peter.levart at gmail.com
> <mailto:peter.levart at gmail.com>> wrote:
>
>
> 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> <mailto: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/ <http://cr.openjdk.java.net/%7Eplevart/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> <mailto:peter.levart at gmail.com> wrote:
>>>>
>>>>> Here's new webrev:
>>>>>
>>>>> http://cr.openjdk.java.net/~plevart/jdk9-dev/Class.getMethods/webrev.06/ <http://cr.openjdk.java.net/%7Eplevart/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
>>>>
>
>
More information about the core-libs-dev
mailing list