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<String,
>>> 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 <martinrb at google.com>
>>> 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
>>>>