When you first start dipping your toes into lock-free programming, it's easy to fall into the trap of thinking that simply wrapping a variable in std::atomic makes your entire data structure thread-safe. It doesn't. Atomic variables guarantee that a single read or write is indivisible, but they don't magically make a sequence of operations atomic.

Take a look at this attempt at a lock-free stack push operation. At first glance, it looks fine because we're using an atomic head pointer.

struct Node {
    int data;
    Node* next;
};

std::atomic<Node*> head{nullptr};

void push(int val) {
    Node* newNode = new Node{val, nullptr};
    // I'm using an atomic, so this should be safe, right?
    newNode->next = head.load(); 
    head.store(newNode);
}

The "Lost Update" Race Condition

If you run this in a high-concurrency environment, you'll notice nodes disappearing from your stack. This is a classic "lost update" bug. Here is exactly what's happening: Thread A loads the current head (let's say it's Node 10). Simultaneously, Thread B loads the same head (Node 10). Thread A stores its newNode as the head. Then, Thread B stores its newNode as the head.

Because Thread B had no idea Thread A just updated the head, Thread B's next pointer still points to Node 10. Node A is now completely orphaned in memory—it's not in the stack, and you've just leaked memory. The load and store were individually atomic, but the gap between them was a window for failure.

Solving it with Compare-and-Swap

To fix this, we need a way to say: "Update the head to my new node, but only if the head is still the same node I saw when I started." In C++, we do this with compare_exchange_weak (often called CAS - Compare-And-Swap).

void push(int val) {
    Node* newNode = new Node{val, nullptr};
    
    // We load the current head into a local variable
    Node* currentHead = head.load();
    
    do {
        // Update our new node's next pointer to the current head
        newNode->next = currentHead;
        
        // compare_exchange_weak does the heavy lifting:
        // If head == currentHead, it sets head = newNode and returns true.
        // If head != currentHead, it updates currentHead to the actual current head and returns false.
    } while (!head.compare_exchange_weak(currentHead, newNode));
}

I used compare_exchange_weak instead of strong here. In a loop like this, the "weak" version is generally more performant on ARM and PowerPC architectures because it's allowed to fail spuriously even if the values match. Since we're looping anyway, a spurious failure doesn't hurt us—it just means we try again.

The Nuance of Memory Ordering

You'll notice I used the default memory ordering in the example above, which is std::memory_order_seq_cst (sequentially consistent). It's the safest option, but it's also the slowest because it forces a total global ordering of operations across all CPU cores.

In a real-world high-performance system, you'd likely optimize this. For the push, we need the newNode's data to be visible to any thread that later pops it. This means the store (inside the CAS) needs release semantics, and the load needs acquire semantics. If you use memory_order_relaxed here, a different thread might see the new head pointer but see garbage data inside the Node because the CPU reordered the writes. Lock-free programming isn't just about avoiding locks; it's about managing how memory is synchronized between cores.

📋 Practical Task

Implement a Lock-Free Stack Pop Operation

Now that you've seen how to push to a Treiber Stack using compare_exchange_weak, your task is to implement the pop function. This is slightly trickier because you have to handle the empty stack case and ensure you don't suffer from a race condition where the head is changed between the time you read it and the time you try to remove it.

Requirements:

• The function should return a std::optional<int> (or a similar mechanism) to handle cases where the stack is empty.
• Use std::atomic<Node*> head.
• Implement a loop using compare_exchange_weak to ensure that the node being popped is still the current head at the moment of removal.
• Ensure you properly delete the popped node to avoid memory leaks.

struct Node {
    int data;
    Node* next;
};

std::atomic<Node*> head{nullptr};

// TODO: Implement this function
std::optional<int> pop() {
    // Your code here
}