並行プリミティブ 基礎

文は命令ではない。共有カウンタ上の x++ は 3 命令だ：スレッド A が x を読み、1 を足し、書き戻す。この不可分性をハードウェアは保証せず、スケジューラはスレッド B の 3 命令をどこにでも落とせる。

どちらも x = 0 から 1 ずつ足すつもりなので、答えは 2 だ。スレッド B のブロックをスレッド A のタイムライン上でドラッグし、一番下の行 —— 各ステップ後の x —— を見てほしい：

2 になるのは両端だけだと分かる。その間では B はA が書き戻す前に x を読み、両方のレジスタが 0 を持ち、両方が 1 を書き、インクリメントが 1 回消える。例外は飛ばない。全行が書かれたとおりに走り、カウンタだけが間違っている。

ブロックのドラッグで届くのは、スケジューラが選べる順序のうち 4 つだけだ。 3 命令ずつ 2 列のマージは 20 通りあり、スライダはその全部を歩く。下の帯ではいま手にしているものを矢印が指し、その隣に2 で終わるものと更新を失うものが並ぶ：

2 つ。正しい答えを出すのは 20 通り中 2 通りだけで、どちらも片方が走り切ってからもう片方が始まる場合だ。レースがテストを生き延びるのはこれが理由で、更新の消失に特殊なハードウェアも負荷も要らない —— それが既定の結果だ。

同じ形は「確認してから動く」あらゆるコードに潜む。ここではスレッド A がマップにキーの有無を尋ね、 4 命令後にそれを取り出す ——スレッド B の remove を A の命令列の中で滑らせてほしい：

9 つの落下点のうち 4 つが確認と取得の間に入り、そこでは直前に存在を証明したキーに対して取得が null を返す。これがアトミック性バグの変装だ：個々にはアトミックな 2 呼び出しが、アトミックでない列に合成されている。ConcurrentHashMap は助けにならず、1 回の呼び出しであるcomputeIfAbsent は助けになる。

ハードウェアにも同じものがある。lock 前置の命令が不可分なのは、オペランドが1 本の 64 バイトキャッシュラインに収まっている間だけだ ——8 バイトのアトミックを60 バイト目の境界越しにドラッグしてほしい：

分割されたオペランドは 2 本のラインにまたがり、コアは 1 回のラインロックで覆えずバスロックに退避する：約 1,000 サイクル、3 GHz で 330 ns、整列時の 20 ns に対してだ。しかもバスロックはソケット上の全コアを止める。 Linux の split_lock_detect は、これを遅い謎ではなくシグナルに変える。

その 3 GHz が、このページのナノ秒すべての機械だ：1 ソケット、コアは 1 ダイ。どの定数もその clock のサイクル数から導いた桁の値で —— L1 ヒット 1 ns、無競合アトミック 20 ns、ライン転送 100 ns、park と wake で 2 µs —— 特定型番のベンチマークではない。

直し方は 2 つあり、しかも同じものではない。ミューテックスはセクション全体を排他にする。fetch_addはそれをハードウェアが割らない 1 命令に潰す。両者を切り替えて、スレッド B のブロックをもう一度ドラッグしてほしい：

どちらでもオフセットは効かなくなる —— それが両者の意味だ。違いは射程で、fetch_add は 1 マシンワード、ミューテックスは何でも扱う。代金は次節で払う。素の版が壊す不変条件はこれだ：read-modify-write のロードとストアの間、他のどのスレッドも x を読み書きしない。

glibc のミューテックスは 3 状態の 32 ビットワード 1 つだ：0 は空き、 1 は保持、2 は保持かつ待機者あり。ロックは 0 から 1 への compare-and-swap だけ ——システムコールなし、カーネルなし。カーネルが現れるのは実際に待つときだけだ。

競合した獲得を一歩ずつ進めて、一番下の行のfutex ワードと、カーネルに入る 2 ステップを見てほしい：

カーネルなのはごく一部だと分かる。スレッド A はシステムコール 1 回もなしに取って放し、払うのは負けたスレッド B の futex_wait だけだ。ステップ 4 にも注目：B は先にワードを 1 から 2 へ動かす必要がある。さもないと A のアンロックは待機者を知る術がなく、futex_wake を省いてしまう。

この非対称性が性能の話のすべてだ。競合しないロックとアンロックはアトミック 2 回、約 40 ns。眠るほうはシステムコールとコンテキストスイッチと起床で約 2 µs かかる。競合する割合を上げてほしい：

平均が床を離れる速さを見てほしい。競合 10% の時点で平均はすでに 240 ns —— 競合しない場合の 6 倍だ —— 10 回に 9 回はまだカーネルに入っていないのに。ロックが遅いのではなく、待つのが遅い。

だから実装は眠る前にスピンする。スピン予算を決めて、次に保持側が実際にロックを持つ時間を動かしてほしい：

予算より短ければ待機側は眠らず、待ち時間は保持時間そのものだ。予算を超えると予算をまるごと焼いた上で眠り、そのうえ保持側を待ち切ることになる —— 必要な futex_wake はロックが実際に空くまで送れないので、獲得できるのは解放のあと 1.5 µs であって、解放の瞬間ではない。glibc のPTHREAD_MUTEX_ADAPTIVE_NP がスピンに上限を置くのはこのためで、ユーザ空間のスピンロックが間違いなのも同じ理由だ：保持側はセクションの途中で追い出され得る。

セマフォは同じワードで、フラグの代わりにカウントを持つ。パーミットが 8 ワーカーのうち何本が同時に中に入れるかを決める：

パーミット 1 ならミューテックスだが、噛む違いが 1 つある：セマフォには所有者がいないので、一度も wait していないスレッドからの sem_post も合法だ。だから有界キューには正しく、相互排他には間違っている —— そこでは所有者チェックこそが二重アンロックを捕まえるからだ。

条件変数は足りない部品を足す —— 状態が変わったと誰かが言うまで眠る —— 罠は、起こされたことが述語について何も語らない点だ。ガードを if と while で切り替えて、シーケンスを進めてほしい：

if では、待機側は他人宛の起床で cond_wait を抜け、述語がまだ偽でもそのまま動く。POSIX はこれを明示的に許す：スプリアスウェイクアップは合法で、pthread_cond_signal が複数を起こすこともある。あのwhile は防御ではなく契約だ。

ロック 2 つとスレッド 2 つは、相互排他が自分に牙を剥く場所だ。スレッド B がロックを取る順序を選び、4 回の獲得を進めてほしい：

同じ順序なら閉路はできない：ロック 1 を取ったほうが走り切って両方放す。 B を逆にすると 4 ステップ目で輪が閉じ、互いに相手の欲しいものを持ったままどちらも譲らない。検出もタイムアウトもなく、プロセスはただ止まる。グローバルなロック順序が防ぎ、機械的に検査もできる：アドレス順か、静的な rank だ。

最後のロックは、みんなが反射で手を伸ばすものだ。rwlock はセクションを買い戻し、代金にキャッシュライン転送 1 回を取る：カウンタは競合していて、1 回の読みがそれに 3 回触る。ミューテックスが自分のワードに触るのは 2 回だ：

セクションの価値に注目してほしい。500 ns のセクションでは rwlock が 3.1 M/s、ミューテックスが 1.4 M/s で、書き込み比率 80% まで勝つ。100 ns に落とすとどの比率でも勝てない：読み経路が余計に渡るライン 1 往復が 100 ns で、守っていたセクション全体と同じだからだ。

compare_exchange は汎用の read-modify-write だ：メモリがまだ自分の読んだ値を持つときだけ新しい値を公開する。そうでなければ失ったのはデータではなくレースで、もう一周する。

別のコアが先に着く回数を上げて、各試行が読んだ値と、交換が実行された時点でメモリにあった値を見比べてほしい：

失敗してもループが誤っているわけではない —— 失敗こそが仕組みだ。ただしロードと交換の間で計算したものは毎回捨てられるので、CAS ループは短く、副作用がなくてはならない。確保したり、ログを吐いたり、別のロックを取るループは、その仕事を試行ごとに 1 回ずつやる。

fetch_add は同じものに見えて違う：再試行が自分のループではなくコアの内側で起こる。1 つのカウンタにコアを積み上げてほしい：

スループットは同じではない。理由はどちらの行も 1 つだ。キャッシュラインが直列資源で、一度に 1 コアにしか居られず、動かすのに 100 ns かかる。fetch_add は 1 インクリメントにつき 1 往復だけ使うので、コア数によらず毎秒 1000 万を保つ。ループは 1 試行につき 1 往復を使う。8 コアでは8 回の試行のうち 7 回が捨てられ、その 7 回も 1 往復ずつ払っているので、同じラインが出せる成功は毎秒 130 万、8 分の 1 だ。ループが中に入っている命令を選ぶべきだ。

そのラインは 64 バイト幅で、2 つのカウンタが別の変数であることなど気にしない。コア 1 のカウンタをコア 0 のラインの中へドラッグしてほしい：

両方の書き込みが 1 本のラインに落ちるので、インクリメントのたびにラインがコア間で往復し、20 ns のアトミックが 100 ns になる ——触れ合いもしない 2 変数で 5 倍だ。これがフォルスシェアリングで、ソース上は見えない。alignas(64) と Java の @Contended は 1 ラインぶんに詰めるためにある。

ロックフリーのコードには、どれだけアトミックにしても防げない失敗が 1 つある。別スレッドの pop, pop, push を、読み取りと CAS の間の窓に滑り込ませてほしい：

CAS が成功するのを見てほしい。比較したポインタは読んだものとビット単位で同じで、ハードウェアには文句のつけようがない —— しかしそれが指すノードは途中で解放され、押し戻されている。head はアロケータが配り終えたメモリを指す。これが ABA だ。対策はタグ付きポインタ —— 空きビットのバージョンカウンタ —— か、 hazard pointer やエポックのような回収方式だ。

それらを踏まえると価格表は短い。1 つのアトミック命令が買うのはラインの 1 往復で、下で変わるのは何コアがそのラインを欲しがるかだけだ：

1 コアではアトミックが 20 ns、素のロードが 1 ns —— 20 倍だが、まだ安い。8 コアではCAS ループが 800 ns。バーは払った 8 往復に切られていて、成立するのは最後の 1 往復だけだ。アトミックは命令あたり安く、競合するラインあたり高い。最適化はラインを散らすことだ。

ストアはメモリへは行かない。コアごとのストアバッファに入って即座にリタイアする —— だからキャッシュミスの数十ナノ秒ではなく 0.3 ns で済む。別のコアがその書き込みを見るのはバッファが吐き出された時点で、発行した時点ではない。

生産者は data = 42、次にflag = 1 を書く。2 つのストアがそれぞれバッファを出る時刻を動かして、一番下の行を読んでほしい：

フラグをデータより先に出すと、別コアは古いデータの上に立ったフラグを見る：フラグを信じた消費者は 0 を読み、それを 42 と呼ぶ。コンパイラのバグでもハードウェアのバグでもない —— 2 つのストアは無関係なアドレス宛で、そのコードの単一スレッド上の意味には両者を順序づけるものがないからだ。

まさにそれを縛るのが memory_order だ：release ストアはその前の書き込みより前に並べ替えられない。順序を選んでから、消費者が読む時刻をスクラブしてほしい：

relaxed には窓がある ——サイクル 2 ではフラグが見えてデータが見えない。acquire/release にその窓はない。ストアが速くなったのではなく、コンパイラもコアももう順序を入れ替えられないからだ。バグとは窓のことで、順序はそれを閉じる。

順序は対で効く。release だけでは何も保証されず、読み手が反対側を受け取らなければならない。両端が揃うまでは消費者の読みはどれも古い —— スライダで半分ずつ組んでほしい：

両方が揃うまで何も起こらないと分かる。relaxed なロードに読まれた release ストアは依然としてデータレースで、その前の 3 つの書き込みは古いままだ。acquire ロードがその release の書いた値を読んだ瞬間、生産者がそれ以前に行った書き込みが、消費者がそれ以後に行うすべてから見える。それが happens-before で、しかも推移的だ。

acquire/release を生き延びる並べ替えが、これまで作られたどの機械にも 1 つある。両コアがストアしてから相手の変数をロードする —— フェンスを外した状態で4 つの結果を進め、次に入れてほしい：

両コアが 0 を読み得る。2 つのプログラムのどんなインタリーブも出せない結果だ。相手のロードが出ていく時点で、どちらのストアも自分のストアバッファに座ったままだからだ。フルフェンス —— mfence、または seq_cst がコンパイルされる lock 前置のストア —— だけが先に吐き出す。 x86 で seq_cst だけが金を取る理由がこれだ。

そしてそこが、機械を替えると通用しなくなる部分だ。アーキテクチャを切り替えて、3 つの順序を歩いてほしい：

x86 は 4 つのうち 3 つをタダで禁じるので relaxed のコードは偶然ほぼ正しく、金を払うのは seq_cstだけだ —— 20 ns の xchg 対 0.3 ns のストア。ARMv8 は 4 つとも許すので acquire/release が ldar と stlr ぶん掛かり、seq_cst はその上に何も足さない。罠は最初の列だ： x86 でしか走らせていないコードは、順序を一度も試されていない。

2 ns ではアトミック 1 回に勝るものはない。rwlock が出るのは252 ns になってからで、多くの人の予想より遅い。8 人のリーダが、カウンタの余分な 1 往復を取り返す必要があるからだ。そしてミューテックスのバーは決して最短にならない。スピンはロックが空いた瞬間に取れて、眠りは取れないからだ。持っているのは内側のバーだ。3.2 µs では、スピンロックが1 コアまるごとを 3.2 µs、しかも 7 コアぶん空回りさせる。適応ミューテックスは 1 µs の予算を焼いて眠る。レイテンシは感じるもので、内側のバーは払うものだ。

int want = 0;
if (!cas(&m, &want, 1))  // 0 -> 1
    lock_slow(&m);  // futex_wait
/* ... critical section ... */
if (xchg(&m, 0) == 2)  // waiters?
    futex_wake(&m, 1);

その 1 ワードは機械全体の上限でもある。1 操作のうち5% をロック内で過ごす負荷について、コア数を上げてほしい：

曲線が戻ることに注目してほしい。31 コアを超えると、増えたコアは貢献より長くラインを運ぶ： 64 コアは 7.8 倍、31 コアは 9.0 倍だ。Amdahl は寝かせるだけで、一貫性の項が悪化させる。

• if で守った cond_wait。 ループが契約だ。
• スレッド間に relaxed。 順序を与えない。
• 1 struct に熱いカウンタ 2 本。同じライン、5 倍の税。
• ユーザ空間のスピンロック。保持側は途中で追い出される。
• 読みやすい順にロックを取る。先に全体順序を決めよ。