On 11/01/2014 06:49 PM, Peter Levart wrote:
On 10/30/2014 07:13 PM, Martin Buchholz wrote:
Which is why I was expecting to have to write an adaptive
data structure that switches from linear search to hash-based when
some threshold is exceeded.
...or two data structures. Since I have already arranged so that
construction of MethodTable gets an upper limit on the total number of
possible Method(s) that can be added to it, we can have two
MethodTable implementations and switch based on this number:
http://cr.openjdk.java.net/~plevart/jdk9-dev/Class.getMethods/webrev.05/
Hi,
I made some progress on this front. I created new MethodTable
implementation (the third one) with similar performance as HashMap
based, but producing half the garbage. I also added some optimizations
to getMethod(), getMethods() and MethodTable in general that deal with
special cases / parameter types comparison and have measurable impact on
performance (for example loading all rt.jar classes and calling
getMethods() for them):
Original:
19658 classes loaded in 2.003623648 seconds.
494392 methods obtained in 0.932151066 seconds.
494392 methods obtained in 0.968247076 seconds.
494392 methods obtained in 0.989218185 seconds.
494392 methods obtained in 1.018700179 seconds.
494392 methods obtained in 0.945078767 seconds.
494392 methods obtained in 0.930856897 seconds.
494392 methods obtained in 0.905420555 seconds.
494392 methods obtained in 0.89253006 seconds.
494392 methods obtained in 0.914590141 seconds.
494392 methods obtained in 0.891616716 seconds.
494392 methods obtained in 0.891839815 seconds.
494392 methods obtained in 0.892863985 seconds.
494392 methods obtained in 0.960643274 seconds.
494392 methods obtained in 0.959266392 seconds.
494392 methods obtained in 0.894688322 seconds.
494392 methods obtained in 0.892751891 seconds.
494392 methods obtained in 0.912542838 seconds.
494392 methods obtained in 0.912219636 seconds.
494392 methods obtained in 0.895791468 seconds.
494392 methods obtained in 0.891673959 seconds.
Patched:
19658 classes loaded in 2.145270948 seconds.
494398 methods obtained in 0.722630874 seconds.
494398 methods obtained in 0.697521755 seconds.
494398 methods obtained in 0.689642554 seconds.
494398 methods obtained in 0.742724992 seconds.
494398 methods obtained in 0.695693313 seconds.
494398 methods obtained in 0.685169108 seconds.
494398 methods obtained in 0.663012634 seconds.
494398 methods obtained in 0.666446935 seconds.
494398 methods obtained in 0.675662884 seconds.
494398 methods obtained in 0.65369404 seconds.
494398 methods obtained in 0.656608178 seconds.
494398 methods obtained in 0.668384051 seconds.
494398 methods obtained in 0.657548957 seconds.
494398 methods obtained in 0.672332234 seconds.
494398 methods obtained in 0.655699295 seconds.
494398 methods obtained in 0.671819628 seconds.
494398 methods obtained in 0.657232183 seconds.
494398 methods obtained in 0.654462137 seconds.
494398 methods obtained in 0.659630473 seconds.
494398 methods obtained in 0.674219391 seconds.
(the difference in method count is expected - patched code contains new
methods in existing rt.jar classes ;-)
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.
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.
Regards, Peter
