You are designing a heavily used shared data structure and a colleague proposes replacing its mutex with a hand-written non-blocking algorithm on the grounds that "locks are slow". How do you decide whether a non-blocking design is the right call, and what would you propose instead if it is not?

## Reframe the claim "Locks are slow" is a folk belief inherited from an era of naive lock implementations. Today, an uncontended lock acquisition is a handful of instructions on an already-owned cache line, and mature implementations spin briefly before parking a waiting thread, so short critical sections rarely reach the kernel. Meanwhile, a lock-free retry loop under contention repeatedly acquires exclusive ownership of the same cache line and throws work away on failure. Both designs serialise at the same physical bottleneck. The honest comparison is therefore not "lock versus lock-free" but "how much contended sharing does the design have at all". ## What non-blocking actually buys 1. **Scheduler independence.** A blocking design's worst case is the lock holder being descheduled at the wrong instant — preempted by a higher-priority thread, taking a page fault, hitting a runtime pause, or being killed. Every waiter then waits for the scheduler, not for the work. Lock-free algorithms have no holder, so no such dependency exists. 2. **Bounded tail latency.** Where the requirement is a percentile, not a mean, the blocking worst case may be unacceptable even though the average is fine. 3. **Contexts that must not block.** Signal handlers, interrupt paths, real-time threads, and code that must remain usable when other participants may die. 4. **Priority inversion avoidance** without needing inheritance protocols. Notice that none of these is "more operations per second". If someone's justification is throughput, they have probably misdiagnosed the problem. ## The costs - **Correctness is genuinely hard.** Memory ordering must be right; intermediate states must be legal and detectable; multi-step updates need helping so a stalled thread cannot strand the structure. Reclaiming nodes that other threads may still be dereferencing is a research-grade subproblem in its own right, and in environments without automatic memory management it is where most hand-rolled attempts fail. - **Testing is weak.** Bugs appear as rare interleavings under specific hardware and load. Ordinary unit tests do not find them. You need history-based linearizability checking, systematic interleaving exploration, long stress runs across different machines — and you must budget for that. - **Maintenance burden.** The next engineer to touch the file must reconstruct an invariant argument that is not visible in the code. A subtle change silently breaks it. - **Tail behaviour can be worse.** A retry loop under heavy contention can starve an individual thread indefinitely; lock-freedom guarantees system progress, not per-thread bounds. ## The decision procedure I would use 1. **Measure.** Is the structure actually the bottleneck, at realistic contention, with realistic operation mix? Very often the hot path is elsewhere, or contention is far lower than assumed. 2. **Name the requirement.** Throughput, mean latency, tail latency, or fault/preemption tolerance? Only the last two point at non-blocking designs. 3. **Try to remove the sharing.** In rough order of payoff: - **Partition**: per-core or per-shard state, combined on read. Contention disappears rather than being converted into retries. - **Batch**: amortise each shared update over many logical operations. - **Read-mostly**: build a new immutable version and publish it, so readers never write shared state. - **Single ownership**: one thread owns the structure and others send it work; hand-offs batch, ownership transfers do not. - **Shorter critical sections**: move allocation, formatting, I/O and computation outside the lock. Frequently this alone dissolves the problem. 4. **If non-blocking is warranted, do not hand-roll it.** Use a well-reviewed implementation from a standard library or an established source. Published algorithms have known proofs and known pitfalls; a bespoke one has neither. 5. **Consider a narrower non-blocking structure.** Many systems need only a single-producer/single-consumer ring buffer or a bounded queue, which are dramatically simpler and faster than a general lock-free container. 6. **Re-measure and keep the benchmark.** Whatever is chosen, the benchmark that justified it should live in the repository so a later change cannot quietly undo the result. ## What I would say to the colleague That I agree the structure deserves attention, that lock-freedom is a guarantee about scheduling rather than a speed feature, and that we should first establish which requirement is unmet. If it turns out to be a latency percentile driven by preemption of a lock holder, non-blocking is the right tool and we should adopt an existing implementation. If it is throughput, the higher-leverage change is almost always to stop sharing the hot state — and that change is also simpler to review, test and maintain, which matters more over the life of the system than any single benchmark result.