Java 8 ConcurrentHashMap, LongAdder and StampedLock

Introduction

This tutorial covers three concurrency improvements that arrived in Java 8: a redesigned ConcurrentHashMap with atomic update methods and bulk operations, the high-throughput counter LongAdder, and StampedLock, a lock with an optimistic read mode. We will start with how Java 8's ConcurrentHashMap locks much less than a synchronized map, and the methods that make per-key updates atomic. We will then see why LongAdder beats AtomicLong when many threads count at once, and how StampedLock's optimistic reads work. Lastly, we will run an example of all three and summarise when to use each.

(This tutorial assumes the basics of threads and thread pools - see Java multithreading basicsClick to read: Java multithreading basics and ExecutorService and thread poolsClick to read: ExecutorService and thread pools.)

ConcurrentHashMap in Java 8

A map wrapped by Collections.synchronizedMap() has one lock: while one thread updates any key, every other thread waits, even for unrelated keys. ConcurrentHashMap was always finer-grained, and Java 8 rewrote it so that each bin (bucket) of the hash table is locked separately, only while it is being changed. Inserting into an empty bin needs no lock at all, just an atomic compare-and-swap, reads never lock, and a bin with many colliding keys is turned into a balanced tree to keep lookups fast.
Collections.synchronizedMap with one lock versus Java 8 ConcurrentHashMap with a lock per bin
Locking less is only half the story. The other half is that the Java 8 Map methodsClick to read tutorial: Java 8 Map merge, putIfAbsent and forEach with Examples - merge(), compute(), computeIfAbsent() and computeIfPresent() - are atomic on a ConcurrentHashMap. A read-modify-write such as "add 1 to this user's count" is one indivisible step, so two threads can never both read 5 and both write 6.

ConcurrentHashMap's new methods

  • Atomic updates: merge(), compute(), computeIfAbsent() and computeIfPresent(), run as one step per key. Keep the functions short: other updates to the same bin wait while they run.
  • Bulk operations: forEach(), search() and reduce() (with variants such as reduceValuesToLong()) run over the whole map. Their first argument is a parallelism threshold: the map processes them in parallel in the common fork/join pool if it has more entries than that. 1 means "as parallel as possible" and Long.MAX_VALUE means "sequential".
  • mappingCount(): the number of entries as a long, preferred to size() for very large maps. While other threads are updating, it is an estimate.
  • ConcurrentHashMap.newKeySet(): a thread-safe Set backed by a ConcurrentHashMap - there is no ConcurrentHashSet class.
  • As before, null keys and values are not allowed, so a null result from get() always means "absent".

LongAdder - counting without contention

AtomicLong.incrementAndGet() is thread-safe, but every thread updates the same variable with a compare-and-swap; when many threads count at once, most attempts fail and retry, and the counter becomes a bottleneck. LongAdder, added in Java 8, spreads the count over several internal cells: under contention, threads update different cells, and sum() adds the cells together when you ask for the total.
AtomicLong with one contended value versus Java 8 LongAdder with several cells added by sum()
The trade-off is in the read: sum() is not an atomic snapshot, so while other threads are incrementing, it may miss increments that happen during the call. That is fine for statistics such as request counts, and wrong for things like generating unique ids, where AtomicLong is still the right tool. Java 8 also added DoubleAdder, and LongAccumulator / DoubleAccumulator, which work the same way for any associative function such as Math::max.

StampedLock - optimistic reads

StampedLock is a lock for data that is read far more often than it is written. Like a read-write lock, it has an exclusive writeLock() and a shared readLock(), each returning a long stamp to pass back when unlocking. Its new feature is the optimistic read: tryOptimisticRead() returns a stamp without locking anything; you read the fields into local variables, then call validate(stamp). If no writer took the lock in between, the values are consistent and you are done - without any locking cost. If one did, you read again under a real read lock.
Java 8 StampedLock optimistic read - tryOptimisticRead, read fields, validate the stamp, fall back to readLock
StampedLock is not reentrant - a thread that already holds it and asks for it again deadlocks - and it does not support Conditions. Use it inside small, self-contained classes, as in the example below.

Java 8 code example of the concurrency additions

SalaryBand guards a minimum and maximum salary with a StampedLock. ConcurrencyJava8 counts logins from four threads with a ConcurrentHashMap and a LongAdder, then uses the bulk operations and the salary band.
SalaryBand.java - a class guarded by a StampedLock
//SalaryBand.java
import java.util.concurrent.locks.StampedLock;

// A pay band read far more often than it is changed
public class SalaryBand {
  private final StampedLock lock = new StampedLock();
  private double min;
  private double max;

  public SalaryBand(double min, double max) {
    this.min = min;
    this.max = max;
  }

  public void update(double newMin, double newMax) {
    long stamp = lock.writeLock();            // exclusive
    try {
      min = newMin;
      max = newMax;
    } finally {
      lock.unlockWrite(stamp);
    }
  }

  // Optimistic read: no locking unless a write happened in between
  public double midpoint() {
    long stamp = lock.tryOptimisticRead();
    double lo = min;
    double hi = max;
    if (!lock.validate(stamp)) {              // a writer got in: read again under a real lock
      stamp = lock.readLock();
      try {
        lo = min;
        hi = max;
      } finally {
        lock.unlockRead(stamp);
      }
    }
    return (lo + hi) / 2;
  }

  // Exposed only to demonstrate validate() in the example
  public StampedLock lock() { return lock; }
}
Java 8 code showing ConcurrentHashMap merge, computeIfAbsent, bulk operations, LongAdder and StampedLock
//ConcurrencyJava8.java
import java.util.Arrays;
import java.util.List;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.LongAdder;

public class ConcurrencyJava8 {

  public static void main(String[] args) throws InterruptedException {
    List<String> logins = Arrays.asList("Tom", "Harry", "Tom", "Nancy", "Tom", "Harry");

    // 1. Atomic per-key updates: 4 threads count logins at the same time
    ConcurrentHashMap<String, Integer> loginCount = new ConcurrentHashMap<>();
    LongAdder totalLogins = new LongAdder();
    ExecutorService pool = Executors.newFixedThreadPool(4);
    for (int t = 0; t < 4; t++) {
      pool.execute(() -> {
        for (int i = 0; i < 10_000; i++) {
          for (String user : logins) {
            loginCount.merge(user, 1, Integer::sum);   // atomic read-modify-write
            totalLogins.increment();                   // low-contention counter
          }
        }
      });
    }
    pool.shutdown();
    pool.awaitTermination(1, TimeUnit.MINUTES);
    System.out.println("1. per user: Tom=" + loginCount.get("Tom")
        + " Harry=" + loginCount.get("Harry") + " Nancy=" + loginCount.get("Nancy")
        + ", total (LongAdder): " + totalLogins.sum());

    // 2. computeIfAbsent creates a value only once, even when threads race
    ConcurrentHashMap<String, Set<String>> teams = new ConcurrentHashMap<>();
    teams.computeIfAbsent("Finance", k -> ConcurrentHashMap.newKeySet()).add("Tom Jones");
    teams.computeIfAbsent("Finance", k -> ConcurrentHashMap.newKeySet()).add("Harry Major");
    System.out.println("2. Finance team size: " + teams.get("Finance").size());

    // 3. Bulk operations with a parallelism threshold
    long sum = loginCount.reduceValuesToLong(1, Integer::longValue, 0L, Long::sum);
    String busiest = loginCount.search(1, (user, n) -> n >= 120_000 ? user : null);
    System.out.println("3. reduce: " + sum + ", search: " + busiest
        + ", mappingCount: " + loginCount.mappingCount());

    // 4. StampedLock: optimistic reads that are validated
    SalaryBand band = new SalaryBand(4000, 6000);
    System.out.println("4. midpoint " + band.midpoint());
    long stamp = band.lock().tryOptimisticRead();
    System.out.println("   stamp valid before a write? " + band.lock().validate(stamp));
    band.update(4500, 6500);
    System.out.println("   stamp valid after a write?  " + band.lock().validate(stamp)
        + ", new midpoint " + band.midpoint());
  }
}
 OUTPUT of the above code
1. per user: Tom=120000 Harry=80000 Nancy=40000, total (LongAdder): 240000
2. Finance team size: 2
3. reduce: 240000, search: Tom, mappingCount: 3
4. midpoint 5000.0
   stamp valid before a write? true
   stamp valid after a write?  false, new midpoint 5500.0

Explanation of the code

  • Part 1: four threads each process the six logins 10,000 times. Every merge() is atomic, so the counts are exact - Tom appears three times per pass, so 4 x 10,000 x 3 = 120,000. With a plain HashMap and get() followed by put(), updates would be lost and the totals would vary from run to run. The LongAdder total is read with sum() only after the pool has terminated, when it is exact.
  • Part 2: computeIfAbsent() creates the Finance set only if it is missing, atomically, so two threads cannot both create one and lose an add. ConcurrentHashMap.newKeySet() makes the set itself thread-safe.
  • Part 3: reduceValuesToLong(1, ...) adds all counts, potentially in parallel; search() returns the first non-null result of its function - here the only user with at least 120,000 logins; mappingCount() returns the number of entries as a long.
  • Part 4: midpoint() uses an optimistic read. The example then takes a stamp, shows that it is valid, performs a write with update(), and shows that the same stamp is no longer valid - exactly the situation in which midpoint() falls back to readLock().

When to use which

  • Shared map updated by many threads: ConcurrentHashMap with merge() or compute() - never "get, then put".
  • A counter or sum updated by many threads, read occasionally: LongAdder. Values that must be exact at every moment, such as sequence numbers: AtomicLong.
  • Small state read very often, written rarely: StampedLock with optimistic reads, kept inside one class. For simple cases, or where reentrancy is needed, synchronized or ReentrantReadWriteLock is easier to get right - see synchronized and volatileClick to read: synchronized and volatile.
  • Immutable data needs no locks at all; see Immutability in JavaClick to read: Immutability in Java.

Summary

In this tutorial we first saw how Java 8's ConcurrentHashMap locks individual bins instead of the whole map, and that its merge() and compute() methods are atomic. Next we covered its new bulk operations with parallelism thresholds, mappingCount() and newKeySet(). We then saw how LongAdder avoids contention by spreading a count over cells, and how StampedLock's optimistic read validates a stamp instead of locking. We then ran an example counting logins from four threads, building a thread-safe set, running bulk operations and invalidating an optimistic read. Lastly, we summarised when to use each tool.

Java 8 ConcurrentHashMap, LongAdder and StampedLock - JavaBrahman