Deep Dive Summary: Lock-free Programming is Dead - Long Live Lock-free Programming!
Speaker: Fedor Pikus
Conference: C++Now 2026
Topic: Microarchitecture, Concurrency, Lock-Free Data Structures, and Low-Level C++ Optimization
Executive Overview
For decades, modern C++ concurrent programming followed a simple, widely accepted rule: Lock-free algorithms should be used for high-contention, performance-critical paths, while locks should be reserved for low-contention or non-critical code.
In this landmark C++Now 2026 presentation, Fedor Pikus demonstrates that advancements in modern CPU microarchitecture (x86-64 Intel/AMD, ARM Grace/Graviton, Apple Silicon) have completely inverted this paradigm:
- At High Contention: Properly engineered spin locks outperform lock-free (
compare_exchangeloops) and wait-free (fetch_add) atomic algorithms. - At Low Contention: Taking a spin lock—even once every 100 iterations—severely degrades surrounding CPU out-of-order execution performance ("pipeline poisoning"), whereas atomics excel without stalling execution pipelines.
- The Optimal Modern Paradigm: High-performance concurrent data structures must combine both techniques—utilizing custom spin locks for high-contention index allocation/state transitions and atomic handoffs for low-contention payload access.
Progress Guarantees & Theoretical Definitions
Before diving into hardware microarchitecture, Pikus clarifies the classical computer science definitions of thread progress:
| Guarantee | CS Definition | Typical C++ Primitive | Hardware Reality |
|---|---|---|---|
| Wait-Free | Every thread completes its operation in a bounded number of algorithmic steps. | std::atomic::fetch_add |
Not constant time. Hardware cache-line invalidation forces sequential memory execution. |
| Lock-Free | At least one thread makes progress overall; losers retry in a loop. | std::atomic::compare_exchange_weak / strong |
High contention causes severe CAS-retry loops and cache coherence thrashing. |
| Lock-Based | One thread holds exclusive access; all other contending threads wait/block. | std::mutex, Custom Spin Locks |
OS mutexes incur context switch overhead, but well-tuned spin locks eliminate CAS retry overhead. |
Key Distinction: Computer science definitions measure algorithmic steps, not CPU clock cycles. A "wait-free" instruction executes a single instruction step, but at the hardware level, cache coherency mechanisms force memory accesses to serialize, causing hardware-level waiting.
Microarchitectural Deep Dive: Why Atomics Fail Under High Contention
1. Cache Coherency and Read-For-Ownership (RFO)
Modifying any atomic variable requires exclusive access to its underlying 64-byte cache line:
- To write to a cache line, a CPU core must issue a Read-For-Ownership (RFO) request across the interconnect.
- The requesting core must wait for all other cores holding that cache line in a Shared (S) state to invalidate their local L1/L2 caches and send back an Acknowledgment (ACK) signal.
- Under heavy multi-threaded contention, cores spend the majority of their clock cycles waiting for speed-of-light electrical signal propagation across the chip to complete RFO invalidation handshakes.
2. True Sharing vs. False Sharing
Experimentation proves that false sharing (multiple independent atomics residing on the same 64-byte cache line) and true sharing (all threads hammering the exact same atomic variable) suffer from the exact same latency penalty at high thread counts. The hardware bottleneck is the cache line granularity, not the specific integer being modified.
Engineering a High-Performance Spin Lock
To outperform atomics at high contention, a spin lock must be engineered specifically to respect hardware cache coherency protocols.
Critical Design Features:
- Pre-Read Probe (Test-and-Test-and-Set):
- Before attempting an expensive atomic operation (
atomic_exchange), the thread performs a relaxed, read-only load of the lock flag. - Reading allows the core to acquire the cache line in a Shared (S) state without revoking exclusive access from the thread currently holding the lock.
- Before attempting an expensive atomic operation (
- Pre-Read Retries:
- Performing ~8 relaxed reads on x86 before attempting an atomic swap ensures that in-flight RFO signals have time to settle, preventing premature cache-line stealing.
- Aggressive Back-off:
- Unlocking a spin lock requires writing
0to memory, which itself requires an RFO request. If waiting threads continuously hammer the lock with atomic writes, they steal the cache line from the lock holder, severely delaying the unlock operation. - Back-off logic (or yielding) keeps waiting threads from stealing the cache line during lock release.
- Unlocking a spin lock requires writing
The Low-Contention Asymmetry: "Pipeline Poisoning"
When benchmarking code that mixes parallel payload computation (e.g., local mathematical tasks) with synchronization (e.g., updating a shared counter):
- High Contention Domain: Spin locks deliver up to 2.5x higher overall application throughput compared to atomics.
- Low Contention Domain: When synchronization occurs rarely (e.g., 1 out of 100 iterations), using a spin lock causes program throughput to plummet compared to atomics.
High Contention (1:1 Parallel to Shared Work):
[Spin Lock] ========================> 2.5x Throughput vs Atomics
[Atomic CAS] ========> 1.0x
Low Contention (100:1 Parallel to Shared Work):
[Atomic CAS] ========================> 1.0x (Fast Execution)
[Spin Lock] =====> 0.25x (Severe Pipeline Poisoning)
Hardware Profiling & Root Cause Analysis (Intel VTune / Linux Perf)
By inspecting CPU hardware performance counters (RESOURCE_STALLS.STORE_BUFFER), Pikus identified the exact microarchitectural bottleneck:
- Store Buffer Stalls: Spin locks force massive store buffer stalls in x86 execution pipelines. On x86 architectures, memory writes exit the store buffer in strict program retirement order.
- Implicit vs. Explicit Dependencies:
- Atomics (
fetch_add, CAS): Fuse control and data into a single variable. The CPU out-of-order execution engine can inspect the instruction stream and recognize explicit data dependencies, allowing non-dependent payload instructions to flow around the atomic operation. - Locks: Separate control (the lock flag) from data (the guarded payload). Because the CPU cannot reason through implicit memory dependencies across bidirectional
acquire/releasememory barriers, it cannot predict safety across the critical section. As a result, the out-of-order execution pipeline flushes and stalls until the lock and unlock operations fully retire.
- Atomics (
Practical Application: The Hybrid MPMC Ring-Buffer Queue
To prove these findings, Fedor Pikus constructed a high-throughput Multi-Producer Multi-Consumer (MPMC) ring-buffer queue designed around hybrid synchronization:
+-----------------------------------------------------------------------+
| MPMC QUEUE DESIGN |
+-----------------------------------------------------------------------+
| High-Contention Domain --> Spin Lock (Guards Head / Tail Indices) |
| Separate Cache Lines --> Prevents Producer/Consumer Thrashing |
+-----------------------------------------------------------------------+
| Low-Contention Domain --> Atomic Slot Keys (std::atomic<Key>) |
| Exclusive Slot Access --> Zero Lock Overhead for Payload Handoff |
+-----------------------------------------------------------------------+
Performance Benchmark Results:
- Throughput: Dramatically outperforms traditional pure lock-free MPMC queues across Intel Granite Rapids, AMD Zen 5, Nvidia Grace, and Apple Silicon.
- Average Latency: Significantly lower mean and 95th/99th percentile latency compared to pure lock-free implementations.
- Tail Latency Exception (99.99%+): Pure lock-free queues only win at extreme tail latencies where thread preemption risks affect lock-based structures.
Duration & Power Considerations: When Spin Locks Fail
While spin locks excel at short critical sections, they carry severe operational trade-offs if critical section processing times grow long:
- Busy-Waiting Energy Waste: A thread waiting on a spin lock burns 100% CPU core utilization, drawing maximum power, generating heat, and causing thermal throttling.
- Thread Preemption Disaster: If the thread holding a spin lock is preempted by the OS scheduler (context-switched out), all contending threads will actively spin for their entire OS time slice doing zero productive work while waiting for the lock holder to be rescheduled.
- The Industrial Solution (Adaptive / Two-Phase Locks):
Production systems (e.g., database kernels, runtime engines) utilize adaptive locks:
- Phase 1: Spin for a short, bounded duration (~50–100 iterations using CPU pause hints like
_mm_pause()orYIELD). - Phase 2: If the lock remains unacquired, yield execution to the OS kernel via a
futexsleep system call.
- Phase 1: Spin for a short, bounded duration (~50–100 iterations using CPU pause hints like
Architectural Anomalies & Microarchitectural Surprises
- Cache-Line Separation of Lock and Payload: Placing the spin lock flag and the guarded data variable on different cache lines improves high-contention throughput. It prevents waiting threads (doing relaxed pre-reads on the lock flag) from invalidating the lock holder's cache line while it modifies the payload variable.
- AMD Zen 4 / Zen 5 Near-Memory Atomics:
AMD Zen 4 introduced hardware execution ALUs directly inside the L3 memory controller. If a core attempts a
fetch_addwithout owning the cache line, it offloads the operation directly to the L3 controller, bypassing L1/L2 cache-line invalidation cycles. - Apple Silicon CAS Back-off:
Apple M-series chips use a power-efficient, high-latency directory interconnect. Implementing explicit back-off inside a
compare_exchangeloop on Apple Silicon improves throughput by 10x, elevating CAS performance close to spin lock levels.
Summary Principles for Modern C++ Concurrency
- High Contention: Abandon pure lock-free CAS loops. Use properly engineered spin locks featuring relaxed pre-read probes, iteration limits, and back-off logic.
- Low Contention: Avoid locks completely. Use atomic primitives (
std::atomic) to prevent CPU store buffer flushes and out-of-order pipeline stalls. - Hybrid Architecture: Structure concurrent data structures to use spin locks for high-contention indexing (e.g., ring-buffer head/tail allocation) and atomic state flags for low-contention data transfer.
- Bounded Work: Keep spin lock critical sections strictly bounded to a few dozen nanoseconds; fall back to adaptive OS-backed locks (
futex) if processing times can exceed thread time-slices.
#include <atomic>
#include <chrono>
#include <new>
#include <thread>
#if defined(__x86_64__) || defined(_M_X64)
#include <emmintrin.h> // For _mm_pause()
#endif
// Align to prevent false sharing with adjacent cache lines
class alignas(std::hardware_destructive_interference_size) AdaptiveSpinLock {
public:
AdaptiveSpinLock() noexcept = default;
// Non-copyable, non-movable
AdaptiveSpinLock(const AdaptiveSpinLock&) = delete;
AdaptiveSpinLock& operator=(const AdaptiveSpinLock&) = delete;
void lock() noexcept {
// Phase 1: Fast path (Uncontended)
if (!state_.exchange(true, std::memory_order_acquire)) {
return;
}
// Phase 2: Active Spin Loop with Pre-Read (Test-and-Test-and-Set)
int spin_count = 0;
constexpr int MAX_SPINS = 64; // Max active CPU spinning iterations
while (true) {
// Pre-read probe: Read in a relaxed loop to stay in 'Shared' (S) cache state.
// Avoids sending RFO (Read-For-Ownership) signals while waiting.
while (state_.load(std::memory_order_relaxed)) {
pause_cpu(spin_count);
// Phase 3: Adaptive Fallback to OS-backed Sleeping
// If spinning takes too long, stop burning CPU/power and park the thread.
if (++spin_count > MAX_SPINS) {
// C++20/23 std::atomic::wait uses OS futex/synch primitives natively
state_.wait(true, std::memory_order_relaxed);
}
}
// Attempt to acquire lock via atomic exchange once pre-read detects key is free
if (!state_.exchange(true, std::memory_order_acquire)) {
return; // Lock acquired successfully
}
}
}
bool try_lock() noexcept {
// First check relaxed state to avoid cache invalidation on failure
if (state_.load(std::memory_order_relaxed)) {
return false;
}
return !state_.exchange(true, std::memory_order_acquire);
}
void unlock() noexcept {
// Unconditionally release lock
state_.store(false, std::memory_order_release);
// Notify any waiting thread that was parked in state_.wait()
state_.notify_one();
}
private:
// Flushes execution pipeline & saves power during short spinning
static void pause_cpu(int spin_count) noexcept {
if (spin_count < 16) {
#if defined(__x86_64__) || defined(_M_X64)
_mm_pause(); // Informs x86 pipeline of spin loop; reduces power & store buffer pressure
#elif defined(__aarch64__)
asm volatile("yield" ::: "memory"); // ARM yield hint
#endif
} else {
// Hint to OS scheduler to run other threads on the same core/time-slice
std::this_thread::yield();
}
}
// False = Unlocked, True = Locked
std::atomic<bool> state_{false};
};
