Are these lines in a lock-free queue not necessary?

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)

Reticulate

They appear to be checking that the local variables have been set consistently, but I'll leave it to others to answer whether they affect the correctness of the code. – Raimes

Answer 1

Yeah, in Java, given that it has garbage collection, those ifs have only real value as optimization, and it's kinda a big one: CAS is incredibly expensive compared to just a read from memory, so making sure the value hasn't changed in the meantime, and thus decreasing the chance of failing on the subsequent CAS, helps reduce the number of CAS-retries, which helps performance.

You can also move the first == last && tail-update check to inside the head.CAS, as a further optimization: the tail can lag behind only if the head was updated, so checking that only if the CAS succeeded makes sense. You can also move tail.get there then, as you don't need it anywhere else. Example 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;
    }
}

}

Gripping

Answer 2

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

Example costs from MSDN:

• 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.

Tatyanatau

Answer 3

it's non-blocking linked list algorithm. A detailed description is in the JCP book (15.4.2. A Nonblocking Linked List)

Cl