Implementing Lock Free Stacks

Welcome back to your journey through lock-free programming in Go. Building on the knowledge from our last lesson on atomic operations, we'll now dive into a practical implementation of a lock-free stack. This lesson is a crucial next step in understanding how to create efficient, thread-safe data structures without using traditional locks. By the end of this unit, you'll have a firmer grasp on how to manage concurrency with atomic operations.

In this lesson, you'll learn how to implement a lock-free stack using atomic operations, but before we move on, let's understand why we need lock-free data structures in the first place.

In the previous course, we learned about lock-based data structures, where we use locks to protect shared resources from concurrent access. This approach ensures that only one goroutine can access the resource at a time, and a logical question arises: why do we need lock-free data structures? The answer lies in the limitations of lock-based approaches. Locks can introduce performance bottlenecks, especially in highly concurrent applications, where contention for locks can lead to goroutine contention and reduced scalability. Lock-free data structures, on the other hand, allow multiple goroutines to access shared resources concurrently without blocking each other. This approach can improve performance and scalability in multithreaded applications.

Here are some real-world scenarios where lock-free data structures can be beneficial over lock-based ones:

• High-performance applications requiring low latency and high throughput, such as financial trading systems, gaming engines, and real-time analytics platforms.
• Applications with a large number of goroutines contending for shared resources, where lock contention can lead to performance degradation.
• Applications requiring high scalability to utilize the full potential of modern multicore processors.

Here's a simple example to illustrate the lock-free stack concept:

package main

import (
    "fmt"
    "sync/atomic"
    "time"
    "unsafe"
)

type Node struct {
    data int
    next unsafe.Pointer // *Node
}

type LockFreeStack struct {
    head unsafe.Pointer // *Node
}

func NewLockFreeStack() *LockFreeStack {
    return &LockFreeStack{
        head: nil,
    }
}

func (s *LockFreeStack) Push(value int) {
    newNode := &Node{
        data: value,
        next: nil,
    }
    
    for {
        oldHead := atomic.LoadPointer(&s.head)
        newNode.next = oldHead
        
        // Print statement for push operation
        fmt.Printf("Pushing: %d\n", value)
        
        if atomic.CompareAndSwapPointer(&s.head, oldHead, unsafe.Pointer(newNode)) {
            break
        }
    }
}

func (s *LockFreeStack) Pop() (int, bool) {
    for {
        oldHead := atomic.LoadPointer(&s.head)
        
        if oldHead == nil {
            // Print if pop fails
            fmt.Println("Pop failed - stack is empty.")
            return 0, false
        }
        
        oldHeadNode := (*Node)(oldHead)
        newHead := oldHeadNode.next
        
        // Print statement for pop attempt
        fmt.Println("Attempting to pop...")
        
        if atomic.CompareAndSwapPointer(&s.head, oldHead, newHead) {
            result := oldHeadNode.data
            // Print the popped value
            fmt.Printf("Popped: %d\n", result)
            return result, true
        }
    }
}

In this example, we've implemented a simple lock-free stack using atomic operations with the following components:

• We define a Node structure to represent each element in the stack. Each node contains a data value and a next pointer to the next node stored as an unsafe.Pointer. This type is necessary for atomic pointer operations in Go.
• The LockFreeStack struct contains a single member variable head of type unsafe.Pointer. This pointer points to the top of the stack.
• The Push method adds a new element to the stack. It creates a new Node with the given value, sets its next pointer to the current head of the stack, and then atomically updates the head pointer to point to the new node. The atomic.CompareAndSwapPointer function is used to perform the atomic update in a loop until it succeeds.
• The Pop method removes the top element from the stack. It loads the current head, then repeatedly attempts to swing head to the next node using atomic.CompareAndSwapPointer. If the stack is empty (oldHead == nil), it returns 0, false. Otherwise, it reads the node's data and returns it along with true. Note that Go's garbage collector will automatically handle the memory of the removed node.

Next, let's use the lock-free stack in a multithreaded environment to see how it performs under concurrent access.

package main

import (
    "fmt"
    "sync"
    "time"
)

func pushItems(stack *LockFreeStack, start, end int, wg *sync.WaitGroup) {
    defer wg.Done()
    for i := start; i < end; i++ {
        stack.Push(i)
        time.Sleep(50 * time.Millisecond) // Add delay
    }
}

func popItems(stack *LockFreeStack, count int, wg *sync.WaitGroup) {
    defer wg.Done()
    for i := 0; i < count; i++ {
        stack.Pop()
        time.Sleep(30 * time.Millisecond) // Add delay
    }
}

func main() {
    stack := NewLockFreeStack()
    var wg sync.WaitGroup

    // Create multiple goroutines for push and pop operations
    wg.Add(4)
    go pushItems(stack, 1, 10, &wg)
    go popItems(stack, 7, &wg)
    go pushItems(stack, 10, 20, &wg)
    go popItems(stack, 7, &wg)

    wg.Wait()
}

Here we have a simple main function that creates multiple goroutines to perform push and pop operations on the lock-free stack concurrently. The pushItems function pushes a range of integers onto the stack with a delay of 50 milliseconds between each push operation. The popItems function pops a specified number of items from the stack with a delay of 30 milliseconds between each pop operation. We use a sync.WaitGroup to wait for all goroutines to complete before the program exits.

When you run this code, you'll see the push and pop operations interleaved across multiple goroutines, demonstrating the lock-free stack's ability to handle concurrent access without blocking. You can experiment with different goroutine counts, delays, and stack sizes to observe how the lock-free stack behaves under various conditions. Note that the output may vary depending on the timing of goroutine execution, and the printed messages might be interleaved since we are not using any synchronization mechanisms to order the output.

Lock-free stacks are important because they ensure high performance and scalability in applications requiring concurrent access. They help avoid performance bottlenecks commonly associated with traditional locks. With a lock-free stack, you can achieve improved responsiveness and throughput in your multithreaded applications. By learning how to implement these structures, you'll be better equipped to write software that maximizes the capabilities of modern multicore processors.

Excited to see lock-free programming in action? Let's jump into the practice section and build your own lock-free stack!