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{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:
Node left, right;
enum {STABLE, LEFT, RIGHT} flag;
} anchor;
- We make Anchor immutable and use an AtomicReference to wrap it
- Whenever we want to update an anchor, we create a new Anchor object and use AtomicReference.compareAndSwap() to update the anchor automatically.
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?
