Re: Loading classes with many methods is very expensive

[Peter Levart]

Sorry, I apologize. I'll start a new thread on core-libs only.

Peter

On 10/30/2014 10:47 AM, Aleksey Shipilev wrote:

Guys, can you please start a new RFR thread for Peter's change? You have
a bug ID now, and the discussion should be searchable by bug ID.

Also, you are spamming two aliases (corelibs + hotspot-runtime) instead
of one ;)

-Aleksey.

On 10/30/2014 12:43 PM, Peter Levart wrote:

On 10/30/2014 10:29 AM, Peter Levart wrote:

I might get away with excluding seq from hashCode computation and only
use it in equals(). This way Key(s) could be modified in-place
(hashCode would not change, entry would stay in same bucket), it would
just become equal to some other Key. Modification operations would
keep the invariant that there are no duplicate Key(s) at any time in
the Map. All entries sharing same method signature would end-up in the
same bucket (and maybe share it with entries that just happen to have
the same hashCode mod capacity) and we would get a similar linked list
of entries as with previous approach - only without another level of
indirection...

That would not work. I would have to have the Key object accessible.
Since Map does not have a getKey(key) operation, I would have to store
the Key as a value too. And we're back to MethodList approach...

Peter

Re: Loading classes with many methods is very expensive

[Aleksey Shipilev]

Guys, can you please start a new RFR thread for Peter's change? You have
a bug ID now, and the discussion should be searchable by bug ID.

Also, you are spamming two aliases (corelibs + hotspot-runtime) instead
of one ;)

-Aleksey.

On 10/30/2014 12:43 PM, Peter Levart wrote:
> On 10/30/2014 10:29 AM, Peter Levart wrote:
>> I might get away with excluding seq from hashCode computation and only
>> use it in equals(). This way Key(s) could be modified in-place
>> (hashCode would not change, entry would stay in same bucket), it would
>> just become equal to some other Key. Modification operations would
>> keep the invariant that there are no duplicate Key(s) at any time in
>> the Map. All entries sharing same method signature would end-up in the
>> same bucket (and maybe share it with entries that just happen to have
>> the same hashCode mod capacity) and we would get a similar linked list
>> of entries as with previous approach - only without another level of
>> indirection... 
> 
> That would not work. I would have to have the Key object accessible.
> Since Map does not have a getKey(key) operation, I would have to store
> the Key as a value too. And we're back to MethodList approach...
> 
> Peter
> 

Re: Loading classes with many methods is very expensive

[Peter Levart]

On 10/30/2014 10:29 AM, Peter Levart wrote:
I might get away with excluding seq from hashCode computation and only 
use it in equals(). This way Key(s) could be modified in-place 
(hashCode would not change, entry would stay in same bucket), it would 
just become equal to some other Key. Modification operations would 
keep the invariant that there are no duplicate Key(s) at any time in 
the Map. All entries sharing same method signature would end-up in the 
same bucket (and maybe share it with entries that just happen to have 
the same hashCode mod capacity) and we would get a similar linked list 
of entries as with previous approach - only without another level of 
indirection... 


That would not work. I would have to have the Key object accessible. 
Since Map does not have a getKey(key) operation, I would have to store 
the Key as a value too. And we're back to MethodList approach...


Peter

Re: Loading classes with many methods is very expensive

[Peter Levart]

Hi Stanimir,

On 10/30/2014 12:00 AM, Stanimir Simeonoff wrote:

Hi Peter,

The removal of value wrapper is a clever approach to reduce the new
instances created although it feels very unnatural (at least to me).


Number of objects created is practically the same. Previous approach 
used same MethodList instances for keys and values. New approach uses 
just Key instances, values are Methods themselves. It's allways 1 
additional object per Method, but new approach might use a couple of 
more Map.Entry objects (when multiple methods with same signature are 
present). New approach is different in that it was designed to keep the 
insertion order of Method(s) (LinkedHashMap), but you found out this is 
not true (below)...



  Small
optimization; eagerly calculate the hash in the c'tor,
hash =

  149 method.getReturnType().hashCode() ^
  150 System.identityHashCode(method.getName()) ^
  151 Arrays.hashCode(method.getParameterTypes()

and so the real int hashCode(){return seq+hash;}


Right, that would be an time/space trade-off. It might not be on 64bit 
arch - just on 32bit. I should check. Perhaps hashCode should not depend 
on seq (see below).




Also I am not sure if method.getName().hashCode() would be better or not,
if previously identityHashCode is not invoked on that string and depending
on the configured hashCode (-XX:hashCode) generator System.identityHashCode
might be slow or worse call C random() which doesn't scale. Setting the
hashCode requires a CAS too. CAS is of course one-time off but still


Thanks for pointing that out. I'll use String.hashCode() then.



About the order of the returned methods: if you remove and then put from/to
the LHM the order of iteration is going to be greatly altered. Is that ok?


Excelent point!

I might get away with excluding seq from hashCode computation and only 
use it in equals(). This way Key(s) could be modified in-place (hashCode 
would not change, entry would stay in same bucket), it would just become 
equal to some other Key. Modification operations would keep the 
invariant that there are no duplicate Key(s) at any time in the Map. All 
entries sharing same method signature would end-up in the same bucket 
(and maybe share it with entries that just happen to have the same 
hashCode mod capacity) and we would get a similar linked list of entries 
as with previous approach - only without another level of indirection...


Regards, Peter



Stanimir

On Wed, Oct 29, 2014 at 7:16 PM, Peter Levart 
wrote:


On 10/29/2014 02:08 PM, Joel Borggrén-Franck wrote:


Hi Peter,

I'm not entirely convinced this is a bug.

The lookup order for getMethod has for a long time been walk up
superclasses and return what you find there first without even looking at
interfaces. It might be desirable to change that but I'm not sure.


Hi Joel,

It has been for a long time like that as you say, but for a long time Java
did not have default methods. It's unexpected for getMethod() to return a
method that is not contained in getMethods() result.

Anyway, I have created a bug to track this:

https://bugs.openjdk.java.net/browse/JDK-8062389

For next iteration of the getMethods() O(n^2) fix, I used a slightly
different approach, which you might like more or not. Instead of using
linked-lists of Method objects as values of a LinkedHashMap I created a
special Key object, holding a reference to Method object and an additional
'seq' int field, which discriminates among methods with same signature.
Values of LinkedHashMap are Method objects themselves:

http://cr.openjdk.java.net/~plevart/jdk9-dev/Class.getMethods/webrev.03/

I have encapsulated this functionality into a package-private
java.lang.MethodTable. The implementation of this API can be easily changed
to using linked-lists as values of LinkedHashMap if desired. The
performance characteristics are similar, with hardly measurable advantage
of this latest approach as can be seen from http://cr.openjdk.java.net/~
plevart/jdk9-dev/Class.getMethods/GetAllRtMethods.java benchmark:

Original code:

19658 classes loaded in 2.071013902 seconds.
494392 methods obtained in 1.089983418 seconds.
494392 methods obtained in 0.952488497 seconds.
494392 methods obtained in 0.912878317 seconds.
494392 methods obtained in 0.940293784 seconds.
494392 methods obtained in 0.987640733 seconds.
494392 methods obtained in 0.925393355 seconds.
494392 methods obtained in 0.89397002 seconds.
494392 methods obtained in 0.915042463 seconds.
494392 methods obtained in 0.897669082 seconds.
494392 methods obtained in 0.878140502 seconds.

Patched code:

19658 classes loaded in 2.153024197 seconds.
494392 methods obtained in 0.875651469 seconds.
494392 methods obtained in 0.791937742 seconds.
494392 methods obtained in 0.780995693 seconds.
494392 methods obtained in 0.759593461 seconds.
494392 methods obtained in 0.766528355 seconds.
494392 methods obtained in 0.756567663 seconds.
494392 methods obtained in 0.7

Re: Loading classes with many methods is very expensive

[Stanimir Simeonoff]

Hi Peter,

The removal of value wrapper is a clever approach to reduce the new
instances created although it feels very unnatural (at least to me). Small
optimization; eagerly calculate the hash in the c'tor,
hash =

 149 method.getReturnType().hashCode() ^
 150 System.identityHashCode(method.getName()) ^
 151 Arrays.hashCode(method.getParameterTypes()

and so the real int hashCode(){return seq+hash;}

Also I am not sure if method.getName().hashCode() would be better or not,
if previously identityHashCode is not invoked on that string and depending
on the configured hashCode (-XX:hashCode) generator System.identityHashCode
might be slow or worse call C random() which doesn't scale. Setting the
hashCode requires a CAS too. CAS is of course one-time off but still

About the order of the returned methods: if you remove and then put from/to
the LHM the order of iteration is going to be greatly altered. Is that ok?

Stanimir

On Wed, Oct 29, 2014 at 7:16 PM, Peter Levart 
wrote:

> On 10/29/2014 02:08 PM, Joel Borggrén-Franck wrote:
>
>> Hi Peter,
>>
>> I'm not entirely convinced this is a bug.
>>
>> The lookup order for getMethod has for a long time been walk up
>> superclasses and return what you find there first without even looking at
>> interfaces. It might be desirable to change that but I'm not sure.
>>
>
> Hi Joel,
>
> It has been for a long time like that as you say, but for a long time Java
> did not have default methods. It's unexpected for getMethod() to return a
> method that is not contained in getMethods() result.
>
> Anyway, I have created a bug to track this:
>
> https://bugs.openjdk.java.net/browse/JDK-8062389
>
> For next iteration of the getMethods() O(n^2) fix, I used a slightly
> different approach, which you might like more or not. Instead of using
> linked-lists of Method objects as values of a LinkedHashMap I created a
> special Key object, holding a reference to Method object and an additional
> 'seq' int field, which discriminates among methods with same signature.
> Values of LinkedHashMap are Method objects themselves:
>
> http://cr.openjdk.java.net/~plevart/jdk9-dev/Class.getMethods/webrev.03/
>
> I have encapsulated this functionality into a package-private
> java.lang.MethodTable. The implementation of this API can be easily changed
> to using linked-lists as values of LinkedHashMap if desired. The
> performance characteristics are similar, with hardly measurable advantage
> of this latest approach as can be seen from http://cr.openjdk.java.net/~
> plevart/jdk9-dev/Class.getMethods/GetAllRtMethods.java benchmark:
>
> Original code:
>
> 19658 classes loaded in 2.071013902 seconds.
> 494392 methods obtained in 1.089983418 seconds.
> 494392 methods obtained in 0.952488497 seconds.
> 494392 methods obtained in 0.912878317 seconds.
> 494392 methods obtained in 0.940293784 seconds.
> 494392 methods obtained in 0.987640733 seconds.
> 494392 methods obtained in 0.925393355 seconds.
> 494392 methods obtained in 0.89397002 seconds.
> 494392 methods obtained in 0.915042463 seconds.
> 494392 methods obtained in 0.897669082 seconds.
> 494392 methods obtained in 0.878140502 seconds.
>
> Patched code:
>
> 19658 classes loaded in 2.153024197 seconds.
> 494392 methods obtained in 0.875651469 seconds.
> 494392 methods obtained in 0.791937742 seconds.
> 494392 methods obtained in 0.780995693 seconds.
> 494392 methods obtained in 0.759593461 seconds.
> 494392 methods obtained in 0.766528355 seconds.
> 494392 methods obtained in 0.756567663 seconds.
> 494392 methods obtained in 0.739177848 seconds.
> 494392 methods obtained in 0.729245613 seconds.
> 494392 methods obtained in 0.74081083 seconds.
> 494392 methods obtained in 0.731749505 seconds.
>
>
> Martin's ManyMethodsBenchmark shows this algorithm has O(n) time
> complexity too:
>
> Original:
>
> Base class load time: 131.95 ms
> getDeclaredMethods: 65521 methods, 32.00 ms total time, 0.0005 ms per
> method
> getMethods: 65530 methods, 44.24 ms total time, 0.0007 ms per
> method
> Derived class load time: 32525.23 ms
> getDeclaredMethods: 65521 methods, 30.37 ms total time, 0.0005 ms per
> method
> getMethods: 65530 methods, 7897.03 ms total time, 0.1205 ms per
> method
>
> Patched:
>
> Base class load time: 129.72 ms
> getDeclaredMethods: 65521 methods, 32.76 ms total time, 0.0005 ms per
> method
> getMethods: 65530 methods, 42.68 ms total time, 0.0007 ms per
> method
> Derived class load time: 31620.47 ms
> getDeclaredMethods: 65521 methods, 30.49 ms total time, 0.0005 ms per
> method
> getMethods: 65530 methods, 88.23 ms total time, 0.0013 ms per
> method
>
>
> I have also run Martin's LoadAllClassesAndMethods test (Thanks Martin, I
> changed it slightly so that exceptions are collected and reported at the
> end instead of bailing-out on first exception).
>
> Original LoadAllClassesAndMethods write classlist.txt:
>
> class load: 23052 classes, 1563.75 ms total time,

Re: Loading classes with many methods is very expensive

[Peter Levart]

On 10/29/2014 02:08 PM, Joel Borggrén-Franck wrote:

Hi Peter,

I’m not entirely convinced this is a bug.

The lookup order for getMethod has for a long time been walk up superclasses 
and return what you find there first without even looking at interfaces. It 
might be desirable to change that but I’m not sure.


Hi Joel,

It has been for a long time like that as you say, but for a long time 
Java did not have default methods. It's unexpected for getMethod() to 
return a method that is not contained in getMethods() result.


Anyway, I have created a bug to track this:

https://bugs.openjdk.java.net/browse/JDK-8062389

For next iteration of the getMethods() O(n^2) fix, I used a slightly 
different approach, which you might like more or not. Instead of using 
linked-lists of Method objects as values of a LinkedHashMap I created a 
special Key object, holding a reference to Method object and an 
additional 'seq' int field, which discriminates among methods with same 
signature. Values of LinkedHashMap are Method objects themselves:


http://cr.openjdk.java.net/~plevart/jdk9-dev/Class.getMethods/webrev.03/

I have encapsulated this functionality into a package-private 
java.lang.MethodTable. The implementation of this API can be easily 
changed to using linked-lists as values of LinkedHashMap if desired. The 
performance characteristics are similar, with hardly measurable 
advantage of this latest approach as can be seen from 
http://cr.openjdk.java.net/~plevart/jdk9-dev/Class.getMethods/GetAllRtMethods.java 
benchmark:


Original code:

19658 classes loaded in 2.071013902 seconds.
494392 methods obtained in 1.089983418 seconds.
494392 methods obtained in 0.952488497 seconds.
494392 methods obtained in 0.912878317 seconds.
494392 methods obtained in 0.940293784 seconds.
494392 methods obtained in 0.987640733 seconds.
494392 methods obtained in 0.925393355 seconds.
494392 methods obtained in 0.89397002 seconds.
494392 methods obtained in 0.915042463 seconds.
494392 methods obtained in 0.897669082 seconds.
494392 methods obtained in 0.878140502 seconds.

Patched code:

19658 classes loaded in 2.153024197 seconds.
494392 methods obtained in 0.875651469 seconds.
494392 methods obtained in 0.791937742 seconds.
494392 methods obtained in 0.780995693 seconds.
494392 methods obtained in 0.759593461 seconds.
494392 methods obtained in 0.766528355 seconds.
494392 methods obtained in 0.756567663 seconds.
494392 methods obtained in 0.739177848 seconds.
494392 methods obtained in 0.729245613 seconds.
494392 methods obtained in 0.74081083 seconds.
494392 methods obtained in 0.731749505 seconds.


Martin's ManyMethodsBenchmark shows this algorithm has O(n) time 
complexity too:


Original:

Base class load time: 131.95 ms
getDeclaredMethods: 65521 methods, 32.00 ms total time, 0.0005 ms per method
getMethods: 65530 methods, 44.24 ms total time, 0.0007 ms per method
Derived class load time: 32525.23 ms
getDeclaredMethods: 65521 methods, 30.37 ms total time, 0.0005 ms per method
getMethods: 65530 methods, 7897.03 ms total time, 0.1205 ms per 
method


Patched:

Base class load time: 129.72 ms
getDeclaredMethods: 65521 methods, 32.76 ms total time, 0.0005 ms per method
getMethods: 65530 methods, 42.68 ms total time, 0.0007 ms per method
Derived class load time: 31620.47 ms
getDeclaredMethods: 65521 methods, 30.49 ms total time, 0.0005 ms per method
getMethods: 65530 methods, 88.23 ms total time, 0.0013 ms per method


I have also run Martin's LoadAllClassesAndMethods test (Thanks Martin, I 
changed it slightly so that exceptions are collected and reported at the 
end instead of bailing-out on first exception).


Original LoadAllClassesAndMethods write classlist.txt:

class load: 23052 classes, 1563.75 ms total time, 0.0678 ms per class
4 exceptions encountered:
  java.lang.IncompatibleClassChangeError: 
jdk.nashorn.internal.codegen.CompilationPhase$10 and 
jdk.nashorn.internal.codegen.CompilationPhase$10$1 disagree on 
InnerClasses attribute
  java.lang.IncompatibleClassChangeError: 
jdk.nashorn.internal.codegen.CompilationPhase$5 and 
jdk.nashorn.internal.codegen.CompilationPhase$5$1 disagree on 
InnerClasses attribute
  java.lang.IncompatibleClassChangeError: 
java.security.ProtectionDomain$3 and java.security.ProtectionDomain$3$1 
disagree on InnerClasses attribute
  java.lang.IncompatibleClassChangeError: java.lang.Compiler and 
java.lang.Compiler$1 disagree on InnerClasses attribute

getMethods: 23052 classes, 831.87 ms total time, 0.0361 ms per class

Patched LoadAllClassesAndMethods diff classlist.txt:

class load: 23051 classes, 1596.58 ms total time, 0.0693 ms per class
5 exceptions encountered:
  java.lang.IncompatibleClassChangeError: 
jdk.nashorn.internal.codegen.CompilationPhase$10 and 
jdk.nashorn.internal.codegen.CompilationPhase$10$1 disagree on 
InnerClasses attribute
  java.lang.IncompatibleClassChangeError: 
jdk.nashorn.internal.codegen.CompilationPhase$5 and 
jdk.nashorn.int

Re: Loading classes with many methods is very expensive

[Joel Borggrén-Franck]

Hi Peter,

I’m not entirely convinced this is a bug.

The lookup order for getMethod has for a long time been walk up superclasses 
and return what you find there first without even looking at interfaces. It 
might be desirable to change that but I’m not sure.

cheers
/Joel

On 29 okt 2014, at 12:26, Peter Levart  wrote:

> Hi Joel,
> 
> I found an inconsistency between getMethod() and getMethods() results that is 
> present in current JDK8/9 code and in my latest webrev.02. The following 
> program:
> 
> import java.util.stream.Collectors;
> import java.util.stream.Stream;
> 
> public class GetMethodTest {
> 
>static void test(Class clazz) throws Exception {
> 
>System.out.println(clazz.getName() + ".class.getMethods():  " +
>   Stream
>   .of(clazz.getMethods())
>   .filter(m -> m.getDeclaringClass() != 
> Object.class)
>   .collect(Collectors.toList()));
> 
>System.out.println(clazz.getName() + ".class.getMethod(\"m\"): " +
>   clazz.getMethod("m"));
> 
>System.out.println();
>}
> 
>public static void main(String[] args) throws Exception {
>test(I.class);
>test(J.class);
>test(A.class);
>test(B.class);
>}
> }
> 
> interface I {
>void m();
> }
> 
> interface J extends I {
>default void m() {}
> }
> 
> abstract class A implements I {}
> 
> abstract class B extends A implements J {}
> 
> 
> prints:
> 
> I.class.getMethods():  [public abstract void I.m()]
> I.class.getMethod("m"): public abstract void I.m()
> 
> J.class.getMethods():  [public default void J.m()]
> J.class.getMethod("m"): public default void J.m()
> 
> A.class.getMethods():  [public abstract void I.m()]
> A.class.getMethod("m"): public abstract void I.m()
> 
> B.class.getMethods():  [public default void J.m()]
> B.class.getMethod("m"): public abstract void I.m()
> 
> B.class.getMethods() reports default method J.m() (which I think is correct), 
> but B.class.getMethod("m") reports the abstract I.m() inherited from A, 
> because here the getMethod0() algorithm stops searching for and consolidating 
> any methods in (super)interfaces. Do you agree that this is a bug?
> 
> 
> Regards, Peter
> 
> On 10/27/2014 02:45 PM, Joel Borggrén-Franck wrote:
>> Hi Peter,
>> 
>> As always, thanks for doing this! It has been on my todolist for a while but 
>> never quite bubbling up to the top.
>> 
>> I don’t have time to look att his right now, but I expect to have some free 
>> time next week, but i have two short comments
>> 
>> First, I have been thinking about moving MethodArray to its’s own top-level 
>> class, isn’t it about time?
>> 
>> Second I would expect testing for the missing cases you uncovered (good 
>> catch!).
>> 
>> I’ll try to get back to you asap.
>> 
>> cheers
>> /Joel
>> 
>> 
>> On 26 okt 2014, at 23:53, Peter Levart  wrote:
>> 
>>> On 10/26/2014 09:25 PM, Peter Levart wrote:
 19657 classes loaded in 1.987373401 seconds.
 494141 methods obtained in 1.02493941 seconds.
 
 vs.
 
 19657 classes loaded in 2.084409717 seconds.
 494124 methods obtained in 0.915928578 seconds.
>>> Hi,
>>> 
>>> As you might have noticed, the number of methods obtained from patched code 
>>> differed from original code. I have investigated this and found that 
>>> original code treats abstract class methods the same as abstract interface 
>>> methods as far as multiple inheritance is concerned (it keeps them together 
>>> in the returned array). So I fixed this and here's new webrev which behaves 
>>> the same as original code:
>>> 
>>> http://cr.openjdk.java.net/~plevart/jdk9-dev/Class.getMethods/webrev.02/
>>> 
>>> Comparing original vs. patched code still shows speed-up:
>>> 
>>> Original:
>>> 
>>> 19657 classes loaded in 1.980493029 seconds.
>>> 494141 methods obtained in 0.976318927 seconds.
>>> 494141 methods obtained in 0.886504437 seconds.
>>> 494141 methods obtained in 0.911153722 seconds.
>>> 494141 methods obtained in 0.880550509 seconds.
>>> 494141 methods obtained in 0.875526704 seconds.
>>> 494141 methods obtained in 0.877258894 seconds.
>>> 494141 methods obtained in 0.871794344 seconds.
>>> 494141 methods obtained in 0.884159644 seconds.
>>> 494141 methods obtained in 0.892648522 seconds.
>>> 494141 methods obtained in 0.884581841 seconds.
>>> 
>>> Patched:
>>> 
>>> 19657 classes loaded in 2.055697675 seconds.
>>> 494141 methods obtained in 0.853922188 seconds.
>>> 494141 methods obtained in 0.776203794 seconds.
>>> 494141 methods obtained in 0.858774803 seconds.
>>> 494141 methods obtained in 0.778178867 seconds.
>>> 494141 methods obtained in 0.760043997 seconds.
>>> 494141 methods obtained in 0.756352444 seconds.
>>> 494141 methods obtained in 0.740826372 seconds.
>>> 494141 methods obtained in 0.744264782 seconds.
>>> 494141 methods obtained in 0.73805894 seconds.
>>> 494141 methods obtained in 0.746852752

Re: Loading classes with many methods is very expensive

[Peter Levart]

Hi Joel,

I found an inconsistency between getMethod() and getMethods() results 
that is present in current JDK8/9 code and in my latest webrev.02. The 
following program:


import java.util.stream.Collectors;
import java.util.stream.Stream;

public class GetMethodTest {

static void test(Class clazz) throws Exception {

System.out.println(clazz.getName() + ".class.getMethods():  " +
   Stream
   .of(clazz.getMethods())
   .filter(m -> m.getDeclaringClass() != 
Object.class)

   .collect(Collectors.toList()));

System.out.println(clazz.getName() + ".class.getMethod(\"m\"): " +
   clazz.getMethod("m"));

System.out.println();
}

public static void main(String[] args) throws Exception {
test(I.class);
test(J.class);
test(A.class);
test(B.class);
}
}

interface I {
void m();
}

interface J extends I {
default void m() {}
}

abstract class A implements I {}

abstract class B extends A implements J {}


prints:

I.class.getMethods():  [public abstract void I.m()]
I.class.getMethod("m"): public abstract void I.m()

J.class.getMethods():  [public default void J.m()]
J.class.getMethod("m"): public default void J.m()

A.class.getMethods():  [public abstract void I.m()]
A.class.getMethod("m"): public abstract void I.m()

B.class.getMethods():  [public default void J.m()]
B.class.getMethod("m"): public abstract void I.m()

B.class.getMethods() reports default method J.m() (which I think is 
correct), but B.class.getMethod("m") reports the abstract I.m() 
inherited from A, because here the getMethod0() algorithm stops 
searching for and consolidating any methods in (super)interfaces. Do you 
agree that this is a bug?



Regards, Peter

On 10/27/2014 02:45 PM, Joel Borggrén-Franck wrote:

Hi Peter,

As always, thanks for doing this! It has been on my todolist for a while but 
never quite bubbling up to the top.

I don’t have time to look att his right now, but I expect to have some free 
time next week, but i have two short comments

First, I have been thinking about moving MethodArray to its’s own top-level 
class, isn’t it about time?

Second I would expect testing for the missing cases you uncovered (good catch!).

I’ll try to get back to you asap.

cheers
/Joel


On 26 okt 2014, at 23:53, Peter Levart  wrote:


On 10/26/2014 09:25 PM, Peter Levart wrote:

19657 classes loaded in 1.987373401 seconds.
494141 methods obtained in 1.02493941 seconds.

vs.

19657 classes loaded in 2.084409717 seconds.
494124 methods obtained in 0.915928578 seconds.

Hi,

As you might have noticed, the number of methods obtained from patched code 
differed from original code. I have investigated this and found that original 
code treats abstract class methods the same as abstract interface methods as 
far as multiple inheritance is concerned (it keeps them together in the 
returned array). So I fixed this and here's new webrev which behaves the same 
as original code:

http://cr.openjdk.java.net/~plevart/jdk9-dev/Class.getMethods/webrev.02/

Comparing original vs. patched code still shows speed-up:

Original:

19657 classes loaded in 1.980493029 seconds.
494141 methods obtained in 0.976318927 seconds.
494141 methods obtained in 0.886504437 seconds.
494141 methods obtained in 0.911153722 seconds.
494141 methods obtained in 0.880550509 seconds.
494141 methods obtained in 0.875526704 seconds.
494141 methods obtained in 0.877258894 seconds.
494141 methods obtained in 0.871794344 seconds.
494141 methods obtained in 0.884159644 seconds.
494141 methods obtained in 0.892648522 seconds.
494141 methods obtained in 0.884581841 seconds.

Patched:

19657 classes loaded in 2.055697675 seconds.
494141 methods obtained in 0.853922188 seconds.
494141 methods obtained in 0.776203794 seconds.
494141 methods obtained in 0.858774803 seconds.
494141 methods obtained in 0.778178867 seconds.
494141 methods obtained in 0.760043997 seconds.
494141 methods obtained in 0.756352444 seconds.
494141 methods obtained in 0.740826372 seconds.
494141 methods obtained in 0.744264782 seconds.
494141 methods obtained in 0.73805894 seconds.
494141 methods obtained in 0.746852752 seconds.


55 java/lang/reflect jtreg tests still pass. As they did before, which means 
that we don't have a coverage for such cases. I'll see where I can add such a 
case (EnumSet for example, which inherits from Set interface and 
AbstractColection class via two different paths, so Set.size()/iterator() and 
AbstractCollection.size()/iterator() are both returned from getMethods())...


Regards, Peter

Re: Loading classes with many methods is very expensive

[Jeremy Manson]

Jeremy has already filed a bug (8062116), and is just finishing up the
patch (I jumped the gun a bit by attaching it to the bug - it has a few
bugs in it).  I'll probably have something in reasonable shape to review
tomorrow (I've submitted it internally, and I want to let it spend a day or
so having our test infrastructure throw things at it).

It's actually a JVMTI performance regression.  The data structure that is
being used to store jmethodids isn't great.  I've refactored it a bit to
improve its performance, but it should really be a closed hash table.
There isn't a handy one in HS, so I just made it O(1) for writes.  It's
still O(n) for reads, though, which is nasty.

We can have the real conversation when I post the RFR, though.

Jeremy

On Mon, Oct 27, 2014 at 12:45 PM, Aleksey Shipilev <
aleksey.shipi...@oracle.com> wrote:

> On 27.10.2014 22:01, Martin Buchholz wrote:
> > I'm having trouble keeping up with this thread I started, but I did
> > update the test/benchmark
> >
> http://cr.openjdk.java.net/~martin/webrevs/openjdk9/Class.getMethods-benchmark/
> > <
> http://cr.openjdk.java.net/%7Emartin/webrevs/openjdk9/Class.getMethods-benchmark/
> >
> >
> > I added a test *LoadAllClassesAndMethods *that does what its name says.
> > Although originally written as just a benchmark,
>
> In our recent Nashorn classloading work, we did this benchmark:
>  http://cr.openjdk.java.net/~shade/8053904/ClassLoaderBenchmark.java
>
> ...which, I think can be easily exploded to call getMethods() as well.
>
>
> > Jeremy is independently working on yet another performance problem
> > exposed by *LoadAllClassesAndMethods*
>
> Does Jeremy have a reportable outline? Submit the bug to make this
> thread short :)
>
>
> Thanks,
> -Aleksey.
>
>
>

Re: Loading classes with many methods is very expensive

[Aleksey Shipilev]

On 27.10.2014 22:01, Martin Buchholz wrote:
> I'm having trouble keeping up with this thread I started, but I did
> update the test/benchmark
> http://cr.openjdk.java.net/~martin/webrevs/openjdk9/Class.getMethods-benchmark/
> 
> 
> I added a test *LoadAllClassesAndMethods *that does what its name says. 
> Although originally written as just a benchmark, 

In our recent Nashorn classloading work, we did this benchmark:
 http://cr.openjdk.java.net/~shade/8053904/ClassLoaderBenchmark.java

...which, I think can be easily exploded to call getMethods() as well.


> Jeremy is independently working on yet another performance problem
> exposed by *LoadAllClassesAndMethods*

Does Jeremy have a reportable outline? Submit the bug to make this
thread short :)


Thanks,
-Aleksey.

Re: Loading classes with many methods is very expensive

[Martin Buchholz]

I'm having trouble keeping up with this thread I started, but I did update
the test/benchmark
http://cr.openjdk.java.net/~martin/webrevs/openjdk9/Class.getMethods-benchmark/

I added a test *LoadAllClassesAndMethods *that does what its name says.
Although originally written as just a benchmark, it also checks "en
passant" that all classes in all JRE jar files can be loaded.
Interestingly, openjdk9 passes this test, but proprietary Oracle JDK fails
it.  I think this is a useful packaging-level test of the entire JDK as
well.

java.lang.NoClassDefFoundError: Failed to load
jfxrt.jar(com/sun/deploy/uitoolkit/impl/fx/FXApplet2Adapter$1.class)
at
LoadAllClassesAndMethods.loadAllExtensionClasses(LoadAllClassesAndMethods.java:178)
at
LoadAllClassesAndMethods.methodsByClass(LoadAllClassesAndMethods.java:198)
at LoadAllClassesAndMethods.main(LoadAllClassesAndMethods.java:65)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at
sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
at
sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
at java.lang.reflect.Method.invoke(Method.java:498)
at com.sun.javatest.regtest.MainWrapper$MainThread.run(MainWrapper.java:94)
at java.lang.Thread.run(Thread.java:745)
Caused by: java.lang.NoClassDefFoundError:
com/sun/deploy/uitoolkit/Applet2Adapter
at java.lang.ClassLoader.defineClass1(Native Method)

Jeremy is independently working on yet another performance problem exposed
by *LoadAllClassesAndMethods*


On Mon, Oct 27, 2014 at 8:48 AM, Aleksey Shipilev <
aleksey.shipi...@oracle.com> wrote:

> Hi Peter,
>
> On 10/27/2014 03:45 PM, Peter Levart wrote:
> > I merged the functionality of the method-signature-key with the
> > linked-list node, holding just a reference to Method object and a link
> > to 'next' node. I think this is the most compact temporary datastructure
> > representation for that purpose that leverages standard LinkedHashMap.
>
> I see. I wonder when somebody come with a stress test using multiple
> interfaces with the same signature method :) Seems very unlikely.
>
>
> >>   * Formatting and logic in MethodList.consolidateWith gives me chills.
> I
> >> think at very least introducing variables for m.getDeclaringClass() and
> >> ml.m.getDeclaringClass() improve readability. Also, moving the comments
> >> at the end of the line should improve readability and better highlight
> >> the boolean expression you are spelling out. Below is the
> >> straight-forward rewrite:
> >> ...
> >
> > Excellent. I'll take your formatting if you don't mind ;-)
>
> Sure. Check if I had captured it right first. I think we need to be more
> strict with parentheses to avoid precedence overlooks:
>   (A || B && C) should better be ((A || B) && C) or (A || (B && C))
>
>
> >>* Should we use just methods.put() here?
> >>2851 MethodList ml0 = methods.putIfAbsent(ml, ml);
> >
> > It really doesn't matter as the exception is thrown if (ml0 != null) and
> > LinkedHashMap is forgotten...
> >
> > if (ml0 == null), put and putIfAbsent are equivalent. I used putIfAbsent
> > to make the 3 loops (declared methods, superclass methods,
> > (super)interface methods) more uniform.
>
> Okay.
>
>
> >>
> >>* I wonder if the code would be simpler if we push the
> Map >> MethodList> maintenance to some internal utility class? That would
> >> probably simplify the loops in privateGetPublicMethods?
> >
> > I thought MethodList.add()/consolidateWith() were close to those utility
> > methods. I could extract the logic in each of 3 loops to 3 void methods
> > taking 'methods' Map and a Method instance, but I don't want to pollute
> > the method namespace in j.l.Class any more than necessary and making a
> > special inner class for that is an overkill. Previously the holder for
> > such methods was MethodArray, but it's gone now. I could subclass
> > LinkedHashMap if I wanted to avoid an unnecessary indirection, but
> > that's not a good practice. It's not that bad as it is - 38 lines of
> > code for 3 loops with comments and spacing. I could improve comments
> > though...
>
> Yes. I had to read the entire thing a couple of times to understand how
> this works. Containing most of the logic into MethodList seems like a
> way to improve this. Not sure though.
>
>
> Thanks,
> -Aleksey.
>
>
>

Re: Loading classes with many methods is very expensive

[Aleksey Shipilev]

Hi Peter,

On 10/27/2014 03:45 PM, Peter Levart wrote:
> I merged the functionality of the method-signature-key with the
> linked-list node, holding just a reference to Method object and a link
> to 'next' node. I think this is the most compact temporary datastructure
> representation for that purpose that leverages standard LinkedHashMap.

I see. I wonder when somebody come with a stress test using multiple
interfaces with the same signature method :) Seems very unlikely.


>>   * Formatting and logic in MethodList.consolidateWith gives me chills. I
>> think at very least introducing variables for m.getDeclaringClass() and
>> ml.m.getDeclaringClass() improve readability. Also, moving the comments
>> at the end of the line should improve readability and better highlight
>> the boolean expression you are spelling out. Below is the
>> straight-forward rewrite:
>> ...
> 
> Excellent. I'll take your formatting if you don't mind ;-)

Sure. Check if I had captured it right first. I think we need to be more
strict with parentheses to avoid precedence overlooks:
  (A || B && C) should better be ((A || B) && C) or (A || (B && C))


>>* Should we use just methods.put() here?
>>2851 MethodList ml0 = methods.putIfAbsent(ml, ml);
> 
> It really doesn't matter as the exception is thrown if (ml0 != null) and
> LinkedHashMap is forgotten...
> 
> if (ml0 == null), put and putIfAbsent are equivalent. I used putIfAbsent
> to make the 3 loops (declared methods, superclass methods,
> (super)interface methods) more uniform.

Okay.


>>
>>* I wonder if the code would be simpler if we push the Map> MethodList> maintenance to some internal utility class? That would
>> probably simplify the loops in privateGetPublicMethods?
> 
> I thought MethodList.add()/consolidateWith() were close to those utility
> methods. I could extract the logic in each of 3 loops to 3 void methods
> taking 'methods' Map and a Method instance, but I don't want to pollute
> the method namespace in j.l.Class any more than necessary and making a
> special inner class for that is an overkill. Previously the holder for
> such methods was MethodArray, but it's gone now. I could subclass
> LinkedHashMap if I wanted to avoid an unnecessary indirection, but
> that's not a good practice. It's not that bad as it is - 38 lines of
> code for 3 loops with comments and spacing. I could improve comments
> though...

Yes. I had to read the entire thing a couple of times to understand how
this works. Containing most of the logic into MethodList seems like a
way to improve this. Not sure though.


Thanks,
-Aleksey.

Re: Loading classes with many methods is very expensive

[Peter Levart]

Hi Joel,

Thanks for peeking into the code.

On 10/27/2014 02:45 PM, Joel Borggrén-Franck wrote:

Hi Peter,

As always, thanks for doing this! It has been on my todolist for a while but 
never quite bubbling up to the top.

I don’t have time to look att his right now, but I expect to have some free 
time next week, but i have two short comments

First, I have been thinking about moving MethodArray to its’s own top-level 
class, isn’t it about time?


Well, you're the second (first was Aleksey) to comment on factoring away 
the logic into a separate class. I'll do that then.




Second I would expect testing for the missing cases you uncovered (good catch!).


I plan to add a case or two to appropriate test. I'm thinking about 
test/java/lang/Class/getMethods/StarInheritance.java ...




I’ll try to get back to you asap.


Thank you,

Peter



cheers
/Joel


On 26 okt 2014, at 23:53, Peter Levart  wrote:


On 10/26/2014 09:25 PM, Peter Levart wrote:

19657 classes loaded in 1.987373401 seconds.
494141 methods obtained in 1.02493941 seconds.

vs.

19657 classes loaded in 2.084409717 seconds.
494124 methods obtained in 0.915928578 seconds.

Hi,

As you might have noticed, the number of methods obtained from patched code 
differed from original code. I have investigated this and found that original 
code treats abstract class methods the same as abstract interface methods as 
far as multiple inheritance is concerned (it keeps them together in the 
returned array). So I fixed this and here's new webrev which behaves the same 
as original code:

http://cr.openjdk.java.net/~plevart/jdk9-dev/Class.getMethods/webrev.02/

Comparing original vs. patched code still shows speed-up:

Original:

19657 classes loaded in 1.980493029 seconds.
494141 methods obtained in 0.976318927 seconds.
494141 methods obtained in 0.886504437 seconds.
494141 methods obtained in 0.911153722 seconds.
494141 methods obtained in 0.880550509 seconds.
494141 methods obtained in 0.875526704 seconds.
494141 methods obtained in 0.877258894 seconds.
494141 methods obtained in 0.871794344 seconds.
494141 methods obtained in 0.884159644 seconds.
494141 methods obtained in 0.892648522 seconds.
494141 methods obtained in 0.884581841 seconds.

Patched:

19657 classes loaded in 2.055697675 seconds.
494141 methods obtained in 0.853922188 seconds.
494141 methods obtained in 0.776203794 seconds.
494141 methods obtained in 0.858774803 seconds.
494141 methods obtained in 0.778178867 seconds.
494141 methods obtained in 0.760043997 seconds.
494141 methods obtained in 0.756352444 seconds.
494141 methods obtained in 0.740826372 seconds.
494141 methods obtained in 0.744264782 seconds.
494141 methods obtained in 0.73805894 seconds.
494141 methods obtained in 0.746852752 seconds.


55 java/lang/reflect jtreg tests still pass. As they did before, which means 
that we don't have a coverage for such cases. I'll see where I can add such a 
case (EnumSet for example, which inherits from Set interface and 
AbstractColection class via two different paths, so Set.size()/iterator() and 
AbstractCollection.size()/iterator() are both returned from getMethods())...


Regards, Peter

Re: Loading classes with many methods is very expensive

[Joel Borggrén-Franck]

Hi Peter,

As always, thanks for doing this! It has been on my todolist for a while but 
never quite bubbling up to the top.

I don’t have time to look att his right now, but I expect to have some free 
time next week, but i have two short comments 

First, I have been thinking about moving MethodArray to its’s own top-level 
class, isn’t it about time?

Second I would expect testing for the missing cases you uncovered (good catch!).

I’ll try to get back to you asap.

cheers
/Joel


On 26 okt 2014, at 23:53, Peter Levart  wrote:

> 
> On 10/26/2014 09:25 PM, Peter Levart wrote:
>> 19657 classes loaded in 1.987373401 seconds.
>> 494141 methods obtained in 1.02493941 seconds.
>> 
>> vs.
>> 
>> 19657 classes loaded in 2.084409717 seconds.
>> 494124 methods obtained in 0.915928578 seconds.
> 
> Hi,
> 
> As you might have noticed, the number of methods obtained from patched code 
> differed from original code. I have investigated this and found that original 
> code treats abstract class methods the same as abstract interface methods as 
> far as multiple inheritance is concerned (it keeps them together in the 
> returned array). So I fixed this and here's new webrev which behaves the same 
> as original code:
> 
> http://cr.openjdk.java.net/~plevart/jdk9-dev/Class.getMethods/webrev.02/
> 
> Comparing original vs. patched code still shows speed-up:
> 
> Original:
> 
> 19657 classes loaded in 1.980493029 seconds.
> 494141 methods obtained in 0.976318927 seconds.
> 494141 methods obtained in 0.886504437 seconds.
> 494141 methods obtained in 0.911153722 seconds.
> 494141 methods obtained in 0.880550509 seconds.
> 494141 methods obtained in 0.875526704 seconds.
> 494141 methods obtained in 0.877258894 seconds.
> 494141 methods obtained in 0.871794344 seconds.
> 494141 methods obtained in 0.884159644 seconds.
> 494141 methods obtained in 0.892648522 seconds.
> 494141 methods obtained in 0.884581841 seconds.
> 
> Patched:
> 
> 19657 classes loaded in 2.055697675 seconds.
> 494141 methods obtained in 0.853922188 seconds.
> 494141 methods obtained in 0.776203794 seconds.
> 494141 methods obtained in 0.858774803 seconds.
> 494141 methods obtained in 0.778178867 seconds.
> 494141 methods obtained in 0.760043997 seconds.
> 494141 methods obtained in 0.756352444 seconds.
> 494141 methods obtained in 0.740826372 seconds.
> 494141 methods obtained in 0.744264782 seconds.
> 494141 methods obtained in 0.73805894 seconds.
> 494141 methods obtained in 0.746852752 seconds.
> 
> 
> 55 java/lang/reflect jtreg tests still pass. As they did before, which means 
> that we don't have a coverage for such cases. I'll see where I can add such a 
> case (EnumSet for example, which inherits from Set interface and 
> AbstractColection class via two different paths, so Set.size()/iterator() and 
> AbstractCollection.size()/iterator() are both returned from getMethods())...
> 
> 
> Regards, Peter
> 

Re: Loading classes with many methods is very expensive

[Peter Levart]

Hi Aleksey,

On 10/27/2014 12:23 PM, Aleksey Shipilev wrote:

On 10/27/2014 01:53 AM, Peter Levart wrote:

As you might have noticed, the number of methods obtained from patched
code differed from original code. I have investigated this and found
that original code treats abstract class methods the same as abstract
interface methods as far as multiple inheritance is concerned (it keeps
them together in the returned array). So I fixed this and here's new
webrev which behaves the same as original code:

http://cr.openjdk.java.net/~plevart/jdk9-dev/Class.getMethods/webrev.02/

This seems to be a candidate fix for
https://bugs.openjdk.java.net/browse/JDK-8061950, right? If so, please
assign yourself there. It might be advisable to start the separate RFR
thread for a fix?


That's exactly the issue I was looking for. I assigned it to myself.

Thanks for looking at the code...



My comments for the first reading of the patch:

  * Why MethodList maintains the linked list? Doesn't O(n)
MethodList.add() lead to quadratic complexity again? Should we instead
use the ArrayList for storing method synonyms?


It's not quadratic, but more O(n*m) where n is the number of methods and 
m is the number of methods with same signature inherited via different 
paths from abstract class and/or (super)interfaces. This is typically 1, 
rarely 2, almost never 3 or more. For example:


abstract class A implements I, J, K {}

interface I {  void m(); }

interface J {  void m(); }

interface K {  void m(); }


Here the linked list with signature 'void m()' will contain 3 elements. 
When a particular method for a particular signature is found in a 
(super)interface, it has to be compared with potentially all methods 
having same signature and modifications performed while traversing are: 
do nothing, remove element, append element. So linked-list is perfect 
for that purpose. LinkedList.add() is only called when an abstract 
superclass brings multiple methods with same signature and all of them 
are inherited by abstract subclass - very very rarely is there more than 
1 method with same signature inherited from superclass.


I merged the functionality of the method-signature-key with the 
linked-list node, holding just a reference to Method object and a link 
to 'next' node. I think this is the most compact temporary datastructure 
representation for that purpose that leverages standard LinkedHashMap.




  * Please convert some of the indexed loops into for-each loops for
better readability? E.g:

   for (int i = 0; i < intfcsMethods.length; i++) {
  for (Method m : intfcsMethods[i]) {

   ...to:

   for (Method[] ms : intfcsMethods) {
  for (Method m : ms) {


Good catch. I'll do this.


  * I would think the code would be more readable if MethodList.m was
having a more readable name, e.g. MethodList.base or MethodList.image or
MethodList.primary?


Just MethodList.method will be ok - it's nothing special with this 
method. It just happens to be 1st in list of methods with same signature.


With introduction of local variables (later down), the conditions will 
be shortened in MethodList.consolidateWith() and short field name is not 
needed.





  * Formatting and logic in MethodList.consolidateWith gives me chills. I
think at very least introducing variables for m.getDeclaringClass() and
ml.m.getDeclaringClass() improve readability. Also, moving the comments
at the end of the line should improve readability and better highlight
the boolean expression you are spelling out. Below is the
straight-forward rewrite:


 MethodList consolidateWith(MethodList ml) {
 Method mineM = m;
 Method otherM = ml.m;
 Class mine = mineM.getDeclaringClass();
 Class other = otherM.getDeclaringClass();

 if (other == mine // other 
is same method as mine
 || !Modifier.isAbstract(mineM.getModifiers()) // OR, 
mine is non-abstract method...
 && (other.isAssignableFrom(mine)  // 
...which overrides other
|| other.isInterface() && !mine.isInterface())) {  // 
...class method which wins over interface
 // just return
 return this;
 }
 if (!Modifier.isAbstract(otherM.getModifiers())   // other 
is non-abstract method...
  && (mine.isAssignableFrom(other) // 
...which overrides mine
  || mine.isInterface() && !other.isInterface())) {// 
...class method which wins over interface
 // knock m out and continue
 return (next == null) ? ml : next.consolidateWith(ml);
 }

 // else leave m in and continue
 next = (next == null) ? ml : next.consolidateWith(ml);
 return this;
 }


Excellent. I'll take your formatting if you don't mind ;-)



   * Should we use just methods.put() here?
   2851 Method

Re: Loading classes with many methods is very expensive

[Stanimir Simeonoff]

On Mon, Oct 27, 2014 at 1:23 PM, Aleksey Shipilev <
aleksey.shipi...@oracle.com> wrote:

> On 10/27/2014 01:53 AM, Peter Levart wrote:
> > As you might have noticed, the number of methods obtained from patched
> > code differed from original code. I have investigated this and found
> > that original code treats abstract class methods the same as abstract
> > interface methods as far as multiple inheritance is concerned (it keeps
> > them together in the returned array). So I fixed this and here's new
> > webrev which behaves the same as original code:
> >
> > http://cr.openjdk.java.net/~plevart/jdk9-dev/Class.getMethods/webrev.02/
>
> This seems to be a candidate fix for
> https://bugs.openjdk.java.net/browse/JDK-8061950, right? If so, please
> assign yourself there. It might be advisable to start the separate RFR
> thread for a fix?
>
> My comments for the first reading of the patch:
>
>  * Why MethodList maintains the linked list? Doesn't O(n)
>
MethodList.add() lead to quadratic complexity again? Should we instead
> use the ArrayList for storing method synonyms?
>

But N would be the amount of exactly the same overridden methods from
superclasses and declared in interfaces. Usually there would be zero or
1-2. So the in-place linked list conserves memory, the extra indirection of
ArrayList for n=1 would also be slower. IMO, it's a well designed approach.
The only case where it'd actually matter is hundreds of superclasses each
overriding all of the their methods.

Stanimir


>  * Please convert some of the indexed loops into for-each loops for
> better readability? E.g:
>
>   for (int i = 0; i < intfcsMethods.length; i++) {
>  for (Method m : intfcsMethods[i]) {
>
>   ...to:
>
>   for (Method[] ms : intfcsMethods) {
>  for (Method m : ms) {
>
>  * I would think the code would be more readable if MethodList.m was
> having a more readable name, e.g. MethodList.base or MethodList.image or
> MethodList.primary?
>
>  * Formatting and logic in MethodList.consolidateWith gives me chills. I
> think at very least introducing variables for m.getDeclaringClass() and
> ml.m.getDeclaringClass() improve readability. Also, moving the comments
> at the end of the line should improve readability and better highlight
> the boolean expression you are spelling out. Below is the
> straight-forward rewrite:
>
> > MethodList consolidateWith(MethodList ml) {
> > Method mineM = m;
> > Method otherM = ml.m;
> > Class mine = mineM.getDeclaringClass();
> > Class other = otherM.getDeclaringClass();
> >
> > if (other == mine //
> other is same method as mine
> > || !Modifier.isAbstract(mineM.getModifiers()) //
> OR, mine is non-abstract method...
> > && (other.isAssignableFrom(mine)  //
> ...which overrides other
> >|| other.isInterface() && !mine.isInterface())) {  //
> ...class method which wins over interface
> > // just return
> > return this;
> > }
> > if (!Modifier.isAbstract(otherM.getModifiers())   //
> other is non-abstract method...
> >  && (mine.isAssignableFrom(other) //
> ...which overrides mine
> >  || mine.isInterface() && !other.isInterface())) {//
> ...class method which wins over interface
> > // knock m out and continue
> > return (next == null) ? ml : next.consolidateWith(ml);
> > }
> >
> > // else leave m in and continue
> > next = (next == null) ? ml : next.consolidateWith(ml);
> > return this;
> > }
>
>
>   * Should we use just methods.put() here?
>   2851 MethodList ml0 = methods.putIfAbsent(ml, ml);
>
>   * I wonder if the code would be simpler if we push the Map MethodList> maintenance to some internal utility class? That would
> probably simplify the loops in privateGetPublicMethods?
>
> Thanks,
> -Aleksey.
>
>

Re: Loading classes with many methods is very expensive

[Aleksey Shipilev]

On 10/27/2014 01:53 AM, Peter Levart wrote:
> As you might have noticed, the number of methods obtained from patched
> code differed from original code. I have investigated this and found
> that original code treats abstract class methods the same as abstract
> interface methods as far as multiple inheritance is concerned (it keeps
> them together in the returned array). So I fixed this and here's new
> webrev which behaves the same as original code:
> 
> http://cr.openjdk.java.net/~plevart/jdk9-dev/Class.getMethods/webrev.02/

This seems to be a candidate fix for
https://bugs.openjdk.java.net/browse/JDK-8061950, right? If so, please
assign yourself there. It might be advisable to start the separate RFR
thread for a fix?

My comments for the first reading of the patch:

 * Why MethodList maintains the linked list? Doesn't O(n)
MethodList.add() lead to quadratic complexity again? Should we instead
use the ArrayList for storing method synonyms?

 * Please convert some of the indexed loops into for-each loops for
better readability? E.g:

  for (int i = 0; i < intfcsMethods.length; i++) {
 for (Method m : intfcsMethods[i]) {

  ...to:

  for (Method[] ms : intfcsMethods) {
 for (Method m : ms) {

 * I would think the code would be more readable if MethodList.m was
having a more readable name, e.g. MethodList.base or MethodList.image or
MethodList.primary?

 * Formatting and logic in MethodList.consolidateWith gives me chills. I
think at very least introducing variables for m.getDeclaringClass() and
ml.m.getDeclaringClass() improve readability. Also, moving the comments
at the end of the line should improve readability and better highlight
the boolean expression you are spelling out. Below is the
straight-forward rewrite:

> MethodList consolidateWith(MethodList ml) {
> Method mineM = m;
> Method otherM = ml.m;
> Class mine = mineM.getDeclaringClass();
> Class other = otherM.getDeclaringClass();
> 
> if (other == mine // 
> other is same method as mine
> || !Modifier.isAbstract(mineM.getModifiers()) // OR, 
> mine is non-abstract method...
> && (other.isAssignableFrom(mine)  // 
> ...which overrides other
>|| other.isInterface() && !mine.isInterface())) {  // 
> ...class method which wins over interface
> // just return
> return this;
> }
> if (!Modifier.isAbstract(otherM.getModifiers())   // 
> other is non-abstract method...
>  && (mine.isAssignableFrom(other) // 
> ...which overrides mine
>  || mine.isInterface() && !other.isInterface())) {// 
> ...class method which wins over interface
> // knock m out and continue
> return (next == null) ? ml : next.consolidateWith(ml);
> }
> 
> // else leave m in and continue
> next = (next == null) ? ml : next.consolidateWith(ml);
> return this;
> }


  * Should we use just methods.put() here?
  2851 MethodList ml0 = methods.putIfAbsent(ml, ml);

  * I wonder if the code would be simpler if we push the Map maintenance to some internal utility class? That would
probably simplify the loops in privateGetPublicMethods?

Thanks,
-Aleksey.

Re: Loading classes with many methods is very expensive

[Stanimir Simeonoff]

>
> 55 java/lang/reflect jtreg tests still pass. As they did before, which
> means that we don't have a coverage for such cases. I'll see where I can
> add such a case (EnumSet for example, which inherits from Set interface and
> AbstractColection class via two different paths, so Set.size()/iterator()
> and AbstractCollection.size()/iterator() are both returned from
> getMethods())...
>

Reminds me the case when a package private class implementing a public
interface cannot have its methods invoked via
object.getClass().getMethod(name, classes).invoke(object, args) outside the
package.
Also I can't find any spec. on how multiple equivalent methods should be
returned.



>
> Regards, Peter
>
>

Re: Loading classes with many methods is very expensive

[Peter Levart]

On 10/26/2014 09:25 PM, Peter Levart wrote:

19657 classes loaded in 1.987373401 seconds.
494141 methods obtained in 1.02493941 seconds.

vs.

19657 classes loaded in 2.084409717 seconds.
494124 methods obtained in 0.915928578 seconds.


Hi,

As you might have noticed, the number of methods obtained from patched 
code differed from original code. I have investigated this and found 
that original code treats abstract class methods the same as abstract 
interface methods as far as multiple inheritance is concerned (it keeps 
them together in the returned array). So I fixed this and here's new 
webrev which behaves the same as original code:


http://cr.openjdk.java.net/~plevart/jdk9-dev/Class.getMethods/webrev.02/

Comparing original vs. patched code still shows speed-up:

Original:

19657 classes loaded in 1.980493029 seconds.
494141 methods obtained in 0.976318927 seconds.
494141 methods obtained in 0.886504437 seconds.
494141 methods obtained in 0.911153722 seconds.
494141 methods obtained in 0.880550509 seconds.
494141 methods obtained in 0.875526704 seconds.
494141 methods obtained in 0.877258894 seconds.
494141 methods obtained in 0.871794344 seconds.
494141 methods obtained in 0.884159644 seconds.
494141 methods obtained in 0.892648522 seconds.
494141 methods obtained in 0.884581841 seconds.

Patched:

19657 classes loaded in 2.055697675 seconds.
494141 methods obtained in 0.853922188 seconds.
494141 methods obtained in 0.776203794 seconds.
494141 methods obtained in 0.858774803 seconds.
494141 methods obtained in 0.778178867 seconds.
494141 methods obtained in 0.760043997 seconds.
494141 methods obtained in 0.756352444 seconds.
494141 methods obtained in 0.740826372 seconds.
494141 methods obtained in 0.744264782 seconds.
494141 methods obtained in 0.73805894 seconds.
494141 methods obtained in 0.746852752 seconds.


55 java/lang/reflect jtreg tests still pass. As they did before, which 
means that we don't have a coverage for such cases. I'll see where I can 
add such a case (EnumSet for example, which inherits from Set interface 
and AbstractColection class via two different paths, so 
Set.size()/iterator() and AbstractCollection.size()/iterator() are both 
returned from getMethods())...



Regards, Peter

Re: Loading classes with many methods is very expensive

[Stanimir Simeonoff]

On Mon, Oct 27, 2014 at 12:36 AM, Peter Levart 
wrote:

>
> On 10/26/2014 11:21 PM, Stanimir Simeonoff wrote:
>
>  Great effort.
>
> From first glance: the hashCode and equals of MethodList use
> m.getParameterTypes() which is cloned. I'd rather pay the collision costs
> and rely on the default hashCode/equals of Method itself (hashCode ignores
> the parameters). Possibly hashCode can include the returnType but equals
> should be direct call to Method.equals.
>
>
> Can't do that as Method.equals also compares declaringClass, which is not
> part of method signature.
>
> We could use SharedSecrets to access the internal array of parameterTypes
> directly.
>
>
Opps, very true.

If SharedSecrets is not available, get the parameters in the constructor,
so clone happens once only. Method.clone() should be comparable to the cost
of a LHM node, so the overhead is not so high.
I doubt the JIT can EA clone() which would be the best case scenario.

I was wondering if the computation of size is better than just array copy
(as LHM.iterator is effectively linked list), however for small number of
methods it would keep all the references in L1 so that would be better in
the common case.

Stanimir




> Regards, Peter
>
>
>
>  Stanimir
>
>
>
>
> On Sun, Oct 26, 2014 at 10:25 PM, Peter Levart 
> wrote:
>
>> Hi all,
>>
>> I revamped the Class.getMethods() implementation so that it is faster for
>> common cases and O(n) at the same time, which makes Martin's test happy (at
>> least in part that measures getMethods() speed - the class loading /
>> linkage in VM is a separate issue).
>>
>> With the following test that loads all classes from rt.jar and calls
>> getMethods() on each of them:
>>
>>
>> http://cr.openjdk.java.net/~plevart/jdk9-dev/Class.getMethods/GetAllRtMethods.java
>>
>> And system property 'sun.reflect.noCaches=true' (so that we exercise the
>> logic in every loop - not just 1st), original code prints:
>>
>> 19657 classes loaded in 1.987373401 seconds.
>> 494141 methods obtained in 1.02493941 seconds.
>> 494141 methods obtained in 0.905235658 seconds.
>> 494141 methods obtained in 0.914434303 seconds.
>> 494141 methods obtained in 0.887212805 seconds.
>> 494141 methods obtained in 0.888929483 seconds.
>> 494141 methods obtained in 0.883309141 seconds.
>> 494141 methods obtained in 0.88341098 seconds.
>> 494141 methods obtained in 0.897397146 seconds.
>> 494141 methods obtained in 0.885677466 seconds.
>> 494141 methods obtained in 0.895834176 seconds.
>>
>> Patched code does the same about 10% faster:
>>
>> 19657 classes loaded in 2.084409717 seconds.
>> 494124 methods obtained in 0.915928578 seconds.
>> 494124 methods obtained in 0.785342465 seconds.
>> 494124 methods obtained in 0.784852619 seconds.
>> 494124 methods obtained in 0.793450205 seconds.
>> 494124 methods obtained in 0.849915078 seconds.
>> 494124 methods obtained in 0.77835511 seconds.
>> 494124 methods obtained in 0.764144701 seconds.
>> 494124 methods obtained in 0.754122383 seconds.
>> 494124 methods obtained in 0.747961897 seconds.
>> 494124 methods obtained in 0.7489937 seconds.
>>
>> Martin's test prints on my computer with original code the following:
>>
>> Base class load time: 177.80 ms
>> getDeclaredMethods: Methods: 65521, Total time: 35.79 ms, Time per
>> method: 0.0005 ms
>> getMethods: Methods: 65530, Total time: 50.15 ms, Time per
>> method: 0.0008 ms
>> Derived class load time: 34015.70 ms
>> getDeclaredMethods: Methods: 65521, Total time: 33.82 ms, Time per
>> method: 0.0005 ms
>> getMethods: Methods: 65530, Total time: 8122.00 ms, Time per
>> method: 0.1239 ms
>>
>> And with patched code this:
>>
>> Base class load time: 157.16 ms
>> getDeclaredMethods: Methods: 65521, Total time: 65.77 ms, Time per
>> method: 0.0010 ms
>> getMethods: Methods: 65530, Total time: 44.64 ms, Time per
>> method: 0.0007 ms
>> Derived class load time: 33996.69 ms
>> getDeclaredMethods: Methods: 65521, Total time: 32.63 ms, Time per
>> method: 0.0005 ms
>> getMethods: Methods: 65530, Total time: 92.12 ms, Time per
>> method: 0.0014 ms
>>
>>
>> Here's a webrev of the patch:
>>
>> http://cr.openjdk.java.net/~plevart/jdk9-dev/Class.getMethods/webrev.01/
>>
>> Patched code is simpler (65 lines gone) and I hope, easier to understand
>> and change (I think a change in spec is coming in JDK9 which will handle
>> abstract interface methods the same way as default, right Joel?)
>>
>> I also took the liberty to eliminate some redundant array and
>> Field/Method/Constructor copies. get[Method0,Field0,Counstuctor0] now
>> return 'root' objects. Copying is performed in methods that call them and
>> expose the objects to any code outside java.lang.Class. Also, findFields()
>> and findMethods() don't do copying of Field/Method objects themselves, but
>> rather live that to methods that call them. getInterfaces() method now
>> delegates to getInterfaces(boolean copyArray) so that internally, not array
>> copying is performed.
>>
>> All 5

Re: Loading classes with many methods is very expensive

[Peter Levart]

On 10/26/2014 11:21 PM, Stanimir Simeonoff wrote:

Great effort.

From first glance: the hashCode and equals of MethodList use 
m.getParameterTypes() which is cloned. I'd rather pay the collision 
costs and rely on the default hashCode/equals of Method itself 
(hashCode ignores the parameters). Possibly hashCode can include the 
returnType but equals should be direct call to Method.equals.


Can't do that as Method.equals also compares declaringClass, which is 
not part of method signature.


We could use SharedSecrets to access the internal array of 
parameterTypes directly.


Regards, Peter



Stanimir




On Sun, Oct 26, 2014 at 10:25 PM, Peter Levart > wrote:


Hi all,

I revamped the Class.getMethods() implementation so that it is
faster for common cases and O(n) at the same time, which makes
Martin's test happy (at least in part that measures getMethods()
speed - the class loading / linkage in VM is a separate issue).

With the following test that loads all classes from rt.jar and
calls getMethods() on each of them:


http://cr.openjdk.java.net/~plevart/jdk9-dev/Class.getMethods/GetAllRtMethods.java



And system property 'sun.reflect.noCaches=true' (so that we
exercise the logic in every loop - not just 1st), original code
prints:

19657 classes loaded in 1.987373401 seconds.
494141 methods obtained in 1.02493941 seconds.
494141 methods obtained in 0.905235658 seconds.
494141 methods obtained in 0.914434303 seconds.
494141 methods obtained in 0.887212805 seconds.
494141 methods obtained in 0.888929483 seconds.
494141 methods obtained in 0.883309141 seconds.
494141 methods obtained in 0.88341098 seconds.
494141 methods obtained in 0.897397146 seconds.
494141 methods obtained in 0.885677466 seconds.
494141 methods obtained in 0.895834176 seconds.

Patched code does the same about 10% faster:

19657 classes loaded in 2.084409717  seconds.
494124 methods obtained in 0.915928578 seconds.
494124 methods obtained in 0.785342465 seconds.
494124 methods obtained in 0.784852619 seconds.
494124 methods obtained in 0.793450205 seconds.
494124 methods obtained in 0.849915078 seconds.
494124 methods obtained in 0.77835511 seconds.
494124 methods obtained in 0.764144701 seconds.
494124 methods obtained in 0.754122383 seconds.
494124 methods obtained in 0.747961897 seconds.
494124 methods obtained in 0.7489937 seconds.

Martin's test prints on my computer with original code the following:

Base class load time: 177.80 ms
getDeclaredMethods: Methods: 65521, Total time: 35.79 ms, Time per
method: 0.0005 ms
getMethods: Methods: 65530, Total time: 50.15 ms, Time per
method: 0.0008 ms
Derived class load time: 34015.70 ms
getDeclaredMethods: Methods: 65521, Total time: 33.82 ms, Time per
method: 0.0005 ms
getMethods: Methods: 65530, Total time: 8122.00 ms, Time
per method: 0.1239 ms

And with patched code this:

Base class load time: 157.16 ms
getDeclaredMethods: Methods: 65521, Total time: 65.77 ms, Time per
method: 0.0010 ms
getMethods: Methods: 65530, Total time: 44.64 ms, Time per
method: 0.0007 ms
Derived class load time: 33996.69 ms
getDeclaredMethods: Methods: 65521, Total time: 32.63 ms, Time per
method: 0.0005 ms
getMethods: Methods: 65530, Total time: 92.12 ms, Time per
method: 0.0014 ms


Here's a webrev of the patch:

http://cr.openjdk.java.net/~plevart/jdk9-dev/Class.getMethods/webrev.01/


Patched code is simpler (65 lines gone) and I hope, easier to
understand and change (I think a change in spec is coming in JDK9
which will handle abstract interface methods the same way as
default, right Joel?)

I also took the liberty to eliminate some redundant array and
Field/Method/Constructor copies. get[Method0,Field0,Counstuctor0]
now return 'root' objects. Copying is performed in methods that
call them and expose the objects to any code outside
java.lang.Class. Also, findFields() and findMethods() don't do
copying of Field/Method objects themselves, but rather live that
to methods that call them. getInterfaces() method now delegates to
getInterfaces(boolean copyArray) so that internally, not array
copying is performed.

All 55 java/lang/reflect jtreg tests pass with this patch.


Regards, Peter

Re: Loading classes with many methods is very expensive

[Stanimir Simeonoff]

Great effort.

>From first glance: the hashCode and equals of MethodList use
m.getParameterTypes() which is cloned. I'd rather pay the collision costs
and rely on the default hashCode/equals of Method itself (hashCode ignores
the parameters). Possibly hashCode can include the returnType but equals
should be direct call to Method.equals.

Stanimir




On Sun, Oct 26, 2014 at 10:25 PM, Peter Levart 
wrote:

> Hi all,
>
> I revamped the Class.getMethods() implementation so that it is faster for
> common cases and O(n) at the same time, which makes Martin's test happy (at
> least in part that measures getMethods() speed - the class loading /
> linkage in VM is a separate issue).
>
> With the following test that loads all classes from rt.jar and calls
> getMethods() on each of them:
>
> http://cr.openjdk.java.net/~plevart/jdk9-dev/Class.
> getMethods/GetAllRtMethods.java
>
> And system property 'sun.reflect.noCaches=true' (so that we exercise the
> logic in every loop - not just 1st), original code prints:
>
> 19657 classes loaded in 1.987373401 seconds.
> 494141 methods obtained in 1.02493941 seconds.
> 494141 methods obtained in 0.905235658 seconds.
> 494141 methods obtained in 0.914434303 seconds.
> 494141 methods obtained in 0.887212805 seconds.
> 494141 methods obtained in 0.888929483 seconds.
> 494141 methods obtained in 0.883309141 seconds.
> 494141 methods obtained in 0.88341098 seconds.
> 494141 methods obtained in 0.897397146 seconds.
> 494141 methods obtained in 0.885677466 seconds.
> 494141 methods obtained in 0.895834176 seconds.
>
> Patched code does the same about 10% faster:
>
> 19657 classes loaded in 2.084409717 seconds.
> 494124 methods obtained in 0.915928578 seconds.
> 494124 methods obtained in 0.785342465 seconds.
> 494124 methods obtained in 0.784852619 seconds.
> 494124 methods obtained in 0.793450205 seconds.
> 494124 methods obtained in 0.849915078 seconds.
> 494124 methods obtained in 0.77835511 seconds.
> 494124 methods obtained in 0.764144701 seconds.
> 494124 methods obtained in 0.754122383 seconds.
> 494124 methods obtained in 0.747961897 seconds.
> 494124 methods obtained in 0.7489937 seconds.
>
> Martin's test prints on my computer with original code the following:
>
> Base class load time: 177.80 ms
> getDeclaredMethods: Methods: 65521, Total time: 35.79 ms, Time per method:
> 0.0005 ms
> getMethods: Methods: 65530, Total time: 50.15 ms, Time per method:
> 0.0008 ms
> Derived class load time: 34015.70 ms
> getDeclaredMethods: Methods: 65521, Total time: 33.82 ms, Time per method:
> 0.0005 ms
> getMethods: Methods: 65530, Total time: 8122.00 ms, Time per
> method: 0.1239 ms
>
> And with patched code this:
>
> Base class load time: 157.16 ms
> getDeclaredMethods: Methods: 65521, Total time: 65.77 ms, Time per method:
> 0.0010 ms
> getMethods: Methods: 65530, Total time: 44.64 ms, Time per method:
> 0.0007 ms
> Derived class load time: 33996.69 ms
> getDeclaredMethods: Methods: 65521, Total time: 32.63 ms, Time per method:
> 0.0005 ms
> getMethods: Methods: 65530, Total time: 92.12 ms, Time per method:
> 0.0014 ms
>
>
> Here's a webrev of the patch:
>
> http://cr.openjdk.java.net/~plevart/jdk9-dev/Class.getMethods/webrev.01/
>
> Patched code is simpler (65 lines gone) and I hope, easier to understand
> and change (I think a change in spec is coming in JDK9 which will handle
> abstract interface methods the same way as default, right Joel?)
>
> I also took the liberty to eliminate some redundant array and
> Field/Method/Constructor copies. get[Method0,Field0,Counstuctor0] now
> return 'root' objects. Copying is performed in methods that call them and
> expose the objects to any code outside java.lang.Class. Also, findFields()
> and findMethods() don't do copying of Field/Method objects themselves, but
> rather live that to methods that call them. getInterfaces() method now
> delegates to getInterfaces(boolean copyArray) so that internally, not array
> copying is performed.
>
> All 55 java/lang/reflect jtreg tests pass with this patch.
>
>
> Regards, Peter
>
>

Re: Loading classes with many methods is very expensive

[Peter Levart]

Hi all,

I revamped the Class.getMethods() implementation so that it is faster 
for common cases and O(n) at the same time, which makes Martin's test 
happy (at least in part that measures getMethods() speed - the class 
loading / linkage in VM is a separate issue).


With the following test that loads all classes from rt.jar and calls 
getMethods() on each of them:


http://cr.openjdk.java.net/~plevart/jdk9-dev/Class.getMethods/GetAllRtMethods.java

And system property 'sun.reflect.noCaches=true' (so that we exercise the 
logic in every loop - not just 1st), original code prints:


19657 classes loaded in 1.987373401 seconds.
494141 methods obtained in 1.02493941 seconds.
494141 methods obtained in 0.905235658 seconds.
494141 methods obtained in 0.914434303 seconds.
494141 methods obtained in 0.887212805 seconds.
494141 methods obtained in 0.888929483 seconds.
494141 methods obtained in 0.883309141 seconds.
494141 methods obtained in 0.88341098 seconds.
494141 methods obtained in 0.897397146 seconds.
494141 methods obtained in 0.885677466 seconds.
494141 methods obtained in 0.895834176 seconds.

Patched code does the same about 10% faster:

19657 classes loaded in 2.084409717 seconds.
494124 methods obtained in 0.915928578 seconds.
494124 methods obtained in 0.785342465 seconds.
494124 methods obtained in 0.784852619 seconds.
494124 methods obtained in 0.793450205 seconds.
494124 methods obtained in 0.849915078 seconds.
494124 methods obtained in 0.77835511 seconds.
494124 methods obtained in 0.764144701 seconds.
494124 methods obtained in 0.754122383 seconds.
494124 methods obtained in 0.747961897 seconds.
494124 methods obtained in 0.7489937 seconds.

Martin's test prints on my computer with original code the following:

Base class load time: 177.80 ms
getDeclaredMethods: Methods: 65521, Total time: 35.79 ms, Time per 
method: 0.0005 ms
getMethods: Methods: 65530, Total time: 50.15 ms, Time per 
method: 0.0008 ms

Derived class load time: 34015.70 ms
getDeclaredMethods: Methods: 65521, Total time: 33.82 ms, Time per 
method: 0.0005 ms
getMethods: Methods: 65530, Total time: 8122.00 ms, Time per 
method: 0.1239 ms


And with patched code this:

Base class load time: 157.16 ms
getDeclaredMethods: Methods: 65521, Total time: 65.77 ms, Time per 
method: 0.0010 ms
getMethods: Methods: 65530, Total time: 44.64 ms, Time per 
method: 0.0007 ms

Derived class load time: 33996.69 ms
getDeclaredMethods: Methods: 65521, Total time: 32.63 ms, Time per 
method: 0.0005 ms
getMethods: Methods: 65530, Total time: 92.12 ms, Time per 
method: 0.0014 ms



Here's a webrev of the patch:

http://cr.openjdk.java.net/~plevart/jdk9-dev/Class.getMethods/webrev.01/

Patched code is simpler (65 lines gone) and I hope, easier to understand 
and change (I think a change in spec is coming in JDK9 which will handle 
abstract interface methods the same way as default, right Joel?)


I also took the liberty to eliminate some redundant array and 
Field/Method/Constructor copies. get[Method0,Field0,Counstuctor0] now 
return 'root' objects. Copying is performed in methods that call them 
and expose the objects to any code outside java.lang.Class. Also, 
findFields() and findMethods() don't do copying of Field/Method objects 
themselves, but rather live that to methods that call them. 
getInterfaces() method now delegates to getInterfaces(boolean copyArray) 
so that internally, not array copying is performed.


All 55 java/lang/reflect jtreg tests pass with this patch.


Regards, Peter

Re: Loading classes with many methods is very expensive

[Joel Borggrén-Franck]

On 23 Oct 2014, at 17:44, Peter Levart  wrote:
> 
> Is there a test that validates correctness of getMethods() or at least a set 
> of interfaces and/or classes to exercise the algorithm and compare it to a 
> different implementation?
> 

There is :)

http://hg.openjdk.java.net/jdk9/dev/jdk/file/8b4aa51c8744/test/java/lang/reflect/DefaultMethodMembers/FilterNotMostSpecific.java

IIRC 75% or so of the cases passes both before and after the change.

I have highlighted a number of interesting cases with line comments.

cheers
/Joel

Re: Loading classes with many methods is very expensive

[Peter Levart]

On 10/23/2014 05:44 PM, Peter Levart wrote:

interface A6 extends B6, C6 {}
interface B6 extends D6 { void m(); }
interface C6 extends D6 {}
interface D6 { default void m() {}; }

A6.class.getMethods() returns B6.m, D6.m 


Ah, B6.m re-abstracts the default method D6.m. I can see the rule here. 
Never mind my previous question.



Regards, Peter

Re: Loading classes with many methods is very expensive

[Peter Levart]

On 10/23/2014 05:06 PM, Joel Borggrén-Franck wrote:

Hi Martin,

On 23 okt 2014, at 00:53, Martin Buchholz  wrote:


Here at Google we have both kinds of scalability problems - loading classes
from a classpath with 10,000 jars, and loading a single class file packed
with the maximal number of methods.  This message is about the latter.

If you have a class with ~64k methods with a superclass that also has ~64k
methods, class loading that single class will cost you ~30sec and calling
Class.getMethods another ~10sec.  Both are unacceptably slow. I think both
are due to O(N^2) algorithms, the first in hotspot, and the second in
Class.java.

Throw in lots of interfaces with lots of default methods and i suspect this can 
get even worse. I spent some time thinking about this when fixing an issue with 
reflection for default methods, reviewed here [1].


Hi Joel,

I may have found another issue:

interface A4 extends B4, C4 {}
interface B4 extends D4 { void m(); }
interface C4 extends D4 {}
interface D4 { void m(); }

Calling A4.class.getMethods() returns B4.m, D4.m - this is supposed to 
be OK as per JDK 7 spec.


Changing both methods to default methods:

interface A5 extends B5, C5 {}
interface B5 extends D5 { default void m() {} }
interface C5 extends D5 {}
interface D5 { default void m() {}; }

A5.class.getMethods() returns B5.m - this is new in JDK 8 spec for 
default methods.


Now see the following two examples (just one method is default, the 
other is abstract):


interface A6 extends B6, C6 {}
interface B6 extends D6 { void m(); }
interface C6 extends D6 {}
interface D6 { default void m() {}; }

A6.class.getMethods() returns B6.m, D6.m

// B.m, D.m
interface A7 extends B7, C7 {}
interface B7 extends D7 { default void m() {} }
interface C7 extends D7 {}
interface D7 { void m(); }

A7.class.getMethods() returns B7.m


Do last two examples give expected result? Why are A6 and A7 different? 
What is the rule here? I would expect A6.class.getMethods() only return 
the D6.m default method. This is the non-abstract method that gets used 
when implementing an interface.


If A6 example is really showing a bug, then I may have a solution that 
fixes it *and* is faster than current code for getMethods() + it is O(n)...


Is there a test that validates correctness of getMethods() or at least a 
set of interfaces and/or classes to exercise the algorithm and compare 
it to a different implementation?





I have the start of a fix for Class.java, but it makes the common case
slower.  A really good fix is harder to find.  In general, I think
Class.java could benefit from some performance-oriented rework.  Is anyone
else working on class loading performance, especially in hotspot?


We have been thinking about replacing the duplication of the method lookup 
logic in j.l.Class with a call to the VM which should already have the 
information needed. I’m not sure why the logic was duplicated on the library 
side way back when this was written. This isn’t something we are actively 
working on though.


Does VM have enough information to quickly compile the list of public 
methods (getMethods() equivalent) or only to look-up the public method 
(getMethod() equivalent)?



Regards, Peter



As an aside, I often found myself wanting for the actual method descriptor when 
working with this, but considering there can be *a lot* of instances of 
Method/Constructor adding a descriptor field to Executable wasn’t an obvious 
win to me.

cheers
/Joel

[1] http://mail.openjdk.java.net/pipermail/core-libs-dev/2014-May/026782.html

Re: Loading classes with many methods is very expensive

[Peter Levart]

On 10/23/2014 03:48 PM, Karen Kinnear wrote:

Peter,

Which hotspot algorithm is the one you identified as slow? Would that be
for loading the class or for Class.getMethods?

thanks,
Karen


Martin did it. And Alexey profiled it.

I just noted that Java part of Class.getMethods(), should it be 
rewritten, might be required to keep the order of Method objects 
returned in the array although it is not specified.


Class.getMethods() is based on native Class methods which return 
declared methods. They are not slow. The Java algorithm that combines 
those into a compiled list of public methods (which includes inherited 
from supertypes) is slow for large number of methods since it is O(n^2).


Regards, Peter



On Oct 23, 2014, at 9:37 AM, Peter Levart wrote:


On 10/23/2014 01:57 AM, Stanimir Simeonoff wrote:

Class.java can easily be improved by adding an auxiliary  HasMap indexing the position in the array by name and then checking
only few overloaded signatures in case of a match.
The auxiliary map can be deployed only past some threshold of methods, so
it should not affect the common case.

Alternatively sorting the array and using binary search is quite trivial to
implement as well.

Java Class.getMethods() implementation is complicated by the fact that, 
although not specified, the order of methods in returned array is important. 
Once it changed, if I remember correctly, and broke many programs, so it had to 
be restored...

Peter


Btw, really nice benchmark.

Stanimir


On Thu, Oct 23, 2014 at 1:53 AM, Martin Buchholz 
wrote:


Here at Google we have both kinds of scalability problems - loading classes
from a classpath with 10,000 jars, and loading a single class file packed
with the maximal number of methods.  This message is about the latter.

If you have a class with ~64k methods with a superclass that also has ~64k
methods, class loading that single class will cost you ~30sec and calling
Class.getMethods another ~10sec.  Both are unacceptably slow. I think both
are due to O(N^2) algorithms, the first in hotspot, and the second in
Class.java.

I have the start of a fix for Class.java, but it makes the common case
slower.  A really good fix is harder to find.  In general, I think
Class.java could benefit from some performance-oriented rework.  Is anyone
else working on class loading performance, especially in hotspot?

Here's the benchmark (that could perhaps be integrated into openjdk even
without a fix)


http://cr.openjdk.java.net/~martin/webrevs/openjdk9/Class.getMethods-benchmark/test/java/lang/Class/getMethods/ManyMethodsBenchmark.java.html

Base class load time: 186.44 ms
getDeclaredMethods: Methods: 65521, Total time: 43.27 ms, Time per method:
0.0007 ms
getMethods: Methods: 65530, Total time: 60.82 ms, Time per method:
0.0009 ms
Derived class load time: 33440.13 ms
getDeclaredMethods: Methods: 65521, Total time: 39.71 ms, Time per method:
0.0006 ms
getMethods: Methods: 65530, Total time: 11582.54 ms, Time per
method: 0.1768 ms

Re: Loading classes with many methods is very expensive

[Joel Borggrén-Franck]

Hi Martin,

On 23 okt 2014, at 00:53, Martin Buchholz  wrote:

> Here at Google we have both kinds of scalability problems - loading classes
> from a classpath with 10,000 jars, and loading a single class file packed
> with the maximal number of methods.  This message is about the latter.
> 
> If you have a class with ~64k methods with a superclass that also has ~64k
> methods, class loading that single class will cost you ~30sec and calling
> Class.getMethods another ~10sec.  Both are unacceptably slow. I think both
> are due to O(N^2) algorithms, the first in hotspot, and the second in
> Class.java.

Throw in lots of interfaces with lots of default methods and i suspect this can 
get even worse. I spent some time thinking about this when fixing an issue with 
reflection for default methods, reviewed here [1].

> I have the start of a fix for Class.java, but it makes the common case
> slower.  A really good fix is harder to find.  In general, I think
> Class.java could benefit from some performance-oriented rework.  Is anyone
> else working on class loading performance, especially in hotspot?
> 

We have been thinking about replacing the duplication of the method lookup 
logic in j.l.Class with a call to the VM which should already have the 
information needed. I’m not sure why the logic was duplicated on the library 
side way back when this was written. This isn’t something we are actively 
working on though.

As an aside, I often found myself wanting for the actual method descriptor when 
working with this, but considering there can be *a lot* of instances of 
Method/Constructor adding a descriptor field to Executable wasn’t an obvious 
win to me.

cheers
/Joel

[1] http://mail.openjdk.java.net/pipermail/core-libs-dev/2014-May/026782.html

Re: Loading classes with many methods is very expensive

[Stanimir Simeonoff]

I was under  the impression the declaring order has been abandoned in 1.7
which I considered quite a let down as allowed ordering the function calls
in JMX in a non-chaotic way.


On Thu, Oct 23, 2014 at 4:37 PM, Peter Levart 
wrote:

> On 10/23/2014 01:57 AM, Stanimir Simeonoff wrote:
>
>> Class.java can easily be improved by adding an auxiliary  HasMap> Integer/int[]> indexing the position in the array by name and then
>> checking
>> only few overloaded signatures in case of a match.
>> The auxiliary map can be deployed only past some threshold of methods, so
>> it should not affect the common case.
>>
>> Alternatively sorting the array and using binary search is quite trivial
>> to
>> implement as well.
>>
>
> Java Class.getMethods() implementation is complicated by the fact that,
> although not specified, the order of methods in returned array is
> important. Once it changed, if I remember correctly, and broke many
> programs, so it had to be restored...
>
> Peter
>
>
>
>> Btw, really nice benchmark.
>>
>> Stanimir
>>
>>
>> On Thu, Oct 23, 2014 at 1:53 AM, Martin Buchholz 
>> wrote:
>>
>>  Here at Google we have both kinds of scalability problems - loading
>>> classes
>>> from a classpath with 10,000 jars, and loading a single class file packed
>>> with the maximal number of methods.  This message is about the latter.
>>>
>>> If you have a class with ~64k methods with a superclass that also has
>>> ~64k
>>> methods, class loading that single class will cost you ~30sec and calling
>>> Class.getMethods another ~10sec.  Both are unacceptably slow. I think
>>> both
>>> are due to O(N^2) algorithms, the first in hotspot, and the second in
>>> Class.java.
>>>
>>> I have the start of a fix for Class.java, but it makes the common case
>>> slower.  A really good fix is harder to find.  In general, I think
>>> Class.java could benefit from some performance-oriented rework.  Is
>>> anyone
>>> else working on class loading performance, especially in hotspot?
>>>
>>> Here's the benchmark (that could perhaps be integrated into openjdk even
>>> without a fix)
>>>
>>>
>>> http://cr.openjdk.java.net/~martin/webrevs/openjdk9/Class.
>>> getMethods-benchmark/test/java/lang/Class/getMethods/
>>> ManyMethodsBenchmark.java.html
>>>
>>> Base class load time: 186.44 ms
>>> getDeclaredMethods: Methods: 65521, Total time: 43.27 ms, Time per
>>> method:
>>> 0.0007 ms
>>> getMethods: Methods: 65530, Total time: 60.82 ms, Time per
>>> method:
>>> 0.0009 ms
>>> Derived class load time: 33440.13 ms
>>> getDeclaredMethods: Methods: 65521, Total time: 39.71 ms, Time per
>>> method:
>>> 0.0006 ms
>>> getMethods: Methods: 65530, Total time: 11582.54 ms, Time per
>>> method: 0.1768 ms
>>>
>>>
>

Re: Loading classes with many methods is very expensive

[Karen Kinnear]

Peter,

Which hotspot algorithm is the one you identified as slow? Would that be
for loading the class or for Class.getMethods?

thanks,
Karen

On Oct 23, 2014, at 9:37 AM, Peter Levart wrote:

> On 10/23/2014 01:57 AM, Stanimir Simeonoff wrote:
>> Class.java can easily be improved by adding an auxiliary  HasMap> Integer/int[]> indexing the position in the array by name and then checking
>> only few overloaded signatures in case of a match.
>> The auxiliary map can be deployed only past some threshold of methods, so
>> it should not affect the common case.
>> 
>> Alternatively sorting the array and using binary search is quite trivial to
>> implement as well.
> 
> Java Class.getMethods() implementation is complicated by the fact that, 
> although not specified, the order of methods in returned array is important. 
> Once it changed, if I remember correctly, and broke many programs, so it had 
> to be restored...
> 
> Peter
> 
>> 
>> Btw, really nice benchmark.
>> 
>> Stanimir
>> 
>> 
>> On Thu, Oct 23, 2014 at 1:53 AM, Martin Buchholz 
>> wrote:
>> 
>>> Here at Google we have both kinds of scalability problems - loading classes
>>> from a classpath with 10,000 jars, and loading a single class file packed
>>> with the maximal number of methods.  This message is about the latter.
>>> 
>>> If you have a class with ~64k methods with a superclass that also has ~64k
>>> methods, class loading that single class will cost you ~30sec and calling
>>> Class.getMethods another ~10sec.  Both are unacceptably slow. I think both
>>> are due to O(N^2) algorithms, the first in hotspot, and the second in
>>> Class.java.
>>> 
>>> I have the start of a fix for Class.java, but it makes the common case
>>> slower.  A really good fix is harder to find.  In general, I think
>>> Class.java could benefit from some performance-oriented rework.  Is anyone
>>> else working on class loading performance, especially in hotspot?
>>> 
>>> Here's the benchmark (that could perhaps be integrated into openjdk even
>>> without a fix)
>>> 
>>> 
>>> http://cr.openjdk.java.net/~martin/webrevs/openjdk9/Class.getMethods-benchmark/test/java/lang/Class/getMethods/ManyMethodsBenchmark.java.html
>>> 
>>> Base class load time: 186.44 ms
>>> getDeclaredMethods: Methods: 65521, Total time: 43.27 ms, Time per method:
>>> 0.0007 ms
>>> getMethods: Methods: 65530, Total time: 60.82 ms, Time per method:
>>> 0.0009 ms
>>> Derived class load time: 33440.13 ms
>>> getDeclaredMethods: Methods: 65521, Total time: 39.71 ms, Time per method:
>>> 0.0006 ms
>>> getMethods: Methods: 65530, Total time: 11582.54 ms, Time per
>>> method: 0.1768 ms
>>> 
> 

Re: Loading classes with many methods is very expensive

[Peter Levart]

On 10/23/2014 01:57 AM, Stanimir Simeonoff wrote:

Class.java can easily be improved by adding an auxiliary  HasMap indexing the position in the array by name and then checking
only few overloaded signatures in case of a match.
The auxiliary map can be deployed only past some threshold of methods, so
it should not affect the common case.

Alternatively sorting the array and using binary search is quite trivial to
implement as well.


Java Class.getMethods() implementation is complicated by the fact that, 
although not specified, the order of methods in returned array is 
important. Once it changed, if I remember correctly, and broke many 
programs, so it had to be restored...


Peter



Btw, really nice benchmark.

Stanimir


On Thu, Oct 23, 2014 at 1:53 AM, Martin Buchholz 
wrote:


Here at Google we have both kinds of scalability problems - loading classes
from a classpath with 10,000 jars, and loading a single class file packed
with the maximal number of methods.  This message is about the latter.

If you have a class with ~64k methods with a superclass that also has ~64k
methods, class loading that single class will cost you ~30sec and calling
Class.getMethods another ~10sec.  Both are unacceptably slow. I think both
are due to O(N^2) algorithms, the first in hotspot, and the second in
Class.java.

I have the start of a fix for Class.java, but it makes the common case
slower.  A really good fix is harder to find.  In general, I think
Class.java could benefit from some performance-oriented rework.  Is anyone
else working on class loading performance, especially in hotspot?

Here's the benchmark (that could perhaps be integrated into openjdk even
without a fix)


http://cr.openjdk.java.net/~martin/webrevs/openjdk9/Class.getMethods-benchmark/test/java/lang/Class/getMethods/ManyMethodsBenchmark.java.html

Base class load time: 186.44 ms
getDeclaredMethods: Methods: 65521, Total time: 43.27 ms, Time per method:
0.0007 ms
getMethods: Methods: 65530, Total time: 60.82 ms, Time per method:
0.0009 ms
Derived class load time: 33440.13 ms
getDeclaredMethods: Methods: 65521, Total time: 39.71 ms, Time per method:
0.0006 ms
getMethods: Methods: 65530, Total time: 11582.54 ms, Time per
method: 0.1768 ms

Re: Loading classes with many methods is very expensive

[Aleksey Shipilev]

Hi Martin,

On 23.10.2014 02:53, Martin Buchholz wrote:
> If you have a class with ~64k methods with a superclass that also has ~64k
> methods, class loading that single class will cost you ~30sec and calling
> Class.getMethods another ~10sec.  Both are unacceptably slow. I think both
> are due to O(N^2) algorithms, the first in hotspot, and the second in
> Class.java.

Interesting, this is the profile:
 http://cr.openjdk.java.net/~shade/8061949/calltree-1.txt

...and I submitted two issues as the result of this quick performance
investigation. We also need better benchmarks for this.
 https://bugs.openjdk.java.net/browse/JDK-8061949
 https://bugs.openjdk.java.net/browse/JDK-8061950

Nashorn also generates the mammoth classes on many cases, and therefore
solving both should (at least marginally) help there as well.

-Aleksey.

Re: Loading classes with many methods is very expensive

[Stanimir Simeonoff]

Class.java can easily be improved by adding an auxiliary  HasMap indexing the position in the array by name and then checking
only few overloaded signatures in case of a match.
The auxiliary map can be deployed only past some threshold of methods, so
it should not affect the common case.

Alternatively sorting the array and using binary search is quite trivial to
implement as well.

Btw, really nice benchmark.

Stanimir


On Thu, Oct 23, 2014 at 1:53 AM, Martin Buchholz 
wrote:

> Here at Google we have both kinds of scalability problems - loading classes
> from a classpath with 10,000 jars, and loading a single class file packed
> with the maximal number of methods.  This message is about the latter.
>
> If you have a class with ~64k methods with a superclass that also has ~64k
> methods, class loading that single class will cost you ~30sec and calling
> Class.getMethods another ~10sec.  Both are unacceptably slow. I think both
> are due to O(N^2) algorithms, the first in hotspot, and the second in
> Class.java.
>
> I have the start of a fix for Class.java, but it makes the common case
> slower.  A really good fix is harder to find.  In general, I think
> Class.java could benefit from some performance-oriented rework.  Is anyone
> else working on class loading performance, especially in hotspot?
>
> Here's the benchmark (that could perhaps be integrated into openjdk even
> without a fix)
>
>
> http://cr.openjdk.java.net/~martin/webrevs/openjdk9/Class.getMethods-benchmark/test/java/lang/Class/getMethods/ManyMethodsBenchmark.java.html
>
> Base class load time: 186.44 ms
> getDeclaredMethods: Methods: 65521, Total time: 43.27 ms, Time per method:
> 0.0007 ms
> getMethods: Methods: 65530, Total time: 60.82 ms, Time per method:
> 0.0009 ms
> Derived class load time: 33440.13 ms
> getDeclaredMethods: Methods: 65521, Total time: 39.71 ms, Time per method:
> 0.0006 ms
> getMethods: Methods: 65530, Total time: 11582.54 ms, Time per
> method: 0.1768 ms
>