A very small issue: MethodTable.java:
697 while (i < hwm && next == null) next = methods[i++]; In my opinion the condition should be while (next == null && i < hwm) as next will be non-null on each invocation of next() and generally it's more likely to exit the loop. I suppose HashMapImpl is unused . HashArray.java: 82 Integer.highestOneBit(expectedMaxSize + (expectedMaxSize << 1)) This effectively multiples expectedMaxSize by 3, I guess you meant >> instead. Perhaps extra a method about effective capacity? I will take a deeper look a bit later. Stanimir On Wed, Nov 5, 2014 at 6:58 PM, Peter Levart <peter.lev...@gmail.com> wrote: > 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 > >
