Go 无锁编程

func CompareAndSwapInt32(addr *int32, old, new int32) (swapped bool)

func CompareAndSwapInt64(addr *int64, old, new int64) (swapped bool)

...

func CompareAndSwapPointer(addr *unsafe.Pointer, old, new unsafe.Pointer) (swapped bool)

// Stack 接口
type StackInterface interface {
	Push(interface{})
	Pop() interface{}
}

// 互斥锁实现的栈 (有锁编程)
type MutexStack struct {
	// 栈元素容器用切片表示
	v []interface{}
	// 互斥锁
	mu sync.Mutex
}

func NewMutexStack() *MutexStack {
	return &MutexStack{v: make([]interface{}, 0)}
}

func (s *MutexStack) Push(v interface{}) {
	// 可能同时有多个 goroutine 操作
	// 栈元素操作为临界区，需要加锁
	s.mu.Lock()
	s.v = append(s.v, v)
	s.mu.Unlock()
}

func (s *MutexStack) Pop() interface{} {
	// 可能同时有多个 goroutine 操作
	// 栈元素操作为临界区，需要加锁
	s.mu.Lock()
	var v interface{}
	if len(s.v) > 0 {
		v = s.v[len(s.v)-1]
		s.v = s.v[:len(s.v)-1]
	}
	s.mu.Unlock()
	return v
}

// 栈元素节点
type directItem struct {
	next unsafe.Pointer
	v    interface{}
}

// CAS 操作实现的栈 (无锁编程)
type LockFreeStack struct {
	// 栈元素容器用链表表示
	top unsafe.Pointer
	// 栈长度
	len uint64
}

func NewLockFreeStack() *LockFreeStack {
	return &LockFreeStack{}
}

func (s *LockFreeStack) Push(v interface{}) {
	item := directItem{v: v}
	var top unsafe.Pointer

	for {
		top = atomic.LoadPointer(&s.top)
		item.next = top
		if atomic.CompareAndSwapPointer(&s.top, top, unsafe.Pointer(&item)) {
			// 只有 1 个 goroutine 可以执行到这里
			// 栈元素数量 + 1
			atomic.AddUint64(&s.len, 1)
			return
		}
	}
}

func (s *LockFreeStack) Pop() interface{} {
	var top, next unsafe.Pointer
	var item *directItem

	for {
		top = atomic.LoadPointer(&s.top)
		if top == nil {
			return nil
		}
		item = (*directItem)(top)
		next = atomic.LoadPointer(&item.next)
		if atomic.CompareAndSwapPointer(&s.top, top, next) {
			// 只有 1 个 goroutine 可以执行到这里
			// 栈元素数量 - 1
			atomic.AddUint64(&s.len, ^uint64(0))
			return item.v
		}
	}
}

func Benchmark_Stack(b *testing.B) {
	rand.Seed(time.Now().UnixNano())

	// 初始化测试的随机参数
	length := 1 << 12
	inputs := make([]int, length)
	for i := 0; i < length; i++ {
		inputs[i] = rand.Int()
	}

	ls, ms := NewLockFreeStack(), NewMutexStack()

	b.ResetTimer()

	for _, s := range [...]StackInterface{ls, ms} {
		b.Run(fmt.Sprintf("%T", s), func(b *testing.B) {
			var c int64

			b.RunParallel(func(pb *testing.PB) {
				for pb.Next() {
					i := int(atomic.AddInt64(&c, 1)-1) % length
					v := inputs[i]
					if v >= 0 {
						s.Push(v)
					} else {
						s.Pop()
					}
				}
			})
		})
	}
}

$ go test -run='^$' -bench=. -count=1 -benchtime=2s

## 输出结果如下
Benchmark_Stack/*performance.LockFreeStack-8            16553013               134.0 ns/op
Benchmark_Stack/*performance.MutexStack-8               20625786               172.5 ns/op