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