> >> HashArray.java: >> 82 Integer.highestOneBit(expectedMaxSize + >> (expectedMaxSize << 1)) >> >> >> This effectively multiples expectedMaxSize by 3, I guess you meant >> >> instead. >> > > The intention of capacity(int expectedMaxSize) is to return the smallest > power of 2 number that is greater than 3 * expectedMaxSize / 2. >
The method is copied from IdentityHashMap, so I'm sure it does it right ;-) > > Indeed it does so, it can lead to almost 3x times (i.e. fill factor of .33) waste for some numbers (11, 22, 43) . But I supposed it's a good tradeoff. > Perhaps extra a method about effective capacity? >> > > Don't know what you mean by effective capacity? The capacity() is meant to > size the initial array. And it behaves correctly even for large requested > expectedMaxSize values that would cause an overflow in naively written code. > > I meant to "extract" (not extra) a method for s + (s >> 1) but it's used once only, so please disregard this part. There is some code duplication in the different impl. of consolidate() but trying to refactor it (in a static method) would cause some performance degradation (I don't think there is an intrinsic for the native Class.isInterface()). So, I guess it can be left that way, as it's not too much. 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 >>> >>> >>> >
