... それらはメモリ上で隣り合っています。
CPUがデータを必要とするとき、まずキャッシュを探します。見つかればみんなハッピー——しかし見つからなければ?
この講義では、キャッシュの動作の中核メカニズムと、キャッシュを有効にする鍵となる原理を理解していきます——局所性の原理。
生活に即した例え:図書館の机
あなたは図書館で論文を書いています。机の上には最大4冊の本を置けます——これがあなたの「キャッシュ」、容量は小さいですが、手を伸ばせばすぐ取れます。
特定の本が必要なとき、まず机の上にあるかどうかを確認します:
- 机の上にある(キャッシュヒット):すぐに開いて使える、待ち時間ゼロ。
- 机の上にない(キャッシュミス):立ち上がって本棚を探し、持ってきて机に置く。机が満杯なら、最も長く開かなかった本を本棚に戻さなければならない。
この単純なルールこそ、コンピュータのキャッシュシステムの真髄です——「最近使ったものは残し、使わないものは追い出す」。
さらに、気づくでしょう:論文を書くとき、関連のない本をランダムにめくることはありません。ある期間、同じ参考資料を繰り返し調べます。図書館の何千もの本棚にある本の中で、実際に手に取ったのは二、三十冊だけかもしれません。これが局所性の原理働いているのです。
中核概念:キャッシュヒットとミス
基本用語
| 用語 | 英語 | 意味 |
|---|---|---|
| キャッシュヒット | Cache Hit | CPUが要求したデータがちょうどキャッシュ内に見つかり、直接使用する |
| キャッシュミス | Cache Miss | CPUが要求したデータがキャッシュ内になく、次の階層(より遅い)ストレージからロードする必要がある |
| ヒット率 | Hit Rate | ヒット回数 / 総アクセス回数。高いほど良い(理想は100%に近い) |
| ミスペナルティ | Miss Penalty | ミス発生後、次の階層からデータをロードするために余分にかかる時間 |
| ヒット時間 | Hit Time | キャッシュヒット時にデータを読み取るのに必要な時間 |
簡単な例
キャッシュに3つのスロットがあるとします。CPUがアドレス [10, 20, 10, 30, 10] を順にアクセスします:
| ステップ | アクセスアドレス | キャッシュ状態(アクセス前) | 結果 | 理由 |
|---|---|---|---|---|
| 1 | 10 | [] | ミス | キャッシュが空で、アドレス10が存在しない |
| 2 | 20 | [10] | ミス | アドレス20がキャッシュ内にない |
| 3 | 10 | [10, 20] | ヒット | アドレス10がキャッシュ内にある!(時間的局所性) |
| 4 | 30 | [10, 20] | ミス | アドレス30がキャッシュ内にない |
| 5 | 10 | [10, 20, 30] | ヒット | アドレス10が再びヒットした |
5回のアクセス中2回ヒット、ヒット率 = 40%。高くはないが、キャッシュの原理を示しています。
なぜキャッシュが有効か:局所性の原理
プログラムのメモリアクセスが完全にランダムなら、キャッシュはほぼ役に立ちません——ロードしたばかりなのに使われなくなります。
しかし実際のプログラムの挙動はランダムではありません。それらは強い局所性(Locality)を示します。これこそがキャッシュが有効な根本原因です。
時間的局所性(Temporal Locality)
あるデータがアクセスされたなら、近い将来に再びアクセスされる可能性が高い。
典型的なシナリオ:
- ループ内の変数:
for i in range(1000000): total += i——変数iとtotalが短時間に100万回アクセスされる。 - 関数のホットスポットコード:プログラム中の20%のコードが80%の時間実行され、これらの命令は頻繁に再アクセスされます。
- 頻繁に呼び出される関数のパラメータ:再帰関数内のローカル変数は、呼び出しのたびにスタック上に積み重なります。
空間的局所性(Spatial Locality)
あるデータがアクセスされたなら、その近くのデータもアクセスされる可能性が高い。
典型的なシナリオ:
- 配列の連続走査:
for i in range(len(arr)): sum += arr[i]——arr - 構造体/オブジェクトのフィールド:アクセス
student.nameした後、おそらく次にアクセスするのはstudent.age、それらはメモリ上で隣接しています。 - 順次実行される命令:CPUがアドレス100の命令を実行し終えると、次の命令は高い確率でアドレス104の命令です。
2つの局所性の可視化
时间局部性示意图:
时间轴: t1 t2 t3 t4 t5 t6 t7 t8
访问地址: A B A C A D B A
|_____|_____|_____|
地址 A 在短时间内被多次访问——时间局部性
空间局部性示意图:
内存地址: 100 104 108 112 116 120 124 128
访问顺序: *1 *2 *3 *4 *5
|_____________________________|
连续访问相邻地址——空间局部性
現代CPUはまさに空間的局所性を利用して性能を向上させています:メモリからアドレス100のデータをロードするとき、ついでにアドレス100〜164(キャッシュライン全体、通常64バイト)もキャッシュにロードします。こうすることで、アドレス104にアクセスするときにはすでにキャッシュ内にあるのです。
キャッシュ置換ポリシー:満杯になったらどうするか
キャッシュのスロットは有限で、キャッシュが満杯で新しいデータを取り込む必要があるとき、古いデータを1つ追い出さなければなりません。「誰を追い出すか」という決定が、キャッシュ置換ポリシーです。
| ポリシー | 英語 | ルール | 評価 |
|---|---|---|---|
| LRU(最も長い間使用されていない) | LRU (Least Recently Used) | 最も長い間アクセスされていないデータを追い出す | 最も一般的で、効果が良い |
| FIFO(先入れ先出し) | FIFO (First In First Out) | 最も早くキャッシュに入ったデータを追い出す | 単純だが効果は普通 |
| LFU(最も使用頻度が低い) | LFU (Least Frequently Used) | アクセス回数が最も少ないデータを追い出す | ホットデータには好都合だが、古いデータが「居座る」可能性がある |
| ランダム置換 | Random | ランダムに1つ選んで追い出す | 実装が最も簡単で、効果は悪くない |
LRUは実際に最も良い性能を示します。なぜなら時間的局所性を直接利用しているからです——「最近使っていないものは、短期間内にはおそらく使わない」。
実際のCPUキャッシュは通常、LRUの近似変種(疑似LRUなど)を使用して、ハードウェア実装の複雑さを低減します。
インタラクティブデモ:LRUキャッシュシミュレータ
以下のPythonプログラムは、LRUキャッシュの動作プロセスを完全にシミュレートします。アクセス系列とキャッシュ容量を変更して、ヒット率の変化を観察できます。
例
LRUキャッシュシミュレータ(サンプルデモ)
機能:
1. CPUによるメモリアドレスのアクセス系列をシミュレート
2. LRUポリシーを使用してキャッシュを管理
3. 各アクセスが「ヒット」か「ミス」かをリアルタイムに表示
4. ヒット率を集計して表示
"""
from collections import OrderedDict
class LRUCache:
"""
LRU(最も長い間使用されていない)キャッシュシミュレータ
OrderedDict を使用してアクセス順を管理し、末尾に近いほど最近アクセスされたことを示す
"""
def __init__(self, capacity):
"""
キャッシュを初期化
:param capacity: キャッシュ容量(格納できるエントリ数)
"""
self.capacity = capacity
self.cache = OrderedDict() # 順序付き辞書:key=アドレス、value=データ
self.hits = 0 # ヒットカウント
self.misses = 0 # ミスカウント
self.evictions = 0 # 追い出しカウント
def access(self, address):
"""
メモリアクセスを1回シミュレート
:param address: アクセスするメモリアドレス
:return: (result_str, is_hit)
"""
if address in self.cache:
# キャッシュヒット!
self.hits += 1
# LRUポリシー:ヒットしたエントリを末尾に移動(最近使用されたとマーク)
self.cache.move_to_end(address)
return "HIT", True
else:
# キャッシュミス
self.misses += 1
evicted = None
if len(self.cache) >= self.capacity:
# キャッシュが満杯、最も長い間使用されていないものを追い出す必要があります(OrderedDictの最初の要素)
evicted_addr, _ = self.cache.popitem(last=False)
self.evictions += 1
evicted = evicted_addr
# 「次の階層のストレージ」(データを直接取得するとしてシミュレート)から新しいデータをロード
data = f"DATA_AT_{address}"
self.cache[address] = data
return "MISS", False
def hit_rate(self):
"""現在のキャッシュヒット率(パーセント)を計算"""
total = self.hits + self.misses
if total == 0:
return 0.0
return (self.hits / total) * 100
def current_state(self):
"""現在のキャッシュ内容を返す(最も古いものから最新のものへ)"""
return list(self.cache.keys())
def run_simulation(access_sequence, cache_capacity):
"""
完全なキャッシュシミュレーションを1回実行
:param access_sequence: シミュレートするメモリアクセス系列(intのリスト)
:param cache_capacity: キャッシュ容量
"""
cache = LRUCache(cache_capacity)
print("=" * 70)
print(f"サンプル LRUキャッシュシミュレータ")
print(f)
print(fとは連続しない、行をまたいでいるため)")
print("=" * 70)
print(f"{'ステップ':<6} {'アドレス':<8} {'結果':<8} {'キャッシュ状態(旧→新)':<40}")
print("-" * 70)
for i, addr in enumerate(access_sequence, 1):
result, is_hit = cache.access(addr)
state = cache.current_state()
hit_mark = "HIT [OK]" if is_hit else "MISS X"
print(f"{i:<6} {addr:<8} {hit_mark:<8} {str(state):<40}")
# 統計の出力
print("-" * 70)
print(f"\n統計結果:)
print(f" ヒット数 (Hits) : {cache.hits}")
print(f" ミス数 (Misses): {cache.misses}")
print(f" 追い出し数 (Evictions): {cache.evictions}")
print(f" ヒット率 (Hit Rate) : {cache.hit_rate():.1f}%")
print()
return cache
# ============================================================
# デモ 1:基本的な LRU 動作
# ============================================================
print("\n">>> デモ 1:基本 LRU キャッシュの動作")
print("アクセスシーケンスは時間的局所性を示しています——アドレス10が繰り返しアクセスされます"\n")
run_simulation(
access_sequence=[10, 20, 10, 30, 40, 10, 20, 50, 10, 20],
cache_capacity=4
)
# ============================================================
# デモ 2:異なるキャッシュ容量がヒット率に与える影響
# ============================================================
print("\n">>> デモ 2:キャッシュ容量がヒット率に与える影響")
print("同じアクセスシーケンスでも、異なるキャッシュ容量での挙動"\n")
test_sequence = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5,
1, 2, 3, 4, 5, 6, 7, 1, 2, 3, 4, 5, 6, 7]
print(f"アクセスシーケンスの長さ: {len(test_sequence)}")
print(f"{'容量':<8} {'ヒット':<8} {'ミス':<8} {'ヒット率':<10}")
print("-" * 35)
for cap in [1, 2, 3, 4, 5, 8, 16]:
c = LRUCache(cap)
for addr in test_sequence:
c.access(addr)
print(f"{cap:<8} {c.hits:<8} {c.misses:<8} {c.hit_rate():<8.1f}%")
# ============================================================
# デモ 3:「ランダムアクセス」vs「局所性アクセス」の比較
# ============================================================
print("\n">>> デモ 3:局所性アクセス vs ランダムアクセス")
print("同じキャッシュ容量(8)でも、アクセスパターンが異なるとヒット率に差が出ます"\n")
import random
random.seed(42)
# パターン A:局所性のあるアクセス(配列のループ走査をシミュレート)
local_access = []
for _ in range(20):
# 各ループで 0-15 の範囲を連続的にアクセスし、その後ジャンプ
base = random.randint(0, 50)
for offset in range(5):
local_access.append(base + offset)
# パターン B:完全にランダムなアクセス
random_access = [random.randint(0, 100) for _ in range(100)]
for label, seq in [("局所性アクセス", local_access), ("ランダムアクセス", random_access)]:
c = LRUCache(8)
for addr in seq:
c.access(addr)
print(f" {label}: ヒット率 = {c.hit_rate():.1f}% (総アクセス {len(seq)} 回)")
インタラクティブデモ:キャッシュヒット/ミスのリアルタイムシミュレーション
局所性を持つメモリアクセスシーケンスをランダム生成(30回)、毎回のキャッシュ検索過程をアニメーションで表示し、ヒット率をリアルタイム集計して変化曲線を描画します
このコードを実行すると、次のことがわかります:
- キャッシュ容量が大きいほどヒット率は高くなります——ただし向上幅は徐々に逓減します(限界効果)
- 局所性のあるアクセスパターンのヒット率は、ランダムアクセスよりはるかに高い——これがキャッシュが効果的な理由です
- LRU方式では、繰り返しアクセスされるアドレスはキャッシュに残り続け、ほとんど追い出されません
キャッシュミスの3つのタイプ
すべての「キャッシュミス」が同じというわけではありません。ハードウェアエンジニアはこれを3つに分類しています:
| タイプ | 英語 | 発生タイミング | 回避できるか |
|---|---|---|---|
| 強制ミス | Compulsory Miss (Cold Miss) | 初めてデータにアクセスするとき、キャッシュにはまだ存在しない | 回避不可(初回アクセスは常にコールド) |
| 容量ミス | Capacity Miss | ワーキングセット(プログラムが活発に使用するデータ)がキャッシュ容量より大きい | キャッシュを増やすか、ワーキングセットを減らす |
| コンフリクトミス | Conflict Miss | 異なるアドレスがキャッシュ内の同じ位置にマッピングされる(ダイレクトマップキャッシュでよく発生) | セットアソシアティブまたはフルアソシアティブマッピングを使う |
一般のプログラマーにとって、関わる機会が多いのは最初の2つです:
- 強制ミス:回避はできませんが、プログラムの実行時間が長いほど影響は小さくなります。
- 容量ミス:データ構造のサイズやアクセスパターンの最適化で緩和できます。例えば、よりコンパクトなデータ型を使う、大きな配列をブロック単位で処理するなど。
キャッシュミスを理解することは、高性能なコードを書くための鍵です。簡単な経験則:データのアクセスパターンをキャッシュに優しくしましょう——配列を走査するときはメモリレイアウト順にアクセスし、ジャンプアクセスを避け、頻繁に一緒に使うデータはメモリ上でも近くに配置します。
プログラミング実践:キャッシュフレンドリーなコード
古典的な例を見てみましょう:2次元配列を走査するとき、行方向の走査 vs 列方向の走査では、性能に大きな差が出ます。
例
キャッシュフレンドリー vs キャッシュに優しくない配列走査 (サンプル デモ)
同じデータに対する異なるアクセス方法がキャッシュ性能にどう影響するかをデモします
"""
import time
# Pythonにおけるリストの格納方法:2次元配列 = リストのリスト
# arr[i][j] において arr[i] は行全体であり、メモリ上では連続している
# したがって、行方向の走査 = キャッシュフレンドリー、列方向の走査 = キャッシュに不友好
def traverse_row_major(arr):
"""
行方向の走査:まず行番号 i を固定し、次に列 j を走査する
アクセスパターン:arr
メモリレイアウト:これらの要素はメモリ上で連続しています -- 空間的局所性が良い!
"""
total = 0
rows = len(arr)
cols = len(arr[0])
for i in range(rows):
for j in range(cols):
total += arr[i][j]
return total
def traverse_column_major(arr):
"""
列方向の走査:まず列番号 j を固定し、次に行 i を走査する
アクセスパターン:arr
メモリレイアウト:これらの要素はメモリ上で飛び飛びになります -- 空間的局所性が悪い!
"""
total = 0
rows = len(arr)
cols = len(arr[0])
for j in range(cols):
for i in range(rows):
total += arr[i][j]
return total
# 大きな配列を作成(1000 x 1000)
SIZE = 1000
print(f"{SIZE}x{SIZE} の2次元配列を作成中...")
arr = [[i * SIZE + j for j in range(SIZE)] for i in range(SIZE)]
# 最初にウォームアップして、コールドスタートの偏りを避ける
traverse_row_major(arr)
traverse_column_major(arr)
# 正式なテスト
print("\n"性能比較を開始(3回実行して平均を取ります):")
print("-" * 50)
def benchmark(func, arr, trials=3):
"""複数回実行して平均時間を計算"""
times = []
for _ in range(trials):
start = time.perf_counter()
func(arr)
elapsed = time.perf_counter() - start
times.append(elapsed)
return sum(times) / len(times)
row_time = benchmark(traverse_row_major, arr)
col_time = benchmark(traverse_column_major, arr)
print(f"行方向の走査(キャッシュフレンドリー): {row_time:.4f} 秒")
print(f"列方向の走査(キャッシュに不友好): {col_time:.4f} 秒")
print(f"列方向は行方向より遅い: {col_time / row_time:.1f} 倍")
print()
print("原因の分析:")
print(" 行方向の走査では、arr[i])
print(" 最初に arr[i])
print(" 後続の arr[i])
print()
print(" 列方向の走査では、arr)
print(" ほぼ毎回メモリからのロードが必要になり、キャッシュヒット率は極めて低い")
# 補足:簡単なテスト - Python の id() でメモリアドレスを確認
print("\n"メモリレイアウトの検証(小規模な配列でのデモ):")
small = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(f"arr)
print(f"arr)
print(f"arr)
print(f"arr)