A shared index-update queue on one of our workers was the wall in every profile: sixteen goroutines contending on a single mutex, and the flame graph showing sync.(*Mutex).Lock as a flat bar. The obvious next step – replace the mutex with a lock-free structure – is one of the few performance moves where the “obvious” answer is frequently wrong. We benchmarked both, shipped a lock-free stack for one hot path, and learned exactly where the boundary between “lock-free helps” and “lock-free loses” sits.

What lock-free actually buys

A CAS-based structure avoids the mutex’s three costs: the lock handoff, the goroutine park/wake cycle when a thread loses, and the contended lock’s cache-line ping-pong. But it does not remove contention – a failed CompareAndSwap just retries, burning CPU while it waits. Lock-free is bounded blocking, not no waiting.

The one thing Go gives you that the classic literature does not: the GC handles memory reclamation. A popped node is garbage when no goroutine references it, and the GC will not collect a node a goroutine still holds in a local variable. That means you do not need hazard pointers or epoch-based reclamation, which is half of why lock-free stacks are hard in C++. This is the single biggest difference between reading about Treiber stacks and writing one in Go.

The Treiber stack in Go

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
type Node struct {
	Value interface{}
	Next  unsafe.Pointer
}

type Stack struct {
	head unsafe.Pointer
}

func (s *Stack) Push(v interface{}) {
	n := &Node{Value: v}
	for {
		head := atomic.LoadPointer(&s.head)
		n.Next = head
		if atomic.CompareAndSwapPointer(&s.head, head, unsafe.Pointer(n)) {
			return
		}
	}
}

func (s *Stack) Pop() (interface{}, bool) {
	for {
		head := atomic.LoadPointer(&s.head)
		if head == nil {
			return nil, false
		}
		n := (*Node)(head)
		next := atomic.LoadPointer(&n.Next)
		if atomic.CompareAndSwapPointer(&s.head, head, next) {
			return n.Value, true
		}
	}
}

Push is the easy half: set the new node’s Next to the observed head and CAS it in. Pop has the classic race – between reading n.Next and CAS-ing, another goroutine may have changed the head, in which case the CAS fails and you retry with fresh observations. sync/atomic’s pointer loads and CAS are sequentially consistent, so the ordering is handled for you; do not mix plain n.Next reads into the loop without the atomic forms.

The ABA trap

ABA is the classic lock-free failure: a CAS succeeds because the pointer value matches, but the configuration changed in between. For a stack, this happens when node A is popped, then later pushed back so head points at A again – and a concurrent Pop that observed A.Next = B succeeds against a head that now points at A with a different Next.

In Go this is not a theoretical problem, it is a rule about your own code:

• The GC prevents use-after-free, so the dangerous C++ version of ABA is unreachable.
• But if you “optimize” by pooling nodes and reusing a popped node for the next Push, you reintroduce ABA directly – the same node value returns to the head with stale Next data, and a concurrent CAS can succeed against the wrong configuration.

Our rule: always allocate a fresh node on Push, never reuse a popped one. With fresh allocations, a popped node is gone, ABA cannot occur, and the allocation cost is an mcache bump that is cheaper than the lock it replaced. The moment you add node pooling, you void the correctness warranty. If profiling says allocation is the problem, fix allocation – do not fix it by breaking the stack.

The producer/consumer caveat

A Treiber stack is MPSC-friendly (multiple producers, one consumer) in the sense that the head CAS serializes everyone – and that is exactly the problem. Every producer spins on the same head word, which lives in one cache line. Under sustained contention from sixteen goroutines, the head line is the bottleneck, and the lock-free version stops being faster than the mutex. Our bench:

1
2
3
BenchmarkStackMutex-16    8 goroutines   78 ns/op
BenchmarkStackTreiber-16  8 goroutines   52 ns/op
BenchmarkStackTreiber-16  32 goroutines  210 ns/op  (CAS retries dominate)

The lock-free version wins at 8 goroutines and loses at 32, because the mutex parks losers instead of letting them spin on a cache line. The 32-goroutine case is not exotic – it is a worker pool at full tilt.

When to reach for it

Lock-free is the exception, not the default. Our practical order of attack:

1. Shard first. We got a 4x win from 16 mutex-guarded queues indexed by goroutine, with no atomic and no unsafe at all. Contention divided by 16 is not contention.
2. A channel is a queue. For bounded producer/consumer work, Go’s chan is internally synchronized and sized; use it before rolling your own.
3. Lock-free only when: the path is measured-hot, the contention is bounded and known (few producers), and you can write a CAS loop with bounded retries and a fresh-node policy. Keep it in one small file with a comment block explaining the invariants – future-you will need them.

Production lessons

• Pad the Stack struct to its own cache line (64 bytes on amd64) if it sits adjacent to hot fields; otherwise false sharing brings back the ping-pong you removed.
• Add runtime.Gosched() or a small backoff to the retry loop. A pure CAS spin under sustained contention can pin a core at 100% doing nothing useful.
• Run everything under -race. It does not replace reasoning about ABA, but it catches the plain misuse that lock-free code invites.
• Benchmark at the production goroutine count. 8-goroutine results are a lie about 32-goroutine behavior.