RFR: 8266642: improve ResolvedMethodTable hash function [v2]

[Denghui Dong]

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:


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).

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?

> 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:


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