最適化の測り方 — 静的と動的は別物

この回の位置づけ

以降のすべての最適化の回が、この回で作った物差しを使う。 最初に作る理由がこれである。

なぜ測るのか

B1（定数畳み込みとピープホール）では「命令数が16%減った」と報告した。 しかし、その16%は本当に速くなったのだろうか。

int main() {
    int i; int s;
    s = 0;
    for (i = 0; i < 200; i = i + 1) { s = s + i; }
    return s % 256;
}

このプログラムが出力するアセンブリは70命令ほどである。 しかし、実行される命令は 7,840個ある。ループ本体が200回繰り返されるからである。

つまり、ループの外にある命令を1個消しても、ほとんど速くならない。 逆に、ループの中の1命令を消すと200命令分速くなる。 「命令数が減った」だけでは、どちらの話をしているのか分からない。

2つの物差し

どちらも意味がある。組み込み機器ではコードサイズ（静的）が制約になるし、 実行速度が問題なら動的を見る必要がある。

動的命令数の測り方

qemu には、実行した命令を記録する仕組みがある。

qemu-riscv64 -one-insn-per-tb -d exec,nochain ./prog

• -d exec は、実行のたびに Trace ... という行を出す
• 既定では複数命令をまとめた単位（トランスレーションブロック）ごとに出るので、 -one-insn-per-tb で1命令 = 1行にそろえる

出てくる行はこの形をしている。

Trace 0: 0x7fe594000100 [003411ef/000000000001038c/0202c078/00000201] _start
                                  ↑ 実行した命令のアドレス(PC)

落とし穴: libc が混ざる

そのまま数えると、loop_sum は 144,220命令になる。 自分のプログラムは7,840命令なので、95%が libc の起動処理である。

_start(libc) → 環境変数の準備 → ロケール初期化 → ... → main → ...

これでは自分の最適化の効果が埋もれてしまう。そこで、 自作した関数のアドレス範囲だけを数える。

1. アセンブリの .globl から自作関数の名前を集める
2. nm で実行ファイルの各シンボルのアドレスを引く
3. Trace 行の PC がその範囲に入っているものだけ数える

これで 144,220 → 7,840 に絞り込める。

ベンチマーク集

bench/ に5本用意した。以降の回でも同じものを使う。

いずれも .ans を持ち、test_runner.py で正しさを確認できる。 最適化した結果が正しいことの確認にも、そのまま使う。

実装

nm の呼び出し（our_symbol_ranges）と範囲判定（in_ranges）、 qemu の起動はスケルトンで用意してある。

python3 golden.py       # 5本のベンチマークを両方の物差しで測る

テスト

python3 check.py     # 数え上げの単体テスト(未実装は SKIP)
python3 golden.py    # ベンチマークの正しさ + 静的/動的の表

check.py の後半は、同じプログラムの反復回数だけを変えて測り、

• 動的命令数はほぼ2倍になる
• 静的命令数はほとんど変わらない

ことを確かめる。物差しが正しく機能していることの検証である。

測ってみると

教員の実装で golden.py を走らせると、こうなる。

ベンチマーク       静的      動的    増幅率
bubble             340     24023      71x
fib_rec             77     73993     961x
loop_sum            70      7840     112x
matmul             453     27958      62x
strops             243     77108     317x

fib_rec は静的にはいちばん小さい（77命令）のに、 動的にはいちばん大きい（73,993命令）。再帰が深く展開されるからである。 静的命令数だけを見ていたら、ここが重いとは分からない。

全構成の基準表 — O 系列の命令数はすべてここから読む

O3 以降の各回は「前」と「後」の表を出すが、その「前」がどの構成なのかは回ごとに違う。 そこで、5つの構成の実測値をここに1つだけ置く。 以降の回は、この表からの差分だけを語る。

列は累積である（右の列は左の列に1つ足したもの）。 O2（フローグラフ）と O5（生存解析）は解析だけを行い命令を減らさないので、列を持たない。

静的命令数。

ベンチマーク       素   +isel  +regalloc  +copyprop,dce  +layout
bubble            340    301        264            234      233
fib_rec            77     73         73             72       70
loop_sum           70     65         49             44       43
matmul            453    411        344            309      308
strops            243    225        192            176      173
合計             1183   1075        922            835      827

動的命令数。

ベンチマーク       素   +isel  +regalloc  +copyprop,dce  +layout
bubble          24023  20566      18824          16161    15952
fib_rec         73993  69061      69061          69060    68073
loop_sum         7840   7038       5032           4230     4030
matmul          27958  24606      21589          18814    18563
strops          77108  69066      59877          51875    50135
合計           210922 190337     174383         160140   156753

素から +layout まで通すと、静的 30.1%減・動的 25.7%減である。

素の出力は何でできているか

素の 1,183命令のうち 587命令（49.6%）が、コマ2 以来の push/pop の往復 （addi sp, sp, -8 / sd a0, 0(sp) / ld a1, 0(sp) / addi sp, sp, 8）である。 式の途中結果をメモリに逃がすたびに4命令を払っている勘定で、 出力のおよそ半分が値の往復に消えている。 これを減らすのが O4（変数をレジスタへ）と B2（式の途中結果をレジスタへ）の主題である。

# 自分の出力でも数えてみる（matmul は 242/453）
python3 optcc.py --passes '' O1_measure/bench/matmul.c \
    | grep -cE 'addi sp, sp, -?8$|(sd|ld) a[0-9]+, 0\(sp\)$'

発展課題

1. B1 と比べる: advanced/B1_fold_peephole/foldcc.py でコンパイルしたものを 同じ物差しで測り、静的16%減が動的では何%減になるか調べる
2. 関数ごとに測る: いまは自作コード全体をまとめて数えている。 nm の情報を使えば関数ごとに分けられる。どの関数が重いか（プロファイル）が分かる
3. 実行時間と比べる: time qemu-riscv64 ./prog の実測時間と動的命令数を比べる。 命令数に比例するか。しないとすればなぜか（メモリアクセスの速さの違い）
4. 命令の種類別に数える: ロード/ストア、分岐、算術に分けて数える。 最適化の狙いどころが見えてくる

この資料の原稿を見る