Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8244960

Optimize ConcurrentHashMap lookup when backing array null

    Details

    • Type: Bug
    • Status: In Progress
    • Priority: P3
    • Resolution: Unresolved
    • Affects Version/s: None
    • Fix Version/s: None
    • Component/s: core-libs
    • Labels:
      None

      Description

      See Christoph Dreis' message on core-libs-dev
      https://markmail.org/message/daugmlvtwmhrvdrh
      ---
      I found an optimization opportunity in ConcurrentHashMap that seems relatively straight-forward.

      When ConcurrentHashMap.get() is called on an empty map, the key's hashCode() method is still called while it doesn't seem necessary to do so.

      With the attached patch I see the following results:

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

      Before patch
      Benchmark Mode Cnt Score Error Units
      Benchmark.test avgt 10 3,759 ± 0,442 ns/op
      Benchmark.test:·gc.alloc.rate avgt 10 ≈ 10⁻⁴ MB/sec
      Benchmark.test:·gc.alloc.rate.norm avgt 10 ≈ 10⁻⁶ B/op
      Benchmark.test:·gc.count avgt 10 ≈ 0 counts

      For completeness reasons, here is the benchmark I used:

      @BenchmarkMode(Mode.AverageTime)
      @OutputTimeUnit(TimeUnit.NANOSECONDS)
      public class MyBenchmark {

          @State(Scope.Benchmark)
          public static class ThreadState {

              private Map<TestKey, String> map = new ConcurrentHashMap<>();
              private TestKey key = new TestKey(Collections.singleton("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();
              }

      }

      This usually happens if the map is not populated yet - which is also the case for some JDK internal usages. But I've also seen cases where the map stays empty during runtime[1].

      If you think, this is worthwhile I'd appreciate if this patch could be sponsored.

      Cheers,
      Christoph

      [1] https://github.com/spring-projects/spring-framework/blob/master/spring-core/src/main/java/org/springframework/core/SimpleAliasRegistry.java#L49


      ========= PATCH ==========

      --- a/src/java.base/share/classes/java/util/concurrent/ConcurrentHashMap.java Wed May 13 16:18:16 2020 +0200
      +++ b/src/java.base/share/classes/java/util/concurrent/ConcurrentHashMap.java Wed May 13 19:15:46 2020 +0200
      @@ -932,10 +932,9 @@
            * @throws NullPointerException if the specified key is null
            */
           public V get(Object key) {
      - Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
      - int h = spread(key.hashCode());
      + Node<K,V>[] tab; Node<K,V> e, p; int h, n, eh; K ek;
               if ((tab = table) != null && (n = tab.length) > 0 &&
      - (e = tabAt(tab, (n - 1) & h)) != null) {
      + (e = tabAt(tab, (n - 1) & (h = spread(key.hashCode())))) != null) {
                   if ((eh = e.hash) == h) {
                       if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                           return e.val;


        Attachments

          Activity

            People

            • Assignee:
              martin Martin Buchholz
              Reporter:
              martin Martin Buchholz
            • Votes:
              0 Vote for this issue
              Watchers:
              2 Start watching this issue

              Dates

              • Created:
                Updated: