215StampedLock Idioms

Author: Dr. Heinz M. KabutzDate: 2013-12-02Java Version: 8Category: Concurrency

Abstract: Java 8 includes a new synchronization mechanism called StampedLock. It differentiates between exclusive and non-exclusive locks, similar to the ReentrantReadWriteLock. However, it also allows for optimistic reads, which is not supported by the ReentrantReadWriteLock. In this newsletter, we look at some idioms on how to use this new synchronizer.

Welcome to the 215th issue of The Java(tm) Specialists' Newsletter, sent from the Island of Crete. As you would probably have heard by now, Greece is in a state of crisis. Lots of my friends have lost jobs or have had their hours reduced. On one of my flights, I learned about a great new program called "Boroume" - meaning "we can". It connects those with excess food (bakeries, hotels, restaurants, supermarkets) with those that have a need for food (orphanages, old-age homes, shelters). Thus instead of the perfectly good yesterday's bread being thrown away, it can now be consumed by someone in need. They seem to run a lean operation, meaning they do not need lots of funds to get a lot done. I sent a little bit and was overwhelmed by their response. I like clever projects like this, that maximize the available resources we have in our country.

javaspecialists.teachable.com: Please visit our new self-study course catalog to see how you can upskill your Java knowledge.

StampedLock Idioms

As you should know by now, I have a keen interest in concurrency. Even before I wrote the Concurrency Specialist Course, I was doing research for this newsletter. For example, I showed in 2008 how the ReadWriteLock could starve certain threads. In Java 5, the writers were starved and in Java 6, a single reader with many writers could go hungry for CPU cycles. The Java 5 flaw can easily be explained, but the reader starvation was not so obvious and could only be seen with careful experimentation.

The idioms for the ReentrantLock and ReentrantReadWriteLock are quite similar.

Lock lock = new ReentrantLock();

...

lock.lock();
try {
  // do something that needs exclusive access
} finally {
  lock.unlock();
}

And here is the ReentrantReadWriteLock:

ReadWriteLock rwlock = new ReentrantReadWriteLock();

...

rwlock.writeLock().lock();
try {
  // do something that needs exclusive access
} finally {
  rwlock.writeLock().unlock();
}

Even though these idioms were straightforward, a lot of programmers still got them wrong. Even books and articles had incorrect idioms. For example, some wrote the lock() method call into the try block. Or they did not have a finally block to do the unlocking. Using synchronized was so much easier, as the locking/unlocking was ensured by the syntax of the language.

The ReentrantReadWriteLock had a lot of shortcomings: It suffered from starvation. You could not upgrade a read lock into a write lock. There was no support for optimistic reads. Programmers "in the know" mostly avoided using them.

Doug Lea's new Java 8 StampedLock addresses all these shortcomings. With some clever code idioms we can also get better performance. Instead of the usual locking, it returns a long number whenever a lock is granted. This stamp number is then used to unlock again. For example, here is how the code above would look:

StampedLock sl = new StampedLock();

...

long stamp = sl.writeLock();
try {
  // do something that needs exclusive access
} finally {
  sl.unlockWrite(stamp);
}

This still begs the question - why do we need this in the first place? Let's take a slightly larger example and write it with different approaches: synchronized, synchronized/volatile, ReentrantLock, ReentrantReadWriteLock and StampedLock. Lastly we will show how the immutable approach.

BankAccount Without Any Synchronization

Our first BankAccount has no synchronization at all. It also does not check that the amounts being deposited and withdrawn are positive. We will leave out argument checking in our code.

public class BankAccount {
  private long balance;

  public BankAccount(long balance) {
    this.balance = balance;
  }

  public void deposit(long amount) {
    balance += amount;
  }

  public void withdraw(long amount) {
    balance -= amount;
  }

  public long getBalance() {
    return balance;
  }
}

Synchronized BankAccount

The second version uses the synchronized keyword to protect the methods from being called simultaneously by multiple threads on the same BankAccount object. We could either synchronize on "this" or on a private field. For our example, this would not make a difference. In this approach a thread would not be able to read the balance whilst another thread is depositing money.

public class BankAccountSynchronized {
  private long balance;

  public BankAccountSynchronized(long balance) {
    this.balance = balance;
  }

  public synchronized void deposit(long amount) {
    balance += amount;
  }

  public synchronized void withdraw(long amount) {
    balance -= amount;
  }

  public synchronized long getBalance() {
    return balance;
  }
}

Synchronized Volatile BankAccount

The third version uses a combination of the volatile and synchronized keywords. Only one thread at a time can update the balance, but another thread could read the balance in the middle of an update. The volatile modifier is absolutely necessary, since the value might get cached by a thread and so they would not necessarily see the latest value. Also, since it is a 64-bit value, it could get set in two operations on a 32-bit JVM, leading to impossible values. However, this is a very good solution, as it gives us fast reads and is easy to write and understand.

public class BankAccountSynchronizedVolatile {
  private volatile long balance;

  public BankAccountSynchronizedVolatile(long balance) {
    this.balance = balance;
  }

  public synchronized void deposit(long amount) {
    balance += amount;
  }

  public synchronized void withdraw(long amount) {
    balance -= amount;
  }

  public long getBalance() {
    return balance;
  }
}

ReentrantLock BankAccount

The fourth version is similar to the BankAccountSynchronized, except that we are using explicit locks. So what is "better" - ReentrantLock or synchronized? As you can see below, it is a lot more effort to code the ReentrantLock. In Java 5, the performance of contended ReentrantLocks was a lot better than synchronized. However, synchronized was greatly improved for Java 6, so that now the difference is minor. In addition, uncontended synchronized locks can sometimes be automatically optimized away at runtime, leading to great peformance improvements over ReentrantLock. The only reason to use ReentrantLock nowadays is if you'd like to use the more advanced features such as better timed waits, tryLock, etc. Performance is no longer a good reason.

import java.util.concurrent.locks.*;

public class BankAccountReentrantLock {
  private final Lock lock = new ReentrantLock();
  private long balance;

  public BankAccountReentrantLock(long balance) {
    this.balance = balance;
  }

  public void deposit(long amount) {
    lock.lock();
    try {
      balance += amount;
    } finally {
      lock.unlock();
    }
  }

  public void withdraw(long amount) {
    lock.lock();
    try {
      balance -= amount;
    } finally {
      lock.unlock();
    }
  }

  public long getBalance() {
    lock.lock();
    try {
      return balance;
    } finally {
      lock.unlock();
    }
  }
}

ReentrantReadWriteLock BankAccount

The fifth version uses the ReentrantReadWriteLock, which differentiates between exclusive and non-exclusive locks. In both cases, the locks are pessimistic. This means that if a thread is currently holding the write lock, then any reader thread will get suspended until the write lock is released again. It is thus different to the BankAccountSynchronizedVolatile version, which would allow us to read the balance whilst we were busy updating it. However, the overhead of using a ReentrantReadWriteLock is substantial. As a ballpark figure, we need the read lock to execute for about 2000 clock cycles in order to win back the cost of using it. In our case the getBalance() method does substantially less, so we would probably be better off just using a normal ReentrantLock.

import java.util.concurrent.locks.*;

public class BankAccountReentrantReadWriteLock {
  private final ReadWriteLock lock = new ReentrantReadWriteLock();
  private long balance;

  public BankAccountReentrantReadWriteLock(long balance) {
    this.balance = balance;
  }

  public void deposit(long amount) {
    lock.writeLock().lock();
    try {
      balance += amount;
    } finally {
      lock.writeLock().unlock();
    }
  }

  public void withdraw(long amount) {
    lock.writeLock().lock();
    try {
      balance -= amount;
    } finally {
      lock.writeLock().unlock();
    }
  }

  public long getBalance() {
    lock.readLock().lock();
    try {
      return balance;
    } finally {
      lock.readLock().unlock();
    }
  }
}

StampedLock BankAccount

Our sixth version uses StampedLock. I have written two getBalance() methods. The first uses pessimistic read locks, the other optimistic. In our case, since there are no invariants on the fields that would somehow restrict the values, we never need to have a pessimistic lock. Thus the optimistic read is only to ensure memory visibility, much like the BankAccountSynchronizedVolatile approach.

import java.util.concurrent.locks.*;

public class BankAccountStampedLock {
  private final StampedLock sl = new StampedLock();
  private long balance;

  public BankAccountStampedLock(long balance) {
    this.balance = balance;
  }

  public void deposit(long amount) {
    long stamp = sl.writeLock();
    try {
      balance += amount;
    } finally {
      sl.unlockWrite(stamp);
    }
  }

  public void withdraw(long amount) {
    long stamp = sl.writeLock();
    try {
      balance -= amount;
    } finally {
      sl.unlockWrite(stamp);
    }
  }

  public long getBalance() {
    long stamp = sl.readLock();
    try {
      return balance;
    } finally {
      sl.unlockRead(stamp);
    }
  }

  public long getBalanceOptimisticRead() {
    long stamp = sl.tryOptimisticRead();
    long balance = this.balance;
    if (!sl.validate(stamp)) {
      stamp = sl.readLock();
      try {
        balance = this.balance;
      } finally {
        sl.unlockRead(stamp);
      }
    }
    return balance;
  }
}

In our getBalanceOptimisticRead(), we could retry several times. However, as I said before, if memory visibility is all we care about, then StampedLock is overkill.

Immutable BankAccount

Our seventh version has an immutable BankAccount. Whenever we need to change the balance, we create a new account. Most Java programmers have a knee-jerk reaction to this: "Ah, but this will create too many objects!" This might be true. However, contended ReentrantLocks also create objects. Thus this argument is not always valid. You might be better off using a non-blocking algorithm that simply creates a new account and writes it into an AtomicReference using a CompareAndSwap (CAS).

public class BankAccountImmutable {
  private final long balance;

  public BankAccountImmutable(long balance) {
    this.balance = balance;
  }

  public BankAccountImmutable deposit(long amount) {
    return new BankAccountImmutable(balance + amount);
  }

  public BankAccountImmutable withdraw(long amount) {
    return new BankAccountImmutable(balance - amount);
  }

  public long getBalance() {
    return balance;
  }
}

Atomic BankAccount

We need an eigth version, just to satisfy the naysayers who want to see an atomic solution. Here we could either store the balance inside an AtomicLong or inside a volatile long and then use an AtomicLongFieldUpdater or Unsafe to set the field using a CAS.

import java.util.concurrent.atomic.*;

public class BankAccountAtomic {
  private final AtomicLong balance;

  public BankAccountAtomic(long balance) {
    this.balance = new AtomicLong(balance);
  }

  public void deposit(long amount) {
    balance.addAndGet(amount);
  }

  public void withdraw(long amount) {
    balance.addAndGet(-amount);
  }

  public long getBalance() {
    return balance.get();
  }
}

W H Y ???

We have many ways to write similar type of code. In our very simple BankAccount example, the BankAccountSynchronizedVolatile and BankAccountAtomic solutions are both simple and work very well. However, if we had multiple fields and/or an invariant over the field, we would need a slightly stronger mechanism. Let's take for example a point on a plane, consisting of an "x" and a "y". If we move in a diagonal line, we want to update the x and y in an atomic operation. Thus a moveBy(10,10) should never expose a state where x has moved by 10, but y is still at the old point. The fully synchronized approach would work, as would the ReentrantLock and ReentrantReadWriteLock. However, all of these are pessimistic. How can we read state in an optimistic approach, expecting to see the correct values?

Let's start by defining a simple Point class that is synchronized and has three methods for reading and manipulating the state:

public class Point {
  private int x, y;

  public Point(int x, int y) {
    this.x = x;
    this.y = y;
  }

  public synchronized void move(int deltaX, int deltaY) {
    x += deltaX;
    y += deltaY;
  }

  public synchronized double distanceFromOrigin() {
    return Math.hypot(x, y);
  }

  public synchronized boolean moveIfAt(int oldX, int oldY,
                                       int newX, int newY) {
    if (x == oldX && y == oldY) {
      x = newX;
      y = newY;
      return true;
    } else {
      return false;
    }
  }
}

If we use a StampedLock, our move() method look similar to the BankAccountStampedLock.deposit():

public void move(int deltaX, int deltaY) {
  long stamp = sl.writeLock();
  try {
    x += deltaX;
    y += deltaY;
  } finally {
    sl.unlockWrite(stamp);
  }
}

However, the distanceFromOrigin() method could be rewritten to use an optimistic read, for example:

public double distanceFromOrigin() {
  long stamp = sl.tryOptimisticRead();
  int localX = x, localY = y;
  if (!sl.validate(stamp)) {
    stamp = sl.readLock();
    try {
      localX = x;
      localY = y;
    } finally {
      sl.unlockRead(stamp);
    }
  }
  return Math.hypot(localX, localY);
}

In our optimistic distanceFromOrigin(), we first try to get an optimistic read stamp. This might come back as zero if a writeLock stamp has been issued and has not been unlocked yet. However, we assume that it is non-zero and continue reading the fields into local variables localX and localY. After we have read x and y, we validate the stamp. Two things could make this fail: 1. The sl.tryOptimisticRead() method might have come back as zero initially or 2. After we obtained our optimistic lock, another thread requested a writeLock(). We don't know whether this means our copies are invalid, but we need to be safe, rather than sorry. In this version we only try this once and if we do not succeed we immediately move over to the pessimistic read version. Depending on the system, we could get significant performance gains by spinning for a while, hoping to do a successful optimistic read. In our experiments, we also found that a shorter code path between tryOptimisticRead() and validate() leads to a higher chance of success in the optimistic read case.

Here is another idiom that retries a number of times before defaulting to the pessimistic read version. It uses the trick in Java where we break out to a label, thus jumping out of a code block. We could have also solved this with a local boolean variable, but to me this is a bit clearer:

private static final int RETRIES = 5;

public double distanceFromOrigin() {
  int localX, localY;
  out:
  {
    // try a few times to do an optimistic read
    for (int i = 0; i < RETRIES; i++) {
      long stamp = sl.tryOptimisticRead();
      localX = x;
      localY = y;
      if (sl.validate(stamp)) {
        break out;
      }
    }
    // pessimistic read
    long stamp = sl.readLock();
    try {
      localX = x;
      localY = y;
    } finally {
      sl.unlockRead(stamp);
    }
  }
  return Math.hypot(localX, localY);
}

Conditional Write

The last idiom to demonstrate is the conditional write. We first read the current state. If it is what we expect, then we try to upgrade the read lock to a write lock. If we succeed, then we update the state and exit, otherwise we unlock the read lock and then ask for a write lock. The code is a bit harder to understand, so look it over carefully:

public boolean moveIfAt(int oldX, int oldY,
                        int newX, int newY) {
  long stamp = sl.readLock();
  try {
    while (x == oldX && y == oldY) {
      long writeStamp = sl.tryConvertToWriteLock(stamp);
      if (writeStamp != 0) {
        stamp = writeStamp;
        x = newX;
        y = newY;
        return true;
      } else {
        sl.unlockRead(stamp);
        stamp = sl.writeLock();
      }
    }
    return false;
  } finally {
    sl.unlock(stamp); // could be read or write lock
  }
}

Whilst this idiom looks clever, I doubt it is really that useful. Initial tests have shown that it does not perform that well. In addition, it is difficult to write and understand.

This is the first in a three-part series on the StampedLock. The next one will examine how we could write the same class using non-blocking code and how the idioms could be made simpler by means of Java 8 Lambdas. The last newsletter will be dedicated to looking at how it performs against other mechanisms.

Kind regards

Heinz

P.S. Which do you think is the most popular Java library: junit, slf4j or log4j? Click here to find out if you are correct!

Comments

We are always happy to receive comments from our readers. Feel free to send me a comment via email or discuss the newsletter in our JavaSpecialists Slack Channel (Get an invite here)

Related Articles

Browse the Newsletter Archive