CODEWITHSUNDEEP
javamultithreadinglock-free
Shiroko
Shiroko

Reputation: 1427

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

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)

Upvotes: 7

Views: 415

Answers (3)

yetanothercoder
yetanothercoder

Reputation: 1709

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

Upvotes: 0

llongi
llongi

Reputation: 733

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;
    }
}

}

Upvotes: 3

Steve-o
Steve-o

Reputation: 12866

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.

Upvotes: 2

Related Questions