Are these lines needed in an unblocked queue?

Question

Here are some codes from an unlocked 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 members of the queue)

In the deq and enq functions, the first check seems unnecessary to me. (Those who commented on "???") I suspect this is there only for some kind of optimization.

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

(The code is taken from The Art of Multiprocessor Programming, although I reorganized the code style to have less nested ifs and elses, while preserving the code equivalent)

Answer 1

Yes, in Java, given that it has garbage collection, these ifs have only real value as optimization, and it's kind of big: CAS is incredibly expensive compared to just reading from memory, so make sure that the value hasn’t changed in the meantime, and thus reduces the likelihood of a failure on subsequent CASs, helps reduce the number of CAS attempts, which helps performance.

You can also transfer the first == last && tail update check inside head.CAS, as an additional optimization: the tail can lag only if the head has been updated, so checking that only if the CAS succeeds makes sense. You can also move tail.get there, since you no longer need it. Sample code below. Hope this helps!

 public T deq() throws EmptyException { while(true) { Node first = head.get(); Node next = first.next.get(); if (first != head.get()) continue; if (next == null) { throw new EmptyException(); } T value = next.value; if (head.compareAndSet(first, next)) { Node last = tail.get(); if (first == last) { tail.compareAndSet(last, next); } return value; } } 

}

Answer 2

They are not needed, but are used for performance reasons, they notice that the verification occurs without the use of an atomic operation.

Example costs from MSDN :

• MemoryBarrier was measured as receiving 20-90 cycles.
• InterlockedIncrement was measured as taking 36-90 cycles.
• The acquisition or release of a critical section was measured as taking 40-100 cycles.
• The acquisition or release of a mutex was measured at approximately 750-2500 cycles.

Link to this particular method:

[Rudolph and Segall 84] Rudolph, L. and Segall, Z. Dy-namic Decentralized Cache Schemes for Parallel Parallel Parallel Interface Processors. Entry into force Annual Comp-Architecture Architecture Symposium, pages 340i> 347, 1984.

Answer 3

This is a non-blocking linked list algorithm. A detailed description is contained in the JCP book (15.4.2. Non-Blocking List)