仮想メモリとTLB

この章でわかること:

プログラムが見るアドレスが「仮想」であること。ページテーブルによる変換の仕組み
TLB — アドレス変換のキャッシュと、そのミスのコスト(実測で1.9倍)
「メモリを確保する」と「物理メモリを使う」が別物であること (デマンドページング。実測で初回アクセスは220倍遅い)
hugepages、コピーオンライト、mmapの位置づけ
なぜ体系に必須か — 2章のキャッシュ階層は、実はアドレス変換というもう1つの階層の上に載っています。この章なしでは「メモリアクセスのコスト」の全体像が閉じません

メモリの住所は2種類ある

これまで「メモリのアドレス」と呼んできたもの——Rustの参照やポインタの中身——は、実は物理的なDRAMの位置ではありません。プログラムが見るのは仮想アドレス(virtual address)で、 CPUとOSが協力して、アクセスのたびに物理アドレス (physical address)へ変換しています。この仕組み全体を 仮想メモリ(virtual memory)と呼びます。

なぜこんな回りくどいことをするのか。理由は主に3つです。

隔離 — プロセスごとに別の変換表を持たせれば、他のプロセスのメモリは「アドレスが存在しない」ため、原理的に触れません
連続の錯覚 — 物理メモリが断片化していても、仮想空間では連続した巨大な配列を確保できます。Vecが「連続したメモリ」でいられるのは、この錯覚のおかげでもあります
実体の遅延と共有 — 後述のとおり、確保しただけのメモリに実体を与えない、同じ物理メモリを複数プロセスで共有する、といった芸当が可能になります

変換はページ(page)という固定長の単位で行います。主流のページサイズは4KBです(Apple Siliconは16KB)。次の図が変換の全体像です。

flowchart LR
    subgraph va ["プロセスの仮想アドレス空間"]
        v1["ページA"]
        v2["ページB"]
        v3["ページC (未割当)"]
    end
    pt["ページテーブル<br/>(OSが管理する変換表)"]
    subgraph pa ["物理メモリ"]
        p1["フレーム#41"]
        p2["フレーム#7"]
    end
    v1 --> pt --> p1
    v2 --> pt
    pt --> p2
    v3 -.->|対応なし| pt

ページテーブルとページウォーク

変換表であるページテーブル(page table)は、OSがメモリ上に作るデータ構造で、CPU内のMMU(memory management unit)が参照します。

64ビットの仮想空間は広大なので、表は1枚ではなく多段の木になっています。x86-64では一般的に4段です(より広い空間を使う 5段拡張を持つCPUもあります)。つまり1回のアドレス変換は、最悪の場合メモリ読み出し4回(各段の表を1回ずつたどる)を意味します。これをページウォーク(page walk)と呼びます。

2章の感覚で考えると、これは恐ろしい話です。1回のロードのたびに 4回の追加メモリアクセスをしていたら、性能は数分の1になります。当然、CPUはここにもキャッシュを置いています。

TLB — アドレス変換のキャッシュ

TLB(translation lookaside buffer)は、最近使った「仮想ページ→物理フレーム」の変換結果を覚えておく、 MMU専用のキャッシュです。規模の目安は次のとおりです(おおよそ)。

L1 TLB: 数十〜百数十エントリ
L2 TLB: 1500〜3000エントリ程度

ここで重要な計算をしてみます。3000エントリ × 4KBページ = 約12MB。つまりTLBが一度に覆えるメモリ範囲は10MB強しかありません。L3キャッシュより狭いのです。データがキャッシュに載っていても、変換がTLBに載っていない、という状況が普通に起きます。

実験で確かめます。256MBの領域に対して、同じ回数だけアクセスします。 (1)は64バイトおき(毎回別のキャッシュラインですが、ページは64回に 1回しか変わりません)。(2)は約4KBおき(毎回別のライン、かつ毎回別のページ)です。

use std::time::Instant;

fn main() {
    let size = 256 * 1024 * 1024;
    let buf = vec![1u8; size];
    let accesses = 4_000_000;

    let start = Instant::now();
    let mut sum = 0u64;
    let mut pos = 0usize;
    for _ in 0..accesses {
        sum = sum.wrapping_add(buf[pos] as u64);
        pos = (pos + 64) % size;
    }
    println!("64Bおき (ライン単位): {:>9.3?} (sum={sum})", start.elapsed());

    let start = Instant::now();
    let mut sum = 0u64;
    let mut pos = 0usize;
    for _ in 0..accesses {
        sum = sum.wrapping_add(buf[pos] as u64);
        pos = (pos + 4096 + 64) % size;
    }
    println!("4KBおき (ページ単位): {:>9.3?} (sum={sum})", start.elapsed());
}

筆者の実測(Playground)では、64バイトおきが約14ミリ秒、 4KBおきが約27ミリ秒。触れるキャッシュラインの数は同じなのに、ページを毎回跨ぐと1.9倍になりました。増えた分の主因が TLBミスとページウォークのコストです(厳密には、ストライドが広がるとハードウェアプリフェッチの効き方も変わるため、その影響も混ざっています。切り分けたい場合はLinuxの perf stat -e dTLB-load-missesでTLBミス数を直接数えられます)。

対策は2章と同じ結論に戻ります——局所性。データを小さく、近くにまとめることは、キャッシュだけでなくTLBにも効きます。そしてもう1つ、ページ自体を大きくする手があります。

hugepages — ページを大きくする

多くのCPUは4KBのほかに2MBや1GBのページ(hugepages)をサポートしています。仮に3000エントリを2MBページに使えれば約6GBを覆える計算です(大ページ用のTLB構成はCPUごとに異なるため、実際の値はもっと控えめになることもあります)。大量のメモリを走査するデータベースや科学計算では定番の設定です。

Linuxには、条件を満たしたメモリ領域を自動で2MBページにまとめるTHP(transparent huge pages)という仕組みがあり、 Rustプログラムも(何もしなくても)恩恵を受けることがあります。明示的に制御したい場合はmadviseシステムコールや hugepage対応アロケータを使いますが、断片化やレイテンシのばらつきという副作用もあるため、効果は計測で確認します。

「確保」しても何も起きない — デマンドページング

仮想メモリの最も劇的な性質がこれです。 新しく確保した大きな領域は、まだ物理メモリをほぼ消費していません。 OSはページテーブルに「ここは有効(ただし実体なし)」と記録するだけで、実際に物理フレーム(物理メモリのページ)を割り当てるのは 最初にアクセスされた瞬間です。これをデマンドページング (demand paging)と呼びます(正確には、Linuxでは読み出しだけなら共有の「ゼロページ」が見え、書き込みの瞬間に固有のフレームが割り当てられます。また、アロケータが再利用する既存領域には当てはまりません)。

実体のないページへのアクセスはCPUの例外として検出され、 OSが物理フレームを割り当ててから再実行されます。この一連の処理が ページフォールト(page fault)です(ディスクからの読み込みを伴わない軽量なものをminor fault、伴うものをmajor faultと呼びます)。

実験で見ます。4つの時間に注目してください。

use std::hint::black_box;
use std::time::Instant;

fn main() {
    let size = 128 * 1024 * 1024;

    let start = Instant::now();
    let mut zeroed = vec![0u8; size];
    println!("vec![0u8; 128MB] の確保    : {:>11.3?}", start.elapsed());

    let start = Instant::now();
    let ones = vec![1u8; size];
    black_box(&ones);
    println!("vec![1u8; 128MB] の確保    : {:>11.3?}", start.elapsed());
    drop(ones);

    let start = Instant::now();
    for i in (0..size).step_by(4096) {
        zeroed[i] = 1;
    }
    black_box(&zeroed);
    println!("1回目の書き込み(4KiBおき)  : {:>10.3?}", start.elapsed());

    let start = Instant::now();
    for i in (0..size).step_by(4096) {
        zeroed[i] = 2;
    }
    black_box(&zeroed);
    println!("2回目の書き込み(同じ場所)  : {:>10.3?}", start.elapsed());
}

筆者の実測(Playground)はこうでした。

vec![0u8; 128MB]の確保: 約6マイクロ秒 — 128MBが6µsで手に入るはずがありません。OSが「ゼロのページをあとで用意する」約束をしただけです(ゼロ初期化のVecはこの最適化に乗れるよう、 calloc相当の経路を使います)
vec![1u8; 128MB]の確保: 約75ミリ秒 — 1で埋めるには全ページに実際に書くしかなく、その瞬間に物理メモリが実体化します
ゼロ初期化バッファへの1回目の書き込み(4KiBおき): 約73ミリ秒 — 32,768ページ分のページフォールトの値段です(Playgroundのページは4KiB)
同じ場所への2回目の書き込み: 約0.3ミリ秒 — 220倍の差。これが「実体化済み」のメモリの本来の速度です

実務への含意を3つ挙げます。

起動直後は遅い。サーバの最初の数リクエストが遅い原因の 1つがこれです(ほかにキャッシュとJITのウォームアップ)
ベンチマークのウォームアップ(8章)にはページフォールトの償却も含まれています。criterionが最初の数回を捨てるのは正しい設計です
OSが報告するメモリ使用量に「仮想サイズ」と「実使用(RSS)」の 2つがあるのは、まさにこの区別です。また、dropで解放してもアロケータがOSに返すとは限らず、RSSはすぐには減りません

コピーオンライトとmmap

デマンドページングの親戚を2つ紹介します。

コピーオンライト(copy-on-write、COW)は「共有しておいて、書き込まれた瞬間に初めて複製する」技法です。Unixのforkが高速なのは、親子プロセスが物理メモリを共有し、書いたページだけ複製されるからです。Rust標準ライブラリのCow型や Arc::make_mutは、同じ発想をユーザー空間のデータ構造に適用したものと言えます。

mmap(memory map)は、ファイルを仮想アドレス空間に貼り付けるシステムコールです。「読んだページだけがディスクから供給される」デマンドページングの応用で、巨大ファイルの一部だけを触る用途に向きます。通常のread系I/Oとの使い分けは27章で実測します。

まとめ

プログラムが見るアドレスは仮想アドレスで、ページ(4KB等)単位の変換表(ページテーブル)で物理アドレスに変換されます
変換のキャッシュがTLBです。覆える範囲は4KBページで10MB程度と狭く、ページを跨ぎまくるアクセスは実測で1.9倍遅くなりました。対策は局所性とhugepagesです
メモリの確保は約束にすぎず、物理メモリは初回アクセス時のページフォールトで実体化します(実測: 初回は220倍遅い)
COWとmmapは「遅延と共有」という仮想メモリの思想の応用です

次章はキャッシュに戻り、今度はその内部構造——結合性、セット競合、そしてキャッシュブロッキングという技法——を開きます。「なぜこのストライドのときだけ異常に遅いのか」という 2章では説明できなかった現象に答えが付きます。