RFR: 8061950: Class.getMethods() exhibits quadratic time complexity
Peter Levart
peter.levart at gmail.com
Wed Apr 1 18:54:26 UTC 2015
On 03/31/2015 03:35 AM, Martin Buchholz wrote:
> Thanks, Peter.
>
> I've started making my way through these changes.
> It's too bad there's so much complexity here, but I can't come up with
> a simpler solution either.
> So we will probably submit something based on your latest webrev.
> I've collected minor changes into an mq patch to be applied on top of
> yours.
>
> http://cr.openjdk.java.net/~martin/Class.getMethods
> <http://cr.openjdk.java.net/%7Emartin/Class.getMethods>
>
> - need @library
> - it's => its
> - remove end tags
> - Remove => Removes
>
> Should we switch to using testng? I think yes.
Hi Martin,
For start I incorporated your javadoc changes. Here's new webrev
containing them:
http://cr.openjdk.java.net/~plevart/jdk9-dev/Class.getMethods/webrev.09/
I noticed the bug I have discovered a couple of months ago when
preparing this patch, has recently received priority P2:
https://bugs.openjdk.java.net/browse/JDK-8062389
I think I know how to fix that on top of this patch. But perhaps this
should be performed afterwards as a separate change. Currently this
patch retains the status-quo.
Regards, Peter
>
> More review later.
>
>
> On Sun, Mar 29, 2015 at 4:44 AM, Peter Levart <peter.levart at gmail.com
> <mailto:peter.levart at gmail.com>> wrote:
>
> 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/
> <http://cr.openjdk.java.net/%7Eplevart/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