メモリ階層とキャッシュ

この章でわかること:

• なぜメモリの読み書きは、CPUの計算より桁違いに遅いのか
• キャッシュとキャッシュラインの仕組み
• 「局所性」というキャッシュを味方につける条件
• VecとLinkedListの速度差、構造体レイアウトが性能に効く理由

CPUから見るとメモリは遠い

前章の最後で「データが届かなければCPUは待つだけ」と書きました。 どれくらい待つのか、数字で確認します。

メインメモリに使われているDRAM(dynamic RAM)という種類のメモリは、 読み出しの要求を出してから値が届くまで、おおよそ100ナノ秒かかります。 3GHzのCPUにとっての100ナノ秒は約300サイクル。 1サイクルで終わる加算の300倍です。

1章の直喩を延長すると、レジスタが机の上のメモ用紙だとすれば、 メインメモリは、例えば別の階にある書庫のようなものです。 収納力は桁違いですが、取りに行くたびに300歩かかります。

ここで2つの用語を区別しておきます。

• レイテンシ(latency) — 要求してから最初の結果が届くまでの時間
• 帯域幅(bandwidth) — 単位時間あたりに転送できるデータ量

メモリの問題は主にレイテンシです。DRAMの帯域幅は毎秒数十GBと大きいのですが、 「最初の1個が届くまでが遅い」のです。

キャッシュ — 小さくて速いメモリを間に挟む

この300サイクルの待ちを毎回払っていたら、CPUがいくら速くても無意味です。 そこでCPUは、キャッシュ(cache)と呼ばれる小容量・高速なメモリを CPUチップ内に持ち、最近使ったデータの写しを置いておきます。 キャッシュには高価だが高速なSRAM(static RAM)が使われます。

多くのCPUではキャッシュは3段構成で、CPUに近い順にL1、L2、L3と呼びます (Lはlevelの略)。近年の一般的なx86-64 CPUを例に、おおよその数字を挙げます (段数・容量・共有のしかたはCPUのモデルごとに異なります)。

記憶場所	容量の目安	レイテンシの目安
レジスタ	数百バイト	—(演算器の手元にある)
L1キャッシュ	32〜64KB	約4サイクル
L2キャッシュ	256KB〜2MB	約12サイクル
L3キャッシュ	数MB〜数十MB	約40サイクル
メインメモリ(DRAM)	数GB〜	約200〜400サイクル

階層の関係を図にするとこうなります。

flowchart LR
    core["CPUコア"] <--> l1["L1<br/>小さい・速い"] <--> l2["L2"] <--> l3["L3"] <--> dram["メインメモリ<br/>大きい・遅い"]

CPUがデータを読むときはまずL1を探し、なければL2、L3、 最後にメインメモリへと降りていきます。目的のデータがキャッシュに あることをキャッシュヒット(cache hit)、ないことを キャッシュミス(cache miss)と呼びます。 L1にヒットし続ける限り、メモリはほぼレジスタ並みに速く見えます。 ミスするたびに、下の階層のレイテンシを支払います。

なお、この仕組みはすべてハードウェアが自動で行います。 プログラムから「キャッシュに入れる」命令を書くわけではありません。 プログラマにできるのは、キャッシュが効きやすいデータの並べ方と アクセスの仕方を選ぶことです。この章の残りはその方法の話です。

キャッシュライン — 転送は64バイト単位

キャッシュとメモリの間のデータ転送は、1バイト単位ではなく キャッシュライン(cache line)と呼ばれる固定長のかたまり単位で行われます。 x86-64では64バイトが標準的です(Apple SiliconなどARM64系には 128バイトのCPUもあります)。以降は64バイトを前提に説明します。

つまりdata[0](u64なら8バイト)を1個読むだけでも、 その周囲を含む64バイト(u64なら8要素分)がまとめてキャッシュに載ります。 次の図がその様子です。

キャッシュへの転送は64バイトのライン単位。1要素の読み出しでも周囲がまとめて届く

このことを実験で確かめます。64MBの配列(キャッシュより十分大きい)に対して、 「全要素を読む」場合と「8要素おきに読む」場合を比べます。 読み出しの回数は8分の1になるので、素朴に考えれば時間も8分の1に なりそうですが——

読み出し回数を1/8にしたら、1/8の時間になるか?

use std::time::Instant;

fn main() {
    // u64 が800万要素 = 64MB。キャッシュに収まらない大きさにする
    let n = 8_000_000;
    let data: Vec<u64> = (0..n as u64).collect();

    // (1) 全要素を順に読む
    let start = Instant::now();
    let mut sum = 0u64;
    for i in 0..n {
        sum = sum.wrapping_add(data[i]);
    }
    println!("全要素   ({n} 回の読み出し): {:>9.3?}", start.elapsed());
    assert!(sum != 0);

    // (2) 8要素おきに読む(読み出し回数は 1/8)
    let start = Instant::now();
    let mut sum = 0u64;
    let mut i = 0;
    while i < n {
        sum = sum.wrapping_add(data[i]);
        i += 8;
    }
    println!("8個おき ({} 回の読み出し): {:>9.3?}", n / 8, start.elapsed());
    assert!(sum != 0);
}

use std::time::Instant; fn main() { // u64 が800万要素 = 64MB。キャッシュに収まらない大きさにする let n = 8_000_000; let data: Vec<u64> = (0..n as u64).collect(); // (1) 全要素を順に読む let start = Instant::now(); let mut sum = 0u64; for i in 0..n { sum = sum.wrapping_add(data[i]); } println!("全要素 ({n} 回の読み出し): {:>9.3?}", start.elapsed()); assert!(sum != 0); // (2) 8要素おきに読む(読み出し回数は 1/8) let start = Instant::now(); let mut sum = 0u64; let mut i = 0; while i < n { sum = sum.wrapping_add(data[i]); i += 8; } println!("8個おき ({} 回の読み出し): {:>9.3?}", n / 8, start.elapsed()); assert!(sum != 0); }

▶ 実行編集stable / releasePlaygroundで開く ↗

Playground上での筆者の実測では、全要素が約3.7ミリ秒、 8個おきが約5.5ミリ秒でした。読み出し回数を8分の1にしたのに、 速くならないどころか、むしろ遅くなります。

理由はこう説明できます。u64は8バイトなので、8要素おきのアクセスは 「64バイトごとに1回」、つまりすべてのキャッシュラインに触れます。 メモリから運ぶライン数は全要素の場合と同じです。この実験の実行時間を 決めているのはCPUの加算回数ではなく、メモリから運んだラインの本数なのです。

さらに、連続アクセスの側には2つの追い風があります。 1つはプリフェッチ(prefetch)。CPUは「順番に読んでいる」という 規則性を検出すると、要求される前に次のラインを先読みして、 レイテンシを隠します。もう1つはSIMD命令による一括処理で、 これは4章で扱います。

局所性 — キャッシュが効く条件

ここまでの仕組みをプログラム側から見ると、 キャッシュが効くコードの条件は2つに整理できます。

• 空間的局所性(spatial locality) — 使ったデータの近くを続けて使う。 同じラインに載っているデータは、実質ただで読めます
• 時間的局所性(temporal locality) — 同じデータを短い間隔で繰り返し使う。 キャッシュから追い出される前なら、また速く読めます

逆に、キャッシュが最も効かないのが「次にどこを読むか予測できない」 アクセスです。これも実験で確かめます。同じ配列(64MB)を同じ回数たどりますが、 たどる順序だけを「順番どおり」と「ランダム」で比べます。

同じ配列・同じ回数。順序だけを変える

use std::time::Instant;

// 疑似乱数(外部クレートなしで済ませるための簡易実装)
fn xorshift(state: &mut u64) -> u64 {
    *state ^= *state << 13;
    *state ^= *state >> 7;
    *state ^= *state << 17;
    *state
}

fn main() {
    let n: usize = 16_000_000; // u32で64MB。キャッシュに収まらない大きさ

    // next[i] = 「次にたどる添字」。まずは順番どおり
    let seq: Vec<u32> = (0..n as u32).map(|i| (i + 1) % n as u32).collect();

    // 全要素をランダムな順で一巡する輪を作る(Sattolo法)。
    // i -> rand[i] とたどると、全要素を1回ずつ通って戻ってくる
    let mut rand: Vec<u32> = (0..n as u32).collect();
    let mut state = 0x2545_F491_4F6C_DD1D_u64;
    for i in (1..n).rev() {
        let j = (xorshift(&mut state) % i as u64) as usize;
        rand.swap(i, j);
    }

    // どちらも「配列を n 回たどる」点はまったく同じ
    for (name, next) in [("順番どおり", &seq), ("ランダム  ", &rand)] {
        let start = Instant::now();
        let mut pos = 0u32;
        for _ in 0..n {
            pos = next[pos as usize];
        }
        println!("{name}: {:>9.3?} (最終位置 {pos})", start.elapsed());
    }
}

use std::time::Instant; // 疑似乱数(外部クレートなしで済ませるための簡易実装) fn xorshift(state: &mut u64) -> u64 { *state ^= *state << 13; *state ^= *state >> 7; *state ^= *state << 17; *state } fn main() { let n: usize = 16_000_000; // u32で64MB。キャッシュに収まらない大きさ // next[i] = 「次にたどる添字」。まずは順番どおり let seq: Vec<u32> = (0..n as u32).map(|i| (i + 1) % n as u32).collect(); // 全要素をランダムな順で一巡する輪を作る(Sattolo法)。 // i -> rand[i] とたどると、全要素を1回ずつ通って戻ってくる let mut rand: Vec<u32> = (0..n as u32).collect(); let mut state = 0x2545_F491_4F6C_DD1D_u64; for i in (1..n).rev() { let j = (xorshift(&mut state) % i as u64) as usize; rand.swap(i, j); } // どちらも「配列を n 回たどる」点はまったく同じ for (name, next) in [("順番どおり", &seq), ("ランダム ", &rand)] { let start = Instant::now(); let mut pos = 0u32; for _ in 0..n { pos = next[pos as usize]; } println!("{name}: {:>9.3?} (最終位置 {pos})", start.elapsed()); } }

▶ 実行編集stable / releasePlaygroundで開く ↗

筆者の実測(Playground)では、順番どおりが約25ミリ秒、ランダムが約1.7秒。 70倍近い差です。ランダム側は1回あたり約110ナノ秒で、 これは冒頭に挙げたDRAMのレイテンシがほぼそのまま見えている状態です。

このコードでは、次に読む場所がnext[pos]——つまり 今の読み出しの結果を見るまでわからないようになっています。 このようなアクセスパターンをポインタチェイシング(pointer chasing)と 呼びます。予測できないのでプリフェッチは働かず、 1回ごとにメモリのレイテンシを丸ごと支払います。

VecとLinkedListの本当の差

ポインタチェイシング、と聞いて思い当たるデータ構造があります。 連結リストです。LinkedListの各ノードはヒープ上の別々の場所に 確保され、次のノードへはポインタをたどって移動します。

100万要素の合計: Vec vs LinkedList

use std::collections::LinkedList;
use std::time::Instant;

fn main() {
    let n = 1_000_000u64;

    let vec: Vec<u64> = (0..n).collect();
    let list: LinkedList<u64> = (0..n).collect();

    let start = Instant::now();
    let sum: u64 = vec.iter().sum();
    println!("Vec       : {:>9.3?} (sum={sum})", start.elapsed());

    let start = Instant::now();
    let sum: u64 = list.iter().sum();
    println!("LinkedList: {:>9.3?} (sum={sum})", start.elapsed());
}

use std::collections::LinkedList; use std::time::Instant; fn main() { let n = 1_000_000u64; let vec: Vec<u64> = (0..n).collect(); let list: LinkedList<u64> = (0..n).collect(); let start = Instant::now(); let sum: u64 = vec.iter().sum(); println!("Vec : {:>9.3?} (sum={sum})", start.elapsed()); let start = Instant::now(); let sum: u64 = list.iter().sum(); println!("LinkedList: {:>9.3?} (sum={sum})", start.elapsed()); }

▶ 実行編集stable / releasePlaygroundで開く ↗

筆者の実測(Playground)ではVecが約0.4ミリ秒、LinkedListが約3ミリ秒で、 6倍以上の差がつきました。Vecは全要素がメモリ上に連続して並ぶため、 空間的局所性が最大限に働きます。

しかもこの実験はLinkedListにとって好条件です。ノードを一気に 作ったので、たまたまメモリ上でほぼ連続に並んでいます。長時間動く 実際のアプリケーションでは、ノードはメモリのあちこちに散らばり、 差はさらに開きます。

要素数の増減が多いから連結リスト、という教科書的な判断は、 現代のCPUではほとんどの場合Vecに負けます。 LinkedListの公式ドキュメント自身が、 ほぼ常にVecかVecDequeのほうが速いと明記しているほどです。

構造体のレイアウトとパディング

データの「並び」の話をもう一段細かく見ます。構造体のフィールドは メモリ上にどう並ぶのでしょうか。

前提となる規則がアラインメント(alignment)です。多くのCPUでは、 8バイトの値は8の倍数のアドレスに置く、というように、型ごとに 「置いてよいアドレスの単位」が決まっています。この規則を守るために フィールドの間に挿入される無駄な隙間をパディング(padding)と呼びます。

フィールドの並びとサイズ

use std::mem::{align_of, size_of};

// フィールドの並び順はコンパイラにまかせる(既定)
#[allow(dead_code)]
struct Auto {
    a: u8,
    b: u64,
    c: u16,
}

// C言語と同じ規則: 宣言順に、アラインメントを守って並べる
#[allow(dead_code)]
#[repr(C)]
struct CLayout {
    a: u8,
    b: u64,
    c: u16,
}

fn main() {
    println!(
        "既定     : size = {:2} bytes, align = {} bytes",
        size_of::<Auto>(),
        align_of::<Auto>()
    );
    println!(
        "#[repr(C)]: size = {:2} bytes, align = {} bytes",
        size_of::<CLayout>(),
        align_of::<CLayout>()
    );
}

use std::mem::{align_of, size_of}; // フィールドの並び順はコンパイラにまかせる(既定) #[allow(dead_code)] struct Auto { a: u8, b: u64, c: u16, } // C言語と同じ規則: 宣言順に、アラインメントを守って並べる #[allow(dead_code)] #[repr(C)] struct CLayout { a: u8, b: u64, c: u16, } fn main() { println!( "既定 : size = {:2} bytes, align = {} bytes", size_of::<Auto>(), align_of::<Auto>() ); println!( "#[repr(C)]: size = {:2} bytes, align = {} bytes", size_of::<CLayout>(), align_of::<CLayout>() ); }

▶ 実行編集stable / releasePlaygroundで開く ↗

u8 + u64 + u16の合計は11バイトですが、結果は16バイトと24バイトです (64ビット環境での実測です)。

• #[repr(C)](C言語互換の並び)では宣言順に置くため、 a: u8の後に7バイト、c: u16の後に6バイトのパディングが入り24バイト
• Rustの既定のレイアウトでは、コンパイラがフィールドを 並べ替えてパディングを減らし、16バイトに収めます。 ただし既定レイアウトの結果は言語仕様として保証されておらず、 コンパイラのバージョンで変わりえます。順序やサイズを固定したいときに 使うのが#[repr(C)]です

1個あたり8バイトの差は、100万要素のVecにすると16MB対24MBの差になります。 同じキャッシュ容量に載る要素数が1.5倍違うということです。

使うフィールドだけを連続に並べる

構造体の配列には、もう1つ落とし穴があります。 一部のフィールドしか使わない走査では、使わないフィールドまで キャッシュラインに載ってくることです。

// AoS: 構造体の配列 (Array of Structs)
struct Player {
    x: f32,
    y: f32,
    hp: u32,
    name: String, // 24バイト
}
let players: Vec<Player> = /* ... */;
// 座標だけ使いたいのに、hp や name もラインに載ってくる

// SoA: 配列の構造体 (Struct of Arrays)
struct Players {
    x: Vec<f32>,
    y: Vec<f32>,
    hp: Vec<u32>,
    name: Vec<String>,
}
// x だけの走査なら、ラインの64バイト全部が x で埋まる

前者をAoS(array of structs)、後者をSoA(struct of arrays)と 呼びます。座標だけを全件走査する処理では、SoAはキャッシュラインの 64バイトすべてが必要なデータで埋まるため、転送効率が上がります。 何でもSoAにすべきという話ではなく、「全件走査する熱いフィールドが 一部だけ」という場面の設計手段です。SoAは4章のSIMDや GPUのメモリでも決定的に重要になります。

まとめ

• メインメモリ(DRAM)のレイテンシは約100ナノ秒。CPUの加算の数百倍です
• CPUはL1/L2/L3のキャッシュに写しを置いてこの遅さを隠します。 転送は64バイトのキャッシュライン単位です
• キャッシュを効かせる鍵は空間的・時間的局所性。 実験では、アクセス順序を変えただけで70倍近い差が出ました
• Vecが速いのは連続配置ゆえ。LinkedListはポインタチェイシングの塊です
• Rustコンパイラはフィールドを並べ替えてパディングを減らします。 熱いフィールドが一部だけなら SoA も検討します

キャッシュは「データの待ち」を減らす仕組みでした。 次章では、CPUが「命令の処理」そのものを流れ作業で重ねて速くする仕組み、 パイプラインと分岐予測を見ます。ここでも鍵になるのは「予測」です。