メモリ階層
Memory Hierarchy ・ メモリかいそう
速いが小さい記憶から遅いが大きい記憶までを段に積み、よく使うものを上に置く構造。
✦ 30秒で試す — 航海データ量がある線を越えた日から、急に遅くなる全部が主記憶に収まるときと比べて、1回の読み出しの平均は？予想してみる概要
メモリ階層は、コンピュータの記憶装置を「速いが小さいもの」から「遅いが大きいもの」へと段に積み重ねた構造のことです。CPU内部のレジスタを頂点に、CPUキャッシュ（L1/L2/L3）、主記憶（RAM。DRAM という半導体で作られる作業用のメモリ）、そしてSSDやHDDといったストレージ（電源を切っても消えない記憶装置）までが1本の階段を成しており、プログラムが扱うデータは常にこの階段のどこかに置かれています。
なぜわざわざ段にするのかというと、「速くて大きくて安いメモリ」が物理的に作れないからです。速い記憶素子は高価で、CPUの近くに置ける量も限られます。大容量の記憶はどうしても遅くなります。そこで、よく使うデータだけを上の速い段に置き、残りは下の遅くて大きい段に置く — この分業によって、全体としては「ほぼ速い段の速度で、下の段の容量を使える」ように見せかけているのがメモリ階層の本質です。
普段プログラムを書くときにこの階層を直接操作することはほとんどありません。しかし性能問題の多くはここに根を持っています。「同じ計算量なのに書き方ひとつで数倍速くなる」「データがメモリに載り切らなくなった途端に何百倍も遅くなる」といった現象は、どの段にデータが載っているかの違いで説明できます。
なぜ生まれたか
問題の根は、CPUとメモリの速度差が開き続けたことにあります。初期のコンピュータではCPUとメモリの速さは釣り合っていましたが、1980年代以降、CPUの演算速度が年率で急伸したのに対し、主記憶（DRAM）の応答速度はわずかしか改善しませんでした。その結果、現代のCPUにとって主記憶からの読み出しは数百サイクルの待ちになり、「計算そのものより、データが届くのを待つ時間のほうが長い」という逆転が起きました。この現象は「メモリの壁（memory wall）」と呼ばれます。
一方で、性質の違う記憶素子はそれぞれ手元にありました。SRAM（速いが高価で小さい）、DRAM（そこそこ速く、安くて大きい）、磁気ディスクやフラッシュメモリ（ずっと遅いが、さらに大きく、電源を切っても消えない）です。どれか1つを選ぶのではなく、全部を組み合わせて「よく使うデータほど速い段に寄せる」仕掛けを作れば、コストを抑えたまま実効速度を稼げる — これがメモリ階層という設計の答えでした。
この仕掛けは、各段の境目ごとに別々の担い手が実装しています。CPUと主記憶の間ではハードウェアが自動で動くCPUキャッシュが、主記憶とストレージの間ではOSの仮想メモリ（使っていないページをストレージへ退避し、必要になったら戻す仕組み）とページキャッシュが働きます。アプリケーションが Redis のようなキャッシュを置くのも、同じ発想を上の層で繰り返したものです。
詳細
階段を桁で眺める
メモリ階層を理解する第一歩は、各段の容量とレイテンシ（1回の読み出しにかかる時間）を「桁」で把握することです。正確な数値は製品や世代で変わりますが、桁の感覚はほぼ普遍です。ピラミッドの絵だけでは段と段の差が「少し遅い」程度に見えてしまうので、下の図では時間を対数目盛（1目盛りで10倍）に並べました。
L1キャッシュは約1ナノ秒、主記憶は約100ナノ秒、SSDは約100マイクロ秒、HDDは数ミリ秒 — 隣り合う段の間ですら数倍、主記憶とSSDの間では約1000倍、L1とHDDの間では数百万倍の差があります。人間の時間に引き伸ばして、L1の1ナノ秒を「1秒」とすると、主記憶は「1分40秒」、SSDは「1日強」、HDDは「2か月」です。この桁の感覚があると、「ディスクI/Oを1回減らす」ことの重みが直感的に分かるようになります。
階層を機能させる鍵 — 局所性
ただ段を積んだだけでは速くなりません。この構造が機能するのは、プログラムのメモリアクセスに「局所性（locality）」という強い偏りがあるからです。時間的局所性は「一度使ったデータは近いうちにまた使われる」傾向（ループの中の変数など）、空間的局所性は「使ったデータの近くもすぐ使われる」傾向（配列を順に読むなど）です。
この偏りのおかげで、「最近使ったものとその周辺」だけを上の段に置いておけば、アクセスの大半は速い段で完結します。上の段に目当てのデータがあれば「ヒット」、なければ下の段まで取りに行く「ミス」で、ヒット率が実効速度を支配します。逆に、巨大なデータをランダムに飛び回るような局所性の乏しいアクセスを書くと、階層の恩恵を受けられずミスの嵐になります。データ構造の選び方とアクセスの順序が性能に直結する理由がここにあります。ライン単位の読み込みなど、ハードウェア側の具体的な仕組みはCPUキャッシュの記事で掘り下げます。
載るか載らないか — 作業セットと崖
性能を左右するもう一つの見方が「作業セット（working set）」です。プログラムがある時間帯に繰り返し触るデータの総量のことで、これがどの段に収まるかで速度が決まります。作業セットがL1に収まっているうちは、どのアクセスも1ナノ秒前後で済みます。L1の容量を少し超えると、はみ出した分のアクセスだけがL2へ取りに行き、平均がじわりと上がります。そして主記憶の容量を超えた瞬間、はみ出した分はSSDまで取りに行くことになり、平均は100ナノ秒台から数十マイクロ秒へ、桁ごと跳ね上がります。性能のグラフが坂ではなく階段と崖になるのはこのためです。
下の部品で、作業セットの大きさのつまみを右へドラッグしてみてください。データが段からあふれるたびに、1回のアクセスの平均時間が対数目盛の上で段差状に跳ねます（ここではデータ全体をランダムに触る単純なモデルで計算しています）。
右のグラフの下にあるつまみを右へドラッグして、作業データ（プログラムが繰り返し触るデータ）を大きくしてみてください。いまは 16 KB で、すべて L1 に収まっています。
実務でよく見る「データ量がある線を越えた日から急に遅くなった」は、たいていこの崖です。RDBMSの索引や頻繁に読む表が主記憶（バッファプール）に収まっているうちは速く、収まらなくなるとディスク読み込みが急増します。対策は、崖の手前に留まるように作業セットを小さくする（必要な列だけ読む、データを分割する）か、段そのものを増やす（メモリを増設する）かのどちらかです。
各段の担い手
頂点のレジスタはCPUが演算に直接使う作業台で、コンパイラがどの変数をレジスタに置くかを決めます。その下のL1〜L3キャッシュはハードウェアが自動で管理し、プログラムからは見えません。主記憶はプロセスのコードとデータ — スタックとヒープもここに置かれます — の本籍地です。
主記憶とストレージの間では、OSが2つの役目を果たします。1つは仮想メモリで、プロセスのページのうちしばらく使われていないものをストレージのスワップ領域へ追い出します。この出し入れが頻発して処理がほとんど進まなくなる状態が「スラッシング」で、メモリ不足のマシンが極端に遅くなる正体です。もう1つがページキャッシュです。OSはストレージから読んだファイルシステム上のファイルの中身を、空いている主記憶に残しておきます。同じファイルを2回目に読むと驚くほど速いのはこのためで、free コマンドで「使用中」のメモリが多く見えても、その多くは必要になれば手放せるページキャッシュです。
同じ主記憶でも近い・遠いがある — NUMA
CPUソケットを複数積んだサーバでは、主記憶も一枚岩ではありません。各CPUに直結したメモリがあり、隣のCPUのメモリへは相互接続を経由して取りに行くため、遅延がおよそ1.5〜2倍になります。この「どのCPUから見るかでメモリの近さが変わる」構成を NUMA（Non-Uniform Memory Access）と呼びます。大きなデータベースや仮想化基盤では、プロセスやスレッドを実行するCPUと、そのデータを置くメモリを同じ側にそろえる（NUMA を意識した配置にする）だけで、目に見えて速くなることがあります。
同じ思想はソフトウェアにも続いている
メモリ階層の考え方は、ハードウェアの中で終わりません。アプリケーションが速いキャッシュ（Redis など）をRDBMSの手前に置くのも、CDNが利用者の近くにコンテンツの複製を置くのも、「よく使うものを速い（近い）場所に置き、ヒット率で実効速度を稼ぐ」という同じ思想です。GPUにもレジスタ・共有メモリ・デバイスメモリという階層があり、GPUプログラミングの最適化も結局はこの階層とのつき合い方が中心になります。何を上の段に載せるか、いつ捨てるか、下の段との食い違いをどう防ぐか — 上位のキャッシュ設計の判断は、すべてこの一段の問題の変奏として見えてきます。
試問
左に L1 キャッシュから HDD までの記憶の段（容量と1回の読み出し時間）、右に作業データ（プログラムが繰り返し触るデータ）の大きさと、1回のアクセスの平均時間のグラフがあります。グラフの下のつまみを左右にドラッグすると、作業データの大きさが変わります。いまは作業データが 64GB に膨らみ、システムが遅くなっています。
右のグラフの下にあるつまみを右へドラッグして、作業データ（プログラムが繰り返し触るデータ）を大きくしてみてください。いまは 64 GB で、平均は 50 µs です。