メモリ階層

「メモリは速いが小さく、ストレージは大きいが遅い」--- この制約がコンピュータアーキテクチャの全てを支配する。

この章で学ぶこと

• メモリ階層の各レベルの特性（速度・容量・コスト）を体系的に説明できる
• キャッシュのマッピング方式・置換アルゴリズム・書き込みポリシーを理解する
• 局所性の原理を活かしたキャッシュフレンドリーなプログラミングを実践できる
• 仮想メモリ・ページング・TLBの動作原理を説明できる
• NUMA・Huge Pages・メモリプロファイリングの実務知識を習得する
• ストレージ階層（SSD/HDD）の内部構造とアクセス特性を理解する

前提知識

• 2進数の基本的な理解（ビット、バイト、アドレス表現）
• C言語またはPythonの基礎的な読解力

1. メモリ階層ピラミッド

1.1 全体像

コンピュータのメモリシステムは、速度・容量・コストのトレードオフに基づく階層構造で構成される。上位に行くほど高速・小容量・高コスト、下位に行くほど低速・大容量・低コストとなる。この設計は、プログラムが示す「局所性」の性質を活用し、少量の高速メモリで大容量のメモリシステムを「見かけ上」高速に動作させるためのものである。

メモリ階層ピラミッド（2025年時点の代表的なスペック）:

  速い・高い・小さい
  ▲
  │  ┌─────────────────┐
  │  │   レジスタ        │ ← ~0.3ns, ~1KB, CPU内部
  │  │   (Register)      │    整数用16本(x86-64) + SIMD用
  │  ├─────────────────┤
  │  │  L1キャッシュ      │ ← ~1ns (3-4 cycles), 64KB×2
  │  │  (L1i/L1d)        │    命令キャッシュとデータキャッシュに分離
  │  ├─────────────────┤
  │  │  L2キャッシュ      │ ← ~3-10ns (10-20 cycles), 256KB-2MB
  │  │  (L2 Unified)     │    コアごとに専用
  │  ├─────────────────┤
  │  │  L3キャッシュ      │ ← ~10-30ns (30-70 cycles), 8-96MB
  │  │  (L3/LLC)         │    全コア共有、インクルーシブまたは非インクルーシブ
  │  ├─────────────────┤
  │  │  メインメモリ      │ ← ~50-100ns, 8-256GB, DDR5-5600等
  │  │  (DRAM/RAM)       │    揮発性、ランダムアクセス可能
  │  ├─────────────────┤
  │  │  NVMe SSD         │ ← ~10-100μs, 256GB-8TB
  │  │  (Flash NAND)     │    不揮発性、ブロック単位でアクセス
  │  ├─────────────────┤
  │  │  SATA SSD / HDD   │ ← ~50μs-10ms, 256GB-20TB
  │  │                    │    HDDは機械的シーク遅延が支配的
  │  ├─────────────────┤
  │  │  テープ / クラウド  │ ← ~秒-分, PB級, アーカイブ用途
  │  │  (Cold Storage)    │    最低コスト、オフラインアクセス
  │  └─────────────────┘
  ▼
  遅い・安い・大きい

この階層構造がなぜ「うまくいく」のかを理解するために、次の直感的な比喩を考えてみよう。自宅のデスクで仕事をしている場面を想像する。

• レジスタ = 手に持っている書類（即座にアクセスできるが、同時に持てる枚数は限られる）
• L1キャッシュ = デスクの上の書類（手を伸ばせばすぐ取れる）
• L2キャッシュ = デスクの引き出し（少し探す必要があるが、すぐ見つかる）
• L3キャッシュ = 同じ部屋の本棚（立ち上がって取りに行く必要がある）
• DRAM = 隣の部屋の書庫（歩いて取りに行く）
• SSD = 同じ建物内の資料室（エレベーターで移動する必要がある）
• HDD = 隣の建物の倉庫（外に出て移動する必要がある）
• テープ = 別の都市にある倉庫（郵送で取り寄せる）

1.2 レイテンシ比較（Jeff Dean の数値 --- 2025年改訂版）

重要な洞察: メインメモリ（DRAM）はL1キャッシュの約100倍遅い。HDDに至ってはL1の約200万倍遅い。この巨大な速度差こそが、メモリ階層設計の根本的な動機である。

1.3 帯域幅（Bandwidth）の比較

レイテンシ（1回のアクセスにかかる時間）とともに、帯域幅（単位時間あたりに転送できるデータ量）も重要な性能指標である。

1.4 なぜ階層構造が「経済的」なのか

仮に全てのメモリをL1キャッシュ相当のSRAMで構成しようとすると、128GBのメモリシステムは数十万ドルのコストになる。一方、階層構造を採用することで、わずかな量のSRAM（数十MB）と大量の安価なDRAM（数十GB）の組み合わせにより、コストを数百ドルに抑えつつ、ほとんどのアクセスをキャッシュで高速に処理できる。

これが成立するのは、プログラムの挙動が「局所的」であるためだ。典型的なプログラムでは、全アドレス空間のうち、ある短い時間に実際にアクセスされるのはごく一部（ワーキングセット）であり、そのワーキングセットがキャッシュに収まっている限り、システム全体はキャッシュの速度で動作しているように見える。

2. レジスタとSRAM

2.1 レジスタ --- CPUの最高速メモリ

レジスタはCPU内部に直接組み込まれた最小・最速の記憶素子である。ALU（算術論理演算装置）と直接接続されており、ワイヤ遅延なしでデータの読み書きが可能である。

x86-64アーキテクチャの主要レジスタ構成:

汎用レジスタ（64ビット × 16本）:

合計容量: 汎用16×8B=128B + SIMD(AVX-512) 32×64B=2048B + 特殊 ≈ 数KB

ARM (AArch64) アーキテクチャとの比較:

2.2 SRAM vs DRAM --- 2つのメモリ技術

キャッシュに使用されるSRAM（Static RAM）とメインメモリに使用されるDRAM（Dynamic RAM）は、根本的に異なるセル構造を持つ。

SRAMセル（6トランジスタ構成）:

- 6個のトランジスタで1ビットを保持
- 電源が供給される限りデータは安定
- リフレッシュ不要 → 高速アクセス可能
- セルサイズが大きい → 容量あたりのコストが高い

DRAMセル（1トランジスタ + 1キャパシタ）:

- 1トランジスタ+1キャパシタで1ビット
- キャパシタの電荷は時間とともに漏れる
- 定期的なリフレッシュが必要（~64ms周期）
- セルサイズが小さい → 大容量化が容易

SRAMとDRAMの比較表:

3. キャッシュの仕組み

3.1 なぜキャッシュが必要か --- メモリウォール問題

CPUの処理速度とメモリの応答速度の間には、年を追うごとに広がる深刻なギャップが存在する。これを「メモリウォール問題」(Memory Wall Problem) と呼ぶ。

CPUとメモリの速度ギャップ（メモリウォール問題）:

  相対性能
  │
  │   CPU性能         ／
  │              ／
  │          ／        ← 年 ~50-60% 向上（ムーアの法則時代）
  │        ／              2010年代以降は鈍化、~20%/年
  │      ／
  │    ／
  │  ／     ←──── このギャップが「メモリウォール」
  │／
  │─ ─ ─ ─ ─ ─ ─ メモリ帯域
  │──────────────── メモリレイテンシ ← 年 ~7% 改善
  │
  └──────────────────────────────────────── 年
   1980        1990        2000        2010        2025

  1980年: CPU 1サイクル ≈ メモリ 1サイクル
  2000年: CPU 1サイクル ≈ メモリ 100サイクル
  2025年: CPU 1サイクル ≈ メモリ 200-300サイクル

  → キャッシュなしではCPUが99%以上の時間をメモリ待ちに費やす

この問題の本質は、DRAMのレイテンシ改善がCPU速度の向上に追いついていないことにある。DRAMの帯域幅は比較的改善されているが（DDR5は DDR4比で約2倍）、レイテンシの改善は微小である。キャッシュは、この速度ギャップを「局所性」を利用して隠蔽するための仕組みである。

3.2 キャッシュの基本動作

キャッシュは、メインメモリの部分的なコピーを高速なSRAMに保持する仕組みである。CPUがメモリアドレスにアクセスする際、まずキャッシュを確認し、データが存在すれば（キャッシュヒット）高速に取得し、存在しなければ（キャッシュミス）下位の階層からデータを取得してキャッシュに格納する。

キャッシュの基本動作フロー:

  CPU がアドレス A のデータを要求
  │
  ▼
  L1 キャッシュを検索
  │
  ├── ヒット → データを CPU に返す（~1ns）
  │              ★ 最も高速なパス
  │
  └── ミス → L2 キャッシュを検索
              │
              ├── ヒット → データを L1 に格納し CPU に返す（~4ns）
              │
              └── ミス → L3 キャッシュを検索
                          │
                          ├── ヒット → データを L2, L1 に格納し返す（~12ns）
                          │
                          └── ミス → DRAM にアクセス
                                      │
                                      └── データを L3, L2, L1 に格納し返す（~100ns）
                                           ★ L1 の約100倍のペナルティ

3.3 キャッシュライン --- データ転送の最小単位

キャッシュとメモリ間のデータ転送は、1バイト単位ではなく、「キャッシュライン」と呼ばれる固定サイズのブロック（通常64バイト）単位で行われる。

キャッシュラインの構造（64バイトの場合）:

  1本のキャッシュライン:

メモリアドレスの分解（64バイトライン、256セットの8-Wayキャッシュの場合）:

│           │
                         │           └─ キャッシュライン内のバイト位置
                         │              (64バイト = 2^6 → 6ビット)
                         │
                         └─ どのセットに格納するか
                            (256セット = 2^8 → 8ビット)

  例: int 配列 a[16] がメモリ上で連続している場合

|←────────── 1キャッシュライン (64B) ──────────→|←────── 次のキャッシュライン ──→|
  int は 4 バイトなので、1キャッシュラインに 16 個の int が格納される
  → a[0] にアクセスすると a[0]~a[15] が一度にキャッシュに読み込まれる
  → 以降の a[1]~a[15] へのアクセスは全てキャッシュヒット

3.4 キャッシュのマッピング方式

メモリアドレスをキャッシュのどの位置に格納するかを決定する方式には、以下の3種類がある。

3つのキャッシュマッピング方式:

1. ダイレクトマップ（Direct-Mapped）:
   各メモリアドレスが格納できるキャッシュラインは1箇所のみ

   メモリブロック:  0  1  2  3  4  5  6  7  8  9 10 11
   キャッシュライン: ┌──┐
                    │ 0│ ← ブロック 0, 4, 8, ... が格納される
                    │ 1│ ← ブロック 1, 5, 9, ...
                    │ 2│ ← ブロック 2, 6, 10, ...
                    │ 3│ ← ブロック 3, 7, 11, ...
                    └──┘
   格納先 = ブロック番号 mod キャッシュライン数

   長所: インデックス計算が単純で高速、ハードウェアが小さい
   短所: 衝突ミスが多い（例: ブロック0と4が交互にアクセスされると
         毎回キャッシュミスが発生 = スラッシング）

2. フルアソシアティブ（Fully Associative）:
   任意のメモリブロックをキャッシュの任意の位置に格納可能

   キャッシュライン: ┌──┐
                    │  │ ← どのブロックでも格納可能
                    │  │ ← どのブロックでも格納可能
                    │  │ ← どのブロックでも格納可能
                    │  │ ← どのブロックでも格納可能
                    └──┘
   長所: 衝突ミスが発生しない
   短所: 全ラインのタグを同時に比較する必要がある
         → 回路面積・消費電力が大きく、大容量キャッシュでは非現実的
   用途: TLB（エントリ数が少ない）、一部の小容量キャッシュ

3. セットアソシアティブ（Set-Associative）: ★ 現代CPUの標準
   キャッシュを複数のセットに分割し、各セットに N 本のライン（Way）を持つ
   格納先のセットはアドレスで決定、セット内のどのWayに入れるかは自由

   8-Way Set-Associative の例:

格納先セット = ブロック番号 mod セット数
   セット内のどのWayに格納するかは置換ポリシー（LRU等）で決定

   長所: ダイレクトマップの速さとフルアソシアティブの柔軟性のバランス
   現代CPUの典型値:
     L1: 8-Way, 64セット (64×8×64B = 32KB)
     L2: 4-8-Way
     L3: 12-16-Way

3.5 キャッシュの置換ポリシー

キャッシュが満杯のとき、新しいデータを格納するためにどのラインを追い出すかを決定するアルゴリズムが「置換ポリシー」である。

3.6 キャッシュの書き込みポリシー

データを書き込む際のメインメモリとの整合性の取り方には2つのポリシーがある。

書き込みポリシー:

1. ライトスルー（Write-Through）:
   書き込み時に、キャッシュとメインメモリの両方に即座に反映

   CPU → Write → [L1 Cache] → 同時に → [DRAM]
                  (更新)                  (更新)

   長所: メモリとキャッシュが常に一致（整合性が保証される）
   短所: 書き込みのたびにメモリアクセスが発生（遅い）
   対策: ライトバッファ（Write Buffer）で書き込みを一時的にバッファリング

2. ライトバック（Write-Back）: ★ 現代CPUの主流
   書き込み時にキャッシュのみ更新し、追い出し時にメインメモリに反映

   CPU → Write → [L1 Cache] (Dirty bit = 1 に設定)
                  (更新)

   追い出し時:
   [L1 Cache] (Dirty bit == 1) → [DRAM] に書き戻し

   長所: 書き込み頻度が高い場合にメモリアクセスを大幅に削減
   短所: キャッシュとメモリの内容が一時的に不一致になる
         マルチコアでのキャッシュコヒーレンシが複雑

3.7 キャッシュコヒーレンシ --- マルチコア時代の課題

マルチコアプロセッサでは、各コアが独自のL1/L2キャッシュを持つため、同一メモリアドレスのデータが複数のキャッシュに異なる値で存在する可能性がある。この問題を「キャッシュコヒーレンシ問題」と呼ぶ。

キャッシュコヒーレンシ問題の例:

  Core 0                    Core 1

│                         │
       │  Core 0 が X = 100 に更新
       │  ┌──────────┐
       │  │ X = 100  │ ← Core 0 のキャッシュは更新済み
       │  └──────────┘
       │                    ┌──────────┐
       │                    │ X = 42   │ ← Core 1 は古い値を保持！
       │                    └──────────┘
       │                         │
       └────────┬────────────────┘
                │

  ┌─────────────────────────┐
  │ メインメモリ: X = 42     │ ← ライトバックなのでまだ古い値
  └─────────────────────────┘

→ Core 1 が X を読むと 42（古い値）が返る = データ不整合！

この問題を解決するために、MESIプロトコル（およびその拡張版）が使用される。

MESIプロトコルでは、あるコアがShared状態のデータを書き換える際、他の全コアの該当キャッシュラインをInvalidに変更する（インバリデーション）。これにより整合性が保たれるが、マルチコア環境でのバス通信（スヌーピング）のオーバーヘッドが発生する。

False Sharing（偽の共有）: 異なるコアが「異なる変数」にアクセスしていても、それらが同じキャッシュラインに乗っている場合、MESIプロトコルによる不要なインバリデーションが発生し、性能が大幅に低下する。これはマルチスレッドプログラミングにおける重要なアンチパターンである（後述のアンチパターンセクションで詳述）。

4. 局所性の原理

4.1 概要

メモリ階層が効率的に機能する理由は、プログラムのメモリアクセスパターンが「局所的」であることに依存している。この性質を「局所性の原理」(Principle of Locality) と呼ぶ。局所性には2つの形態がある。

4.2 時間的局所性（Temporal Locality）

「最近アクセスしたデータは、近い将来また使われる可能性が高い」

# 時間的局所性の例: ループカウンタと累算変数
def compute_sum(data: list[int]) -> int:
    total = 0                      # total: 非常に高い時間的局所性
    count = 0                      # count: 非常に高い時間的局所性
    for i in range(len(data)):     # i: 高い時間的局所性
        total += data[i]
        count += 1
    return total // count if count > 0 else 0
    # total, count, i はループの全反復で繰り返しアクセスされる
    # → コンパイラはこれらをレジスタに割り当てる（レジスタ割り当て最適化）
    # → レジスタに収まらない場合でも L1 キャッシュに保持される

時間的局所性が高いデータの例:

• ループカウンタ、累算変数
• 頻繁に呼ばれる関数のコード
• グローバル変数、頻繁にアクセスされるデータ構造のルートノード

4.3 空間的局所性（Spatial Locality）

「あるアドレスにアクセスしたら、近くのアドレスも近い将来使われる可能性が高い」

# 空間的局所性の例: 配列の連続アクセス
def process_image(pixels: list[int], width: int, height: int) -> None:
    # 行優先で連続アクセス → 高い空間的局所性
    for y in range(height):
        for x in range(width):
            pixels[y * width + x] = transform(pixels[y * width + x])
    # pixels[0], pixels[1], pixels[2], ... はメモリ上で連続
    # → 1回のキャッシュラインロード（64B）で int 16個分をカバー
    # → キャッシュミス率 = 1/16 = 6.25%（理論値）

空間的局所性が高いアクセスパターンの例:

• 配列の順次走査
• 構造体のフィールドアクセス（フィールドはメモリ上で連続）
• 命令の逐次実行（プログラムカウンタのインクリメント）

4.4 キャッシュミスの3C分類

キャッシュミスは発生原因に基づいて3つに分類される（3C分類: Compulsory, Capacity, Conflict）。

4.5 局所性を定量的に理解するコード例

/* 行優先 vs 列優先アクセスによるキャッシュミス率の違い */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define N 4096  /* 4096 x 4096 = 16M 要素, 64MB (int) */
 
int matrix[N][N];
 
/* 行優先アクセス（空間的局所性あり） */
long long sum_row_major(void) {
    long long sum = 0;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            sum += matrix[i][j];   /* matrix[i][0], [i][1], [i][2]... は連続 */
    return sum;                     /* キャッシュミス率: ~1/16 = 6.25% */
}
 
/* 列優先アクセス（空間的局所性なし） */
long long sum_col_major(void) {
    long long sum = 0;
    for (int j = 0; j < N; j++)
        for (int i = 0; i < N; i++)
            sum += matrix[i][j];   /* matrix[0][j], [1][j], [2][j]... はストライド N */
    return sum;                     /* キャッシュミス率: ~100%（Nが大きい場合） */
}
 
int main(void) {
    /* 配列を初期化 */
    srand(42);
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            matrix[i][j] = rand() % 100;
 
    clock_t start, end;
 
    start = clock();
    long long s1 = sum_row_major();
    end = clock();
    printf("Row-major: sum=%lld, time=%.3fs\n",
           s1, (double)(end - start) / CLOCKS_PER_SEC);
 
    start = clock();
    long long s2 = sum_col_major();
    end = clock();
    printf("Col-major: sum=%lld, time=%.3fs\n",
           s2, (double)(end - start) / CLOCKS_PER_SEC);
 
    /* 典型的な結果:
     * Row-major: ~0.05s
     * Col-major: ~0.30s (6倍遅い)
     * N が大きくなるほど差が広がる（L3キャッシュを超えるため）
     */
    return 0;
}

5. 仮想メモリ

5.1 概要と目的

仮想メモリは、各プロセスに独立した連続アドレス空間を提供し、物理メモリの効率的な管理とプロセス間の保護を実現するOS/ハードウェア協調の仕組みである。

仮想メモリの3つの主要な目的:

1. 抽象化: 各プロセスは自分だけの広大な連続アドレス空間を持っているかのように振る舞える
2. 保護: あるプロセスが別のプロセスのメモリを読み書きすることを防ぐ
3. 効率化: 物理メモリの断片化を隠蔽し、実際に使用しているページのみに物理メモリを割り当てる

仮想メモリの概念図:

  プロセスA の仮想アドレス空間         物理メモリ (RAM)

│                    │
  プロセスB の仮想アドレス空間         │                    │

│
  両プロセスとも同じ仮想アドレス              │
  (0x0000_0000) を使うが、                    ▼
  物理的には異なるフレームにマッピング    ┌──────────┐
                                          │ SSD/HDD  │
  物理メモリが不足 → ページアウト ────→   │ (Swap)   │
                                          └──────────┘

5.2 ページングの仕組み

仮想アドレス空間と物理メモリは、ともに「ページ」と呼ばれる固定サイズのブロック（通常4KB）に分割される。仮想ページを物理フレーム（物理ページ）に対応付ける情報を保持するのが「ページテーブル」である。

x86-64 の 4段階ページテーブル:

仮想アドレス（48ビット有効）:

│         │         │         │
     ▼         ▼         ▼         ▼

各テーブル: 512エントリ × 8バイト = 4KB (1ページに収まる)
  仮想アドレス空間: 2^48 = 256TB
  物理ページサイズ: 4KB (2^12)

  ページテーブルウォークのコスト:
  最大4回のメモリアクセスが必要 = 4 × 100ns = 400ns
  → これでは遅すぎるため TLB で高速化する

5.3 TLB（Translation Lookaside Buffer）

TLBは、仮想ページ番号(VPN)から物理フレーム番号(PFN)への変換結果をキャッシュする、専用の高速連想メモリである。

アドレス変換の仕組み:

  仮想アドレス

│
         ▼

│ TLBヒット                        │
         ▼                                  ▼
  物理アドレス

TLBヒットのコスト: ~1ns（パイプラインに統合）
  TLBミスのコスト: ~10-100ns（ページテーブルウォーク）
  ページフォルトのコスト: ~1ms (SSD) / ~10ms (HDD)

  TLBカバレッジ = TLBエントリ数 × ページサイズ
  例: 1024エントリ × 4KB = 4MB
  例: 1024エントリ × 2MB(Huge Pages) = 2GB ← 大幅に改善

5.4 ページフォルト

ページフォルトは、仮想ページに対応する物理フレームが存在しない場合に発生する例外（ハードウェア割り込み）である。

ページフォルトの処理フロー:

  1. CPU が仮想アドレス VA にアクセス
  2. TLB ミス → ページテーブルウォーク
  3. ページテーブルエントリの Present ビット = 0
  4. ★ ページフォルト例外が発生
  5. CPU は現在の命令実行を中断し、OS のページフォルトハンドラに制御を移す
  6. OS は以下を判定:
     ├── 不正アクセス（セグメンテーション違反）
     │   → SIGSEGV を送信してプロセスを終了
     │
     ├── デマンドページング（初回アクセス）
     │   → 新しい物理フレームを割り当て、ゼロクリアして返す
     │
     ├── ページがスワップアウトされている
     │   → ディスクからページを読み込む（~1ms SSD / ~10ms HDD）
     │
     └── Copy-on-Write (CoW)
         → ページをコピーして書き込み可能にする
  7. ページテーブルを更新（Present=1, PFN を設定）
  8. TLB に新しいエントリを追加
  9. 中断した命令を再実行

  コスト分析:
  - マイナーページフォルト（ディスクI/Oなし）: ~1-10μs
  - メジャーページフォルト（ディスクI/Oあり）: ~1ms (SSD) / ~10ms (HDD)
  → メジャーページフォルトは通常のメモリアクセスの 10,000~100,000 倍遅い
  → 頻繁なページフォルト（スラッシング）はシステムを実質的に停止させる

5.5 ページ置換アルゴリズム

物理メモリが満杯のとき、新しいページを読み込むためにどのページをスワップアウトするかを決定するのがページ置換アルゴリズムである。

6. ストレージ階層: SSD と HDD

6.1 HDD（Hard Disk Drive）の構造と特性

HDDは磁気ディスク上にデータを記録する機械式ストレージデバイスである。

HDDの内部構造:

アクセス時間の構成:

7200rpm HDD の場合:
  - 平均シーク時間: ~4-8ms
  - 平均回転待ち: 1/(7200/60)/2 = ~4.17ms
  - 平均アクセス時間: ~8-12ms
  - 連続読み出し帯域: 100-250MB/s
  - ランダム4KB読み出し: ~100 IOPS

6.2 SSD（Solid State Drive）の構造と特性

SSDはNANDフラッシュメモリを使用した半導体ストレージデバイスである。可動部品がないため、HDDに比べてランダムアクセスが桁違いに速い。

SSDの内部アーキテクチャ:

NANDフラッシュの特性:
  - 読み出し: ページ単位（4-16KB）
  - 書き込み: ページ単位（4-16KB）
  - 消去: ブロック単位（256KB-数MB） ★ 読み書きより大きい単位
  - 消去回数に上限あり（TLC: ~1000-3000回、QLC: ~100-1000回）

  Write Amplification (書き込み増幅):
  - 4KB の論理書き込みに対して、ブロック消去+再書き込みで
    256KB 以上の物理書き込みが発生する可能性
  - FTL（Flash Translation Layer）がこれを最小化する

SSD vs HDD 比較表:

7. NUMA（Non-Uniform Memory Access）

7.1 NUMAアーキテクチャの概要

マルチソケットサーバーでは、各CPUソケットが自身の「ローカルメモリ」を持ち、他のソケットのメモリへのアクセス（リモートアクセス）はインターコネクト経由で行われるため遅延が増加する。このような非均一なメモリアクセス特性を持つアーキテクチャをNUMAと呼ぶ。

NUMAアーキテクチャ（2ソケットサーバーの例）:

│      UPI / CXL リンク         │
             └───────────────────────────────┘
                リモートアクセス: ~130-160ns
                (ローカルの約1.5-2倍の遅延)

7.2 NUMA対応のプログラミング

/* Linux での NUMA-aware メモリ割り当て */
#include <numa.h>
#include <numaif.h>
 
void numa_aware_allocation(void) {
    /* NUMA が利用可能か確認 */
    if (numa_available() < 0) {
        fprintf(stderr, "NUMA is not available\n");
        return;
    }
 
    /* ノード数を確認 */
    int num_nodes = numa_max_node() + 1;
    printf("NUMA nodes: %d\n", num_nodes);
 
    /* 特定のNUMAノードにメモリを割り当て */
    size_t size = 1024 * 1024 * 1024;  /* 1GB */
    void *local_mem = numa_alloc_onnode(size, 0);  /* ノード0に割り当て */
 
    /* このスレッドをノード0のCPUにバインド */
    struct bitmask *cpumask = numa_allocate_cpumask();
    numa_node_to_cpus(0, cpumask);
    numa_sched_setaffinity(0, cpumask);
 
    /* local_mem へのアクセスはローカル速度（~80ns） */
    memset(local_mem, 0, size);
 
    numa_free(local_mem, size);
    numa_free_cpumask(cpumask);
}

8. Huge Pages とメモリ管理の実践

8.1 Huge Pages の必要性

通常の4KBページでは、大容量メモリをカバーするために膨大な数のTLBエントリが必要になる。Huge Pages（2MBまたは1GB）を使用することで、同じTLBエントリ数でより広いメモリ範囲をカバーできる。

TLBカバレッジの比較:

  通常ページ（4KB）の場合:
  TLBエントリ 1024個 × 4KB = 4MB のカバレッジ
  → 64GBのメモリ空間に対して TLBミス率が高い

  Huge Pages（2MB）の場合:
  TLBエントリ 1024個 × 2MB = 2GB のカバレッジ
  → 64GBのメモリ空間でも TLBミス率が大幅に低下

  Huge Pages（1GB）の場合:
  TLBエントリ 4個 × 1GB = 4GB のカバレッジ
  → データベースやHPCワークロードに最適

8.2 Linux での Huge Pages 設定

# Transparent Huge Pages (THP) の状態確認
cat /sys/kernel/mm/transparent_hugepage/enabled
# [always] madvise never
 
# 明示的な Huge Pages の予約（2MB × 1024 = 2GB）
echo 1024 > /proc/sys/vm/nr_hugepages
 
# Huge Pages の使用状況確認
cat /proc/meminfo | grep -i huge
# HugePages_Total:    1024
# HugePages_Free:     1024
# HugePages_Rsvd:        0
# HugePages_Surp:        0
# Hugepagesize:       2048 kB

/* C言語での Huge Pages 利用例 */
#include <sys/mman.h>
#include <stdio.h>
 
int main(void) {
    size_t huge_page_size = 2 * 1024 * 1024;  /* 2MB */
    size_t alloc_size = 256 * huge_page_size;   /* 512MB */
 
    /* MAP_HUGETLB で Huge Pages を要求 */
    void *ptr = mmap(NULL, alloc_size,
                     PROT_READ | PROT_WRITE,
                     MAP_PRIVATE | MAP_ANONYMOUS | MAP_HUGETLB,
                     -1, 0);
 
    if (ptr == MAP_FAILED) {
        perror("mmap with MAP_HUGETLB failed");
        /* フォールバック: 通常のページで割り当て */
        ptr = mmap(NULL, alloc_size,
                   PROT_READ | PROT_WRITE,
                   MAP_PRIVATE | MAP_ANONYMOUS,
                   -1, 0);
        if (ptr == MAP_FAILED) {
            perror("mmap fallback failed");
            return 1;
        }
        /* madvise で THP を要求 */
        madvise(ptr, alloc_size, MADV_HUGEPAGE);
    }
 
    printf("Allocated %zu MB with Huge Pages\n", alloc_size / (1024 * 1024));
 
    /* 使用 */
    memset(ptr, 0, alloc_size);
 
    munmap(ptr, alloc_size);
    return 0;
}

9. キャッシュフレンドリーなプログラミング

9.1 データ構造のレイアウト: AoS vs SoA

データ構造のメモリレイアウトは、キャッシュ効率に決定的な影響を与える。「必要なデータだけがキャッシュラインに乗る」レイアウトを選択することが重要である。

/*
 * AoS (Array of Structures) vs SoA (Structure of Arrays)
 * ゲームエンジンにおけるパーティクルシステムの例
 */
 
/* ===== AoS: Array of Structures ===== */
struct ParticleAoS {
    float x, y, z;        /* 位置: 12バイト（よく使う） */
    float vx, vy, vz;     /* 速度: 12バイト（よく使う） */
    float r, g, b, a;     /* 色:   16バイト（描画時のみ） */
    float lifetime;        /* 寿命: 4バイト（たまに使う） */
    int   texture_id;      /* テクスチャ: 4バイト（描画時のみ） */
    char  name[16];        /* 名前: 16バイト（デバッグ時のみ） */
};  /* 合計: 64バイト = ちょうど1キャッシュライン */
 
struct ParticleAoS particles_aos[100000];
 
/* 位置の更新処理: */
void update_positions_aos(int n, float dt) {
    for (int i = 0; i < n; i++) {
        particles_aos[i].x += particles_aos[i].vx * dt;
        particles_aos[i].y += particles_aos[i].vy * dt;
        particles_aos[i].z += particles_aos[i].vz * dt;
    }
    /* 問題: 各パーティクルが64バイト。位置と速度の更新に必要なのは
     * x,y,z,vx,vy,vz の 24バイトだけなのに、name や texture_id など
     * 不要な40バイトもキャッシュラインに乗ってしまう。
     * → キャッシュの利用効率: 24/64 = 37.5%
     */
}
 
/* ===== SoA: Structure of Arrays ===== */
struct ParticleSystemSoA {
    float *x,  *y,  *z;       /* 位置 */
    float *vx, *vy, *vz;      /* 速度 */
    float *r,  *g,  *b, *a;   /* 色 */
    float *lifetime;           /* 寿命 */
    int   *texture_id;         /* テクスチャ */
    /* name は別途管理 */
};
 
struct ParticleSystemSoA psys;
 
/* 位置の更新処理: */
void update_positions_soa(int n, float dt) {
    for (int i = 0; i < n; i++) {
        psys.x[i] += psys.vx[i] * dt;
        psys.y[i] += psys.vy[i] * dt;
        psys.z[i] += psys.vz[i] * dt;
    }
    /* 利点: x[], vx[] は連続メモリ。キャッシュラインに float 16個が乗る。
     * 不要な color, name, texture_id はキャッシュに乗らない。
     * → キャッシュの利用効率: ほぼ100%
     * → SIMD (AVX2/AVX-512) でベクトル化も容易
     */
}

9.2 ループのブロッキング（タイリング）

大規模な行列演算では、ナイーブな実装ではキャッシュに収まらないストライドアクセスが発生する。ブロッキング（タイリング）は、データをキャッシュに収まるサイズのブロックに分割して処理する手法である。

/*
 * 行列乗算 C = A × B のキャッシュ最適化
 * N×N 行列（float、Row-Major格納）
 */
 
/* ===== ナイーブ実装（キャッシュミス多発） ===== */
void matmul_naive(int N, float *A, float *B, float *C) {
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) {
            float sum = 0.0f;
            for (int k = 0; k < N; k++)
                sum += A[i*N + k] * B[k*N + j];
                /*     ^^^^^^^^^^   ^^^^^^^^^^
                 *     行方向:OK    列方向:NG!
                 *
                 * A[i*N+k]: k が1増えると隣のfloat → 空間的局所性あり
                 * B[k*N+j]: k が1増えると N 個先のfloat → ストライドアクセス
                 *   N=1024 の場合、ストライド = 4096バイト = 64キャッシュライン分
                 *   → B へのアクセスはほぼ毎回キャッシュミス
                 */
            C[i*N + j] = sum;
        }
}
 
/* ===== ブロッキング（タイリング）実装 ===== */
void matmul_blocked(int N, float *A, float *B, float *C) {
    /* ブロックサイズ: L1キャッシュ（32KB）に3つのブロックが収まるサイズ
     * BLOCK^2 × 4bytes × 3行列 ≤ 32KB
     * BLOCK ≈ sqrt(32768 / 12) ≈ 52 → 64に丸める */
    int BLOCK = 64;
 
    for (int ii = 0; ii < N; ii += BLOCK)
        for (int jj = 0; jj < N; jj += BLOCK)
            for (int kk = 0; kk < N; kk += BLOCK)
                /* 内側ループ: BLOCK×BLOCK のサブ行列同士の乗算
                 * A, B, C の各サブブロックがL1キャッシュに収まる */
                for (int i = ii; i < ii+BLOCK && i < N; i++)
                    for (int j = jj; j < jj+BLOCK && j < N; j++) {
                        float sum = C[i*N + j];
                        for (int k = kk; k < kk+BLOCK && k < N; k++)
                            sum += A[i*N+k] * B[k*N+j];
                        C[i*N + j] = sum;
                    }
    /* N=1024 での性能改善: ナイーブ比で 3-8 倍高速
     * N=4096 での性能改善: ナイーブ比で 5-15 倍高速
     * キャッシュミス率: ナイーブ ~25% → ブロッキング ~1-3%
     */
}

9.3 プリフェッチ

ハードウェアプリフェッチャーは、連続的なアクセスパターンを検出して事前にデータをキャッシュにロードする。しかし、不規則なアクセスパターンに対しては、明示的なソフトウェアプリフェッチが有効である。

/* ソフトウェアプリフェッチの例 */
#include <immintrin.h>  /* _mm_prefetch */
 
/* リンクリストの走査にプリフェッチを適用 */
struct Node {
    int data;
    struct Node *next;
};
 
long long sum_list_prefetch(struct Node *head) {
    long long sum = 0;
    struct Node *curr = head;
    while (curr != NULL) {
        /* 2ノード先をプリフェッチ（レイテンシを隠蔽） */
        if (curr->next && curr->next->next) {
            _mm_prefetch((const char *)curr->next->next, _MM_HINT_T0);
        }
        sum += curr->data;
        curr = curr->next;
    }
    return sum;
    /* プリフェッチなし: ノードごとに ~100ns (DRAMレイテンシ)
     * プリフェッチあり: プリフェッチが間に合えば大幅に改善
     * ただし効果はノード間の距離とアクセスパターンに依存 */
}

9.4 データ構造のキャッシュ効率比較

プログラムで使用するデータ構造の選択は、キャッシュ性能に直接的な影響を与える。以下に主要なデータ構造のキャッシュ特性を比較する。

/*
 * キャッシュ効率を考慮したデータ構造選択の指針:
 *
 * 1. 順次アクセスが主 → 配列/vector を第一選択
 *    std::list は「ほぼ使わない」が現代のベストプラクティス
 *
 * 2. 検索が主 → ソート済み配列 + 二分探索 or ハッシュ(open addressing)
 *    std::map (赤黒木) はポインタ追跡でキャッシュ効率が悪い
 *
 * 3. ノードサイズ ≤ キャッシュラインサイズ (64B) に収める
 *    不要なフィールドは別構造体に分離する (Hot/Cold splitting)
 *
 * 4. メモリプールで同種オブジェクトを近接配置する
 *    malloc のフラグメンテーションによる局所性低下を防ぐ
 */

9.5 メモリアライメントとパディング

構造体のフィールド配置順序とアライメントは、キャッシュ効率とメモリ使用量に影響する。

/* 構造体のパディングによるメモリ浪費の例 */
 
/* 悪い配置: パディングが多い */
struct BadLayout {
    char   a;       /* 1バイト + 7バイトのパディング */
    double b;       /* 8バイト */
    char   c;       /* 1バイト + 3バイトのパディング */
    int    d;       /* 4バイト */
    char   e;       /* 1バイト + 7バイトのパディング */
    double f;       /* 8バイト */
};
/* sizeof(BadLayout) = 40バイト（実データは23バイト、パディング17バイト） */
 
/* 良い配置: サイズの大きい順に並べる */
struct GoodLayout {
    double b;       /* 8バイト */
    double f;       /* 8バイト */
    int    d;       /* 4バイト */
    char   a;       /* 1バイト */
    char   c;       /* 1バイト */
    char   e;       /* 1バイト + 1バイトのパディング */
};
/* sizeof(GoodLayout) = 24バイト（実データは23バイト、パディング1バイト） */
 
/*
 * 10万個の構造体配列の場合:
 * BadLayout:  40 × 100,000 = 4,000,000バイト (3.81MB)
 * GoodLayout: 24 × 100,000 = 2,400,000バイト (2.29MB)
 * → 40%のメモリ節約 + キャッシュラインに多くの要素が乗る
 *
 * 確認方法:
 * gcc/clang: -Wpadded オプションでパディング警告を出力
 * pahole コマンド: 構造体のレイアウトを可視化
 */

9.6 ループ展開とキャッシュの相互作用

ループ展開（Loop Unrolling）はCPUパイプラインとキャッシュの両方に影響を与える最適化手法である。

/* ループ展開によるパイプライン効率改善の例 */
 
/* 展開なし */
float dot_product_basic(float *a, float *b, int n) {
    float sum = 0.0f;
    for (int i = 0; i < n; i++) {
        sum += a[i] * b[i];  /* 依存チェーン: sum の更新が毎回直列 */
    }
    return sum;
}
 
/* 4倍展開: 依存チェーンを4本に分割 */
float dot_product_unrolled(float *a, float *b, int n) {
    float sum0 = 0.0f, sum1 = 0.0f, sum2 = 0.0f, sum3 = 0.0f;
    int i;
    for (i = 0; i + 3 < n; i += 4) {
        sum0 += a[i]   * b[i];    /* 独立した4つの累積加算 */
        sum1 += a[i+1] * b[i+1];  /* → CPUが4つを並列実行可能 */
        sum2 += a[i+2] * b[i+2];
        sum3 += a[i+3] * b[i+3];
    }
    float sum = sum0 + sum1 + sum2 + sum3;
    for (; i < n; i++) sum += a[i] * b[i]; /* 残余ループ */
    return sum;
    /*
     * 効果:
     * 1. ループオーバーヘッド（分岐, カウンタ更新）を 1/4 に削減
     * 2. 4本の独立した依存チェーンによりパイプライン効率向上
     * 3. プリフェッチャーのストリーム検出がしやすくなる
     *
     * 注意: 現代のコンパイラ (-O2/-O3) は自動展開を行う
     *       手動展開はプロファイリング結果に基づいて判断する
     */
}

10. メモリアロケータとキャッシュ

10.1 標準アロケータ（malloc/free）の問題点

標準の malloc/free は汎用的なメモリアロケータだが、長時間稼働するプログラムではメモリのフラグメンテーションが進行し、空間的局所性が低下する。

mallocの一般的な動作とフラグメンテーション:

  時間が経つにつれてメモリがフラグメント化:

→ 関連するオブジェクトがメモリ上でバラバラに配置
  → 空間的局所性が低下 → キャッシュ効率が悪化

  対策: 用途別のメモリアロケータを使用する

10.2 アリーナアロケータ（プールアロケータ）

ゲームエンジンやデータベースエンジンでは、キャッシュ効率を高めるために専用のメモリアロケータを使用する。

/*
 * シンプルなアリーナアロケータの実装例
 * 同種のオブジェクトを連続メモリに配置し、空間的局所性を最大化する
 */
#include <stdlib.h>
#include <stdint.h>
 
typedef struct Arena {
    uint8_t *memory;     /* 確保済みメモリブロック */
    size_t   capacity;   /* 全体サイズ */
    size_t   offset;     /* 次の割り当て位置 */
} Arena;
 
Arena arena_create(size_t capacity) {
    Arena arena;
    arena.memory = (uint8_t *)aligned_alloc(64, capacity);
    arena.capacity = capacity;
    arena.offset = 0;
    return arena;
}
 
void *arena_alloc(Arena *arena, size_t size) {
    size_t aligned_size = (size + 7) & ~7;  /* 8バイト境界アライメント */
    if (arena->offset + aligned_size > arena->capacity) return NULL;
    void *ptr = arena->memory + arena->offset;
    arena->offset += aligned_size;
    return ptr;
}
 
void arena_reset(Arena *arena) {
    arena->offset = 0;  /* 全オブジェクトを一括解放 O(1) */
}
 
void arena_destroy(Arena *arena) {
    free(arena->memory);
}
 
/*
 * 利点:
 * 1. 連続メモリに配置 → 空間的局所性が最大化
 * 2. free が不要 → フラグメンテーションなし
 * 3. arena_reset で O(1) 一括解放
 *
 * 用途: ゲームのフレーム単位メモリ、パーサーのAST構築、
 *       Webサーバーのリクエスト単位メモリ管理
 */

11. メモリプロファイリングの実践

11.1 Linux perfによるキャッシュミスの計測

# キャッシュミスの統計情報を取得
perf stat -e cache-references,cache-misses,L1-dcache-loads,L1-dcache-load-misses \
         ./my_program
 
# 出力例:
#  1,234,567,890  cache-references
#     12,345,678  cache-misses       #  1.00% of all cache refs
#  5,678,901,234  L1-dcache-loads
#    567,890,123  L1-dcache-load-misses  # 10.00% of all L1-dcache loads
 
# キャッシュミスが発生するコード位置を特定
perf record -e cache-misses ./my_program
perf report

11.2 Valgrind (Cachegrind) によるシミュレーション

# Cachegrind でキャッシュ動作をシミュレーション
valgrind --tool=cachegrind ./my_program
 
# 出力例:
# ==12345== I   refs:      1,234,567,890
# ==12345== I1  misses:          123,456
# ==12345== LLi misses:           12,345
# ==12345== I1  miss rate:          0.01%
# ==12345== LLi miss rate:         0.00%
# ==12345==
# ==12345== D   refs:        567,890,123  (345,678,901 rd + 222,211,222 wr)
# ==12345== D1  misses:       56,789,012  ( 34,567,890 rd +  22,221,122 wr)
# ==12345== LLd misses:        5,678,901  (  3,456,789 rd +   2,222,112 wr)
# ==12345== D1  miss rate:           10.0% (       10.0%   +        10.0%)
# ==12345== LLd miss rate:            1.0% (        1.0%   +         1.0%)
 
# ソースコード行ごとのキャッシュミス情報
cg_annotate cachegrind.out.12345

12. アンチパターン

12.1 アンチパターン1: False Sharing（偽の共有）

False Sharing は、マルチスレッドプログラムにおいて、論理的に独立した変数が同一キャッシュラインに配置されることで、MESIプロトコルによる不要なキャッシュラインの無効化が発生し、性能が大幅に低下する現象である。

/* ===== False Sharing のアンチパターン ===== */
#include <pthread.h>
#include <stdio.h>
#include <time.h>
 
#define NUM_THREADS 4
#define ITERATIONS 100000000
 
/* 悪い例: カウンタが同じキャッシュラインに乗る */
struct BadCounters {
    long count[NUM_THREADS];  /* 4つの long が連続 = 32バイト < 64バイト
                               * → 全て同じキャッシュラインに入る */
};
 
/* 良い例: パディングでキャッシュラインを分離 */
struct GoodCounters {
    struct {
        long count;
        char padding[64 - sizeof(long)];  /* 64バイトアラインメント */
    } per_thread[NUM_THREADS];
};
 
struct BadCounters  bad_counters  = {0};
struct GoodCounters good_counters = {0};
 
void *bad_worker(void *arg) {
    int id = *(int *)arg;
    for (long i = 0; i < ITERATIONS; i++) {
        bad_counters.count[id]++;
        /* Thread 0 が count[0] を更新
         * → count[1], [2], [3] も同じキャッシュラインなので
         *   Thread 1,2,3 のキャッシュラインが無効化される
         * → 全スレッドが毎回L3またはDRAMからリロード */
    }
    return NULL;
}
 
void *good_worker(void *arg) {
    int id = *(int *)arg;
    for (long i = 0; i < ITERATIONS; i++) {
        good_counters.per_thread[id].count++;
        /* 各スレッドのカウンタは別のキャッシュラインにある
         * → 他スレッドのキャッシュラインに影響しない
         * → 各スレッドが独立してL1キャッシュで動作 */
    }
    return NULL;
}
 
/* 典型的な性能差:
 * Bad  (False Sharing あり): ~8秒 (4スレッド)
 * Good (False Sharing なし): ~0.5秒 (4スレッド)
 * → 16倍の性能差！
 * スレッド数が増えるほど差は拡大する
 */

12.2 アンチパターン2: ポインタ追跡（Pointer Chasing）

リンクリストやツリー構造のような、ポインタを辿ってメモリのランダムな位置にアクセスするパターンは、空間的局所性が低く、キャッシュ効率が極めて悪い。

/* ===== ポインタ追跡のアンチパターン ===== */
 
/* 悪い例: リンクリストの走査 */
struct LinkedNode {
    int value;
    struct LinkedNode *next;  /* ヒープ上のランダムな位置を指す */
};
 
long long sum_linked_list(struct LinkedNode *head) {
    long long sum = 0;
    struct LinkedNode *curr = head;
    while (curr) {
        sum += curr->value;  /* ← ほぼ毎回キャッシュミス (~100ns) */
        curr = curr->next;   /*   next が指す先はメモリ上でバラバラ */
    }
    return sum;
    /* 100万要素の場合:
     * 最悪: 100万 × 100ns = 100ms（全てDRAMアクセス）
     * 配列なら: 100万 × 4B = 4MB → L3に収まり ~5ms
     */
}
 
/* 良い例: 配列ベースの連続データ構造 */
long long sum_array(int *data, int n) {
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        sum += data[i];  /* ← 16回に1回だけキャッシュミス */
    }
    return sum;
    /* 100万要素: ~5ms（キャッシュに収まる場合はさらに高速） */
}
 
/* 妥協案: Unrolled Linked List（連結配列リスト） */
#define BLOCK_SIZE 256
struct UnrolledNode {
    int values[BLOCK_SIZE];    /* ブロック内は連続アクセス → 局所性高い */
    int count;
    struct UnrolledNode *next; /* ブロック間のみポインタ追跡 */
};
/* キャッシュミスは BLOCK_SIZE 要素に1回に抑えられる */

12.3 アンチパターン3: 巨大なワーキングセット

ワーキングセット（短時間に実際にアクセスされるメモリ領域）がキャッシュ容量を大幅に超えると、容量ミスが多発して性能が劇的に低下する。

# ===== ワーキングセット超過の影響 =====
 
import time
import array
 
def benchmark_working_set(sizes_mb):
    """異なるサイズのワーキングセットでの性能を比較"""
    for size_mb in sizes_mb:
        n = size_mb * 1024 * 1024 // 4  # int は 4バイト
        data = array.array('i', range(n))
 
        # ランダムアクセス（最悪ケース）
        import random
        indices = list(range(n))
        random.shuffle(indices)
        sample = indices[:min(1_000_000, n)]
 
        start = time.time()
        total = 0
        for idx in sample:
            total += data[idx]
        elapsed = time.time() - start
 
        ns_per_access = elapsed * 1e9 / len(sample)
        print(f"  {size_mb:6d} MB: {ns_per_access:8.1f} ns/access")
 
# 典型的な出力:
#       1 MB:      3.5 ns/access  ← L2 キャッシュに収まる
#       4 MB:      5.2 ns/access  ← L3 キャッシュに収まる
#      32 MB:     12.0 ns/access  ← L3 キャッシュの容量付近
#     128 MB:     85.0 ns/access  ← DRAM アクセスが支配的
#    1024 MB:    110.0 ns/access  ← 完全に DRAM 依存
#
# → L3 キャッシュ容量を超えた途端に性能が急激に悪化する
#   これが「キャッシュの崖」(Cache Cliff) と呼ばれる現象

13. 実践演習

演習1（基礎）: レイテンシの直感を養う

Jeff Deanの数値を使い、以下の処理にかかる概算時間を計算せよ。

問題:

1. 1000要素の int 配列（4KB）をL1キャッシュ内で線形探索する場合の合計レイテンシ
2. 100万要素のソート済み配列をL3キャッシュ内で二分探索する場合のレイテンシ（比較回数 × L3レイテンシ）
3. NVMe SSD から 100MB のファイルを連続読み出しする場合の所要時間
4. 同じ 100MB を HDD から連続読み出しする場合の所要時間

解答の目安:

1. 1000要素がL1に収まる → 1000 × 1ns = 1μs。ただし分岐予測ミスの影響で実際は2-3μs程度
2. log2(1,000,000) ≈ 20回の比較。各比較でL3アクセスが発生すると仮定 → 20 × 12ns = 240ns。実際にはTLBミスや分岐予測ミスで500ns-1μs程度
3. 100MB ÷ 7GB/s(PCIe 4.0) ≈ 14ms。初回シーク16μsを加えても約14ms
4. 100MB ÷ 200MB/s ≈ 500ms。初回シーク8msを加えて約508ms

演習2（応用）: キャッシュ効率の測定

好きなプログラミング言語で以下を実装し、性能差を比較せよ。

問題:

1. N×N 行列の行優先合計 vs 列優先合計を実装し、N=1000, 4000, 8000 で実行時間を比較せよ
2. 連続メモリの配列（ArrayList/Vector）とリンクリストで、100万要素の走査速度を比較せよ
3. AoS と SoA のレイアウトで、「位置のみ更新」処理の速度を比較せよ

計測のポイント:

• 少なくとも5回測定して中央値を使用する
• JIT言語（Java、C#等）ではウォームアップを十分に行う
• 可能であれば perf stat でキャッシュミス率を確認する

演習3（発展）: システム全体のメモリ分析

自分が開発しているアプリケーション（またはオープンソースのアプリケーション）について以下を調査せよ。

問題:

1. アプリケーションのワーキングセットサイズを推定せよ（top、ps、/proc/[pid]/smaps 等を使用）
2. ワーキングセットがL3キャッシュに収まるか判定し、収まらない場合の影響を考察せよ
3. perf stat でL1/L2/L3キャッシュミス率とTLBミス率を計測せよ
4. ページフォルトが発生しうる場面を特定し、Huge Pages の適用効果を考察せよ
5. マルチスレッド部分がある場合、False Sharing の可能性を検証せよ

14. FAQ

Q1: GC（ガベージコレクション）はキャッシュにどう影響しますか？

A: GCはキャッシュ効率に大きな影響を与える。主な影響は以下の通り。

• マーク&スイープGC: 到達可能な全オブジェクトを走査するため、ヒープ全体をスキャンする。この過程でキャッシュの内容がほぼ全て入れ替わる（キャッシュポリューション）。ワーキングセットが大きいほど影響が深刻
• 世代別GC: 若い世代（Young Generation）のみを頻繁に回収し、古い世代は稀にしか回収しない。若い世代は通常小さいため（数MB-数十MB）、L3キャッシュに収まることが多く、キャッシュへの影響は限定的
• コンパクションGC: オブジェクトをメモリ上で移動させてフラグメンテーションを解消する。移動直後は参照の局所性が向上する可能性があるが、移動中はキャッシュが汚染される
• 並行GC（ZGC、Shenandoah等）: GCスレッドがアプリケーションスレッドと並行して動作するため、GCスレッドのメモリアクセスがアプリケーションのキャッシュを汚染する。ただし、Stop-the-World時間が短いためレイテンシジッターは小さい

Q2: 仮想メモリは常にパフォーマンスに悪影響ですか？

A: 通常の状態では、仮想メモリのオーバーヘッドはTLBにより隠蔽されるため、ほぼ無視できる。問題になるケースは以下の通り。

• TLBミスの多発: ワーキングセットがTLBカバレッジ（4KB × 1024エントリ = 4MB）を超えると、TLBミスが増加する。対策として、Huge Pages（2MB/1GB）の使用が効果的
• ページフォルト（スラッシング）: 物理メモリが不足してページフォルトが頻発する状態（スラッシング）は、システムを実質的に停止させる。対策は物理メモリの増設が最も確実
• 多段ページテーブルウォーク: x86-64の4段階ページテーブルでは、TLBミス時に最大4回のメモリアクセスが必要。これ自体はハードウェアPTW(Page Table Walker)で高速化されている
• mmap の罠: 大きなファイルを mmap すると、初回アクセス時にマイナーページフォルトが発生する。MAP_POPULATE フラグや madvise(MADV_WILLNEED) で事前読み込みすることで回避可能

Q3: Apple Silicon の統合メモリ（Unified Memory）はなぜ速いのですか？

A: 従来のPCアーキテクチャでは、CPU用のDDR DRAMとGPU用のGDDR/HBMが物理的に分離されており、CPU-GPU間のデータ転送にはPCIeバス（~32GB/s）を経由する必要があった。

Apple Silicon（M1/M2/M3/M4シリーズ）の統合メモリアーキテクチャでは:

• CPU、GPU、Neural Engine（NPU）が同一のLPDDR5メモリを直接参照する（コピー不要）
• LPDDR5の全帯域（~200-400GB/s）を全コンポーネントが共有する
• CPUの計算結果をGPUがゼロコピーで利用できるため、CPU→GPU間のデータ転送レイテンシが実質ゼロ
• AI推論ワークロード（LLM等）では、モデル全体をメモリに保持したままCPU/GPU/NPUで分担処理できる

Q4: DDR5 と DDR4 の違いは何ですか？

A: DDR5はDDR4の後継規格であり、主に帯域幅が大幅に向上している。

レイテンシ（CASレイテンシ）はほぼ同等だが、帯域幅は約1.75倍に向上している。「DRAMのレイテンシはほとんど改善されない」というメモリウォール問題の本質を体現している。

Q5: キャッシュのウォームアップとは何ですか？

A: アプリケーション起動直後やコンテキストスイッチ直後は、キャッシュの内容が無効（コールド状態）であるため、初期のメモリアクセスは全てキャッシュミスとなる。キャッシュのウォームアップとは、ワーキングセットのデータがキャッシュに読み込まれ、ヒット率が定常状態に達するまでの過程を指す。

ベンチマーク測定においては、ウォームアップフェーズを設けてキャッシュ状態を安定させてから計測を開始することが重要である。ウォームアップなしの測定は、コールドミスの影響を含むため、定常状態の性能を正しく反映しない。

15. 発展トピック

15.1 メモリ技術の最新動向

15.2 キャッシュ階層の将来

現代のプロセッサでは、L1/L2/L3の3階層が標準だが、以下のような変化が進行している。

• L4キャッシュの登場: Intel Meteor LakeではeDRAMベースのL4キャッシュ（128MB）を搭載。GPUとCPUで共有
• 3D V-Cache: AMDの3D V-Cache技術では、L3キャッシュをダイの上に積層し、最大128MBのL3キャッシュを実現。ゲーム等のキャッシュ感応的なワークロードで大幅な性能向上
• 適応型キャッシュポリシー: 機械学習ベースの動的キャッシュ置換ポリシーの研究が進んでいる

FAQ

Q1: このトピックを学ぶ上で最も重要なポイントは何ですか？

実践的な経験を積むことが最も重要です。理論だけでなく、実際にコードを書いて動作を確認することで理解が深まります。

Q2: 初心者がよく陥る間違いは何ですか？

基礎を飛ばして応用に進むことです。このガイドで説明している基本概念をしっかり理解してから、次のステップに進むことをお勧めします。

Q3: 実務ではどのように活用されていますか？

このトピックの知識は、日常的な開発業務で頻繁に活用されます。特にコードレビューやアーキテクチャ設計の際に重要になります。

16. まとめ

17. 次に読むべきガイド

18. 参考文献

1. Bryant, R. E. & O'Hallaron, D. R. Computer Systems: A Programmer's Perspective. 3rd Edition, Pearson, 2015.
   • メモリ階層・仮想メモリの包括的な解説。学部レベルの標準的教科書
2. Hennessy, J. L. & Patterson, D. A. Computer Architecture: A Quantitative Approach. 6th Edition, Morgan Kaufmann, 2017.
   • キャッシュ設計・メモリ技術の定量的分析。大学院レベルの標準的教科書
3. Drepper, U. "What Every Programmer Should Know About Memory." 2007. https://people.freebsd.org/~lstewart/articles/cpumemory.pdf
   • DRAM・キャッシュ・NUMA・プロファイリングの実践的ガイド。必読文献
4. Dean, J. & Barroso, L. A. "The Tail at Scale." Communications of the ACM, 56(2):74-80, 2013.
   • 大規模分散システムにおけるレイテンシの影響を考察。"Numbers Everyone Should Know" の原典
5. Intel Corporation. Intel 64 and IA-32 Architectures Optimization Reference Manual. 2024.
   • x86プロセッサのキャッシュ・メモリ最適化の公式リファレンス
6. Levinthal, D. Performance Analysis Guide for Intel Core i7 Processor and Intel Xeon 5500 Processors. Intel, 2009.
   • perfカウンタを用いたキャッシュ性能分析の実践ガイド
7. Fog, A. "Optimizing software in C++: An optimization guide for Windows, Linux and Mac platforms." https://www.agner.org/optimize/
   • データ構造レイアウト・キャッシュ最適化の実践的テクニック集

次に読むべきガイド

• ストレージシステム - 次のトピックへ進む

参考文献

• MDN Web Docs - Web技術のリファレンス
• Wikipedia - 技術概念の概要