計算量と実測が食い違うとき — キャッシュ・分岐・メモリ帯域

同じO(n)のコードが実測では桁で違う——O記法が意図的に捨てている「メモリの現実」を、キャッシュ階層・分岐予測・メモリ帯域の3つの側面から解き明かす。

同じO(n)なのに、速度が桁で違う

こんな経験はないでしょうか。教科書どおりに計算量を見積もり、O(n)のアルゴリズムを選んだのに、実際に走らせると想定よりはるかに遅い。あるいは、同じO(n)のはずの2つの書き方を測り比べたら、片方が何十倍も速かった。

具体例を2つ挙げます。1つ目は「n個の数の合計」。配列に並んだ数を先頭から足すのも、連結リスト（各要素が次の要素の場所を指すデータ構造）を辿りながら足すのも、どちらも要素をn回訪ねるO(n)です。ところが実測すると、大きなnでは配列が桁違いに速いのが普通です。2つ目は「2次元配列の全要素の合計」。行方向に舐めても列方向に舐めても同じO(n²)ですが、大きな配列ではやはり実測が大きく食い違います。

O記法が間違っているのではありません。O記法は「nを増やしたとき計算の手数がどう増えるか」だけを語る道具であって、1手あたりの重さについては最初から何も言っていないのです。そして現実のコンピュータでは、この「1手の重さ」がアクセスの仕方ひとつで数百倍変わります。この記事では、その差を生む三大要因——キャッシュ・分岐予測・メモリ帯域——を順に見ていきます。

比喩: 机の上・本棚・別棟の倉庫

CPUを、資料を読みながら書類を作る作業者だと考えてください。資料の置き場所は3段階あります。

1. 机の上: 手を伸ばせば一瞬で取れる。ただし数冊しか置けない
2. 背後の本棚: 立ち上がって数秒。数十冊入る
3. 別棟の倉庫: 取り寄せに数分。ここには何でもある

これがメモリ階層の姿です。机の上がCPU内部のキャッシュ、倉庫がメインメモリ（DRAM）にあたり、実機でも一番近い記憶と一番遠い記憶では取り寄せ時間が2桁ほど違います。

重要な仕掛けがもう1つ。倉庫の係員は、1冊頼まれると同じ箱に入っている隣の資料もまとめて持ってきます。次に必要な資料がその箱に入っていれば、倉庫まで行かずに済む。この「箱」がキャッシュライン（多くのCPUで64バイト単位）です。つまり、資料を並び順に読む作業者は速く、あちこちの箱から1冊ずつ取り寄せる作業者は遅い。同じ冊数を読んでいても、です。

O記法が置いている仮定

計算量の理論はRAMモデルという理想の機械を前提にしています。そこでは「どのメモリ番地を読むのも等しく1ステップ」。この仮定のおかげで理論はシンプルになり、アルゴリズム同士の本質的な優劣を比べられます（この土台は計算量の基礎で扱いました）。

実測時間との関係を1本の式にするとこうなります。

$T(n)$ が実際にかかる時間、$f(n)$ がO記法の中身（nやn²といった増え方の形）、$c$ が「1手あたりの平均コスト」を表す定数倍です。つまり、実際に待たされる時間は「手数の増え方の形」に「1手がその機械でどれだけ重いか」を掛けたもの、ということ。O記法は $c$ を捨てて $f(n)$ だけを比べますが、実測で効いてくるのはむしろ $c$ のほう。キャッシュに乗るかどうかで $c$ が100倍変われば、同じO(n)でも100倍の速度差になります。そして現実のnでは、$f(n)$ の形の差より $c$ の差のほうが大きいことが珍しくありません。

ここから先は、この定数倍 $c$ の中身を3つの引き出し——キャッシュ・分岐予測・メモリ帯域——の順に開け、それぞれ「なぜ効くのか」「どう測って直すのか」まで下ろしていきます。