Pangram verdict · v3.3
We believe this text is mainly human-written, with some AI content.
AI likelihood · overall
HumanArticle text · 1,030 words · 5 segments analyzed
A spin-lock is a lock that never sleeps. Instead of yielding to the scheduler, the thread stays on the CPU and spins. No syscalls. No context switches. In this post, we’ll build a version, step by step, that is 5.7x faster while drawing 5.4x less energy.Benchmark §Threads increment a shared counter under the lock.1 1 Run on a box tuned for benchmarking. Built with clang. All optimizations enabled. template <typename Lockable> auto BM_SpinLock(benchmark::State& state) -> void { alignas(std::hardware_destructive_interference_size) static auto lockable = Lockable{}; alignas(std::hardware_destructive_interference_size) static auto counter = std::uint64_t{}; pinThread(state.thread_index()); for (auto _ : state) { lockable.lock(); ++counter; lockable.unlock(); } benchmark::DoNotOptimize(counter); } The lock and the counter get a cache line each. Threads are pinned.A naive spin-lock §An atomic bool and an exchange loop.2 2 exchange atomically writes true and returns the previous value. false means the lock was free and is now ours. true means someone else holds it, so we retry. class SpinLockV1 { std::atomic_bool locked_{false}; public: auto lock() noexcept -> void { while (locked_.exchange(true)); } auto unlock() noexcept -> void { locked_.store(false); } }; Uncontended it takes 3.14 ns. Two threads take 61.5 ns, twenty times as long. Four take 246 ns.$ ./benchmark --benchmark_filter='V1>' BM_SpinLock<SpinLockV1>/real_time/threads:1 3.14 ns BM_SpinLock<SpinLockV1>/real_time/threads:2 61.5 ns BM_SpinLock<SpinLockV1>/real_time/threads:4 246 ns A core must own the line exclusively to write it, so waiters take it from each other.
L1-d misses go from 1.27% at one thread to 61.73% at four, and one branch in eight is mispredicted.3 3 Whether the exchange succeeds is decided by the other cores, so the branch predictor has nothing to learn.
$ perf stat -d ./benchmark --benchmark_filter='V1>.*threads:1' 1,638,619,370 instructions # 0.51 insn per cycle 244,253 branch-misses # 0.11% of all branches 75,519 L1-dcache-load-misses # 1.27% of all L1-dcache accesses $ perf stat -d ./benchmark --benchmark_filter='V1>.*threads:4' 1,231,495,723 instructions # 0.02 insn per cycle 33,824,516 branch-misses # 12.52% of all branches 208,756,315 L1-dcache-load-misses # 61.73% of all L1-dcache accesses Spinning costs energy.4 4 High-frequency trading shops care about it. Exchange colocation services charge for power, and NYSE caps at 32 kW. At four threads it draws 64.92 J.5 5 Reading the RAPL counters requires system-wide mode (-a) and root, so the figure covers the whole package, idle cores included. $ perf stat -a -e power/energy-pkg/ ./benchmark --benchmark_filter='V1>.*threads:4' 64.92 Joules power/energy-pkg/ Memory ordering §The default is seq_cst, stronger than a lock needs. It only has to acquire on the way in and release on the way out.class SpinLockV2 { std::atomic_bool locked_{false}; public: auto lock() noexcept -> void { while (locked_.exchange(true, std::memory_order_acquire)); } auto unlock() noexcept -> void { locked_.store(false, std::memory_order_release); } }; On x86 lock is unchanged.SpinLockV2::lock(): mov al, 1 xchg byte ptr [rdi], al // Locked exchange, both orderings test al, 1 jne .LBB0_1 ret The difference is in unlock. The default ordering adds a second locked read-modify-write, on top of the one in lock.SpinLockV1::unlock(): xor eax, eax xchg byte ptr [rdi], al // Locked read-modify-write ret With memory_order_release, unlock is a plain store.SpinLockV2::unlock(): mov byte ptr [rdi], 0 // Plain store ret One atomic instead of two. 3.14 ns to 1.57 ns uncontended, 246 ns to 131 ns at four threads.$ ./benchmark --benchmark_filter='V2>' BM_SpinLock<SpinLockV2>/real_time/threads:1 1.57 ns BM_SpinLock<SpinLockV2>/real_time/threads:2 32.5 ns BM_SpinLock<SpinLockV2>/real_time/threads:4 131 ns Miss rates fall too. L1-d 61.73% to 21.16%, branches 12.52% to 7.43%. Energy drops to 34.45 J.$ perf stat -d ./benchmark --benchmark_filter='V2>.*threads:4' 773,887,322 instructions # 0.03 insn per cycle 12,348,239 branch-misses # 7.43% of all branches 99,804,390 L1-dcache-load-misses # 21.16% of all L1-dcache accesses The exchange writes the line even when it fails.
Waiters must stop writing.Test and test-and-set §Exchange once, then wait on a read-only load. The _mm_pause instruction marks the loop as a spin-wait, so the core idles.6 6 The load can be relaxed. What orders the critical section is the exchange that succeeds, not the reads that fail.
class SpinLockV3 { std::atomic_bool locked_{false}; public: auto lock() noexcept -> void { while (locked_.exchange(true, std::memory_order_acquire)) { while (locked_.load(std::memory_order_relaxed)) { // Read-only spin _mm_pause(); // Backoff } } } auto unlock() noexcept -> void { locked_.store(false, std::memory_order_release); } }; Two threads drop by a third, 32.5 ns to 21.3 ns. Four threads gain 8%, 131 ns to 120 ns.$ ./benchmark --benchmark_filter='V3>' BM_SpinLock<SpinLockV3>/real_time/threads:1 1.58 ns BM_SpinLock<SpinLockV3>/real_time/threads:2 21.3 ns BM_SpinLock<SpinLockV3>/real_time/threads:4 120 ns L1-d misses fall from 21.16% to 17.31%, branches from 7.43% to 3.72%. A read-only spin is predictable.$ perf stat -d ./benchmark --benchmark_filter='V3>.*threads:4' 1,290,214,448 instructions # 0.05 insn per cycle 12,089,906 branch-misses # 3.72% of all branches 83,836,255 L1-dcache-load-misses # 17.31% of all L1-dcache accesses Energy falls 10%, from 34.45 J to 30.97 J.$ perf stat -a -e power/energy-pkg/ ./benchmark --benchmark_filter='V3>.*threads:4' 30.97 Joules power/energy-pkg/ Every waiter pauses for the same length of time, so they all wake together.Exponential backoff §Intel documents the fix. Wait longer each round, doubling up to a cap.7 7 Example 2-10, Contended Locks with Increasing Back-off, in the Intel Optimization Reference Manual (PDF, 248966-050US). class SpinLockV4 { std::atomic_bool locked_{false}; public: auto lock() noexcept -> void { auto backoff = 1; while (locked_.exchange(true, std::memory_order_acquire)) { do { for (auto i = 0; i < backoff; ++i) _mm_pause(); // Backoff backoff = backoff < 64 ? backoff << 1 : 64; // Exp. growth } while (locked_.load(std::memory_order_relaxed)); // Read-only spin } } auto unlock() noexcept -> void { locked_.store(false, std::memory_order_release); } }; Waiters back off by different amounts and stop waking together. Four threads drop from 120 ns to 43.0 ns.$ ./benchmark --benchmark_filter='V4>' BM_SpinLock<SpinLockV4>/real_time/threads:1 1.58 ns BM_SpinLock<SpinLockV4>/real_time/threads:2 18.3 ns BM_SpinLock<SpinLockV4>/real_time/threads:4 43.0 ns L1-d misses fall from 17.31% to 12.88%.$ perf stat -d ./benchmark --benchmark_filter='V4>.*threads:4' 600,071,010 instructions # 0.07 insn per cycle 8,296,063 branch-misses # 6.17% of all branches 33,717,087 L1-dcache-load-misses # 12.88% of all L1-dcache accesses Energy falls to 11.92 J, 5.4x less than the naive version.$ perf stat -a -e power/energy-pkg/ ./benchmark --benchmark_filter='V4>.*threads:4' 11.92 Joules power/energy-pkg/ Summary §Reproduce it with the benchmark.Version1 thread2 threads4 threadsNotesV13.14 ns61.5 ns246 ns / 64.92 JNaiveV21.57 ns32.5 ns131 ns / 34.45 JMemory orderingV31.58 ns21.3 ns120 ns / 30.97 JTest and test-and-setV41.58 ns18.3 ns43.0 ns / 11.92 JExponential backoffIn most code, std::mutex is still the right default. Consider a spin-lock when the threads are pinned to dedicated cores, and only after measuring.8 8 With one writer and many readers, consider a seqlock instead.