キャッシュフレンドリーなデータレイアウト
配列の構造体を設計し、キャッシュ局所性を高めるようデータをパックします。
「キャッシュフレンドリーなデータレイアウト」はCoddyKit上の無料C++ Academyレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはC++ Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 C++ Academyコースには全4レッスンが含まれています。
メモリー階層
CPUには複数のキャッシュレベル（L1、L2、L3）があり、メインメモリーよりはるかに高速です。キャッシュフレンドリーなコードは、頻繁に使うデータをCPUの近くに保ちます。
キャッシュライン
メモリーはキャッシュライン単位で読み込まれ、通常は64バイトです。1バイトを読み込むと、ライン全体が読み込まれます。この特性を活用してください。
参照の局所性
重要な性質は2つあります。
- 空間的局所性 — 近くにあるメモリーをすぐに使うこと
- 時間的局所性 — 同じメモリーをすぐに再利用すること
連続配置とリンク配置
ベクターはデータを連続して格納するため、反復処理がキャッシュフレンドリーです。リンクリストではメモリーが分散し、ステップごとにキャッシュが破綻します。
// Cache friendly
std::vector<int> v(1000);
for (auto& x : v) ++x;
// Cache UNfriendly
std::list<int> l(1000);
for (auto& x : l) ++x;AoSとSoA
レコードの配列には2つのレイアウトがあります。
- AoS（Array of Structs） — 自然なレイアウトですが、1つのフィールドを反復処理する際にもすべてのフィールドに触れます
- SoA（Struct of Arrays） — ほとんどのループが一部のフィールドだけを使う場合に適しています
// AoS
struct Particle { float x, y, z, vx, vy, vz; };
std::vector<Particle> particles;
// SoA
struct Particles {
std::vector<float> x, y, z, vx, vy, vz;
};構造体のパッキング
パディングを最小限にするには、メンバーを大きいものから小さいものへ並べます。paholeなどのツールで実際のレイアウトを確認できます。
struct Bad { char c; double d; char c2; }; // padded
struct Good { double d; char c; char c2; }; // smaller偽共有
同じキャッシュライン上にある異なる変数へ2つのスレッドが書き込むと、お互いのキャッシュが無効化されます。性能に壊滅的な影響があります。64バイトになるようパディングを追加してください。
struct alignas(64) Counter {
std::atomic<int> value;
};ホットデータとコールドデータの分離
頻繁にアクセスするホットデータと、ほとんどアクセスしないコールドデータを別々の構造体に分けます。CPUはホットな部分だけをキャッシュします。
事前確保
繰り返し再確保されるのを避けるため、reserveでベクターの容量を事前に確保します。再確保のたびにすべての要素がコピーされるため、コストが高く、キャッシュにも悪影響を与えます。
逐次アクセスの優位性
配列を線形に走査するのが最も高速です。ハードウェアのプリフェッチャーが次のキャッシュラインを予測して自動的に読み込みます。
間接参照を避ける
ポインターを使うと、CPUは依存関係をたどらなければなりません。走査では、std::vector<T*>はstd::vector<T>より低速です。間接参照は必要な場合にだけ使ってください。
最適化の前にプロファイリングする
「キャッシュフレンドリー」は指針であって、絶対的なルールではありません。perfやVTuneなどのツールで、キャッシュミスがどこで性能に影響しているかを測定してから最適化します。
理解度チェック
同じサイズのstd::listを反復処理する場合と比べて、std::vectorを反復処理する方が通常ははるかに高速なのはなぜですか。
まとめ
現代のCPUはキャッシュに大きく依存しています。連続配置のコンテナーを優先し、選択的なフィールドアクセスにはSoAを使い、構造体をパッキングし、偽共有を避けてください。perfやVTuneでキャッシュミスをプロファイリングし、ホットスポットを見つけます。
よくある質問
「キャッシュフレンドリーなデータレイアウト」レッスンは無料ですか？
はい。「キャッシュフレンドリーなデータレイアウト」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、C++ Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 C++ Academyコースには全4レッスンが含まれています。
「キャッシュフレンドリーなデータレイアウト」で何を学びますか？
配列の構造体を設計し、キャッシュ局所性を高めるようデータをパックします。 ブラウザで直接実行するハンズオンコードでC++ Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
C++ Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのC++ Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。
「キャッシュフレンドリーなデータレイアウト」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このC++ Academyレッスンでコードを書いて実行できますか？
はい。すべてのC++ Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- キャッシュフレンドリーなデータレイアウト
- 分岐予測とホットループ
- perf、vtune、Sanitizerによるプロファイリング
- Google Benchmarkによるマイクロベンチマーク