メカニカル・シンパシー：ハードウェアに優しいコード

はじめに — 同じ計算量、違う速度
メモリ階層 — 速度の崖
キャッシュライン — キャッシュは一つずつ運ばない
データ局所性 — 配列 vs リンクリスト
アクセスパターンがすべて — 行優先 vs 列優先
分岐予測 — CPUは未来を推測する
フォルスシェアリング — 見えない競合
データ配置 — SoA vs AoS
予測可能なアクセスパターンが核心だ
いつ気にかけ、いつ無視するか
おわりに
参考資料

はじめに — 同じ計算量、違う速度

アルゴリズムの授業は、時間計算量でコードを判断せよと教えます。O(n)はO(n²)より速い、定数倍は無視せよ。この見方はおおむね正しく有用です。しかし実務で性能を掘り下げると、奇妙な壁にぶつかります。明らかに同じO(n)なのに、あるコードが別のコードより10倍、ときには50倍速いのです。どちらも要素を一度ずつしか走査していないのに、です。

この差はアルゴリズムではなくハードウェアから来ます。現代のCPUは、私たちが想像する単純な計算機ではありません。複数層のキャッシュ、分岐を先読みする予測器、複数の命令を重ねて実行するパイプラインで満ちた複雑な機械です。この機械の動き方を理解し、それに合わせてコードを書く態度を**メカニカル・シンパシー(mechanical sympathy)**と呼びます。もともとF1ドライバーのジャッキー・スチュワートが「機械を理解するドライバーのほうが速く走る」という意味で使った言葉ですが、ソフトウェアにもそのまま当てはまります。

この記事は、ハードウェアに優しいコードがなぜ速いのか、そしてどうそういうコードを書くのかを扱います。核心となるテーマはキャッシュ、データ局所性、分岐予測、フォルスシェアリング、そしてデータ配置です。

メモリ階層 — 速度の崖

性能を理解する出発点は、メモリが一つではないという事実です。CPUと主記憶(RAM)の間には複数層のキャッシュがあり、各層は速度とサイズが劇的に異なります。上へ行くほど速く小さく、下へ行くほど遅く大きくなります。

  階層          おおよそのレイテンシ  相対速度         サイズ
  ------------------------------------------------------------
  レジスタ      ~0.3 ns              1倍 (基準)       数百バイト
  L1キャッシュ  ~1 ns                約3倍遅い        32〜64 KB
  L2キャッシュ  ~4 ns                約10倍遅い       256KB〜1MB
  L3キャッシュ  ~12 ns               約40倍遅い       数〜数十MB
  主記憶        ~100 ns              約300倍遅い      数〜数百GB
  SSD           ~100,000 ns          約30万倍         数百GB〜数TB

この表で最も重要なのは、層と層の間隔が崖のように急なことです。L1キャッシュからデータを読むのと主記憶から読むのとは、およそ100倍の差です。CPUにとって100nsは永遠にも等しいです。その時間があれば数百個の命令を実行できるのですから。

このレイテンシを人間の時間感覚に例えると実感が湧きます。

  CPU 1サイクルを1秒とすると:
  L1キャッシュ アクセス  = 約3秒
  L2キャッシュ アクセス  = 約10秒
  L3キャッシュ アクセス  = 約40秒
  主記憶 アクセス        = 約5分
  SSD アクセス           = 約数日

つまりCPUが主記憶を待つのは、人間で言えばコーヒーを一杯飲みに行って戻ってくるようなものです。だから現代の性能最適化の相当な部分は「計算を減らすこと」ではなく「メモリ待ちを減らすこと」、すなわちデータをできるだけキャッシュの中に置くことです。計算はすでに十分速いのです。遅いのはデータを取ってくることです。

キャッシュライン — キャッシュは一つずつ運ばない

キャッシュを理解する核心の概念がキャッシュライン(cache line)です。CPUがメモリからデータをキャッシュに持ってくるとき、私たちが要求したその1バイトだけを持ってくるのではありません。代わりに、そのバイトを含む固定サイズの塊を丸ごと持ってきます。この塊がキャッシュラインで、ほとんどの現代CPUで64バイトです。

  int(4バイト)一つを要求しても:

  メモリ:  [.. 要求した int を含む64バイトのライン丸ごと ..]
                        |
                        v
  キャッシュ: [64バイトのライン全体が載る]

  つまり近くのデータ60バイトも「おまけで」キャッシュに入る

この事実が途方もない結果を生みます。あるデータにアクセスすると、その隣にあったデータがタダでキャッシュに一緒に載ります。だからメモリ上で互いに近くにあるデータを続けてアクセスすると、大半がすでにキャッシュにあってとても速いです。逆にメモリのあちこちに散らばったデータをアクセスすると、毎回新しいキャッシュラインを持ってこねばならず遅いです。

これが次に話すデータ局所性の物理的な根拠です。「近くにあるデータを続けて使え」という助言は、結局「キャッシュライン一つで何度も得をせよ」という意味です。

データ局所性 — 配列 vs リンクリスト

データ局所性の力を最も鮮明に示す例が、配列とリンクリストの比較です。教科書的には二つにトレードオフがあります。配列はランダムアクセスが速く挿入が遅い、リンクリストは挿入が速くランダムアクセスが遅い。しかし実際の走査性能を測ると、リンクリストが配列よりはるかに遅い場合が多く、挿入・削除が頻繁な状況ですら配列が勝つことがよくあります。理由はキャッシュです。

  配列: 要素がメモリに連続して並ぶ
  [e0][e1][e2][e3][e4][e5][e6][e7] ...
   |-- キャッシュライン一つに複数の要素が一緒に来る --|
   走査時はほぼキャッシュヒット → 速い

  リンクリスト: ノードがメモリのあちこちに散らばる
  [node2] ......... [node0] ..... [node3] ... [node1]
      各ノードへ行くたびにポインタを追ってジャンプ
      ほぼキャッシュミス → 遅い (毎回メモリ往復)

配列は要素をメモリに連続して配置します。だから配列を最初から最後まで走査すると、キャッシュライン一つが複数の要素を運んでくるので、大半のアクセスがキャッシュヒットです。おまけにCPUはこの逐次的なパターンを検知し、次に必要になるデータを先に持ってくるプリフェッチ(prefetch)までします。

リンクリストは違います。各ノードはヒープのあちこちに散らばって確保され、ノード同士はポインタでのみつながります。だからリストを走査するにはポインタを追ってメモリのあちこちにジャンプせねばなりません。ノードごとに新しいキャッシュラインを持ってこねばならず、しかも次のノードがどこにあるかは現在のノードを読まないとわからないので、プリフェッチも難しいです。結果はキャッシュミスの連続です。

核心の教訓はこれです。ビッグオー記法はアクセス回数だけを数えますが、実際の速度はそのアクセスがキャッシュヒットかミスかに大きく左右されます。逐次的に走査する作業なら、連続メモリを使う配列(またはベクタ、動的配列)が大半で勝ちます。

アクセスパターンがすべて — 行優先 vs 列優先

同じデータでも、どんな順序でアクセスするかで速度が大きく分かれます。2次元配列を走査する古典的な例を見ましょう。大半の言語(C、NumPyの既定など)は2次元配列を行優先(row-major)でメモリに格納します。つまり一つの行の要素がメモリに連続して並びます。

import numpy as np
A = np.zeros((10000, 10000))

# 方式1: 行優先で走査 (メモリ順序と一致)
total = 0.0
for i in range(10000):
    for j in range(10000):
        total += A[i][j]     # 内側ループが連続メモリを走査 → 速い

# 方式2: 列優先で走査 (メモリ順序と食い違う)
total = 0.0
for j in range(10000):
    for i in range(10000):
        total += A[i][j]     # 各アクセスが一行ぶんジャンプ → キャッシュミス激増

二つのコードは正確に同じ要素を、正確に同じ回数だけ足します。アルゴリズム的に完全に同一です。ところが実際には方式1が方式2より数倍速いです。言語とサイズによっては5倍から10倍以上の差になることもあります。

理由はキャッシュラインです。方式1は内側ループがメモリに連続して並ぶ一行を順に走査するので、キャッシュライン一つが複数の要素を運んできて大半がヒットします。方式2は内側ループが列を下っていきますが、行優先の格納では同じ列の要素はメモリ上で一行ぶん(ここでは1万個)離れています。だからアクセスごとに新しいキャッシュラインを持ってこねばならず、持ってきたラインの残り63バイトは使われもせず捨てられます。

教訓は明確です。データを格納された順序でアクセスせよ。多次元配列なら、メモリレイアウト(行優先か列優先か)を知り、一番内側のループが連続メモリを走査するようにループ順序を合わせねばなりません。この単純な原則一つが、しばしばどんなアルゴリズム改善よりも大きな性能向上をもたらします。

分岐予測 — CPUは未来を推測する

現代のCPUが速いもう一つの秘密がパイプライニングです。CPUは命令を一つ終えてから次を始めるのではなく、複数の命令を組み立てラインのように重ねて処理します。ところがここに問題があります。ifのような分岐に出くわすと、CPUは条件の結果が出る前に「次にどちらの命令をパイプラインに入れるか」を決めねばなりません。

そこでCPUは分岐予測器(branch predictor)を使います。過去のパターンを見て「この分岐はおそらく真(または偽)だろう」と推測し、その側の命令を先にパイプラインに詰めて実行を始めます。推測が当たれば何の損もなく速く進みます。しかし外れると、先に詰めて実行していた命令を全部捨てて(パイプラインフラッシュ)、正しい側からやり直さねばなりません。この罰則が数十サイクルに達します。

この事実は有名な観察につながります。ソートされたデータを処理するほうが、ソートされていないデータを処理するより速いことがある、というものです。

# 大きな配列でしきい値より大きい値だけ合算
threshold = 128
total = 0
for x in data:
    if x >= threshold:      # この分岐の予測可能性が速度を左右する
        total += x

もしdataがソートされていれば、この分岐はしばらくずっと偽で、ある地点からずっと真になります。予測器はこの規則的なパターンを簡単に学習し、ほぼ常に当てます。逆にdataがランダムなら、分岐結果が予測不能に跳ねて予測器が半分ほど外します。外すたびにパイプラインがフラッシュされ、同じコードが数倍遅くなることがあります。

ここから得られる実務的な洞察がいくつかあります。第一に、予測可能な分岐は安く、予測不能な分岐は高いです。第二に、ときには分岐そのものをなくすこと(分岐なしコード, branchless)が有利です。例えば条件によって値を足すか否かを、分岐の代わりに算術で表せば、誤予測の罰則を避けられます。

# 分岐の代わりに算術で (誤予測なし)
# (x >= threshold) は True/False = 1/0 として扱われる
total += x * (x >= threshold)

もちろん分岐なしコードが常に速いわけではなく、可読性を損なうこともあるので、無条件に適用するものではありません。核心は、ホットループ(hot loop)の中の予測不能な分岐が隠れた性能泥棒でありうるという認識です。

フォルスシェアリング — 見えない競合

マルチスレッドコードで特に巧妙な性能の落とし穴がフォルスシェアリング(false sharing)です。複数のスレッドがそれぞれ別の変数を各自修正していて、論理的には何の衝突もないのに、性能が急激に落ちる現象です。犯人はまたもキャッシュラインです。

先に見たように、キャッシュは64バイトのライン単位で動きます。ところがCPUコアごとに自分のキャッシュがあり、複数のコアが同じデータをキャッシュするときは一貫性(coherence)を保たねばなりません。あるコアがあるキャッシュラインを修正すると、他のコアが持つ同じラインの写しは無効化(invalidate)されます。

問題は、別々の変数でも偶然同じキャッシュラインの中にあると、まるで同じデータを取り合っているかのように扱われることです。

  スレッドAが counter[0] を、スレッドBが counter[1] を修正するとしよう。
  二つの変数が同じ64バイトのキャッシュラインの中にあると:

  [ counter[0] | counter[1] | ... 同じ64バイトのライン ... ]
       ^A が書く        ^B が書く

  A が書くたびに B のキャッシュラインが無効化され、
  B が書くたびに A のキャッシュラインが無効化される。
  二つのスレッドは論理的に独立なのに、キャッシュラインをピンポンして互いを遅くする。

これがフォルスシェアリングです。本当にデータを共有しているのではなく(各自別の変数)、キャッシュラインを共有しているために生じる偽の競合です。症状は厄介です。コードは完璧に正確に動くのに、スレッドを増やしても性能が上がらないか、かえって下がります。

解決策は、問題の変数たちを別々のキャッシュラインへ押し出すことです。よくパディング(padding)を入れて、各スレッドのデータが独立したキャッシュラインを占めるようにします。

  解決: 各スレッドのデータの間にパディングを入れてラインを分離

  [ counter[0] + パディング(ラインを埋める) ][ counter[1] + パディング ]
        スレッドA専用のライン                   スレッドB専用のライン

  もう互いのラインに触れないので、ピンポンが消える

フォルスシェアリングは目に見えにくく診断が厄介です。マルチスレッドにしたのにスケールしないなら、スレッドたちが触るデータが偶然同じキャッシュラインに集まっていないか疑ってみる価値があります。

データ配置 — SoA vs AoS

データをメモリにどう配置するかを設計レベルで扱うテーマが、構造体の配列(Array of Structures, AoS)と配列の構造体(Structure of Arrays, SoA)です。同じデータを入れても、この二つはキャッシュ効率が大きく異なります。

AoSは私たちが自然に思い浮かべる方式です。各個体を構造体にし、その構造体を配列に入れます。

  AoS (構造体の配列):
  struct Particle { float x, y, z; float mass; ... };
  Particle particles[N];

  メモリ: [x0 y0 z0 m0][x1 y1 z1 m1][x2 y2 z2 m2] ...
          一つの粒子の全フィールドがくっついている

SoAは逆に、フィールドごとに別々の配列を作ります。

  SoA (配列の構造体):
  struct Particles { float x[N]; float y[N]; float z[N]; float mass[N]; };

  メモリ: [x0 x1 x2 x3 ...][y0 y1 y2 ...][z0 z1 z2 ...] ...
          同じフィールド同士が連続してくっついている

なぜこの差が重要なのでしょうか。ある作業が特定のフィールドだけ大量に走査する場合を考えましょう。例えばすべての粒子のx座標だけを更新する物理シミュレーションのループがあるとします。

AoSではx座標がメモリ上で互いに離れています(間にy、z、massが挟まっているので)。だからxだけ走査してもキャッシュラインには使わないy、z、massが一緒に付いてきて、キャッシュ空間が無駄になります。一方SoAではx座標が一つの配列に連続してくっついているので、キャッシュラインがxだけでぎっしり埋まって来ます。キャッシュが倹約的に使われ、逐次アクセスなのでプリフェッチもよく効きます。またSoAはSIMD(一つの命令で複数のデータを処理)のベクトル化にも有利です。

  x座標だけ大量に処理するとき:

  AoS: キャッシュラインに x 一つ + 無駄になる y,z,mass  → キャッシュ効率が低い
  SoA: キャッシュラインが x だけでぎっしり             → キャッシュ効率が高い、SIMD親和的

ただしSoAが常に正しいわけではありません。一つの個体の全フィールドをまとめて頻繁に扱うなら(例: 粒子一つを丸ごと読んで処理)、AoSのほうがその個体のフィールドを一つのキャッシュラインに集めてくれて有利です。核心はアクセスパターンです。「フィールド単位で走査するか、個体単位で走査するか」を見て配置を決めねばなりません。ゲームエンジン、物理エンジン、データ処理システムでSoAがよく選ばれる理由は、こうしたシステムのホットループが大抵、特定のフィールドだけを大量に走査するからです。

予測可能なアクセスパターンが核心だ

ここまでの話を貫く一つの原理があります。CPUとキャッシュは予測可能な逐次アクセスを愛し、ランダムで散らばったアクセスを嫌う、ということです。

CPUにはハードウェアプリフェッチャ(prefetcher)があります。これはメモリのアクセスパターンを観察し、規則的な逐次アクセスを検知すると、次に必要になるデータを先にキャッシュへ引き込みます。だから配列を順に走査するような予測可能なパターンでは、データが必要になる前にすでにキャッシュに到着しています。プリフェッチャの助けでメモリのレイテンシがほぼ隠されます。

逆にアクセスがランダムだと、プリフェッチャがパターンを読めず助けられません。ポインタをあちこち追う data構造(リンクリスト、木、ハッシュテーブルのチェイニング)や、インデックスがばらばらのアクセスはプリフェッチャを無力化します。

ここから実務の原則を整理できます。

逐次的にアクセスせよ. できるならデータを格納された順序で走査せよ。
連続メモリを好め. 散らばったノードより連続した配列がキャッシュにもプリフェッチャにも有利。
アクセスパターンに合わせてデータを配置せよ. よく一緒に使うデータは近く(同じキャッシュライン)に置き、フィールド単位で走査するならSoAを検討せよ。
ホットループの分岐を予測可能にせよ. 必要ならソートするか分岐をなくせ。
マルチスレッドではフォルスシェアリングを避けよ. スレッドごとのデータを別のキャッシュラインに分離せよ。

これらの原則はすべて一つの態度に収束します。コードを書くとき、データがメモリでどう配置され、どんな順序でアクセスされるかを意識すること。それがメカニカル・シンパシーの実践です。

いつ気にかけ、いつ無視するか

ここまで読んで「ではすべてのコードをこう最適化すべきか」と思うかもしれませんが、そうではありません。メカニカル・シンパシーは常に適用する規則ではなく、必要なときに取り出す道具です。

大半のコードは性能がボトルネックではありません。可読性と正確性のほうがはるかに重要で、早すぎる低レベル最適化はコードを複雑にするだけです。ドナルド・クヌースの有名な言葉のように「早すぎる最適化は諸悪の根源」です。だから第一の原則は常に計測です。プロファイラで実際のホットスポットを見つけ、そこだけに集中せねばなりません。

メカニカル・シンパシーが本当に重要になる場所は明確です。膨大なデータを繰り返し処理するホットループ、ゲーム・物理・グラフィックスのリアルタイムレンダリング、高頻度取引や大規模データ処理のようにレイテンシがそのままコストになるシステムです。こうした場所では、アルゴリズムの計算量をすでに磨いた後でも、キャッシュ最適化で数倍の追加の得を得られます。

バランスの取れた態度はこうです。普段は明確で単純なコードを書きつつ、ハードウェアがどう動くかは理解しておくこと。そうすれば本当に性能が必要な瞬間に、どこをどう手直しすべきかがわかります。メカニカル・シンパシーはすべてのコードに適用する強迫ではなく、必要な瞬間に発揮する眼力です。

おわりに

同じ時間計算量のコードが実際には数十倍も違う理由は、コンピュータが教科書の中の抽象的な計算機ではなく、キャッシュとパイプラインと予測器で満ちた物理的な機械だからです。メモリ階層には速度の崖があり、キャッシュはライン単位で動き、データ局所性が走査速度を左右し、分岐予測がホットループの成否を分け、フォルスシェアリングがマルチスレッドのスケールを阻み、データ配置(AoSとSoA)がキャッシュ効率を決めます。

メカニカル・シンパシーは、この機械の心を汲んでコードを書く態度です。データを連続して置き、逐次的にアクセスし、分岐を予測可能にし、アクセスパターンに合わせて配置すること。このすべては結局「ハードウェアが好む方式でデータを扱え」という一つの原理に要約されます。

ビッグオー記法は今なお貴重な出発点です。しかしその下には、それだけでは説明できない性能の世界があります。その世界を理解する開発者は、同じアルゴリズムでもはるかに速いコードを書きます。機械を理解するドライバーがより速く走るように、です。

参考資料

Mechanical Sympathy (Martin Thompson のブログ): https://mechanical-sympathy.blogspot.com/
What Every Programmer Should Know About Memory (Ulrich Drepper): https://people.freebsd.org/~lstewart/articles/cpumemory.pdf
Latency Numbers Every Programmer Should Know: https://gist.github.com/jboner/2841832
Data-Oriented Design (Richard Fabian): https://www.dataorienteddesign.com/dodbook/
Agner Fog — Software optimization resources: https://www.agner.org/optimize/