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?