RFR: 8061950: Class.getMethods() exhibits quadratic time complexity
Martin Buchholz
martinrb at google.com
Tue Mar 31 01:35:38 UTC 2015
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
- need @library
- it's => its
- remove end tags
- Remove => Removes
Should we switch to using testng? I think yes.
More review later.
On Sun, Mar 29, 2015 at 4:44 AM, Peter Levart <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/
>
>
> 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>
> 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> <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> <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
>>
>>
>>
>>
>
>
More information about the core-libs-dev
mailing list