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

[Claes Redestad]

Hi,

On 2020-05-19 15:15, Christoph Dreis wrote:
> 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.

I think we should try to keep any changes here as simple as possible.

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

Something like that, yes.

Thanks!

/Claes

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