Setup
No AI for this kata. Work it out by hand first, then run it.
package main
import (
"fmt"
"sync"
)
func main() {
counter := 0
var wg sync.WaitGroup
for w := 0; w < 4; w++ {
wg.Add(1)
go func() {
defer wg.Done()
for i := 0; i < 100_000; i++ {
counter++
}
}()
}
wg.Wait()
fmt.Println(counter)
}The program runs on a machine with 4 or more CPU cores.
After you commit, do the kata itself:
- Explain on paper exactly how a single increment gets lost. Write out the interleaving step by step.
- Fix the program three ways: with a mutex, with an atomic counter, and by giving each worker its own count and adding them up at the end.
- Before timing them, predict which fix is fastest and which is slowest. Then measure.
Outcome
Well under 400,000, and different on every run. It’s common to see results like 140,000 or 210,000, and the number changes every time. Go’s race detector (go run -race) reports a data race on counter.
counter++ isn’t one step. It’s load, add, store. When two workers load the same value at the same time, both store value + 1, and one increment is lost. With 4 workers running flat out on separate cores, this happens constantly, not occasionally.
For the fixes, the usual ranking from slowest to fastest is: mutex, then atomic, then per-worker counts. Per-worker counts are fastest because the workers don’t share anything until the end. Results vary by machine, which is why you measure.
Senior commentary
“The most popular wrong answer is ‘slightly under’: people picture lost updates as rare collisions. They’re rare when the shared operation is a small part of the work. Here it’s all of the work, on four cores at once, so collisions are the normal case.
“The bigger lesson is in step 3. The best way to deal with shared state is often to stop sharing it. Locks and atomics make sharing safe; splitting the work makes it unnecessary.”
Discussion questions
- How would the answer change with 1 CPU core? With the loop doing real work between increments?
- Why can’t tests reliably catch this bug? What tool can?
- Where in your own code do several requests or workers update the same value?