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

Joel Borggrén-Franck joel.franck at oracle.com
Thu Nov 13 09:39:58 UTC 2014

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. Then you could add different implementations of MethodTable (with additional unit tests) as follow up patches.

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.

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.

Have you double checked that all methods returning root Method/Ctors are private?

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.


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.


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.


155         if (lookupObj == null) throw new NullPointerException();

use Objects.requreNonNull() ?


More information about the core-libs-dev mailing list