キャッシュラインと偽共有 — 隣の席のせいで遅くなる

一言でいうと

キャッシュは64バイトのライン単位で動き、コアたちはそのライン単位で所有権をやり取りするので、別々の変数でも同じラインにあれば、性能が互いを削り合います。

なぜ必要なのか

マルチコアのシステムでは、同じメモリを複数のコアが、それぞれのキャッシュに載せておけます。あるコアが値を変えたのに、他のコアが古い値を見続けるなら、プログラムは崩壊します。そのため、ハードウェアはキャッシュコヒーレンシプロトコル(MESI系)を動かします。あるコアがラインを修正するには、他のコアのコピーを無効化して、排他的な所有権を得る必要があります。

ここで重要な事実は、この所有権の争いの単位が変数ではなくキャッシュラインだという点です。

どう動くのか

スレッドAがカウンターaを、スレッドBがカウンターbを、それぞれ懸命にインクリメントするとします。2つはまったく別の変数で、ロックも不要です。ところが、aとbが構造体の中に並んで宣言され、同じ64バイトのラインに入ってしまったら、Aが書くたびにBのキャッシュでそのラインが無効化され、Bが書くたびにAのものが無効化されます。論理的には共有がないのに、ハードウェアのレベルでは、奪い合いが続く状態です。これをフォルスシェアリング(false sharing)といいます。

症状が特徴的です。スレッドを増やしたのにスループットが増えない、あるいはむしろ減ります。ロックの競合をいくら探しても見つかりません。ロックがないからです。

対処は単純です。コアごとに書き込むデータを、別々のキャッシュラインに置きます。構造体にパディングを入れたり、配列の要素をラインサイズの倍数にアラインしたりします。

似た種類の落とし穴がもう1つあります。スプリットロック(split lock)です。アトミック演算のオペランドが2つのキャッシュラインにまたがっていると、CPUは高速なコヒーレンシの経路を使えず、外部バスのロックをかける必要があります。800サイクルを超え、その間、無関係な他のコアまで止まります。Linuxカーネルは、これを検出する機能を提供していて、ブートパラメーターsplit_lock_detectのデフォルト値はwarnです。カーネルログに関連する警告が出ているなら、実際の性能問題である可能性が高いです。

現場での姿

高性能なキュー、カウンターの配列、スレッドごとの統計収集器が、典型的な被害者です。特に、「スレッドごとに自分のスロットにだけ書くから、ロックは不要だ」と設計した配列が危険です。スロットのサイズが8バイトなら、8個のスロットが1つのラインに入り、8つのスレッドが1つのラインを巡って争います。

逆に、この原理を利用することもできます。一緒に読まれるフィールドを1つのラインにまとめておけば、1回のミスですべてを取得できます。読み取り専用で一緒に使われる値は、くっつけて、異なるコアが書く値は、離して置きます。規則は、この1行に要約されます。

次のラボですること

ライン単位で動くというこの性質を、時間で測ってみます。配列を複数のストライドでなぞって、ラインを1つどれだけ使って捨てるかによって、読み取りのコストがどう分かれるかを見て、同じ行列を行優先と列優先で走査して、アクセス順序だけで何倍の差が開くかを確認します。最後に、走査を断片に切り分けて、その損を取り戻します。