Go High-Performance Programming EP11: lock-free coding

Introduction

The previous article discussed two lock-free programming strategies: eliminating shared data and avoiding concurrent access to the same data through careful design. While achieving lock-free programming is ambitious, it could be more practical. Generally, when discussing lock-free techniques, the aim is to avoid locks, and using Compare-And-Swap (CAS) is a good alternative. If CAS is insufficient, we can minimize the granularity of Mutex or replace it with RWMutex.

Advantages of Lock-Free Programming

• Reduces thread blocking and waiting time
• It avoids thread priority inversion.
• Improves concurrency performance.
• Eliminates issues like race conditions, deadlocks, and starvation.
• Simplifies and clarifies code.

This article will explore and implement several lock-free programming techniques in Go.

Channel

The Go language advocates for the principle of sharing memory through communication, as stated in its official blog: Share Memory By Communicating

Do not communicate by sharing memory; instead, share memory by communicating.

Channels enable lock-free programming because:

1. Channel transfer ownership of data.
2. The channel uses internal locks for synchronization.

For example:

type Resource string 
func Poller(in, out chan *Resource) { 
    for r := range in { 
        // Process the URL 
        // Send the processed Resource to the output channel 
        out <- r 
    } 
}

Data flows between in and out channels without multiple goroutines operate simultaneously on the same data, achieving a lock-free design.

CAS (Compare-And-Swap)

Modern CPUs support atomic CAS operations, allowing atomic data exchange in multithreaded environments. CAS helps avoid data inconsistencies caused by unpredictable execution orders and interruptions.
more about CAS: Decrypt Go: Atomic Package Addressing Concurrency Issues

Lock-Free Stack Using CAS

A stack can typically be implemented with slice and RWMutex for concurrency safety. Alternatively, CAS can be used to implement a lock-free stack. 
Below is an example:

Benchmarking

A simple benchmark test shows the lock-free stack outperforms the slice + RWMutex implementation by approximately 20%. 
The performance gains are even more significant in high-concurrency scenarios.

func BenchmarkConcurrentPushLockFree(b *testing.B) { 
    stack := NewStackByLockFree() 
    for i := 0; i < b.N; i++ { 
       stack.Push(i) 
    } 
} 
func BenchmarkConcurrentPushSlice(b *testing.B) { 
    stack := NewStackBySlice() 
    for i := 0; i < b.N; i++ { 
       stack.Push(i) 
    } 
}

➜  lock-free git:(main) ✗ go test --bench=. 
BenchmarkConcurrentPushLockFree-10      22657522                49.66 ns/op 
BenchmarkConcurrentPushSlice-10         29135671                59.04 ns/op

Struct Copy: Trading Space for Time

Struct Copy is a technique that avoids data contention by duplicating shared resources. Each goroutine operates on its copy, eliminating the need for locks.
example:

Each goroutine owns a unique instance by wrapping shared resources with a BufferWrapper, avoiding data races, and using sync.Pool further optimizes memory allocation.

Benchmarking

func BenchmarkSingleBuffer_print(b *testing.B) { 
    for i := 0; i < b.N; i++ { 
       run_buff_bench(singleBuff) 
    } 
} 
func BenchmarkBufferWrapper_print(b *testing.B) { 
    bufferWrapper := NewBufferWrapper() 
    for i := 0; i < b.N; i++ { 
       run_buff_bench(bufferWrapper) 
    } 
} 
func run_buff_bench(buff printId) { 
    wg := sync.WaitGroup{} 
    f := func(id int) { 
       defer wg.Done() 
       for j := 0; j < 10000; j++ { 
          buff.print(id) 
       } 
    } 
    for j := 0; j < 100; j++ { 
       wg.Add(1) 
       go f(j) 
    } 
    wg.Wait() 
}

BenchmarkSingleBuffer_print-10                 4         261640427 ns/op 
BenchmarkBufferWrapper_print-10               67          18320110 ns/op

A similar technique is used in fastjson’s Parser. We see this operation in many performance optimization scenarios.

Conclusion

This article explored three practical techniques for lock-free programming in Go, with performance tests validating their effectiveness. While fully lock-free programming is challenging, proper design and technique selection can significantly reduce lock usage and enhance concurrency performance.