C の性能・Makefile・lldb：キャッシュ順序の実測とクラッシュ解析

シリーズ：C 講座 第6回／全6回（上級）。 正しい C は書けるようになり、次は速くし、複数ファイルのプロジェクトとしてビルドし、ほかの人の環境で落ちたときにデバッグする必要がある方向けの記事です。読み終えると、同じ処理をする 2 つのループのどちらが速いかを予測して測れ、変更したファイルだけを正しく作り直す Makefile を書け、lldb でクラッシュの呼び出し履歴とローカル変数を取り出せるようになります。

組込みや研究室のコードでは、IDE ではなく Makefile とターミナルで開発することがまだ普通です。そこで毎日のように起きるのが次の 3 つです。同じ合計を求める 2 つのループが 50 倍違う。プロジェクトが古いオブジェクトファイルのまま「正常に」ビルドされ、でたらめな値を出す。クラッシュの報告が Segmentation fault: 11 の 1 行だけ。シリーズ最終回の今回は、3 つとも実際に動かしたプログラムで扱います。数値は実測、エラーメッセージはコピー、lldb のセッションも本物です。

実行環境： Apple clang 21.0.0、GNU Make 3.81（macOS 付属）、lldb-2103、Apple Silicon Mac（M1 Pro）、macOS。時間は clock_gettime(CLOCK_MONOTONIC) で 1 回の実行の中で 5 回測った最速値で、実行全体を 4 回繰り返し最後の値を引用しています。パスは ~/demo/… に短縮しました。学習の全体像はプログラミング学習ロードマップへ。

メモリの順序が効く理由：キャッシュラインを一段落で

CPU コアは RAM から 1 バイトずつ読みません。キャッシュライン（多くの x86-64 では 64 バイト、この M1 Pro は sysctl で hw.cachelinesize: 128）単位で小さく速いキャッシュに取り込み、前へ進むパターンを見ると次のラインを先読み（プリフェッチ）します。だからアドレス順に読めば最初のアクセス以降はほぼタダで、飛び回るとそのたびに遅い階層まで取りに行きます。C ではこれがそのまま見えます。2 次元配列 m[i][j] は行ごとに格納されるので、m[i][j] と m[i][j+1] は隣同士、m[i][j] と m[i+1][j] は 1 行分離れています。

実測：行順と列順で 54 倍

static int64_t sum_rows(const int *m) {            /* m[i][j]、j が内側：連続アクセス */
    int64_t s = 0;
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) s += m[(size_t)i * N + j];
    return s;
}
static int64_t sum_cols(const int *m) {            /* m[i][j]、i が内側：16KiB ずつ飛ぶ */
    int64_t s = 0;
    for (int j = 0; j < N; j++) for (int i = 0; i < N; i++) s += m[(size_t)i * N + j];
    return s;
}

N = 4096 なら行列は int が 1,680 万個、64MiB で、チップ上のどのキャッシュより大きくなります。2 つの関数は同じ数を違う順序で足します。

rows (i outer)             1.13 ms  (result 8583959407)
columns (j outer)         61.58 ms  (result 8583959407)

結果は同じで時間は 54 倍。行のループは 64MiB をおよそ 59GB/s で流し読みし、clang がベクトル化（1 命令で複数の int を加算）までしています。列のループは 1 回に 4096 × 4 = 16KiB 飛ぶので、キャッシュライン 1 本から役に立つ int は 1 つだけで、隣が必要になる前にラインが追い出されます。4 回の実行全体で、行は 1.13〜1.48ms、列は 60.5〜63.0ms の間でした。

よくある間違い： 数式に「各列 j について、各行 i について」と書かれているのを、そのまま二重ループに写すこと。列優先で格納する Fortran や MATLAB のコードを移植するときに特によく起きます。実際に起きること： 結果は正しいまま、黙って 50 倍遅くなります。修正： 最後の添字を一番内側のループにする。列方向の走査がホットパスなら、データを一度転置しておきます。

構造体の配列（AoS）と配列の構造体（SoA）

レコードにも同じ考えが当てはまります。粒子 1,000 万個を 2 通りで持ちます。

struct Particle { double x, y, z, vx, vy, vz, mass; int64_t id; };    /* 64 バイト */
struct Particles { double *x, *y, *z, *vx, *vy, *vz, *mass; int64_t *id; };

1 つ目は構造体の配列（Array of Structs、AoS）で、p[i].x の後ろに p[i].y、続いて粒子 i の残りが並びます。2 つ目は配列の構造体（Struct of Arrays、SoA）で、x の値が連続しています。x だけを合計すると：

AoS sum of x              10.87 ms  (result 4995000000)
SoA sum of x               9.35 ms  (result 4995000000)
AoS sum of x, 4 acc       10.67 ms  (result 4995000000)
SoA sum of x, 4 acc        2.35 ms  (result 4995000000)

最初の 2 行が正直な意外さです。SoA はわずか 14% しか速くありませんでした。単純な 2 つのループは、どちらもメモリ以外のところで詰まっていたのです。double の合計 s += … は鎖になっていて、加算のたびに前の加算の完了を待つ必要があり（浮動小数点の加算は数サイクルかかる）、浮動小数点の加算は結合法則が成り立たず順序を変えると結果が変わりうるので、コンパイラは勝手に並べ替えられません。そのため両方とも「加算のレイテンシごとに 1 回の加算」の速さで回っていました。

鎖を独立した 4 本の合計（s0 += x[i]; s1 += x[i+1]; …）に分けるとその制約が外れ、今度はメモリが速さを決めます。SoA は 2.35ms に下がり、AoS は使う 8 バイトごとに 64 バイトの粒子を丸ごとキャッシュに運ぶ（1 周で 640MB 対 80MB）ので 10.67ms のままでした。データ配置が効くのは、ループがメモリを待つほど速くなってから。 コードベースを SoA に作り替える前に、まず測ってください。（ここでは値が整数なので 4 本の合計でも結果は完全に一致します。任意の double では最後のビットが変わることがあります。）

計測プログラム全体（cache.c、1 ファイル）は英語版にあります。合計で約 1.3GB を確保するので、メモリの少ない機械では P を減らしてください。

変更したファイルだけ作り直す Makefile

.c ファイルが増えると、毎回手で全部コンパイルするのは遅くて間違えやすくなります。make は Makefile の規則（「ターゲット: 前提条件」と、その次の行にターゲットを作るコマンド＝レシピ）を読み、前提条件の方が新しいときだけターゲットを作り直します。3 ファイルのプロジェクト（main.c、stats.c、parse.c と stats.h）：

CC      = clang
CFLAGS  = -std=c17 -Wall -Wextra -O2 -g -MMD -MP
OBJS    = main.o stats.o parse.o

app: $(OBJS)
    $(CC) $(CFLAGS) -o $@ $(OBJS)

%.o: %.c
    $(CC) $(CFLAGS) -c $< -o $@

-include $(OBJS:.o=.d)

.PHONY: clean
clean:
    rm -f app $(OBJS) $(OBJS:.o=.d)

$@ はターゲット、$< は最初の前提条件、%.o: %.c はすべてのオブジェクトに対するパターンルールです。肝心なのは -MMD -MP で、clang がコンパイルのついでに main.c がインクルードしたヘッダの一覧を main.d に書き出し、-include がそれを Makefile に取り込みます。生成されたファイル：

main.o: \
  …/MacOSX.sdk/SDKSettings.json \
  main.c stats.h
…/MacOSX.sdk/SDKSettings.json:
stats.h:

（SDK の SDKSettings.json が依存に入るのは Apple clang の特徴です。Xcode を更新すると作り直されるという意味で、望ましい動きです。）初回ビルド、何も変えていないビルド、1 ファイル変更後のビルド：

$ make
clang -std=c17 -Wall -Wextra -O2 -g -MMD -MP -c main.c -o main.o
clang -std=c17 -Wall -Wextra -O2 -g -MMD -MP -c stats.c -o stats.o
clang -std=c17 -Wall -Wextra -O2 -g -MMD -MP -c parse.c -o parse.o
clang -std=c17 -Wall -Wextra -O2 -g -MMD -MP -o app main.o stats.o parse.o
$ ./app
count=3 mean=3.000
$ make
make: `app' is up to date.
$ touch parse.c && make
clang -std=c17 -Wall -Wextra -O2 -g -MMD -MP -c parse.c -o parse.o
clang -std=c17 -Wall -Wextra -O2 -g -MMD -MP -o app main.o stats.o parse.o

parse.o とリンクだけが走りました。make -j4 は互いに独立したコンパイルを並列に実行します。

Makefile の罠 3 つを再現

罠 1：TAB の代わりに空白。 レシピ行は本物の TAB で始める必要があります。エディタが空白を入れることがよくあります。GNU Make 3.81 のメッセージ：

Makefile.spaces:6: *** missing separator.  Stop.

6 行目が最初のレシピ行です。cat -t Makefile で本物のタブは ^I と見え、空白が見えたらそれがバグです。エディタで Makefile だけはタブを保つよう設定してください。

罠 2：ヘッダの依存がない。 何も失敗しないので一番危険です。同じ Makefile から -MMD -MP と -include を除いた版でビルドし、stats.h の構造体の先頭にフィールドを 1 つ足します。

struct stats { const char *label; long count; double sum; };   /* 元は { long count; double sum; } */

$ make -f Makefile.naive
make: `app' is up to date.

make は stats.h が関係することを知らないので、何も作り直しません。次にやりがちなこと、main.c を編集します（ここでは touch）：

$ make -f Makefile.naive
clang -std=c17 -Wall -Wextra -O2 -g -c main.c -o main.o
clang -std=c17 -Wall -Wextra -O2 -g -o app main.o stats.o parse.o
$ ./app
count=4621256167635550208 mean=3.000
exit=0

main.o は新しい配置、stats.o は古い配置を使っています。stats_add（古い配置）は count をオフセット 0、sum をオフセット 8 に書き、main（新しい配置）は count をオフセット 8 から読みました。そこには double の 9.0（1.5 + 2.5 + 5.0）のビットがあります。0x4022000000000000 = 4621256167635550208。警告もクラッシュもなく exit 0。依存を扱う Makefile で make clean && make すると count=3 mean=3.000 に戻りました。メモリ破壊とそっくりに見えるビルドシステムのバグで、「クリーンビルドしたら直った」はまさにこれを疑うべきときです。

罠 3：同じ 1 秒の中での変更。 ビルドの直後にすぐ parse.c を touch しました。

make: `app' is up to date.
parse.c 1794494800.980412000
parse.o 1794494800.929907233

parse.c は parse.o より 0.05 秒新しいのに、macOS の Make 3.81 は秒単位で比べて同じと見なしました。1 秒後の touch parse.c && make では作り直されました。普段の編集ではまず当たりませんが、ファイルを生成してすぐ make を呼ぶスクリプトや速い CI の段階では起こりえます。GNU Make はその機能付きでビルドされていれば 1 秒未満の時刻も比べますが、ここに入っている 3.81 はそうではありませんでした（ほかのビルドは試していません）。

lldb でクラッシュを追う

表から設定を読む小さなプログラムです。1 つの項目に値がありません。

#include <stdio.h>
#include <string.h>

struct entry { const char *key; const char *value; };

static const struct entry table[] = {
    { "host", "example.com" }, { "port", "8080" }, { "mode", NULL },  /* mode は値なし */
};

static const char *lookup(const char *key) {
    for (size_t i = 0; i < sizeof table / sizeof table[0]; i++)
        if (strcmp(table[i].key, key) == 0) return table[i].value;
    return NULL;
}

static size_t value_len(const char *key) {
    const char *v = lookup(key);
    return strlen(v);                     /* v が NULL だと落ちる */
}

int main(void) {
    const char *keys[] = { "host", "port", "mode" };
    for (int i = 0; i < 3; i++)
        printf("%s -> %zu chars\n", keys[i], value_len(keys[i]));
    return 0;
}

何の助けもなければ、得られる情報はこれだけです（パイプに流すと最初の 2 行すら出ません）。

bash: line 1: 77904 Segmentation fault: 11  ./crash
exit=139

終了コード 139 は 128 + 11、つまりシグナル 11 番の SIGSEGV です。-O0 -g（デバッグ情報あり、最適化なし）でビルドして lldb で実行します。-b はバッチモード、-o はコマンドの実行、-k はプロセスが落ちたときだけ実行するコマンドです。

clang -std=c17 -Wall -Wextra -O0 -g crash.c -o crash
lldb -b -o run -k bt -k "frame select 1" -k "frame variable" -k "frame select 2" -k "frame variable" -k kill ./crash < /dev/null

(lldb) run
host -> 11 chars
port -> 4 chars
Process 78194 stopped
* thread #1, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=1, address=0x0)
    frame #0: 0x0000000188df6ac4 libsystem_platform.dylib`_platform_strlen + 4
(lldb) bt
* thread #1, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=1, address=0x0)
  * frame #0: 0x0000000188df6ac4 libsystem_platform.dylib`_platform_strlen + 4
    frame #1: 0x00000001000005a0 crash`value_len(key="mode") at crash.c:18:12
    frame #2: 0x000000010000051c crash`main at crash.c:24:46
    frame #3: 0x0000000188a244e4 dyld`start + 6992
(lldb) frame select 1
frame #1: 0x00000001000005a0 crash`value_len(key="mode") at crash.c:18:12
-> 18       return strlen(v);                     /* crashes when v is NULL */
(lldb) frame variable
(const char *) key = 0x000000010000067a "mode"
(const char *) v = 0x0000000000000000
(lldb) frame select 2
(lldb) frame variable
(const char *[3]) keys = ([0] = "host", [1] = "port", [2] = "mode")
(int) i = 2

順に読みます。EXC_BAD_ACCESS (code=1, address=0x0) はアドレス 0 の読み出し、つまり NULL ポインタです。フレーム 0 は C ライブラリ（strlen）の中で、バグがそこにあることはまずありません。フレーム 1 が自分のコードで、key="mode" の value_len、frame variable で v = 0x0。フレーム 2 はループの 3 回目（i = 2）だったと教えてくれます。printf を 1 つも足さずに、画面 1 枚で診断完了。（バッチモードのメモ：最初は -k up を使い標準入力を開いたまま実行したところ終わらず、自分で終了させる必要がありました。< /dev/null で入力を閉じ -k kill で締めると、以後は毎回きれいに終わりました。）

-O2 -g でビルドすると、同じセッションが不親切になります。

    frame #1: 0x00000001000004b0 crash2`value_len(key=<unavailable>) at crash.c:18:12 [opt] [inlined]
warning: crash2 was compiled with optimization - stepping may behave oddly; variables may not be available.
(lldb) frame variable
(const char *) key = <no location, value may have been optimized out>
(const char *) v = 0x0000000000000000

[opt] [inlined]：関数が main に統合され、key はどのレジスタにも残っていません。デバッグはできれば -O0 で行い、出荷は -O2 -g にして利用者からのクラッシュ報告にも行番号が残るようにしましょう。

条件付きブレークポイントを使えば、悪いケースだけ、クラッシュの直前で止まります。

(lldb) breakpoint set -f crash.c -l 18 -c 'v == 0'
Breakpoint 1: where = crash`value_len + 28 at crash.c:18:19, address = 0x0000000100000598
(lldb) run
host -> 11 chars
port -> 4 chars
* thread #1, queue = 'com.apple.main-thread', stop reason = breakpoint 1.1
    frame #0: 0x0000000100000598 crash`value_len(key="mode") at crash.c:18:19
(lldb) frame variable
(const char *) key = 0x000000010000067a "mode"
(const char *) v = 0x0000000000000000

比較として、-fsanitize=address は同じクラッシュをデバッガなしでレポートにします。ERROR: AddressSanitizer: SEGV on unknown address 0x000000000000 … Hint: address points to the zero page. の後に #1 … in value_len crash.c:18、#2 … in main crash.c:24 が続きます。gdb に慣れている方は、bt はそのまま、frame variable は info locals に当たると考えてください（gdb はこの Mac にないので未実行）。

判断表：症状ごとの道具

限界とバージョンのメモ

• 時間はすべて Apple Silicon Mac（M1 Pro）1 台、Apple clang 21.0.0 -O2、実行内 5 回の最速値、全体 4 回の実行です。絶対値はメモリ系で変わり、54 倍という比も CPU ごとに違うはずですが、向きは同じです。
• 最初の節のキャッシュラインの大きさは sysctl の値と一般的な知識で、実測したのはループ全体の時間だけです。
• GNU Make 3.81 は 2006 年の版で、macOS はまだこれを同梱しています。最新の GNU Make（4.x）には .RECIPEPREFIX（TAB 以外の文字を使う）や「did you mean TAB instead of 8 spaces?」のヒントなどがあります。インストールも実行もしていません。
• -MMD -MP は make ではなく GCC／clang のフラグです。
• lldb の出力は整理し（停止後の逆アセンブル行を削除）、パスは短縮しました。PID やアドレスは手元の実行の値で、皆さんの環境では違います。

練習問題

1. 同僚の画像フィルタが float in[H][W] に対して for (x = 0; x < W; x++) for (y = 0; y < H; y++) out[y][x] = f(in[y][x]); と回しています。何を変え、速くなったことをどう証明しますか？
2. -MMD を使わずに、Makefile.naive に最小限なにを足せば stats.h が変わったときに 3 つのオブジェクトがすべて作り直されますか？

解答

1. 最後の添字 x が一番内側になるようにループを入れ替えます：for (y…) for (x…)。証明は、cache.c のような最速値を取る枠組みで、同じ固定シードの入力に対して -O2 で両方の時間を測り、出力（またはそのチェックサム）が一致することを確かめることです。
2. 1 行追加：$(OBJS): stats.h。Make 3.81 で確認しました。touch stats.h の後、make が main.o、stats.o、parse.o を再コンパイルしてリンクしました。欠点はこの一覧を手で保守しなければならないことで、だから -MMD -MP の方が良いのです。

C シリーズはここまでです。これらの道具を実際のデータ構造で使うならソートアルゴリズムの記事を、これから始める同僚にシリーズを勧めるなら第1回をどうぞ。

---

前回： 第5回：未定義動作と最適化 · 次へ： C の後の道はプログラミング学習ロードマップで