Lock-free Deque in Amino project

At fist, Amino Deque implements the algorithm invented by Maged M. Michael in the great paper "CAS-Based Lock-Free Algorithm for Shared Deques".

The deque is a doublely ended queue. Insertion and deletion can happen at both ends. Internally, this deque is represented as a doubly linked list. For each deque, there is an anchor object which comprise of 2 pointers and 1 flag. The pseudo-code is as shown below:

Anchor{
Node left, right;
enum {STABLE, LEFT, RIGHT} flag;
} anchor;

The key idea of this deque algorithm is to automatically updating this anchor field when deque is being changed. An anchor object occupies more than a machine word. Until now, there is no portable way to automatically updating such an "wide" object in Java. Actually, we don't need a wider "CAS" for implementing lock free deque. The idea is simple:

1. We make Anchor immutable and use an AtomicReference to wrap it
2. Whenever we want to update an anchor, we create a new Anchor object and use AtomicReference.compareAndSwap() to update the anchor automatically.

Above approach behaves differently as a wider "CAS" for some special cases. For example, it will judge equalism by comparing identity. It means even two objects has exactly same internal states, "CAS" will fail in comparison phase.
Besides, there is an object allocated for each updating. Will this be a big overhead? Since memory allocation in Java is relatively cheaper than other languages, this approach works well when frequency is moderate. Performance charts are shown below:



This deque is not completely compatible with standard JDK API. For example, it doesn't support element deletion by iterator.remove(). This is normal to Amino lock-free components. To implement such an unusual method for deque, performance of other frequently used methods such as addFirst()/pollFirst()/addLast()/pollLast() will become much slower than before. That's the reason why Amino library choose not to support such methods. I personally don't think it's a big problem. After all, if a data structure supports deletion in the middle, can it still be called a deque/queue/stack?

Performance of Amino Queue

Now we got the performance result of Amino Queue in an 8-core X86 machine which is running Linux and IBM JDK v6. We compared the performance of Amino's LockFreeQueue and java.util.concurrent.ConcurrentLinkedQueue. Both of the two queues used lock-free algorithm. Amino queue's algorithm comes from the brilliant paper "An Optimistic Approach to Lock-Free FIFO Queues" of Edya Ladan-Mozes and Nir Shavit. Result of the micro-benchmark shows Amino queue has some advantage:


The key idea behind the new algorithm is a novel way of replacing the singly-linked list of Michael and Scott, whose pointers are inserted using a costly compare-and-swap (CAS) operation, by an optimistic doubly-linked list, whose pointers are updated using a simple store, yet can be fixed if a bad ordering of events causes them to be inconsistent.

Performance of Amino Stack

In Amino library, stack is the simplest and yet the most useful component. According to our performance test, Amino's stack is far more faster than a lock-protected stack. Today I rerun the performance test on a 8-core X86-64 machine and result is as shown in below diagrams:










In the performance test, the 1st step is warm-up with 8 threads. That's the reason that first column of every bar charts has a label of "8". After that, we increase the thread number from "1" to "128". The test complete in 1,039.557 second.

The code (Apache license) of LockFreeStack can be downloaded at Amino's SF.net SVN