隠れたパフォーマンスキラー「False Sharing」

CPU の製造プロセスの発展に伴い、現在のハイエンド CPU はすでに数十コア・百数十スレッドを備えており、CPU には 1 次・2 次・3 次キャッシュが設計されています。CPU のコアはこれらのキャッシュを持つことでデータ処理を高速化し、メモリへのアクセス頻度を減らすことができ、CPU の計算性能をさらに高められるのです。

CPU のキャッシュ構造とアクセスレイテンシ

CPU のキャッシュ構造、およびメモリ・ハードディスクとの階層関係は下図のとおりです。

よく知られているように、CPU が一度メモリにアクセスするコストは非常に大きく、ディスク上のデータを一度取得しようとすればさらに長い待ち時間が必要になります。現在では mmap のような技術によってこの状況は緩和されていますが、全体として CPU の計算性能はコンピュータ構造全体における天井であり、他のハードウェアはデータ転送速度の面で比べると足を引っ張っている格好です。CPU が各階層のストレージにアクセスするレイテンシを見てみましょう。

ストレージ	記憶媒体	媒体コスト(米ドル)	ランダムアクセスレイテンシ
L1 Cache	SRAM	7	1ns
L2 Cache	SRAM	7	4ns
Memory	DRAM	0.015	100ns
Disk	SSD (NAND)	0.0004	150us
Disk	HDD	0.00004	10ms

見てのとおり、外部ストレージデバイスは容量が大きくコストが低いほど多くのデータを格納できますが、アクセス速度も遅くなります。アクセス速度が速いデバイスほど製造コストは高くなります。CPU が L1 Cache にアクセスする速度はメモリへのアクセスより 100 倍も速く、これこそが CPU の中に L1〜L3 Cache が存在する理由です——Cache を CPU とメモリの間のキャッシュ層として、メモリへのアクセス頻度を減らしているのです。

キャッシュライン（Cache Line）

CPU がメモリから Cache へデータを読み込むとき、1 バイトずつ読み込むのではなく、ブロック単位でまとめて読み込みます。このブロック単位のデータは Cache Line（キャッシュライン）と呼ばれます。つまり Cache Line とは、CPU がメモリから Cache へデータを読み込む単位 なのです。

Cache Line のサイズについては、Linux システムでは次のコマンドで確認できます。

# cpu0 の L1 キャッシュラインサイズを確認する。単位はバイト
$ cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size

主流の CPU の Cache Line は一般的に 64 バイトですが、Apple が開発した M1 チップの Cache Line はすでに 128 バイトになっています。

False Sharing とは何か

メモリ上のデータは Cache Line 単位で CPU Cache にコピーされることが分かりました。次は、Cache の False Sharing とは何か、そしてこの問題をどう回避するかを紹介します。

デュアルコアの CPU があり、2 つのコアがそれぞれ異なるスレッドを並列に実行していて、同時にメモリから 2 つの異なるデータ、すなわち型が long の変数 A と B（各 8 バイト）を読み取るとします。CPU1 は A を取得して変更したく、CPU2 は B を取得して変更したいのですが、この 2 つのデータのアドレスは 物理メモリ（DRAM）上で連続しています。Cache Line のサイズが 64 バイトで、変数 A が Cache Line の先頭位置にある場合、B は A のアドレスのすぐ後ろに続くため、2 つのデータは 同一の Cache Line 内 に位置することになります。そして Cache Line は CPU がメモリから Cache へデータを読み込む単位なので、この 2 つのデータは 2 つの CPU コアそれぞれの Cache に同時に読み込まれます。

ここで一つの問題を考えてみましょう。この 2 つの異なるコアのスレッドがそれぞれ A と B のデータを変更した場合、たとえば CPU1 のスレッドは変数 A だけを変更し、CPU2 のスレッドは変数 B だけを変更したら、何が起こるでしょうか？

このとき、両コアそれぞれの Cache Line 内のデータは不一致になり、最終的な計算結果に影響する可能性が高くなります。両者の Cache Line のデータ一貫性を保証するために、マルチコアキャッシュコヒーレンシの MESI プロトコルが登場しました。

MESI に従うため、あるコアがデータを変更したら、他のコアに通知せざるを得ません。「あなたが持っている Cache Line はすでに期限切れです。メモリからもう一度取得し直してください」と。これがパフォーマンスの損失につながります。

複数の CPU コアが、同一の Cache Line 内にある互いに無関係な変数を並行して変更するとき、False Sharing（偽共有）の問題が発生します。それぞれが操作しているのは明らかに異なるデータなのに、同じキャッシュラインを共有しているために互いに足を引っ張り合うのです。あるコアが Cache Line 内のデータを更新すると、他のコアは行全体のデータを再ロードしなければならず、この過程にはかなりの時間がかかります。

False Sharing を回避するには

最も一般的な手段は Cache Line パディング（Padding）です。原理は、変数の間に無用なデータを詰め込み、ホットな変数を異なるキャッシュラインに隔離することで、異なる CPU コアがアクセスするデータが同一の Cache Line 上に載らないようにし、False Sharing を回避するというものです。

このほかにも、プログラミングレベルのテクニックがいくつかあります。たとえば、頻繁に変更が必要なデータを意図的に異なる Cache Line に配置する、あるいはスレッドローカルストレージ（Thread Local Storage、TLS）を使って異なるスレッド間のデータ競合を回避する、などです。ハードウェアレベルでは、Intel が Cache Allocation Technology（CAT）を提供しており、プログラマが Cache の割り当て方式を明示的に制御できます。さらに Cache Partitioning という技術もあり、Cache を複数の領域に分割して各領域を異なるスレッドに割り当てて使用させることで、同様に異なるスレッド間のデータ競合と False Sharing の問題を回避できます。

False Sharing のほかにも、Cache に関連する注意すべきパフォーマンス問題がいくつかあります。たとえば Cache Miss です。CPU が Cache に存在しないデータにアクセスする必要があるとき Cache Miss が発生し、このとき CPU はメモリからデータを読み取る必要があり、この過程には長い時間がかかります。Cache Miss を減らすには、プリフェッチ（Prefetching）や適切なキャッシュ置換アルゴリズム（Cache Replacement Algorithm）などの手段を活用できます。

小まとめ

Cache はコンピュータアーキテクチャにおいて性能を高める鍵となる一環ですが、読み書きの単位としての Cache Line は、False Sharing のような隠れた罠ももたらしました。複数のコアが同一キャッシュライン内の異なる変数を並行して変更すると、MESI プロトコルの一貫性維持のオーバーヘッドによって性能は目に見えて低下します。回避の考え方は実に直接的です。パディングやデータレイアウトによって、ホットな変数それぞれにキャッシュラインを 1 本ずつ独占させればよいのです。高並行なコードを書くときは、データがメモリ上でどのように配置されるかに気を配ることで、この種の目に見えないパフォーマンスキラーを避けられることが多いのです。