Proper use of AtomicReference.compareAndSet to implement the stack

Question

I experimented with java.util.concurrent and tried to correctly determine how to use AtomicReference.compareAndSet correctly to control concurrent access to a common state unit.

In particular: the correct and safe use of compareAndSet? Any pitfalls?

My test class is a simple stack based on a linked list of nodes.

public class LinkedStack<T> { AtomicReference<Node<T>> topOfStack=new AtomicReference<Node<T>>(); public T push(T e) { while(true) { Node<T> oldTop=topOfStack.get(); Node<T> newTop=new Node<T>(e,oldTop); if (topOfStack.compareAndSet(oldTop, newTop)) break; } return e; } public T pop() { while(true) { Node<T> oldTop=topOfStack.get(); if (oldTop==null) throw new EmptyStackException(); Node<T> newTop=oldTop.next; if (topOfStack.compareAndSet(oldTop, newTop)) return oldTop.object; } } private static final class Node<T> { final T object; final Node<T> next; private Node (T object, Node<T> next) { this.object=object; this.next=next; } } ................... } 

Answer 1

In the current form, it is correct.

Your structure is known as the Treiber Stack. This is a simple, thread-safe, block-free structure that suffers from a single point of contention ( topOfStack ) and therefore tends to scale up a lot (in competition it will be trash, and this does not work very well with MMU). This is a good option if competition is likely to be low, but thread protection is still required.

For further reading on stack scaling algorithms, see "Scalable Stack Algorithm Without a Stack" (pdf) by Danny Handler, Nir Shawit, and Lena Yerushalmi.

Answer 2

Yes, that's exactly how to use it.

Perhaps the following syntax will be more elegant:

 Node<T> oldTop = null; Node<T> newTop = null; do { oldTop=topOfStack.get(); newTop=new Node<T>(e,oldTop); } while (!topOfStack.compareAndSet(oldTop, newTop)); 

Answer 3

Everything looks good (nothing new from what axtavt said), one thing that I think is worth noting is that the speed of unsuccessful pop music or push is now double that of, say, ConcurrentLinkedQueue. When I say “fail,” I just want to say that you will have to execute the while loop again, assuming another thread appears or is pushed in front of you.

Despite the fact that this may be outside the scope of what you are trying to achieve, some kind of delay protocol will help performance in case of high competition.