RFR: 8266642: improve ResolvedMethodTable hash function [v2]

[David Holmes]

On 11/05/2021 3:43 am, Denghui Dong wrote:
> On Fri, 7 May 2021 06:27:25 GMT, Denghui Dong <ddong at openjdk.org> wrote:
> 
>>> JDK-8249719 has fixed the bad hash function problem, however, the performance problem still exists when there are a large number of classes with the same name.
>>> Adding the address of the corresponding ClassLoaderData as a factor of hash can solve the problem.
>>
>> Denghui Dong has updated the pull request incrementally with one additional commit since the last revision:
>>
>>    minor adjustment
> 
> Hi David,
> 
> Thanks for your comment!
> 
>> Can you please elaborate on when there are large numbers of classes with the same name? I can see this may help that case but how likely is that case?
> 
> Actually, the performance problem we noticed occurred in jdk 11u, here's a simplified piece of code:

Is there a real benchmark that demonstrates this, rather than a 
micro-benchmark? I'm just trying to understand under conditions this is 
a real problem.

> 
> import java.lang.invoke.*;
> import java.util.*;
> 
> class Test {
>      public static void main(String[] args) throws Throwable{
>          MethodType mt = MethodType.methodType(void.class);
> 
>          List<MethodHandle> mhs = new ArrayList<>();
>          for (int i = 0; i < 2000; i++) {
>              // In practice, it will point to different methods
>              mhs.add(MethodHandles.lookup().findVirtual(Test.class, "call",
>                                                         MethodType.methodType(void.class))
>                                   .bindTo(new Test()));
>          }
> 
>          for (int i = 0; i < 128; i++) {
>              for (MethodHandle mh : mhs) {
>                  mh.invokeExact();
>              }
>          }
>      }
> 
>      void call() {}
> }
> 
> 
> Run: `java -Xlog:membername+table=debug Test`, and we can see that all of the LambdaForm$MH use a same slot.
> 
> [0.359s][debug][membername,table] ResolvedMethod entry added for java.lang.invoke.LambdaForm$MH/0x0000000800254840.invoke(Ljava/lang/Object;)V index 219
> [0.359s][debug][membername,table] ResolvedMethod entry added for java.lang.invoke.LambdaForm$MH/0x0000000800254c40.invoke(Ljava/lang/Object;)V index 219
> [0.359s][debug][membername,table] ResolvedMethod entry added for java.lang.invoke.LambdaForm$MH/0x0000000800255040.invoke(Ljava/lang/Object;)V index 219
> [0.359s][debug][membername,table] ResolvedMethod entry added for java.lang.invoke.LambdaForm$MH/0x0000000800255440.invoke(Ljava/lang/Object;)V index 219
> 
> 
> 
> This problem doesn't exist in jdk upstream because of the name-mangling mechanism for hidden class(ClassFileParser::mangle_hidden_class_name).

Is the output above from JDK 17 or JDK 11? It seems to show the mangled 
(well "adorned") name, so shouldn't they map to different hash buckets 
anyway?

> However, if the user creates many classes with the same name by different classloaders, the performance problems will still appear, although I also think that the general user will not implement the code in this way.
> 
> My plan is to fix this problem in the upstream and then backport it to JDK 11, what do you think?

I'm not sure it is the right approach to "fix" a problem that doesn't 
really exist in mainline just so it can be backported to 11u

>> And what is the impact on other cases as we're now increasing the overhead of the hash computation.
> 
> I think the overhead is negligible, here is a benchmark based on ResolvedMethodTableHash.java:

Thanks for confirming.

David

> 
> import org.openjdk.jmh.annotations.Benchmark;
> import org.openjdk.jmh.annotations.Fork;
> import org.openjdk.jmh.annotations.Warmup;
> import org.openjdk.jmh.annotations.Setup;
> import org.openjdk.jmh.annotations.*;
> import org.openjdk.jmh.infra.Blackhole;
> 
> import java.lang.invoke.MethodHandle;
> import java.lang.invoke.MethodHandles;
> import java.lang.invoke.MethodType;
> import java.nio.ByteBuffer;
> import java.util.ArrayList;
> import java.util.List;
> import java.util.Random;
> 
> @State(Scope.Benchmark)
> public class MyBenchmark extends ClassLoader {
> 
>      // Produce a class file with the given name and a single method:
>      //     public static native void m();
>      private int writeClass(byte[] buf, String className) {
>         ... same as ResolvedMethodTableHash.java
>      }
> 
>      private List<Class<?>> classes = new ArrayList<>();
>      private Random r = new Random();
> 
>      @Setup
>      public void prepare() throws Exception {
>          for (int i = 0; i < 5000; i ++) {
>              byte[] buf = new byte[100];
>              int size = writeClass(buf, "MH$" + i);
>              classes.add(defineClass(null, buf, 0, size));
>          }
>      }
> 
> 
>      @Benchmark
>      @Fork(value=1)
>      @Warmup(iterations = 5, time = 1)
>      public void test(Blackhole bh) throws Exception {
>          MethodHandle mh = MethodHandles.publicLookup().findStatic(classes.get(r.nextInt(5000)),
>                                                                    "m", MethodType.methodType(void.class));
>          if (mh == null) {
>              throw new RuntimeException();
>          }
>      }
> }
> 
> 
> on linux x86_64,
> 
> result with the patch:
> 
> Result: 904126.215 ±(99.9%) 26603.356 ops/s [Average]
>    Statistics: (min, avg, max) = (852079.715, 904126.215, 927791.630), stdev = 30636.464
>    Confidence interval (99.9%): [877522.859, 930729.571]
> 
> Benchmark                Mode  Samples       Score  Score error  Units
> o.s.MyBenchmark.test    thrpt       20  904126.215    26603.356  ops/s
> 
> 
> result without the patch:
> 
> Result: 883669.014 ±(99.9%) 26455.778 ops/s [Average]
>    Statistics: (min, avg, max) = (830830.551, 883669.014, 906978.220), stdev = 30466.514
>    Confidence interval (99.9%): [857213.236, 910124.792]
> 
> Benchmark                Mode  Samples       Score  Score error  Units
> o.s.MyBenchmark.test    thrpt       20  883669.014    26455.778  ops/s
> 
> -------------
> 
> PR: https://git.openjdk.java.net/jdk/pull/3901
>