Thread Safe Go Lists

Welcome to another fascinating chapter in our course on lock-based concurrent data structures! In our previous lesson, we delved into the world of thread-safe queues using condition variables to enhance synchronization. This time, we shift our focus to lists. Our aim is to explore how to make a list thread-safe, ensuring that even when multiple goroutines modify it, the list remains reliable and consistent. This skill is crucial because it opens up new possibilities for developing efficient and safe concurrent applications.

While Go encourages the use of channels for communication between goroutines, understanding lock-based synchronization with sync.Mutex is equally important. Lock-based lists teach us fine-grained synchronization patterns that are valuable when we require precise control over concurrent access to shared data structures.

In this lesson, you will learn how to implement a thread-safe list using locks. We will cover various operations, such as adding, removing, and finding elements within a list.

Let's take a sneak peek at some code to get a sense of what we will be working on:

type node struct {
    mu   sync.Mutex
    data *int
    next *node
}

type ThreadSafeList struct {
    head node
}

func NewThreadSafeList() *ThreadSafeList {
    return &ThreadSafeList{
        head: node{},
    }
}

func (l *ThreadSafeList) PushFront(value int) {
    newNode := &node{
        data: new(int),
    }
    *newNode.data = value
    
    l.head.mu.Lock()
    defer l.head.mu.Unlock()
    
    newNode.next = l.head.next
    l.head.next = newNode
}

func (l *ThreadSafeList) ForEach(f func(int)) {
    current := &l.head
    current.mu.Lock()
    lk := &current.mu
    
    for current.next != nil {
        next := current.next
        next.mu.Lock()
        nextLk := &next.mu
        
        lk.Unlock()
        f(*next.data)
        
        current = next
        lk = nextLk
    }
    lk.Unlock()
}

func (l *ThreadSafeList) FindFirstIf(predicate func(int) bool) *int {
    current := &l.head
    current.mu.Lock()
    lk := &current.mu
    
    for current.next != nil {
        next := current.next
        next.mu.Lock()
        nextLk := &next.mu
        
        lk.Unlock()
        
        if predicate(*next.data) {
            result := next.data
            nextLk.Unlock()
            return result
        }
        
        current = next
        lk = nextLk
    }
    lk.Unlock()
    return nil
}

func (l *ThreadSafeList) RemoveIf(predicate func(int) bool) {
    current := &l.head
    current.mu.Lock()
    lk := &current.mu
    
    for current.next != nil {
        next := current.next
        next.mu.Lock()
        nextLk := &next.mu
        
        if predicate(*next.data) {
            current.next = next.next
            nextLk.Unlock()
        } else {
            lk.Unlock()
            current = next
            lk = nextLk
        }
    }
    lk.Unlock()
}

Here, we add a new element to the front of the list in a thread-safe manner. Each node in our list includes its own sync.Mutex, ensuring that a lock is held only for the node being modified. This strategy minimizes lock contention, making the list more efficient when accessed by multiple goroutines.

Let's explore the methods we have implemented:

• PushFront: Adds a new element to the front of the list. It locks the head node and then inserts the new node at the front.
• ForEach: Iterates over each element in the list and applies a function to it. It locks each node individually to prevent concurrent modifications.
• FindFirstIf: Searches for the first element in the list that satisfies a given predicate. It locks each node individually to ensure that the list remains consistent.
• RemoveIf: Removes elements from the list that satisfy a given predicate. It locks each node individually to prevent concurrent modifications.

Let's now see how we can use these methods to interact with our thread-safe list in a multi-threaded environment while performing various operations:

func main() {
    list := NewThreadSafeList()
    
    var wg sync.WaitGroup
    
    for i := 0; i < 10; i++ {
        wg.Add(1)
        go func(value int) {
            defer wg.Done()
            list.PushFront(value)
        }(i)
    }
    
    for i := 0; i < 5; i++ {
        wg.Add(1)
        go func(value int) {
            defer wg.Done()
            list.RemoveIf(func(v int) bool {
                return v == value
            })
        }(i)
    }
    
    for i := 0; i < 2; i++ {
        wg.Add(1)
        go func(value int) {
            defer wg.Done()
            result := list.FindFirstIf(func(v int) bool {
                return v == value
            })
            if result != nil {
                fmt.Printf("Found: %d\n", *result)
            }
        }(i)
    }
    
    for i := 0; i < 2; i++ {
        wg.Add(1)
        go func() {
            defer wg.Done()
            list.ForEach(func(value int) {
                fmt.Println(value)
            })
        }()
    }
    
    wg.Wait()
}

In this example, we create a list and spawn multiple goroutines to perform various operations on it concurrently. These goroutines add elements to the list, remove elements, search for elements, and iterate over the list. The thread-safe list ensures that these operations can be performed safely and efficiently in a multi-threaded environment.

Understanding how to implement a thread-safe list using locks is essential for building applications that require concurrent access to a collection of items. In many real-world scenarios, such as managing a list of clients in a server application or logging events in a concurrent environment, efficient and safe access to shared data structures is paramount.

By mastering these techniques, you will gain the ability to create robust and high-performance applications. You will also acquire insights into balancing the trade-offs between safety and performance, preparing you to tackle more advanced problems in concurrent programming confidently.

Are you eager to bring these ideas to life? Let's jump into the practice section and apply what we have learned in exciting real-world scenarios!