Spin-Lockの最適化

スピンロックは決してスリープしないロックです。スケジューラに制御を譲る代わりに、スレッドはCPUに留まり、スピンします。システムコールもコンテキストスイッチもありません。この記事では、5.7倍高速で5.4倍少ないエネルギーを消費するバージョンを段階的に構築していきます。 ベンチマーク §スレッドはロック下で共有カウンタをインクリメントします。 1 1 ベンチマーク用にチューニングされたボックスで実行。clangでビルド。すべての最適化を有効化。 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); } ロックとカウンタはそれぞれキャッシュラインを占有します。スレッドはピン留めされています。 ナイーブなスピンロック §アトミックブール値と交換ループ。 2 2 exchangeはアトミックにtrueを書き込み、以前の値を返します。falseはロックがフリーで、今は我々のものになったことを意味します。trueは誰かが既に保持していることを意味するため、リトライします。 class SpinLockV1 { std::atomic_bool locked_{false}; public: auto lock() noexcept -> void { while (locked_.exchange(true)); } auto unlock() noexcept -> void { locked_.store(false); } }; 競合がない場合、3.14 nsかかります。2つのスレッドでは61.5 nsかかり、20倍長くなります。4つのスレッドでは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 コアは書き込みのためにラインを排他的に所有する必要があるため、待機スレッドは互いにラインを奪い合います。L1-dミスは、1スレッドで1.27%から4スレッドで61.73%に増加し、8回の分岐のうち1回が誤予測されます。 3 3 exchangeが成功するかどうかは他のコアによって決定されるため、分岐予測器は学習するものがありません。 $ 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 スピンはエネルギーを消費します。 4 4 高頻度取引を行う企業はこれに注意を払います。Exchangeのコロケーションサービスは電力料金を請求し、NYSEは32 kWを上限としています。4スレッドでは64.92 Jを消費します。 5 5 RAPLカウンタを読むにはシステム全体モード(-a)とroot権限が必要なため、この数値はアイドルコアを含むパッケージ全体をカバーします。 $ perf stat -a -e power/energy-pkg/ ./benchmark --benchmark_filter='V1>.*threads:4' 64.92 Joules power/energy-pkg/ メモリ順序 §デフォルトはseq_cstであり、ロックが必要とするよりも強いです。ロックは、入る際に取得し、出る際に解放するだけで十分です。 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); } }; x86ではロックは変更されません。 SpinLockV2::lock(): mov al, 1 xchg byte ptr [rdi], al // Locked exchange, both orderings test al, 1 jne .LBB0_1 ret 違いはアンロックにあります。デフォルトの順序付けは、ロック内のものに加えて、2番目のロックされた読み取り・変更・書き込み操作を追加します。 SpinLockV1::unlock(): xor eax, eax xchg byte ptr [rdi], al // Locked read-modify-write ret memory_order_releaseを使用すると、アンロックは単純なストアになります。 SpinLockV2::unlock(): mov byte ptr [rdi], 0 // Plain store ret 2つのアトミック操作ではなく1つです。競合がない場合は3.14 nsから1.57 nsに、4スレッドでは246 nsから131 nsに短縮されます。 $ ./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 ミス率も低下します。L1-dは61.73%から21.16%に、分岐は12.52%から7.43%に低下します。エネルギー消費は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 交換操作は失敗した場合でもラインを書き込みます。待機スレッドは書き込みを停止する必要があります。 テストとテスト・アンド・セット §一度交換し、その後読み取り専用ロードで待機します。_mm_pause命令はループをスピン待機としてマークするため、コアはアイドル状態になります。 6 6 ロードはリラックスして構いません。クリティカルセクションを順序付けるのは、成功する交換操作であり、失敗する読み取り操作ではありません。 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); } }; 2つのスレッドでは32.5 nsから21.3 nsに約3分の1減少します。4つのスレッドでは8%向上し、131 nsから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ミスは21.16%から17.31%に、分岐は7.43%から3.72%に低下します。読み取り専用スピンは予測可能です。 $ 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 エネルギー消費は10%減少し、34.45 Jから30.97 Jになります。 $ perf stat -a -e power/energy-pkg/ ./benchmark --benchmark_filter='V3>.*threads:4' 30.97 Joules power/energy-pkg/ 指数バックオフ §Intelが修正方法を文書化しています。ラウンドごとに待機時間を長くし、キャップまで倍増させます。 7 7 Intel Optimization Reference Manual (PDF, 248966-050US) の例2-10「Contended Locks with Increasing Back-off」を参照。 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); } }; 待機スレッドは異なる量のバックオフを行い、同時にウェイクアップするのをやめます。4つのスレッドでは、120 nsから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ミスは17.31%から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 エネルギー消費は11.92 Jに低下し、ナイーブなバージョンと比較して5.4倍少なくなります。 $ perf stat -a -e power/energy-pkg/ ./benchmark --benchmark_filter='V4>.*threads:4' 11.92 Joules power/energy-pkg/ 概要 §ベンチマークで再現できます。 Version | 1 thread | 2 threads | 4 threads | Notes V1 | 3.14 ns | 61.5 ns | 246 ns / 64.92 J | Naive V2 | 1.57 ns | 32.5 ns | 131 ns / 34.45 J | Memory ordering V3 | 1.58 ns | 21.3 ns | 120 ns / 30.97 J | Test and test-and-set V4 | 1.58 ns | 18.3 ns | 43.0 ns / 11.92 J | Exponential backoff ほとんどのコードでは、std::mutexが依然として適切なデフォルトです。スレッドが専用コアにピン留めされており、測定後であればスピンロックを検討してください。 8 8 書き込みが1つで読み取りが多い場合は、代わりにseqlockを検討してください。