キャッシュに優しいコード — 同じO(n)で10倍差がつく理由

計算量が同じ2つの実装で実行時間が桁違いになるのは、CPUがデータを「1個ずつ」ではなく「64バイトの塊」で運ぶからです。局所性・キャッシュライン・配列と連結リストの実測差・AoS/SoA・ループ順序・false sharing を、前提知識ゼロから、最後は perf で自分の目で確かめるところまで。

比喩: 図書館は1冊だけでは運んでくれない

書庫の奥から本を取り寄せる図書館を想像してください。1冊頼むと、司書は棚のその区画ごと台車に載せて運んできます。あなたが次に頼む本が同じ区画にあれば、台車の上から即座に渡してもらえる。違う区画なら、また往復です。

この図書館では、読む冊数ではなく、往復の回数が待ち時間を決めます。100冊を棚の並び順に読むなら往復は数回で済み、100冊をくじ引きの順に読むなら往復は100回。読んだ冊数は同じ100冊なのに、体感時間はまるで違う。

CPUとメモリの関係がまさにこれです。CPUはメモリから数値を1個ずつ取ってはいません。必ず一定サイズの塊（多くの機種で64バイト）をまとめて持ってきて、手元の小さな棚（キャッシュ）に置きます。アルゴリズムの教科書は「何冊読むか」を数えますが、実行時間を握っているのは「何往復するか」の方です。

なぜ塊で運ぶのか — 局所性という賭け

まとめて運ぶのは、メモリの壁を1からで見たとおり、遠くから1個だけ取ってくるのが極端に高くつくからです。取りに行く手間の大半は移動時間で、ついでに隣も持ってくる分の追加コストはごくわずか。ならば隣ごと持ってきた方が得です。

この「ついで」が当たるかどうかは、プログラムの振る舞いに賭けています。賭けの根拠は2種類の局所性です。

• 時間的局所性: 一度使った値は、すぐまた使われやすい（ループ変数、直近のテーブル）
• 空間的局所性: ある値を使ったら、その隣の値も使われやすい（配列の走査）

ハードウェアはこの賭けにさらに上乗せをします。プリフェッチャという回路が「連続して読んでいる」「一定間隔で飛んでいる」といった規則性を検出し、まだ要求されていない先の塊を勝手に取り寄せておく。規則的に並んだデータを順に舐めるコードが速いのは、この先読みが常に当たるからです。逆に、次にどこを読むかがメモリの中身を見るまで分からないコード（ポインタを辿る構造）では、先読みが原理的に効きません。

仕組み: キャッシュラインという最小単位

キャッシュが扱う最小単位をキャッシュラインと呼びます。x86-64 や多くのArmで64バイト、Appleシリコンでは128バイトです。4バイトの int を1個読むと、その int を含む64バイトが丸ごとキャッシュに載ります。つまり隣の15個も一緒にタダで載る。

連続した配列を先頭から舐めるとき、ミス（＝取り寄せ）が起きる割合は単純な割り算になります。

$s$ は要素1個のバイト数、$B$ はキャッシュラインのバイト数、$m$ はアクセス1回あたりミスが起きる割合です。要するに、4バイトの要素を64バイトの塊で運ぶなら、16回に1回しか取り寄せが発生しない。残り15回は手元の棚から返ってきます。

体感時間はこの $m$ で決まります。

$t_{\text{hit}}$ は手元の棚にあったときの時間、$t_{\text{miss}}$ は取り寄せに追加でかかる時間、$T$ は平均の1アクセスあたり時間です。言い換えると、平均時間 = いつもの時間 + 外れる確率 × 外れたときの罰金。ここで効くのが罰金の大きさで、L1に当たれば数サイクル、DRAMまで行けば数百サイクル相当と、桁が2つ違います（正確な値は機種で変わります）。

だから $m$ が $1/16$ の実装と $m$ が $1$ の実装は、命令数が同じでも実行時間が何倍にもなります。しかも罰金が大きいほど差は開くので、扱うデータがキャッシュ容量を超えた瞬間に、それまで同じ速さだった2つの実装が突然引き離される、という不連続な現象も起きます。O(n) 対 O(n)、勝負は定数倍でつく。これが本記事の主題です。

この図に描かれていないものが、この記事の全部です。曲線はどれも係数1で、同じ形の線が何本も上下に並ぶ様子は出てきません。計算量の議論は、入力を大きくしたときの伸び方だけを比べる道具として作られているので、係数は最初から捨てられているわけです。そして係数を決めているのは、多くの場合アルゴリズムではなくメモリの触り方です。

ここから先は、その係数を作っている4つの要因を順に見ます。データの並べ方（配列と連結リスト）、構造体の持ち方（AoSとSoA）、ループの順序、そして複数スレッドが同じラインに書き込む false sharing です。