CODEWITHSUNDEEP
javaconcurrencylockingconcurrenthashmap
Rocketstella
Rocketstella

Reputation: 97

Does Java ConcurrentHashMap computeIfAbsent() method support key-based "locking"?

https://docs.oracle.com/javase/8/docs/api/java/util/concurrent/ConcurrentHashMap.html#computeIfAbsent-K-java.util.function.Function-

Assume we have 10 threads calling the following codes with different key value. does the "Function" argument provided to the computeIfAbsent method run in parallel, or computeIfAbsent will "lock" the entire table?

Map<String, String> map = new ConcurrentHashMap<>();
map.computeIfAbsent(key, K -> { // long time operation });

Upvotes: 7

Views: 3907

Answers (4)

Alan Wendt
Alan Wendt

Reputation: 13

Probably blocks on the head of the hash chain.

Upvotes: -2

sjngm
sjngm

Reputation: 12861

As I had a non-conclusive behaviour in my actual use-case of a ConcurrentHashMap, I decided to prove it to myself that kaya3's answer is correct:

  private static ConcurrentHashMap<Integer, Integer> map = new ConcurrentHashMap<>();

  public static void main(String[] args) {
    System.out.println(Instant.now());

    IntStream.range(0, 10)
        .mapToObj(i -> {
          Thread thread = new Thread(() -> createValueWithSleep(i));
          thread.start();
          return thread;
        })
        .toList()
        .forEach(thread -> {
          try {
            thread.join();
          } catch (InterruptedException e) {
            throw new RuntimeException(e);
          }
        });

    System.out.println(Instant.now());
    System.out.println(map);
  }

  private static void createValueWithSleep(int i) {
    map.computeIfAbsent(i, k -> {
      try {
        System.out.println(Thread.currentThread().getName());
        Thread.sleep(1000);
      } catch (InterruptedException e) {
        throw new RuntimeException(e);
      }
      return k;
    });
  }

Basically it should create a map with ten entries. Each creation of a value contains a sleep() of one second.

Output:

2024-07-12T18:22:31.159757890Z
Thread-0
Thread-1
Thread-2
Thread-3
Thread-4
Thread-5
Thread-6
Thread-7
Thread-8
Thread-9
2024-07-12T18:22:32.166805176Z
{0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9}

Output proves:

  • code runs through in one second (not ten)
  • each creation runs in its own thread
  • at the end the map contains ten entries

Upvotes: 2

Madis P&#228;rn
Madis P&#228;rn

Reputation: 106

Seems like ConcurrentHashMap.computeIfAbsent will block on some other keys. Code below will block after adding value for i==1. On OpenJdk 17.

public static void main(String[] args) throws Exception {
var c = new ConcurrentHashMap<Integer, Boolean>(1);
var cc = new CountDownLatch(1);
new Thread(() -> {
  c.computeIfAbsent(0, k -> {
    cc.countDown();
    System.out.println("start");
    try {
      Thread.sleep(Long.MAX_VALUE);
    } catch (InterruptedException e) {
      throw new RuntimeException(e);
    }
    return true;
  });
}).start();


cc.await(1, TimeUnit.HOURS);
System.out.println("adding");
for (int i = 1; i < 10_000; i++) {
  System.out.println("i: " + i);
  c.putIfAbsent(i, true);
}
System.out.println("done");

}

Upvotes: 0

kaya3
kaya3

Reputation: 51037

There are two ways to interpret the question.

The first is, theoretically, does the specification of the ConcurrentHashMap.computeIfAbsent method guarantee to synchronize only on the particular key being computed? The answer to this comes straight from the documentation for the method:

Some attempted update operations on this map by other threads may be blocked while computation is in progress, so the computation should be short and simple, and must not attempt to update any other mappings of this map.

This is ambiguous on whether it synchronizes on the whole map or just the individual key, but it doesn't explicitly promise that updates on other keys can proceed in other threads while value-if-absent is being computed. It says "some attempted update operations" may be blocked, but doesn't impose a limit on which or how many are blocked. So the strict answer is, no, a conforming implementation is permitted to synchronize on the whole map object, and block all other updates.

The second interpretation of the question is, practically, does the implementation of the method synchronize on just the individual key? The answer to this will depend on which implementation, but will come from the source code of that implementation.

From the OpenJDK 8 implementation:

Node<K,V> f;
// ...
if(/* ... */) {
    // ...
} /* ... */ else if(/* ... */) {
    Node<K,V> r = new ReservationNode<K,V>();
    synchronized (r) {
        // ...
    }
    // ...
} /* ... */ else {
    // ...
    synchronized (f) {
        // ...
    }
    // ...
}

So the answer (at least if you're using this implementation) is yes, in practice the method synchronizes on an object (either f or r) representing an individual key/value pair, not the whole map, so updates to other keys should not be blocked while the function is computed.

Upvotes: 7

Related Questions