Question: Here is some code from a lock-free queue using compareAndSet (in Java):

```
public void enq(T value) {
    Node newNode = new Node(value);
    while(true) {
        Node last = tail.get();
        Node next = last.next.get();

        if(last != tail.get())
            continue;   //???       

        if (next != null) { //improve tail
            tail.compareAndSet(last, next);
            continue;
        }

        if (last.next.compareAndSet(null, newNode)) {   //update last node
            tail.compareAndSet(last, newNode);  //update tail
            return;
        }
    }
}

public T deq() throws EmptyException {
    while(true) {
        Node first = head.get();
        Node last = tail.get();
        Node next = first.next.get();

        if(first != head.get())
            continue;   //???

        if(first == last) {
            if (next == null)
                throw new EmptyException();

            tail.compareAndSet(last, next);
            continue;
        }

        T value = next.value;
        if (head.compareAnsdSet(first, next)) {
            return value;
        }
    }
}

```

(head and tail are the members of the queue)

In both the deq and enq function, the first check seems unnecessary to me. (The ones commented with "???")
I suspect it's there just for some kind of optimization.

Am I missing something here? Do these checks affect the correctness of the code?

(The code is taken from the "Art of Multi-processor Programming", though I did refactor the code style to have less nested ifs and elses, while keeping the code equivalent)

Answer: 
They are not necessary but used for performance reasons, notice the check occurs without using an atomic operation.

Example costs from [MSDN](http://msdn.microsoft.com/en-us/library/ee418650%28v=vs.85%29.aspx):

* MemoryBarrier was measured as taking 20-90 cycles.
* InterlockedIncrement was measured as taking 36-90 cycles.
* Acquiring or releasing a critical section was measured as taking 40-100 cycles.
* Acquiring or releasing a mutex was measured as taking about 750-2500 cycles.

Reference for this particular technique: 

> 
> [Rudolph & Segall 84] Rudolph, L. and
>  Segall, Z. Dy-namic Decentralized
>  Cache Schemes forMIMD Parallel
>  Processors. Invù roceedingsof
>  theíúvúth Annual Symposium on
>  Com-puter Architecture, pages
>  340i›347, 1984.
> 
> 
>
it's non-blocking linked list algorithm.
A detailed description is in the JCP book (15.4.2. A Nonblocking Linked List)