メモリ階層とキャッシュ

この章でわかること:

なぜメモリの読み書きは、CPUの計算より数百倍遅いのか
キャッシュとキャッシュラインの仕組み
キャッシュが有効に働く条件である「局所性」
VecとLinkedListの速度差、構造体レイアウトが性能に影響する理由

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

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

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

1章の直喩を延長すると、レジスタが机の上のメモ用紙だとすれば、メインメモリは、例えば別の階にある書庫のようなものです。容量はレジスタの数百万倍以上ありますが、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サイクル

階層の関係を次の図に示します。

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);
}

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());
    }
}

筆者の実測(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());
}

筆者の実測(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>()
    );
}

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が命令の処理そのものを流れ作業で重ねて速くする仕組みである、パイプラインと分岐予測を説明します。ここでも中心になる考え方は予測です。