这些线路是否在无锁队列中是不必要的？

Question

以下是使用compareAndSet(在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;
        }
    }
}

(头部和尾部是队列的成员)

在deq和enq函数中,第一次检查对我来说似乎没有必要.(那些评论"???")我怀疑它只是为了某种优化.

我在这里错过了什么吗？这些检查是否会影响代码的正确性？

(代码取自"多处理器编程的艺术",虽然我重构了代码样式以减少嵌套ifs和elses,同时保持代码等效)

Answer 1

是的，在 Java 中，考虑到它有垃圾收集功能，这些 if 只具有优化的真正价值，而且它有点大：与仅从内存中读取相比，CAS 非常昂贵，因此请确保该值在同时，从而减少后续 CAS 失败的机会，有助于减少 CAS 重试次数，从而提高性能。

您还可以将第一个==最后一个&&尾部更新检查移到head.CAS内部，作为进一步的优化：只有当头部更新时，尾部才会落后，因此只有当CAS成功时才进行检查才有意义。您也可以将 tail.get 移到那里，因为您在其他地方不需要它。下面的示例代码。希望这可以帮助！

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

}