Optimize (Linked-)HashMap lookup when backing array is null

[Christoph Dreis]

Hi Claes,

> unlike CHM, HashMap and LinkedHashMap have constant-time size/isEmpty
>  accessors - could this be used to simplify your patch?

I was wondering about that during implementation, but simply took the path I already chose for the CHM.

> So I'd like to see some analysis on microbenchmark that uses a mix of such maps in the same

I see the following results when I introduce a counter and have it look like that:

    @Benchmark
    public String test(ThreadState threadState) {
        if (threadState.counter++ % 2 == 0) {
            return threadState.emptyMap.get(threadState.key);
        }
        return threadState.map.get(threadState.key);
    }

Old
Benchmark                             Mode  Cnt   Score    Error   Units
MyBenchmark.test                      avgt   10   4,916 ±  0,106   ns/op
MyBenchmark.test:·gc.alloc.rate       avgt   10  ≈ 10⁻⁴           MB/sec
MyBenchmark.test:·gc.alloc.rate.norm  avgt   10  ≈ 10⁻⁶             B/op
MyBenchmark.test:·gc.count            avgt   10     ≈ 0           counts

New patched
MyBenchmark.test                      avgt   10   4,493 ±  0,169   ns/op
MyBenchmark.test:·gc.alloc.rate       avgt   10  ≈ 10⁻⁴           MB/sec
MyBenchmark.test:·gc.alloc.rate.norm  avgt   10  ≈ 10⁻⁶             B/op
MyBenchmark.test:·gc.count            avgt   10     ≈ 0           counts

Was that what you had in mind?

Cheers,
Christoph

Am 19.05.20, 14:47 schrieb "Claes Redestad" <claes.redestad at oracle.com>:

    Hi Christoph,

    unlike CHM, HashMap and LinkedHashMap have constant-time size/isEmpty
    accessors - could this be used to simplify your patch?

    It's easy to get heavily biased results in microbenchmarks when all you
    do is repeatedly calling down one path. That is, JIT might speculatively
    assume all HashMaps are empty or non-empty if all you do is call a
    method on only empty or non-empty maps respectively. So I'd like to see
    some analysis on microbenchmark that uses a mix of such maps in the same
    @Benchmark

    /Claes

    On 2020-05-19 14:22, Christoph Dreis wrote:
    > Hi,
    > 
    > similar to JDK-8244960[1] that I reported last week, I noticed that HashMap & LinkedHashMap could benefit from a similar improvement.
    > 
    > I used the following benchmark again to validate the results:
    > 
    > 
    > @BenchmarkMode(Mode.AverageTime)
    > @OutputTimeUnit(TimeUnit.NANOSECONDS)
    > public class MyBenchmark {
    > 
    >      @State(Scope.Benchmark)
    >      public static class ThreadState {
    > 
    >          private Map<TestKey, String> map = new HashMap<>();
    >          private TestKey key = new TestKey(Collections.singleton("test"));
    > 
    >          /*
    >          public ThreadState() {
    >              this.map.put(key, "test");
    >          }
    >          */
    >      }
    > 
    >      @Benchmark
    >      public String test(ThreadState threadState) {
    >          return threadState.map.get(threadState.key);
    >      }
    > 
    > }
    > 
    > Where TestKey is the following:
    > 
    > public class TestKey {
    > 
    > 	private final Set<String> params;
    > 
    > 	public TestKey(Set<String> params) {
    > 		this.params = params;
    > 	}
    > 
    > 	@Override
    > 	public int hashCode() {
    > 		return this.params.hashCode();
    > 	}
    > 
    > }
    > 
    > Applying the (hopefully) attached patch I see the following results:
    > 
    > Patched
    > Benchmark                             Mode  Cnt   Score    Error   Units
    > MyBenchmark.test                      avgt   10   2,717 ±  0,247   ns/op
    > MyBenchmark.test:·gc.alloc.rate       avgt   10  ≈ 10⁻⁴           MB/sec
    > MyBenchmark.test:·gc.alloc.rate.norm  avgt   10  ≈ 10⁻⁶             B/op
    > MyBenchmark.test:·gc.count            avgt   10     ≈ 0           counts
    > 
    > Old
    > Benchmark                             Mode  Cnt   Score    Error   Units
    > MyBenchmark.test                      avgt   10   3,713 ±  0,091   ns/op
    > MyBenchmark.test:·gc.alloc.rate       avgt   10  ≈ 10⁻⁴           MB/sec
    > MyBenchmark.test:·gc.alloc.rate.norm  avgt   10  ≈ 10⁻⁶             B/op
    > MyBenchmark.test:·gc.count            avgt   10     ≈ 0           counts
    > 
    > The case when the map is already filled didn't seem to show any regression.
    > 
    > Unfortunately, there is the caveat of potentially executing the hash() method twice in computeIfPresent if the remapping function returns null and the node is removed. I don't know if this case is really common (or more common than an empty map), but I should mention it for completeness reasons.
    > 
    > One common case for the above scenario is the following: I noticed that in a typical Spring-Boot app Manifest.getTrustedAttributes or Manifest.getEntries() is actually empty. Since this is used during class loading it is executed relatively frequent. I could imagine other use-cases where this might be benefitial for startup scenarios.
    > 
    > In case you think this is worthwhile, I would highly appreciate a sponsoring of the attached patch.
    > 
    > Cheers,
    > Christoph
    > 
    > 
    > [1] https://bugs.openjdk.java.net/browse/JDK-8244960
    > 
    >