メモリレイアウトとデータ局所性（キャッシュを意識した設計）

なぜレイアウトが性能を決めるのか

現代のCPUコアとメインメモリ（DRAM）の速度差は数十倍から数百倍あります。コアがメモリから値を1つ取り出すのに数百サイクル待たされる一方、L1キャッシュなら数サイクルで済みます。この差を埋めるのがキャッシュ階層であり、どのデータがキャッシュに載るかを決めるのがメモリレイアウトです。つまり同じ計算量（Big-O）のアルゴリズムでも、データの並べ方しだいで実測性能は数倍変わります。Big-Oはメモリアクセスを一律「定数時間」と仮定しますが、実機ではそれが崩れるからです。

ポイントは、CPUがメモリを1バイト単位ではなくキャッシュライン単位でやり取りすることです。1つの値が欲しくても、それを含む固定サイズの塊（多くのアーキテクチャで64バイト）が丸ごと運ばれます。この事実が、以降で扱うアライメント・局所性・SoAのすべての前提になります。

アライメントとパディング

CPUは型ごとに「この境界から始まっていてほしい」というアライメント制約を持ちます。一般に、4バイトのintは4の倍数アドレスから、8バイトのdouble/ポインタは8の倍数アドレスから始めるのが効率的（あるいは必須）です。コンパイラはこれを満たすため、フィールドの間や末尾にパディング（詰め物）を自動挿入します。

struct Bad {
    char  a;   // 1 byte
    // ここに 7 byte のパディング
    double b;  // 8 byte（8の倍数境界が必要）
    char  c;   // 1 byte
    // ここに 7 byte のパディング（構造体末尾もアライメント）
};  // sizeof = 24

struct Good {
    double b;  // 8 byte
    char  a;   // 1 byte
    char  c;   // 1 byte
    // ここに 6 byte のパディング
};  // sizeof = 16

中身は同じ3フィールドなのに、Bad は24バイト、Good は16バイトです。違いは宣言順だけ。一般則は「サイズの大きいフィールドから順に並べる」で、これにより隙間が減ります。構造体全体のサイズは、最も厳しいフィールドのアライメント（この例では8）の倍数に切り上げられるため、末尾パディングも生じます。

キャッシュラインと2つの局所性

性能の良し悪しは、ロードしたキャッシュラインをどれだけ無駄なく使えるかで決まります。これを表す原理が局所性で、2種類あります。

• 空間局所性: あるアドレスを参照したら、その近傍も近いうちに参照される傾向。配列を順番に舐めるアクセスは、1ライン分（64バイト＝int 16個分）を一度載せれば後続も同じラインから取れるため、非常に効率的です。
• 時間局所性: 一度参照したデータは、近いうちに再び参照される傾向。ループ内で何度も読む変数や、繰り返し叩く小さなテーブルがこれに当たります。

逆に、ばらばらのアドレスを飛び回るアクセス（連結リストのポインタ追跡や、ハッシュ表の衝突連鎖など）は空間局所性が乏しく、ラインの大半を捨てることになります。配列が連結リストより実測で速い場面が多いのは、計算量が同じでもこの局所性で差がつくからです。ポインタ追跡が遅いのは、各ノードが別々のラインに散らばり、しかも次のアドレスが分かるまで先読みできない（ポインタのデリファレンスが直列化する）ためです。

AoS と SoA

同じデータの集合でも、**構造体の配列（AoS）か配列の構造体（SoA）**かでレイアウトが根本的に変わります。

// AoS: Array of Structs（1要素にxyzが密に同居）
struct Particle { float x, y, z; float mass; };
Particle particles[N];

// SoA: Struct of Arrays（同じフィールドが連続）
struct Particles {
    float x[N], y[N], z[N];
    float mass[N];
};

両者の使い分けは「ループで全フィールドを使うか、一部だけか」で決まります。

たとえば「全粒子の x だけを加算する」ループを考えます。AoSでは1要素16バイト（float 4個）のうち欲しいのは x の4バイトだけで、ラインの約4分の3が無駄になります。SoAなら x[] が連続し、64バイトのラインに16個分の x が載るので、実効的なメモリ帯域がそのまま使い切れます。さらにSoAは同種データが並ぶためSIMD（1命令で複数要素を処理）に乗せやすく、二重の恩恵があります。

逆に「1粒子の位置と質量をまとめて1個だけ計算する」ような処理ではAoSが有利で、関連データが1ラインに収まります。万能解はなく、支配的なアクセスパターンに合わせるのが原則です。

設計の指針

レイアウト最適化は「測ってから」が鉄則です。やみくもにSoA化するとコードの可読性を損ない、アクセスパターンが想定と違えば逆効果にもなります。

• まず素直に書く。AoSやオブジェクト指向的な構造で組み、プロファイラでキャッシュミス率の高いホットループを特定する。
• その箇所だけ、支配的なアクセスに合わせてレイアウトを変える。全フィールド走査ならAoS、一部走査やSIMDならSoA、という基準で判断する。
• 構造体は大きい型から並べ、パディングを減らす。並行コードではホットな変数をライン境界に隔離してフォルスシェアリングを断つ。

まとめ

メモリレイアウトの本質は、CPUがデータをキャッシュライン単位でしか運べないという制約に集約されます。アライメントとパディングは構造体のサイズと密度を左右し、フィールド順という些細な選択がメモリ量と帯域効率を変えます。空間局所性と時間局所性を高めるレイアウト——連続アクセスできる配列、支配的パターンに合わせたAoS/SoAの選択、ホット／コールド分離、フォルスシェアリングの回避——は、計算量を一切変えずに実測性能を引き上げます。アルゴリズムを詰めたら、次はデータをハードウェアに優しく並べる。これが上級者の性能設計の定石です。