The other day I mentioned ConcurrentHashMap favored the judicious use of volatile over locks for read operations. The code becomes significantly more difficult to understand, but the performance gain is also significant. Write operations, however, still involved locking. The question is then, can we improve on write operations and its use of locks? The answer is yes. There are at least two approaches, both of which take a more optimistic approach than locking.
Lock-Free Algorithms
The first is to re-implement our hash table using a lock-free algorithm. Many standard data structures (linked lists, deques, hash tables, etc.) have lock-free implementations. For example, we could use Cliff Click's non-blocking (concurrent, lock-free) hash table as a replacement for our ConcurrentHashMap.
The lock-free approach typically uses a compare-and-set (CAS) or load-link/store-conditional (LL/SC) to atomicity modify values. This is significantly faster than locks under low to moderate contention. I don't know the exact details, but intuitively this makes sense since these instructions are low-level, directly hardware supported, whereas locks are more heavyweight (and are implemented using these very instructions).
/**
* Atomically increments by one the current value.
*
* @return the previous value
*/
public final int getAndIncrement() {
for (;;) {
int current = get();
int next = current + 1;
if (compareAndSet(current, next))
return current;
}
}
When it's just a single variable that requires modification, as in the above example taken from AtomicInteger, things are pretty straightforward. It's when you have to update multiple variables, as when you need to modify the tail pointer and the next to last node in a linked-list, that lock-free implementations become hairy. One way to handle this situation is to put the data structure in a state such that the next operation can put the data structure back into a consistent state, as in the concurrent linked queue implementation below.
/**
* Inserts the specified element at the tail of this queue.
*
* @return <tt>true</tt> (as specified by {@link java.util.Queue#offer})
* @throws NullPointerException if the specified element is null
*/
public boolean offer(E e) {
if (e == null) throw new NullPointerException();
Node<E> n = new Node<E>(e, null);
for (;;) {
Node<E> t = tail;
Node<E> s = t.getNext();
if (t == tail) {
if (s == null) {
if (t.casNext(s, n)) {
casTail(t, n);
return true;
}
} else {
casTail(t, s);
}
}
}
}
A key observation with lock-free algorithms is it's optimistic. Locks are pessimistic: I need to modify this variable, so I'm going to lock it to prevent others from also modifying it. The lock-free approach is optimistic: I'm going to modify this variable, if someone has modified it, I'll retry until I succeed. You can intuitively see how under low to moderate contention lock-free wins.
Transactional Memory
Now, all this is interesting, but programming lock-free algorithms is soooo 1996. For me, it's all about Software Transactional Memory (STM), a second approach to concurrency without locks. STM can perform better than the lock-based approach but without the complexity of lock-free algorithms. I can across STM while reading a paper on "Executing Java Programs with Transactional Memory" in which the authors tried mapping the existing synchronized construct to STM transactions. Granted, it was written by a bunch of Stanfurd guys, but I'll cut them some slack.
STM leverages the work done in the database community around transactions and takes a different approach to concurrency. Instead of using locks or complicated CAS tests in your code, STM code is just normal code with the addition of transactional boundaries. STM enabled code might look something like this
atomic {
balance = myHT.get(accountNumber);
myHT.put(accountNumber, balance + 10}
}
There are no locks in STM, just (atomic) transactions. The beauty of this approach is you can't have deadlocks (*). Moreover, code is now easily "composable" since you don't have to deal with how multiple locks interact when composing different blocks of code that rely on different locks. Performance-wise, if there are not too many conflicts you can intuitively see that it's better than explicitly obtaining a lock.
With STM it's the runtime's responsibility to detect conflicts. Just as in a database transaction you don't explicitly lock a table, with STM you don't explicitly lock your data. You simply tell the runtime that you want to execute this block of code in a transaction. STM is an optimistic approach: you execute your transaction and if there are conflicts you rollback/re-execute. Intuitively, optimistic approaches perform better when there is low to moderate contention/conflict. Transactional memory isn't mainstream yet but I can easily see how it'll make our programming lives so much better once all the kinks are worked out.
Conclusions
In summary, there are at least two approaches we can employ in lieu of locks. We can use lock-free algorithms but this requires extremely careful reasoning about the states of your data. Or we can think of concurrency in terms of transactions and use transactional memory to deal with conflicts.
Comments