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

ConcurrentHashMap.computeIfAbsent(k,f) locks bin when k present

    Details

      Description

      FULL PRODUCT VERSION :
      java version "1.8.0_92"
      Java(TM) SE Runtime Environment (build 1.8.0_92-b14)
      Java HotSpot(TM) 64-Bit Server VM (build 25.92-b14, mixed mode)

      ADDITIONAL OS VERSION INFORMATION :
      OS X 10.11.5

      A DESCRIPTION OF THE PROBLEM :
      Generally, retrieval operations on ConcurrentHashMap are expected to be non-blocking.

      The method computeIfAbsent(k,f) is a non-mutating retrieval operation if the key is already present in the map. That's a common case when the map is used as a lazy-loading cache, which is a common use case for that method.

      However, blocking occurs even when the key is already present.

      Ideally, this should be fixed. If it can't be, then at least the method documentation should declare this behavior. In online forums, I find considerable misinformation about this, with people thinking that it won't block when the key is already present.

      This is copied from the thread dump showing contention:

        java.lang.Thread.State: BLOCKED (on object monitor)
          at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1674)
          - waiting to lock <0x0000000795f80540> (a java.util.concurrent.ConcurrentHashMap$Node)
          at local.ComputIfAbsentTest.benchComputeAbsent(ComputIfAbsentTest.java:87)



      STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
      To reproduce, run a test with 20 threads contending for the same (already-present) values in a ConcurrentHashMap.

      EXPECTED VERSUS ACTUAL BEHAVIOR :
      EXPECTED -
      Expected no blocking.
      ACTUAL -
      The contention is clearly visible in Flight Recorder data, as well as in thread dumps:

        java.lang.Thread.State: BLOCKED (on object monitor)
          at java.util.concurrent.ConcurrentHashMap.computeIfAbsent(ConcurrentHashMap.java:1674)
          - waiting to lock <0x0000000795f80540> (a java.util.concurrent.ConcurrentHashMap$Node)
          at local.ComputIfAbsentTest.benchComputeAbsent(ComputIfAbsentTest.java:87)



      REPRODUCIBILITY :
      This bug can be reproduced always.

      ---------- BEGIN SOURCE ----------
      package local;
      import java.util.ArrayList;
      import java.util.concurrent.ConcurrentHashMap;
      public class Main {
          static final int MAP_SIZE=20;
          static final int THREADS=20;
          static final ConcurrentHashMap<Integer,Integer> map = new ConcurrentHashMap<>();
          static {
              for (int i = 0; i < MAP_SIZE; i++) map.put(i, i);
          }
          static class TestThread extends Thread {
              public void run() {
                  int i=0; int result =0;
                  while(result<Integer.MAX_VALUE) {
                      i = (i+1) % MAP_SIZE;
                      result += map.computeIfAbsent(i, (key)->key+key);
                  }
              }
          }
          public static void main(String[]v) throws InterruptedException {
              ArrayList<Thread> threads = new ArrayList<>();
              for (int i=0;i<THREADS;i++) {
                  TestThread t = new TestThread();
                  threads.add(t);
                  t.start();
              }
              threads.get(0).join();
          }
      }
      ---------- END SOURCE ----------

      CUSTOMER SUBMITTED WORKAROUND :
      The following gives 6x better throughput (in a 20-thread test) for the case that the keys already exist (but is probably slower for the case that they don't):

              public V computeIfAbsent2(K key, Function<? super K, ? extends V> mappingFunction) {
                  V value = get(key);
                  if (value == null) {
                      value = mappingFunction.apply(key);
                      put(key, value);
                  }
                  return value;
              }


        Attachments

          Issue Links

            Activity

              People

              • Assignee:
                martin Martin Buchholz
                Reporter:
                webbuggrp Webbug Group
              • Votes:
                0 Vote for this issue
                Watchers:
                9 Start watching this issue

                Dates

                • Created:
                  Updated:
                  Resolved: