Articles / Systems Programming

776 words

  • go
  • atomics
  • cpu-cache
  • false-sharing
  • performance
  • concurrency

Why a Lock-Free Counter Slows Down as You Add Cores

You replace a mutex-protected counter with atomic.Int64, expecting it to scale. It does not: with many cores hammering it, each increment can cost far more than on a single core. Nothing is blocking and nobody waits on a lock, yet it is still slow. The cost has moved into the hardware.

The experiment

Here is a benchmark with three counters:

  • one shared atomic;
  • one atomic per CPU, packed side by side in a slice;
  • one atomic per CPU, padded so each sits alone.
package counter

import (
	"runtime"
	"sync/atomic"
	"testing"
)

type padded struct {
	n atomic.Int64
	_ [56]byte // pad to 64 bytes, a typical x86 cache line
}

func BenchmarkShared(b *testing.B) {
	var c atomic.Int64
	b.RunParallel(func(pb *testing.PB) {
		for pb.Next() {
			c.Add(1)
		}
	})
}

func BenchmarkPacked(b *testing.B) {
	c := make([]atomic.Int64, runtime.GOMAXPROCS(0))
	var ticket atomic.Int64
	b.RunParallel(func(pb *testing.PB) {
		s := &c[int(ticket.Add(1)-1)%len(c)]
		for pb.Next() {
			s.Add(1)
		}
	})
}

func BenchmarkPadded(b *testing.B) {
	c := make([]padded, runtime.GOMAXPROCS(0))
	var ticket atomic.Int64
	b.RunParallel(func(pb *testing.PB) {
		s := &c[int(ticket.Add(1)-1)%len(c)].n
		for pb.Next() {
			s.Add(1)
		}
	})
}

Run it with go test -bench . -cpu 1,2,4,8. I am not quoting numbers, because they depend heavily on your CPU. The shape is what matters, and it is consistent: Shared gets worse per operation as -cpu rises, while Padded stays flat. Packed usually lands somewhere ugly in between.

What the hardware is doing

CPUs do not share memory byte by byte. They move it around in cache lines, typically 64 bytes on x86 (some ARM parts use 128). Before a core can modify a line, it must own that line exclusively, and the coherence protocol invalidates every other core's copy.

So with one shared counter, every Add(1) goes like this:

  1. The core requests exclusive ownership of the line.
  2. The previous owner's copy is invalidated and the line travels across to the new core.
  3. The core does its increment.
  4. Another core immediately asks for the line, and it moves again.

The increment itself is trivial. The line bouncing between cores is the expensive part, and it is strictly serial: only one core can own the line at a time. Adding cores adds more queueing for that one line, not more throughput.

Quick detour: "lock-free" is a progress claim, not a speed claim

This is the bit that catches people out. Lock-free means some thread always makes progress; it says nothing about how fast. On x86 an atomic add is a single locked instruction that cannot fail, so there is no retry loop here at all.

A compare-and-swap loop is worse under contention, because losers fail and go round again, each time re-fetching the line. Same line ping-pong, plus wasted work. The word "lock-free" on the tin tells you nothing about either.

Why the packed version is also slow

Giving each goroutine its own counter looks like the fix. But eight atomic.Int64 values are 64 bytes in total, so they all sit in one cache line (or two, depending on alignment).

The cores never touch the same variable, yet they fight over the same line. This is false sharing: logically independent data that shares a line behaves as if it were shared. The hardware tracks ownership per line, not per variable, so it cannot tell the difference.

The fix: one line per writer

The padded struct above is the whole trick. Each counter occupies a full cache line, so a core's increments stay in its own cache with no traffic to the others. The write path then scales almost linearly.

The price is on the read side. To get the total you have to sum every shard:

func total(c []padded) int64 {
	var sum int64
	for i := range c {
		sum += c[i].n.Load()
	}
	return sum
}

That is not a snapshot of one instant, because increments carry on while you loop. For a metrics counter that is fine. If you need an exact count at a precise moment, sharding is the wrong tool.

Caveats worth knowing

  • The padding size is a guess about the CPU. 64 bytes suits most x86 chips; Apple silicon uses 128-byte lines, so pad to 128 if you target it. The golang.org/x/sys/cpu package has a CacheLinePad type for exactly this.
  • Alignment is not guaranteed. A slice of 64-byte structs does not have to start on a 64-byte boundary, so a counter can straddle two lines. Go does not give you a direct way to demand that alignment for a slice, which is why generous padding is the usual answer.
  • Assigning goroutines to shards is its own problem. The ticket scheme in the benchmark is stable per goroutine, but real code often just hashes something or uses a per-worker struct. Go has no cheap "current CPU" call, and goroutines can migrate between cores anyway.

Do you need to bother?

Usually not. If a counter is incremented a few thousand times a second, a single atomic is fine and sharding is just more code to get wrong. This only pays off when many cores increment the same variable continuously: request counters on a hot path, per-packet statistics, that sort of thing.

Measure first with the benchmark above, ideally on the actual hardware. If Shared and Padded come out the same at your core count, leave it alone.

← All articles