CPUキャッシュとメモリ階層 入門 - キャッシュラインと局所性から実測まで

同じ要素数の二重ループなのに、i と j を入れ替えただけで実行時間が数十倍変わることがあります。命令数はほとんど同じなのに、なぜここまで差が出るのでしょうか。答えはCPUキャッシュにあります。この記事では、メモリ階層という考え方から、キャッシュライン、参照の局所性、マッピング方式、書き込みポリシーまでを整理したうえで、実際に手元のマシン(Apple M3 Max)で測った数値を添えて、コードの書き方がどう性能に効くのかを見ていきます。

なお、この記事で挙げる具体的な数値はいずれもCPU世代・製品・測定条件で大きく変わります。出典のある値は出典を明記し、手元で測った値は「手元の環境での目安」として区別して書きます。

メモリ階層 - 速さと大きさのトレードオフ

CPUから見たデータの置き場所は、速いが小さいものから遅いが大きいものへと段階的に並んでいます。これをメモリ階層(memory hierarchy)と呼びます。

桁が1段変わるごとに、だいたい10倍前後の差が開きます。ポイントは、この階層をプログラマが明示的に操作するわけではないという点です。レジスタ割り当てはコンパイラが、キャッシュはハードウェアが、ページの物理配置はOSが決めます(仮想メモリとページングの仕組みで扱ったページテーブルとTLBも、この階層の一部です)。プログラマにできるのは「ハードウェアが自動でうまくやれるようなアクセスパターンで書く」ことだけです。

公表されているサイクル数の例

Intelの最適化マニュアル(Intel 64 and IA-32 Architectures Optimization Reference Manual, Document #248966-050US)には、マイクロアーキテクチャごとのキャッシュ諸元表が載っています。

AMDのZen5向け最適化ガイド(Software Optimization Guide for the AMD Zen5 Microarchitecture, 58455 Rev.1.00)も同様に、L1データキャッシュは48KBの12ウェイセットアソシアティブでライトバック、整数ロードのload-to-useレイテンシは4または5サイクル、L2は1MBの16ウェイで14サイクル以上、L3は16ウェイでL2からの追い出し(victim)によって埋められ平均46サイクル、と記載しています。

Intelの表には「ソフトウェアから見えるレイテンシはアクセスパターンなどの条件で変動する」という注記が付いています。これらは理想条件の下限値であり、実アプリでこの通りに出るわけではない、と理解してください。歴史的な比較としては、Ulrich Drepperの "What Every Programmer Should Know About Memory"(LWN.net, 2007年)がPentium Mでの目安として、レジスタ1サイクル以下、L1d約3サイクル、L2約14サイクル、メインメモリ約240サイクルという表を挙げています。20年近く経っても、階層ごとの相対的な開き方はほとんど変わっていません。

手元のマシンの階層を覗く

Linuxでは、カーネルがsysfsに各キャッシュの属性を公開しています。属性名の意味はカーネルの Documentation/ABI/testing/sysfs-devices-system-cpu に定義されており、coherency_line_size(キャッシュラインのバイト数)、ways_of_associativity、number_of_sets、write_policy、allocation_policy などが読めます。

# キャッシュ構成の一覧
lscpu -C
 
# キャッシュラインのバイト数(多くのx86-64環境で64)
getconf LEVEL1_DCACHE_LINESIZE
 
# 生の属性を直接見る
cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size
cat /sys/devices/system/cpu/cpu0/cache/index0/write_policy

macOSには perf も lscpu もありませんが、sysctl で同じ情報が取れます。手元のApple M3 Maxでの実行結果は次の通りでした。

$ sysctl hw.cachelinesize hw.perflevel0.l1dcachesize hw.perflevel0.l2cachesize hw.perflevel1.l1dcachesize
hw.cachelinesize: 128
hw.perflevel0.l1dcachesize: 131072      # Pコア L1D 128KB
hw.perflevel0.l2cachesize: 16777216     # Pコアクラスタ共有 L2 16MB
hw.perflevel1.l1dcachesize: 65536       # Eコア L1D 64KB

Apple Siliconは高性能(P)コアと高効率(E)コアでキャッシュ構成が異なるため、hw.perflevel0 と hw.perflevel1 を分けて見る必要があります。そしてキャッシュラインは128バイトで、x86-64の64バイトとは異なります。これが後述するfalse sharing対策のパディング幅に直結します。

キャッシュラインという単位 - なぜ64バイトなのか

キャッシュはバイト単位では動きません。キャッシュライン(cache line)という固定サイズのブロック単位でメモリとやり取りします。4バイトの int を1つ読んだつもりでも、実際にはその周辺を含む1ライン丸ごとがキャッシュに載ります。

現代のx86-64では64バイトが標準です。Intelの最適化マニュアルはSkylake ClientでもIce Lake Clientでも Line Size を64バイトと記載し、AMDのZen5ガイドも "Cache line size is 64 bytes" と明記しています。Drepperの記事も「初期のキャッシュでは32バイトだったが、いまの標準は64バイト」と書いています。一方でApple Siliconは前述の通り128バイトです。「64バイト」は普遍の定数ではなく、x86-64での慣行だと捉えるのが正確です。

なぜこのサイズに落ち着いたのか。トレードオフは次の3点です。

1. タグのオーバーヘッド: ラインが小さいほどライン数が増え、アドレスのタグを保持するSRAMの割合が増えます。ラインを大きくすればタグの比率は下がります
2. 空間的局所性の取り込み: ラインが大きいほど「ついでに読んだ隣のデータ」が当たる確率が上がります
3. 無駄の増加: 逆にラインが大きすぎると、使わないデータの転送にメモリ帯域を浪費します。ランダムアクセスが多いワークロードほど不利になります

さらに、DRAMがバースト転送でまとまった単位を出す方が効率がよいという事情もあります。この3つのバランスが取れる点として64バイト前後が長く使われている、というのが実情です。

キャッシュラインを意識すると、「構造体のサイズを64バイトの約数・倍数に寄せる」「境界をまたぐ配置を避ける」といった設計判断の意味が見えてきます。AMDのガイドも、64バイト境界をまたぐミスアラインドなロードは最低でも1サイクルのペナルティを受ける、と述べています。

参照の局所性 - キャッシュが効く前提

キャッシュが成立するのは、プログラムのメモリアクセスが完全にランダムではないからです。この経験則を参照の局所性(locality of reference)と呼び、2種類に分けます。

• 時間的局所性(temporal locality): 一度アクセスしたデータは、近い将来もう一度アクセスされやすい。ループカウンタ、ホットなループ本体、頻繁に読むコンフィグ値などが該当します
• 空間的局所性(spatial locality): あるアドレスにアクセスしたら、その近傍のアドレスもアクセスされやすい。配列の順走査、構造体のフィールドを続けて読む処理などが該当します

キャッシュはこの2つを別々の仕掛けで拾います。時間的局所性は「一度載せたラインを置いておく」ことで、空間的局所性は「ラインという広めの単位でまとめて載せる」ことで拾います。逆に言えば、どちらの局所性も持たないアクセスパターン(巨大な配列へのランダムアクセスなど)ではキャッシュはほぼ無力です。

マッピング方式 - どのラインをどこに置くか

メインメモリのあるアドレスのラインを、キャッシュのどの位置に置けるのか。この対応づけの方式がマッピングです。

アドレスはタグ / インデックス / オフセットの3つに分解されます。オフセットはライン内の位置、インデックスはどのセットを見るか、タグは「そのセットに入っているのが本当に目的のラインか」の照合に使います。

Skylake ClientのL1データキャッシュ(32KB、8ウェイ、64Bライン)で計算してみます。

セット数 = 32768 / (8 * 64) = 64セット
 
オフセット : 6ビット (64バイト = 2^6)
インデックス: 6ビット (64セット = 2^6)
タグ       : 残りの上位ビット

つまり下位12ビットが同じアドレス同士は、必ず同じセットを奪い合います。4096バイト間隔で並んだデータを9個以上同時に触ると、8ウェイでは収まらず追い出しが発生します。これが後述するコンフリクトミスの正体で、2のべき乗サイズの配列を並べたときに突然遅くなる現象の原因になります。実務的な回避策は、行の長さに数要素分のパディングを足して2のべき乗を外すことです。

フルアソシアティブは衝突が起きない代わりに、全エントリのタグを並列比較する回路が必要で、容量が大きいと現実的ではありません。そのためデータキャッシュは通常セットアソシアティブが選ばれ、エントリ数の少ないTLBなどでフルアソシアティブが使われます。

置換ポリシー

セットが埋まっているときに、どのラインを追い出すか。理想は「次に使われるのが一番先のもの」ですが未来は分からないので、実装は近似に頼ります。

• LRU(Least Recently Used): 最後に使われてから一番時間が経ったものを追い出す。理論上の基準となる方式です
• 擬似LRU: 真のLRUは順序管理のビットが多く必要なため、ツリー構造などで近似する。ウェイ数の多い実キャッシュではこちらが一般的です
• ランダム / RRIP系: 実装が軽く、ストリーミングアクセスに対してLRUより強い場合があります

LRUというアルゴリズムそのものはLRUキャッシュの仕組みで扱っています。ハードウェアのキャッシュも、アプリケーションのキャッシュも、考えていることは同じです。

ヒット率とミスの3分類

性能を語るときの基本指標が平均メモリアクセス時間(AMAT)です。

AMAT = ヒット時間 + ミス率 × ミスペナルティ

ヒット時間を1サイクル削るのは難しくても、ミス率を半分にすれば効果は大きい。だからチューニングの主戦場はミス率になります。そのミスは、Mark D. HillとAlan Jay Smithによる1989年の論文 "Evaluating Associativity in CPU Caches" 以来、3種類に分類するのが定番です(頭文字を取って3Cと呼ばれます)。

マルチコアではこれに4つ目のC、Coherence(コヒーレンスミス)が加わります。他コアが同じラインに書き込んだせいで自分の持っていたコピーが無効化される、というものです。後述するfalse sharingはこれが原因です。

自分のプログラムがどのミスで詰まっているかは、いきなり分かるものではありません。ワーキングセットのサイズを変えながら測って、キャッシュ容量の境界で急に遅くなるなら容量ミス、特定のサイズだけ突出して遅いなら競合ミス、という当たりの付け方をします。

書き込みポリシー

読み込みだけでなく、書き込みの扱い方にも選択肢があります。Linuxカーネルのsysfs ABIドキュメントは、この2軸をそのまま属性として定義しています。

• ライトスルー(WriteThrough): キャッシュラインと下位メモリの両方に同時に書く。実装が単純でコヒーレンスも取りやすい反面、書き込みのたびに下位への転送が発生します
• ライトバック(WriteBack): キャッシュラインにだけ書き、dirtyビットを立てておく。そのラインが追い出されるときに初めてメモリへ書き戻します。同じ場所を何度も書き換える処理で圧倒的に有利です

現代のCPUのデータキャッシュはほぼライトバックです。Intelの表もSkylake ClientのL1/L2/L3すべてでUpdate Policyを "Writeback" と記載し、AMDのZen5ガイドもL1D・L2・L3をwrite-backと記載しています。

• ライトアロケート(WriteAllocate): 書き込みミスのときも、まずラインをキャッシュに読み込んでから書く。直後にその近傍を読み書きするなら得です
• ノーライトアロケート: 書き込みミスのときはキャッシュに載せず、下位メモリへ直接書く

ライトバック + ライトアロケートの組み合わせが一般的です。ただし「一度書いたきり二度と読まない」大きなバッファ(動画のフレーム出力など)では、ライトアロケートはキャッシュを無駄に汚します。この用途のためにx86には非テンポラルストア(streaming store)が用意されていて、キャッシュを汚さずライトコンバイニングバッファ経由でメモリへ流せます。Intelの最適化マニュアルは第9章でこの使い分けを詳しく扱っています。

実践1: 配列の走査順で数十倍変わる

ここからは実測です。以下のコードは int a[4096][4096](64MB)を、行優先と列優先で合計するだけのものです。

// row-major: メモリ上で連続した順に読む
for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
        s += a[i][j];
 
// column-major: 16KBずつ飛びながら読む
for (int j = 0; j < N; j++)
    for (int i = 0; i < N; i++)
        s += a[i][j];

Cの二次元配列は行優先(row-major)で並ぶので、前者は隣接アドレスを順に舐めます。1回のミスで載った64バイト(あるいは128バイト)のラインに、次に必要な要素が16個(32個)分入っているので、ミスは16回に1回で済みます。後者は毎回16KBジャンプするため、載せたラインの4バイトしか使わずに次のラインへ行き、ハードウェアプリフェッチャも効きません。

手元のM3 Max(clang -O2)での実行結果は次の通りでした。あくまでこの環境での目安です。

row-major (a[i][j]):      4.0 ms
col-major (a[j][i]):    169.8 ms

命令数はほぼ同じで、約40倍の差が付きました。ループを入れ替えるだけの変更が、計算量のオーダーを変えないまま実行時間を桁で動かす、というのがキャッシュの世界です。オーダーが同じアルゴリズム同士を比べるとき、この定数倍が勝敗を決めることは珍しくありません。

実践2: AoSとSoA

構造体の配列(Array of Structures, AoS)と、配列の構造体(Structure of Arrays, SoA)の違いも、キャッシュラインの使い切り方の問題です。Intelの最適化マニュアルもExample 5-19からExample 5-22でこの変換を推奨しています。

// AoS: 1要素48バイト。x だけ欲しくても他のフィールドまで載る
typedef struct { float x, y, z; int id; float pad[8]; } Particle;
Particle *aos;
 
// SoA: x だけの連続配列。ラインを100%使い切れる
float *xs, *ys, *zs;

800万要素で x の合計だけを取る処理を比べた、手元での結果です。

AoS  sum of x:    56.2 ms
SoA  sum of x:    21.4 ms

約2.6倍の差です。AoSは1要素48バイトのうち4バイトしか使わないので、転送したデータの90%以上が無駄になります。SoAならラインいっぱいまで有効データが詰まっており、SIMD命令にも載せやすくなります。

ただし全部SoAにすればよいわけではありません。「1要素の全フィールドをまとめて触る」処理が主体ならAoSの方が有利です。判断基準は「そのループが構造体の一部だけを舐めるか、全体を使うか」です。

実践3: 連結リストと配列

データ構造の選択もキャッシュ効率を大きく左右します。400万要素を合計するだけの処理を、long の配列と、要素ごとに malloc して順序をシャッフルした連結リストで比べました。

array traversal      :     2.2 ms
linked list traversal:   713.1 ms

計算量はどちらもO(n)ですが、実測で約300倍の開きが出ました。連結リストは次のノードのアドレスがロードしてみるまで分からないため、メモリレベル並列性が効かず、ミスのレイテンシがそのまま直列に積み上がります。しかもノードごとに next ポインタ分のメモリを食い、ラインの利用率も落ちます。

この極端さは「バラバラに確保したノードを、確保順と無関係な順序でたどる」という最悪ケースを作ったためですが、長時間動くアプリで断片化が進むと現実に近づいていきます。挿入削除がO(1)だからという理由だけで連結リストを選ぶと、実測では配列に負けることがよくある、と覚えておくと役に立ちます。ハッシュテーブルのチェイン法がオープンアドレス法に実測で負けやすいのも、根は同じ理由です。

実践4: false sharing とマルチスレッド

複数コアが別々の変数を更新しているのに、それらが同じキャッシュラインに載っているせいで、コヒーレンスプロトコルがラインを行き来させて遅くなる。これがfalse sharing(偽共有)です。ソースコード上は共有していないのに、ハードウェアから見ると同じラインを共有しているので、この名前が付いています。

// 悪い例: 4スレッド分のカウンタが同じラインに同居する
struct { long v; } counters[4];
 
// 良い例: ラインサイズ分パディングして別ラインへ分ける
struct { long v; char pad[128 - sizeof(long)]; } counters[4];

手元のM3 Max(4スレッド、各5000万回のインクリメント)での結果です。

1 thread  packed                 : 246.2 ms
4 threads packed (false sharing) : 453.6 ms
4 threads padded                 : 383.5 ms

パディングした方が速いものの、差は1.2〜1.6倍程度で、実行のたびに揺れました。この測定ではインクリメント自体のストア・ロード依存が支配的で、コヒーレンスのコストが相対的に薄まっているためと考えられます。false sharingの影響度はコア間の距離やコヒーレンス実装に強く依存するので、「必ず何倍遅くなる」という一般化はできません。パディングは効くこともあるが、まず計測して確かめるべき対象です。

パディング幅の決め方について、Intelの最適化マニュアルは「false-sharing threshold」という考え方を示しています。CLFLUSHのライン幅(CPUID.01H:EBX[15:8])を使い、取得できない場合は安全側の64バイトを既定値にせよ、という指針です。Apple Siliconのように128バイトの環境もあるため、移植性を考えるなら128バイト境界に揃えておくのが無難です。C++には std::hardware_destructive_interference_size もあります。

Linux環境では perf c2c がキャッシュライン単位のcache-to-cache転送を追跡してくれるので、どの変数がfalse sharingを起こしているかを特定できます。IntelのマニュアルもこのツールとHITMカウンタによる検出手順を紹介しています。排他制御そのものの設計はミューテックスとセマフォ、デッドロック、スレッドモデルの前提は並行と並列・プロセスとスレッドを参照してください。

実践5: プリフェッチ

ミスペナルティを隠す仕組みがプリフェッチです。CPUはアクセスパターンを推測して、必要になる前にラインを持ってきます。Intelの最適化マニュアル9.5.2節が挙げるハードウェアプリフェッチャの性質は、そのままコードを書く側の指針になります。

• データアクセスパターンに規則性が必要。ストライドが一定であること、あるいは連続ミスのストライドがトリガ閾値より小さいこと
• 起動にはある程度の連続ミスが必要で、短い配列ではオーバーヘッドが上回る
• 4KBのページ境界を越えてプリフェッチしない。新しいページは通常のロードで先に触る必要がある
• ストライドが64バイトに近い小刻みなアクセスで最も効く

つまり「連続に近い順で舐める」「ストライドを小さく保つ」「配列を細切れにしない」という素直な書き方が、そのままプリフェッチャに味方する書き方になります。実践1の列優先ループがあれほど遅かったのは、プリフェッチャが助けてくれなかったからでもあります。

規則性のないアクセスでは、GCC/Clangの __builtin_prefetch などでソフトウェアプリフェッチを明示する手もあります。ただし発行しすぎると帯域と発行スロットを浪費するので、Intelのマニュアルも「ソフトウェアプリフェッチの数は最小限に」と述べています。まず計測、次に投入、そして再計測という順序を守るべき最適化です。

計測する - perf と macOS

推測でキャッシュを語らないために、計測方法を押さえておきます。Linuxでは perf が第一選択です。

# 概要 + L1/LLCのデータキャッシュ統計(-d を重ねるとTLBまで出る)
perf stat -d ./myprog
 
# イベントを指定して測る(使えるイベント名は環境依存)
perf list cache
perf stat -e cache-references,cache-misses,L1-dcache-loads ./myprog
 
# ばらつきを見るため複数回実行して平均と標準偏差を出す
perf stat -r 10 ./myprog
 
# false sharing を起こしているキャッシュラインを特定する
perf c2c record ./myprog && perf c2c report

perf stat のマニュアルは -d について "detailed events, L1 and LLC data cache"、-d -d について "more detailed events, dTLB and iTLB events" と説明しています。イベント名はCPUによって差があるので、必ず perf list で実在を確認してから使ってください。

macOSには perf がありません。代わりに次の手段があります。

• Xcode Instruments の CPU Counters テンプレート: PMUイベントを選んで計測できます。テンプレート一覧は xcrun xctrace list templates で確認でき、手元の環境では CPU Counters と Processor Trace が利用可能でした
• sysctl: 前述の通り、キャッシュ構成そのものの確認に使います
• 自作のマイクロベンチマーク: この記事の実測値もすべてこの方法です。clock_gettime(CLOCK_MONOTONIC, ...) で時間を測り、ワーキングセットサイズを2倍ずつ変えながら1アクセスあたりのコストを出します

利用可能なPMUイベントの一覧は、Appleが公開している Apple Silicon CPU Optimization Guide に掲載されています(閲覧には開発者アカウントの登録と追加の同意が必要です)。

なお、自作ベンチマークでは最適化でループごと消える事故が頻発します。今回のポインタチェイスも、素直に書いたところ測定時間が0になり、ロードを volatile 経由にして初めて意味のある値が出ました。測定結果が「速すぎる」ときは、まず消えていないかを疑ってください。

ワーキングセットサイズを変えて階層を見る

ランダムなポインタチェイス(1ノードを1ラインに配置)で、確保サイズを2倍ずつ増やしながら1アクセスあたりの時間を測ると、階層の境界が段差として見えます。手元のM3 Maxでの目安です。

この数値はランダムアクセスなのでTLBミスやOSのコアスケジューリングの影響を含んでおり、純粋なキャッシュレイテンシではありません(実際、Pコアの16MB L2の内側であるはずの4MBの時点で大きく跳ねています)。ただし、階層をまたぐたびにコストが数倍になるという構造は、はっきり読み取れます。同じ手順は他の環境でも再現できるので、自分の常用マシンで一度測っておくと感覚が身につきます。

まとめ - 何を覚えて帰るか

• メモリ階層は、レジスタからSSDまで、1段ごとにおよそ1桁ずつ遅く・大きくなる。プログラマが直接操作するのではなく、ハードウェアが自動でうまく動ける書き方をするのが仕事
• キャッシュはライン単位で動く。x86-64では64バイトが標準、Apple Siliconでは128バイト。「64バイト固定」と決め打ちしない
• キャッシュが効くのは参照の局所性があるから。時間的局所性はラインを保持することで、空間的局所性はラインという単位で拾っている
• ミスは compulsory / capacity / conflict の3種類(マルチコアではcoherenceを加えて4種類)。どれで詰まっているかで打ち手が変わる
• 実務で効くのは、連続アクセスにする、必要なフィールドだけを密に並べる(SoA)、ポインタで飛び回らない、共有カウンタをラインで分ける、の4点
• 数値は必ず自分の環境で測る。CPU世代・コンパイラ・OSスケジューラで簡単に変わる

キャッシュ最適化は、まず正しく動くコードとプロファイルがあってからの話です。データ量が小さいうちは何をしても同じで、アルゴリズムのオーダーの方が支配的です。それでも、ホットループの中で「このループはラインをいくつ触るか」を頭の片隅で数えられるようになると、書くコードの質は確実に変わります。データの並べ方という観点ではデータ圧縮の基礎やガベージコレクションの仕組みも地続きの話題です。

参考リンク

• Intel 64 and IA-32 Architectures Optimization Reference Manual Volume 1 (Document #248966-050US): https://cdrdv2-public.intel.com/821612/248966-Optimization-Reference-Manual-V1-050.pdf
• Intel 64 and IA-32 Architectures Optimization Reference Manual(配布ページ): https://www.intel.com/content/www/us/en/developer/articles/technical/intel64-and-ia32-architectures-optimization.html
• Software Optimization Guide for the AMD Zen5 Microarchitecture (58455 Rev.1.00): https://docs.amd.com/v/u/en-US/58455_1.00
• Ulrich Drepper, "What Every Programmer Should Know About Memory" Part 1 (LWN.net): https://lwn.net/Articles/250967/
• 同 Part 2: CPU Caches (LWN.net): https://lwn.net/Articles/252125/
• Linux kernel ABI: sysfs-devices-system-cpu(キャッシュ属性の定義): https://raw.githubusercontent.com/torvalds/linux/master/Documentation/ABI/testing/sysfs-devices-system-cpu
• perf-stat(1) - Linux manual page: https://man7.org/linux/man-pages/man1/perf-stat.1.html
• perf-c2c(1) - Linux manual page: https://man7.org/linux/man-pages/man1/perf-c2c.1.html
• lscpu(1) - Linux manual page: https://man7.org/linux/man-pages/man1/lscpu.1.html
• Apple Silicon CPU Optimization Guide(Apple Developer): https://developer.apple.com/documentation/apple-silicon/cpu-optimization-guide
• M. D. Hill and A. J. Smith, "Evaluating Associativity in CPU Caches" (IEEE Trans. Computers, 1989): https://pages.cs.wisc.edu/~markhill/papers/toc89_cpu_cache_associativity.pdf
• Solidigm D7-P5520/P5620 Product Brief(NVMe SSDのレイテンシ諸元): https://www.solidigm.com/content/dam/solidigm/en/site/products/data-center/product-briefs/d7-p5520-p5620-product-brief/documents/d7-p5520-p5620-product-brief.pdf