PGO を hack して Go の Inline Hint に使う

Go には //go:noinline はあるが //go:inline はない。PGO のホットな call site はインライン予算が 80 から 2000 に上がるので、コメントから偽の CPU プロファイルを吐けば実質 //go:inline になる。その実験として inlinehint を作った。

Go 1.20 で PGO が入ったときから、発想自体はありコンパイラがプロファイルをどうマッチするかを正確に再現するのが面倒で放置していたが、LLM にコンパイラのソースを読ませたら一気に書けた。

背景

Go の inline はコストモデルで決まる。関数本体の AST ノードを数え、普通は 80 を超えると呼び出しのままになる。for が1つあるだけで余裕で超える。

directive 自体は何度か提案されている。#21536 は //go:inline を求める issue で閉じられている。 Russ Cox のコメントはおおむねこう。

ソースに最適化の指示を書くのは Go のやり方ではない。コンパイラを賢くする。プログラマをチューニング AI にしない。inline は C の古い register と同じで、コンパイラが決めるべきことを人が言っている。外れた具体例があれば bug を出せ。

directive は実装コストも高い。defer を含む関数がインラインできない。「インラインされなかったらビルドを落とす」すら入っていない。

なので 80 を超えないようにコードを歪めるハックが使われたりする。 名前付き戻り値にするとコストが下がってインラインされる、というのは #38419 にある。for を goto に書き換えるのは runtime でもやっていて、#14768 や #21536 でも話題になっている。巨大な関数のままにするか、呼び出し側を assembly で書くか。

インラインをしてもらいたい時はある。呼び出しが消えると、その先で定数畳み込みや escape analysis が効くことがある。効かないこともある。効くかどうかは -gcflags=-m=2 とベンチマークを見ないと分からない。

PGO が出てから

Go 1.20 で PGO のプレビューが入り、1.21 で GA になった。CPU プロファイルを食わせると、ホットな call site のインライン予算が 2000 になる。ホット判定はエッジ重みの CDF 上位 99%。プロファイルに載っているエッジだけなら、全部ホットになる。

つまりコンパイラはすでに「この呼び出しはホットだから大きくてもインラインしてよい」という口を持っている。本物のプロファイルの代わりに、コメントで印を付けた呼び出しだけを載せた pprof を渡せばいい。

必要なのは、コンパイラがプロファイルから読むキーをソースから再現することだけ。

• 呼び出し元・先のリンカ名
• call site の行オフセット（呼び出しの行 − func キーワードの行）
• Function.start_line（Go 1.20 以降の pprof に入っている）

リンカ名は objabi.PathToPrefix(pkgpath)+"."+name。package main は import path ではなく main.Foo としてコンパイルされる。メソッドは pkg.(*T).M、クロージャは pkg.F.func1、init は pkg.init.0。ジェネリックの実体化名 Foo[go.shape.int] はソースから正確に出せない。

この周辺を手で揃えるのが面倒で、PGO が出てから手をつけていなかった。

何をしているか

関数、または呼び出しのところにコメントを書く。

//inlinehint
func fat(x int) int {
    // ...
}

func run() int {
    return fat(42)
}

関数に付けると、ロードしたパッケージ内の静的な呼び出しが全部ホットになる。特定の呼び出しだけなら、その行の上に書く。

func run() int {
    //inlinehint
    return fat(42)
}

//go:inline も同じ意味として読める。gocheckcompilerdirectives が未知の //go: を落とすので、普段は //inlinehint の方がよい。重みも付けられる。

//inlinehint weight=10000
foo()

//go:fix inline とは別物。//go:fix inline and the source-level inliner にある通り、あちらは gopls / go fix がソース上の呼び出しを関数本体で置き換える指令で、コンパイラのインラインとは関係ない。API の移行用で、最適化の指示ではない。defer を含む関数はソース側でも呼び出しを消せず、go fix はそういう呼び出しを触らない。

使い方

go install github.com/orisano/inlinehint@latest

inlinehint ./...
inlinehint -o cmd/app/default.pgo ./...

go build -pgo=default.pgo ./cmd/app

default.pgo を main パッケージのディレクトリに置けば go build ./cmd/app でも読む。Go 1.21 以降の -pgo=auto がそれ。

手元の例では、sink を3回呼ぶ fat のコストは 188 で、通常の予算 80 を超える。

./main.go:8:6: cannot inline fat: function too complex: cost 188 exceeds budget 80

作られたプロファイルを食わせると以下のようになる。

hot-node enabled increased budget=2000 for func=main.fat
./main.go:9:6: can inline fat with cost 188 as: func(int) int { ... }
hot-budget check allows inlining for call main.fat (cost 188) at ./main.go:17:12 in function main.run
./main.go:17:12: inlining call to fat

-gcflags=-m=2 に -d=pgodebug=1 を足すと hot-budget check allows inlining が出る。

inline にしたあとの呼び出し元は大きくなる。上の例では fat を取り込んだ run がコスト 192 になり、今度は run 自身が inline にできなくなった。呼び出しが消えることと、呼び出し元がインライン対象で残ることの両方を見ることが必要。

コンパイラが何をマッチするか

pprof のサンプルは葉が callee、その上が caller。コンパイラはグラフのエッジを (caller名, callee名, CallSiteOffset) で持つ。オフセットは呼び出し行から関数開始行を引いた値。関数の上に行を足しても、オフセットは変わらない。

ホットはエッジ重みの CDF 上位 99%。このツールが吐くプロファイルは印を付けたエッジしかないので、全部ホットになる。ホットな callee は CanInline の予算が 2000 になり、ホットな call site はコスト 2000 までインラインされる。

呼び出し元がすでに 5000 ノードを超える「大きな関数」だと、ホットでも予算は 20 のまま。#17566 と #26546 のコードサイズ対策。

PGO は //go:noinline を上書きしない。recover、go、defer、本体のない関数、interface method も inline にしない。コスト 2000 超えは結局 inline にできない。

限界

ジェネリックの実体化名はソースから正確に出せない。元の名前を出して warning を出す。

コンパイラを賢くする代わりに、人がホットだと与えている。#21536 で拒否されたものを PGO を悪用することで実現してしまっている。

リンク

• https://github.com/orisano/inlinehint
• Profile-guided optimization in Go 1.21
• //go:fix inline and the source-level inliner
• Proposal: cmd/compile: add a go:inline directive #21536

LZMA SDK のデコーダーを Go に移植した

golzma という Pure Go (+ asm) な LZMA/LZMA2 のデコーダを作った。LZMA SDK の最適化済み asm を Go の asm に移植することで、C 実装と同等の速度を実現している。本記事ではそこに至るまでの経緯と、いくつか副産物として作ったツールについて書く。

背景

Go の LZMA デコーダは LZMA SDK と比較して遅い。

Go で書かれた LZMA のデコーダといえば ulikunitz/xz がデファクトで、bodgit/sevenzip などもこれを利用している。ただこの実装は LZMA SDK の C/C++/asm 実装と比べると遅い。

そこで以前 ulikunitz/xz を小手先で最適化した fork (orisano/xz) を作り、本家に PR も出した。しかし ulikunitz/xz は v2 への rewrite が進行中だったためマージはされず、v2 に rebase しようと試みたところ手元のデータで無限ループが発生し、原因の追究に時間を割けないまま放置することになった。

その後 kulaginds/lzma という、もっと速い実装も出てきたが、それでも kulaginds/lzma の README のベンチマークで触れられている通り、Go 実装は LZMA SDK (C, C++, asm) の実装に対して 2 倍近く遅い。

なぜ Go 実装は LZMA SDK と比較して遅いのか

まずプロファイルを取って、どこで差がついているのかを見た。

• 最適化された asm が使われている
• hot path がレジスタを満遍なく使ってメモリ読み込みを最小限にしている
• csel (conditional select) を適切に使って分岐を消している

という点が大きい。特に LZMA の RangeCoder はビットごとに条件分岐が大量に走るので、ここで csel 系の命令が効くかどうかでだいぶ変わる。

Go でも、コンパイラが csel を生成してくれるようにコードを書き換えると、実際に速くなる。だがこれは

• コンパイラの最適化挙動に強く依存していて、いつ速くなったり遅くなったりするか分からない
• 結果として、人が読むには結構不自然なコードになる

という問題がある。再現性のある最適化として手元に残しづらい。

また、hot path でレジスタを使い切るのは現代のコンパイラでも普通に難しい。少なくとも Go コンパイラに「LZMA SDK の asm と同じレベルのレジスタ配置」を期待するのは現実的ではない。

純粋に速度を出すだけなら cgo で LZMA SDK を呼べばよいのだが、cgo を使うと cross build が面倒になる。なので Go + asm の範囲でなんとかしたい。

asm を移植することにする

ということで、asm を移植してしまおうと決めた。

とはいえいくつか問題がある。

Go の asm 関数は inline 化できない

Go の asm で実装された関数は inline 化されない。なので「小さな処理だけを asm 化して、それを大量に呼び出す」というやり方をすると、呼び出しオーバーヘッドの方が勝って逆に遅くなることが多い。今回のように hot loop を asm 化するなら、loop ごとまるごと asm 化する必要がある。

Go の asm には macro がない

LZMA SDK の asm (amd64 / arm64 両方) は macro が使われていて、Go の asm にそのまま貼り付けることはできない。 「macro 展開を手でやって貼る」というのも考えたが、可読性とメンテナンス性が悪くなる。

こういう時は mmcloughlin/avo のような Go の asm を Go コードから生成するライブラリを使いたくなる。が、avo の arm64 対応は長いこと pending になっていて、arm のレイオフの影響などで一旦中止になっている。今回は amd64 だけでなく arm64 もターゲットにしたかったので、avo は使えない。

goasmpy を作る

そこで herumi/s_xbyak のような、「スクリプト言語から asm を出力する」レイヤーを Go asm 向けに自作することにした。それが orisano/goasmpy で、

• amd64 と arm64 に対応
• Python で Go の asm を出力する。Python を macro として使える
• 今回の移植に必要な命令しか実装しない
• Go asm 特有のクセ (擬似命令、フレームポインタ、R28 などのレジスタ予約など) はできるだけ隠蔽する

という方針で作った。

LZMA SDK 側の macro を、Python の関数として書き直してしまえば、本体の処理ロジックは LZMA SDK の asm にかなり近い形のまま移植できる。実際 golzma の gen_lzmadec_amd64.py / gen_lzmadec_arm64.py を見てもらうと、元の LzmaDecOpt.asm / LzmaDecOpt.S と対比しやすい構造になっていると思う。

結果

そうやってできたのが orisano/golzma で、

• cgo 不使用なので cross build が容易
• amd64 / arm64 では LZMA SDK の asm 版とほぼ同等の速度
• それ以外のアーキテクチャでは pure Go の fallback が動く

という構成になっている。LZMA 単体だけでなく LZMA2 ストリームのデコーダも入れてあるので、7z のようなフォーマットから呼び出す用途でも使えるはず。

使ってみてほしい

正直まだ十分にテストできているとは言えない。fuzz テストや手元のデータでは動いているが、世の中の "野良 LZMA データ" は色々なものがある。

• 性能が実際どうだったか (特に arm64 環境)
• デコードできない / 結果が合わないケースがあったか
• API がイケてないところ

など、使ってみて何かあれば issue や感想を教えてもらえると嬉しい。

• https://github.com/orisano/golzma
• https://github.com/orisano/goasmpy

Benchmarks Game mandelbrot: Rust の `[f64; 8]` が C++ の intrinsics より 1.4 倍遅いのはなぜか

前回の fannkuch-redux に続き、The Benchmarks Game の mandelbrot で C++ と Rust の性能差を調査した。

結論から言うと、Benchmarks Game の上位実装は言語によらず SIMD intrinsics をしっかり書いているものが占めている。Rust でも intrinsics を使えば C++ と同等の性能が出る。言語間の差に見えるものの正体は、intrinsics を使っているかどうかの差であることが多い。本記事では、intrinsics を使わずに [f64; 8] の要素ごと演算で書いた場合になぜ 1.4 倍遅くなるのか、その原因と対策を掘り下げる。

環境

項目	値
CPU	Intel Core i7-8650U (Kaby Lake R)
target-cpu	ivybridge (AVX のみ、AVX2 なし)
rustc	1.94.0 (LLVM 21.1.8)
g++	15 (Debian 12.2.0-14)
OS	Linux 6.1.0-26-amd64
題材	mandelbrot 16000×16000

ベンチマーク結果

best of 5 runs

実装	Time	Instructions	L1-dcache-loads	vs C++
C++ (__m256d intrinsics)	0.51s	12.6G	140M	1.00x
Rust (__m256d intrinsics)	0.52s	13.1G	365M	1.02x
Rust (std::simd, nightly)	0.52s	12.8G	237M	1.02x
Rust ([f64; 8] trait impl)	0.71s	20.5G	956M	1.39x

Rust でも std::arch::x86_64 の intrinsics を使えば C++ と同等の性能が出る。問題は [f64; 8] に対する要素ごとの演算を trait impl で書いた場合に 1.39 倍遅くなること。

元のコード

Benchmarks Game に投稿されている Rust 実装 (#6) がベース。8ピクセルを [f64; 8] で同時処理する。

#[derive(Clone, Copy)]
#[repr(align(32))]
struct F64x8([f64; 8]);

impl Mul for F64x8 {
    fn mul(self, rhs: F64x8) -> F64x8 {
        F64x8([
            self.0[0] * rhs.0[0], self.0[1] * rhs.0[1],
            self.0[2] * rhs.0[2], self.0[3] * rhs.0[3],
            self.0[4] * rhs.0[4], self.0[5] * rhs.0[5],
            self.0[6] * rhs.0[6], self.0[7] * rhs.0[7],
        ])
    }
}

意図としては、8要素の並列演算を書けばコンパイラが <4 x double> × 2 にベクトル化してくれるだろうというもの。C++ 版は __m256d intrinsics で明示的に SIMD 命令を使っている。

根本原因: rustc の BackendRepr

rustc のソースを追うと原因が見える。

① 配列は無条件に BackendRepr::Memory になる

// compiler/rustc_abi/src/layout.rs
fn array_like(...) -> LayoutData {
    // ...
    backend_repr: BackendRepr::Memory { sized: true }
}

[f64; 4] でも [u8; 1000] でも、配列は全て Memory。#[repr(simd)] が付いた型は BackendRepr::SimdVector になり、LLVM の <4 x double> に直接マッピングされる。

② Memory 表現の配列は alloca + GEP + load/store でコード生成される

// compiler/rustc_codegen_ssa/src/mir/rvalue.rs:655
// "All arrays have BackendRepr::Memory"

③ インライン化後、SROA がスカラーに分解

self.0[0] * rhs.0[0] のような要素アクセスが個別の fmul double になる。配列だったという情報は消失する。

④ SLP Vectorizer が事後的に再ベクトル化を試みるが不完全

LLVM の SLP (Superword Level Parallelism) Vectorizer は、スカラー命令の中から並列実行可能なグループを見つけてベクトル化する。算術演算 (fmul, fadd, fsub) は <4 x double> にまとめてくれる。しかし以下は苦手

• 比較 + AND チェーン (fcmp ogt × 8 + and i1 × 7): 部分的にしかベクトル化されない
• ビットマスク生成 (fcmp ole → zext i1 → shl (不均一定数) → or): SLP のパターン認識にマッチしない

C++ 版なら vcmplepd + vmovmskpd の2命令で済む処理が、SLP 経由だと大量のスカラー命令になる。

#[repr(simd)] を使えば？

#[repr(simd)] を付ければ BackendRepr::SimdVector になるが、SIMD 型に対する配列インデックスアクセス (self.0[i]) は MIR レベルで禁止されている (MCP#838)。simd_add 等の intrinsics が必要で元のコードスタイルは維持できない。

std::simd (nightly の portable_simd) なら safe に書けて intrinsics 同等の性能が出るが、安定化されていない。

アセンブリ分析

当初の仮説は「SLP が不完全だからスカラーコードが残って遅い」だった。しかしアセンブリを読むと状況はもう少し複雑だった。

内部ループは完璧にベクトル化されていた

mand8 関数の内部ループ (5イテレーション × 8回) のアセンブリ:

.LBB5_2:                          ; ホットループ
    vmulpd  %ymm11, %ymm11, %ymm5   ; zr² (4 doubles 同時)
    vmulpd  %ymm14, %ymm14, %ymm6
    vmulpd  %ymm12, %ymm12, %ymm7
    vsubpd  %ymm7, %ymm5, %ymm5     ; zr² - zi²
    vaddpd  %ymm5, %ymm0, %ymm5     ; + cr
    ; ... 全て ymm レジスタ (256-bit) での演算
    decq    %rax
    jne     .LBB5_2

全命令が vmulpd/vaddpd/vsubpd の ymm (256-bit = <4 x double>) 演算。SLP は内部ループの算術演算を完璧にベクトル化していた。

問題はループの外にあった

Mandelbrot の計算は 50 イテレーション。元のコードでは「5イテレーション × 8回 (早期脱出チェック付き)」のループの後、末尾の「5イテレーション × 2回」がループ外にアンロールされていた

for _ in 0..8 {
    do_5_iters!();     // ループ内: 完璧にベクトル化
    if abs.all_gt(4.0) { return 0; }
}
do_5_iters!();         // ループ外: 問題のコード
do_5_iters!();         // ループ外: 問題のコード

この末尾2回分が LLVM にアンロールされ、約350命令のスカラー/shuffle 混在コードになっていた

; ループ外の末尾コード (抜粋)
vperm2f128  $49, %ymm14, %ymm11, %ymm3   ; shuffle
vunpcklpd   %xmm14, %xmm6, %xmm6         ; shuffle
vextractf128 $1, %ymm8, %xmm7             ; shuffle
vmulsd      %xmm5, %xmm3, %xmm3          ; スカラー演算
vaddsd      %xmm3, %xmm3, %xmm3          ; スカラー演算
vaddsubpd   %xmm2, %xmm5, %xmm5
; ... 約350命令続く

ループ構造がなくなると、SLP は10イテレーション分の巨大な演算 DAG を相手にすることになる。部分的にしかベクトル化できず、イテレーション間の値受け渡しで vperm2f128, vunpcklpd, vextractf128 等の shuffle が大量発生し、一部は vmulsd (スカラー) に退化していた。

perf stat の数字

	Rust (元)	C++
instructions	20.5G	12.6G
L1-dcache-loads	956M	140M

命令数 1.6 倍、L1 ロード 6.8 倍。ループ外のスカラーコードとスタックへの spill が原因。

解決: 選択的 #[inline(never)]

内部ループが完璧にベクトル化されるなら、末尾もループの中に入れればいい。ただし単純にループ回数を増やすとループ内の条件分岐が増えて最適化を阻害する (実際に試して 0.80s に悪化した)。

最終的に効いたのは早期脱出チェックが不要な区間を #[inline(never)] 関数に分離するアプローチ

#[inline(never)]
fn do_n_rounds(
    n: usize,
    zr: &mut F64x8, zi: &mut F64x8,
    cr: &F64x8, ci: &F64x8,
    abs: &mut F64x8,
) {
    for _ in 0..n {
        for _ in 0..ITERATIONS_WITHOUT_CHECK {
            do_iter(zr, zi, cr, ci, abs);
        }
    }
}

#[inline(never)]
fn mand8(cr: &F64x8, ci: &F64x8, last_pixels: u8) -> u8 {
    // ...
    if last_pixels == 0 {
        // 早期脱出パス: インラインのまま (ループ内でチェック)
        for _ in 0..8 {
            do_5_iters!();
            if abs.all_gt(4.0) { return 0; }
        }
    } else {
        // 全ピクセル集合内パス: 関数呼び出し
        do_n_rounds(8, &mut zr, &mut zi, cr, ci, &mut abs);
    }
    // 末尾2ラウンド: 関数呼び出し (アンロールさせない)
    do_n_rounds(2, &mut zr, &mut zi, cr, ci, &mut abs);

    abs.le_mask(4.0)
}

do_n_rounds が #[inline(never)] なので

1. LLVM はこの関数内でループ構造を維持する
2. SLP がループ本体だけを最適化し、<4 x double> の綺麗なパターンを維持
3. 末尾の10イテレーションがループ外にアンロールされない

関数呼び出しのコスト (数命令) vs 排除できたスカラー/shuffle コード (約350命令)。後者が圧倒的に重い。

改善後の結果

実装	Time	Instructions	L1-dcache-loads	vs C++
C++ (__m256d intrinsics)	0.51s	12.6G	140M	1.00x
Rust (__m256d intrinsics)	0.52s	13.1G	365M	1.02x
Rust (std::simd, nightly)	0.52s	12.8G	237M	1.02x
Rust (選択的 inline(never))	0.57s	15.1G	911M	1.12x
Rust (元)	0.71s	20.5G	956M	1.39x

命令数が 20.5G → 15.1G に 26% 減少。実行時間は 0.71s → 0.57s で 20% 改善。

試して効果がなかったもの

all_gt を f64::min ツリーリダクションに変更

let m01 = self.0[0].min(self.0[1]);
let m23 = self.0[2].min(self.0[3]);
// ...
m_all > threshold

0.63s → 0.66s (悪化)。f64::min が fminnum intrinsic になり NaN ハンドリングのオーバーヘッドが入る。if a < b { a } else { b } に変えても 0.64s で改善せず。

F64x8 を F64x4 × 2 に分離

SLP が2グループを独立にベクトル化できるはず → 0.63s → 0.66s (悪化)。分離するとレジスタ圧力が増加する。

ループ統合 (条件付き早期脱出チェック)

末尾をメインループに統合して if i < 8 { check; } → 0.80s (大幅悪化)。条件分岐の追加がホットループ全体のコード生成に影響した。

残りの 12% の要因

改善後 (0.57s) と C++ (0.51s) にはまだ 12% のギャップがある。

原因は2つ

1. all_gt / le_mask の比較・マスク処理: C++ は vcmplepd + vmovmskpd の2命令。SLP 経由では vcmpnltpd → vextractf128 → vpor → vpackssdw → vtestps と5命令以上になる
2. do_n_rounds の関数呼び出しオーバーヘッド: メモリ経由の引数渡し (L1-dcache-loads が 911M vs 140M)

1 は SLP の構造的限界。fcmp → and i1 チェーンや zext → shl(不均一定数) → or は SLP のリダクション認識にマッチしない。2 は #[inline(never)] の代償。どちらも [f64; N] + SLP の枠組みでは解消できない。

性能差の要因分析

要因	レベル
BackendRepr::Memory による LLVM IR のスカラー化	rustc の設計制約
SLP による算術演算の再ベクトル化	LLVM 最適化 (成功)
SLP による比較・マスク操作の再ベクトル化	LLVM 最適化 (失敗)
ループ外アンロールによるコード品質劣化	LLVM 最適化 (副作用)
#[inline(never)] によるループ構造維持	ソースレベル対策

1.39x の性能差の内訳: ループ外アンロール問題が約 0.14s (全体の半分以上)、比較・マスクの SLP 限界が残りの約 0.06s。前者はソースレベルの #[inline(never)] で解消できたが、後者は [f64; N] + SLP の枠組みでは解消できない。intrinsics や std::simd を使えばこの制約を回避でき、C++ と同等の性能になる。

Benchmarks Game fannkuch-redux: C / C++ / Rust の性能差はなぜ？

偶然流れてきたポスト

この記事の内容に対する話ではないのだけど、一般的にRustはC/C++より若干パフォーマンスが劣るとされるのは何でだろう？LLVMとGCCの性能差？https://t.co/CRKrVKA8PT

— きさく (@namachan10777) 2026年3月7日

これを見て気になったので、The Computer Language Benchmarks Game の fannkuch-redux ベンチマークにおいて、C (gcc #6)・C++ (g++ #6)・Rust (#6) の最速実装を手元環境で追試し、perf と objdump を使ってコンパイラが生成したコードの差異を命令レベルで分析した。

ソースコード

• C (gcc #6): fannkuchredux-gcc-6 — Contributed by Ilya Kurdyukov
• C++ (g++ #6): fannkuchredux-gpp-6 — Contributed by Andrei Simion (with patch from Vincent Yu)
• Rust (#6): fannkuchredux-rust-6 — Contributed by Henry Jayakusuma

環境

項目	値
CPU	Intel Core i7-8650U (Kaby Lake-R, 4C/8T, 1.90GHz base)
OS	Debian, Linux 6.1.0-26-amd64
ISA Features	SSE4.1, SSE4.2, AVX, AVX2
gcc / g++	12.2.0 (Debian 12.2.0-14), 15.2.0 (Debian 15.2.0-14)
rustc	1.84.0 (9fc6b4312 2025-01-07), 1.94.0 (4a4ef493e 2026-03-02)

gcc 12.2 / rustc 1.84.0 は手元環境にたまたま入っていたもの。

コンパイルオプションは Benchmarks Game の公式設定に準拠

C:    gcc -pipe -O3 -fomit-frame-pointer -march=ivybridge -pthread
C++:  g++ -pipe -O3 -fomit-frame-pointer -march=ivybridge -std=c++17 -fopenmp
Rust: rustc -C opt-level=3 -C target-cpu=ivybridge -C codegen-units=1

Rust は Benchmarks Game 公式では rayon クレートを使用。本追試でも同様に cargo build --release + RUSTFLAGS="-C target-cpu=ivybridge" で再現した。

ベンチマーク結果

n=12 で 3 回実行した best を採用（time コマンド使用）。

実装	コンパイラ	Wall time	User CPU	スレッド数	CPU時間比
C	gcc 12.2	1.75s	7.06s	4 (pthread)	1.00x
C	gcc 15.2	1.82s	7.26s	4 (pthread)	1.03x
Rust	rustc 1.94.0	2.07s	15.89s	8 (rayon)	2.25x
C++	g++ 12.2	2.08s	15.93s	8 (OpenMP)	2.26x
C++	g++ 15.2	2.18s	16.46s	8 (OpenMP)	2.33x
Rust	rustc 1.84.0	2.34s	17.77s	8 (rayon)	2.52x

C は 4 スレッドで 8 スレッドの C++ / Rust より速い。シングルスレッド性能に 2 倍以上の差がある。

perf stat: HW カウンタ比較

生データ: perf_stat.txt (gist)

メトリクス	C gcc-12	C gcc-15	C++ g++-12	C++ g++-15	Rust 1.84	Rust 1.94
cycles	25.6B	26.8B	55.7B	57.6B	62.1B	55.6B
instructions	45.3B	44.7B	52.5B	50.2B	68.7B	45.3B
IPC	1.77	1.67	0.94	0.87	1.11	0.81
L1-dcache-loads	701M	482M	8,450M	8,457M	8,840M	8,833M
branches	4,714M	4,705M	6,667M	6,228M	6,417M	6,704M
branch-misses	462M (9.8%)	460M (9.8%)	596M (8.9%)	637M (10.2%)	608M (9.5%)	591M (8.8%)

注目すべき数値

• IPC: C は 1.77、C++/Rust は 0.81〜0.94。同じ命令数でも C の方が 2 倍速くパイプラインを回せている
• L1-dcache-loads: C は 701M、C++/Rust は 8.4B〜8.8B で 12 倍の差。C の内側ループにはメモリアクセスが存在しない
• instructions: Rust 1.94 は 45.3B で C の 45.3B とほぼ同数。にもかかわらずサイクル数は 2.17 倍。命令あたりのレイテンシが問題。一方 Rust 1.84 は 68.7B と 52% 多い

アセンブリ

3 つの実装は同じ基本アルゴリズムを使っているが、ホットループの実装方針が根本的に異なる。

objdump 生データ: objdump_*.txt (gist)

C (gcc #6): 9 命令

;; gcc 12.2 / gcc 15.2 で同一構造
.L20:                                       ;        perf annotate
  vpaddb    xmm7,  xmm8, xmm15             ;  5.4%  動的に反転マスクを計算
  vpshufb   xmm4,  xmm0, xmm15             ;  2.3%  next = perm[perm[0]]
  vmovd     r9d,   xmm4                     ;        first を GPR に取得
  add       eax,   1                        ;  5.7%  flips++
  vpblendvb xmm7,  xmm7, xmm3, xmm7       ; 10.8%  マスク完成（identity とブレンド）
  vmovdqa   xmm15, xmm4                     ;        v3 更新
  vpshufb   xmm0,  xmm0, xmm7              ;        ★ 配列反転実行
  test      r9b,   r9b                      ;        first == 0?
  jne       .L20                            ;  4.2%

特徴

• マスクテーブル不要: vpaddb + vpblendvb で反転マスクを動的計算。{0,-1,-2,...,-15} に first を加算し、符号ビットで vpblendvb することで {first, first-1, ..., 0, identity...} を生成
• _mm_cvtsi128_si32 で先頭要素を GPR に取得: レジスタ間転送 (vmovd) のみ、スタック経由なし
• _mm_shuffle_epi8 でポインタ追跡: perm[first] も vpshufb で XMM 内完結
• 2 回アンロール: X(+=) / X(-=) マクロで偶数/奇数の checksum を交互処理、外側ループの分岐を半減

C++ (g++ #6): 9〜10 命令、store-to-load forwarding がボトルネック

;; g++ 12.2: 10命令
.L_flips:                                   ;        perf annotate
  movsx     rax,   dl                       ;  3.0%
  movzx     edx,   [rsp+rax+0x40]           ; 39.1%  ★ next = current[first]
  shl       rax,   4                        ;
  vpshufb   xmm1,  xmm2, [rsp+rax+0xd0]    ; 11.5%  reverse（マスクテーブル参照）
  lea       eax,   [rcx+1]                  ;  3.0%  flips++
  vmovdqa   xmm2,  xmm1                     ;
  vmovdqa   [rsp+0x40], xmm1                ;  4.0%  ★ current をスタックに書き戻し
  movsx     ecx,   al                       ;        (g++ 12 のみ、15 では消滅)
  test      dl,    dl                       ;
  jne       .L_flips                        ;  2.8%

;; g++ 15.2: 9命令（movsx ecx, al が消え add ecx, 1 に変更）
.L_flips:                                   ;        perf annotate
  movsx     rax,   dl                       ;  3.1%
  add       ecx,   1                        ;        flips++
  movzx     edx,   [rsp+rax+0x40]           ; 38.0%  ★ next = current[first]
  shl       rax,   4                        ;
  vpshufb   xmm1,  xmm2, [rsp+rax+0xd0]    ; 11.2%  reverse
  vmovdqa   xmm2,  xmm1                     ;  3.0%
  vmovdqa   [rsp+0x40], xmm1                ;  3.7%  ★ store back
  test      dl,    dl                       ;
  jne       .L_flips                        ;  2.4%

ボトルネック

• reinterpret_cast<char(&)[16]>(current)[first] → コンパイラが XMM レジスタから可変インデックスのバイトを取得できず、vmovdqa で XMM → スタックに store → movzx でバイト load。XMM (16B) store の直後に 1B load するため、store-to-load forwarding がサイズ不一致で完全転送できず、ストールが発生。全サイクルの 38〜39% がこの 1 命令に集中
• masks_reverse テーブルがスタック上: Masks 構造体（512B）がブロックごとにスタックに構築され、内側ループで毎回 16B load

Rust (#6): rustc 1.84.0 では 14 命令、1.94.0 では 8 命令

;; rustc 1.84.0 (LLVM 19.1.5) — 14 命令
.LBB_flips:                                 ;        perf annotate
  mov       [rsp+0x30], rbx                ; 13.3%  ★ GPR → stack (low 8B)
  mov       [rsp+0x38], r11                ;  2.3%  ★ GPR → stack (high 8B)
  movzx     r15d,  sil                     ;        zero-extend first
  movzx     esi,   [rsp+r15+0x30]          ; 20.1%  ★ next = perm[first] (STALL)
  shl       r15d,  4                       ;        index * 16
  vmovq     xmm14, rbx                    ;        GPR → XMM (low)
  vmovq     xmm15, r11                    ;        GPR → XMM (high)
  vpunpcklqdq xmm14, xmm14, xmm15         ;  6.4%  128-bit に結合
  vpshufb   xmm14, xmm14, [r15+r14]       ; 10.8%  反転実行
  vpextrq   r11,   xmm14, 1               ; 11.7%  ★ XMM → GPR (high)
  vmovq     rbx,   xmm14                  ;        XMM → GPR (low)
  inc       r10d                           ;        flips++
  test      sil,   sil                     ;        next == 0?
  jne       .LBB_flips                     ;

;; rustc 1.94.0 (LLVM 21.1.8) — 8 命令
.LBB_flips:                                 ;        perf annotate
  vmovdqa   [rsp+0x10], xmm14              ;  6.3%  ★ current をスタックに store
  movzx     r10d,  r13b                     ;        zero-extend first
  movzx     r13d,  [rsp+r10+0x10]           ; 36.7%  ★ next = perm[first] (STALL)
  shl       r10d,  4                        ;        index * 16
  vpshufb   xmm14, xmm14, [r10+r14]        ; 11.7%  ★ 反転実行（in-place）
  inc       ebx                             ;  3.2%  flips++
  test      r13b,  r13b                     ;        next == 0?
  jne       .LBB_flips                      ;  3.0%

rustc 1.84.0 の問題点

• u128 を GPR ペア (rbx, r11) で保持: 毎イテレーション vmovq ×2 + vpunpcklqdq で XMM に組み立て、vpshufb で反転後、vpextrq + vmovq で GPR に戻す往復転送が発生
• store-forwarding stall も発生するが、GPR↔XMM 転送コストに埋もれてサイクル比率は 20.1% に留まる

rustc 1.94.0 での改善

• u128 を XMM レジスタ (xmm14) で保持: GPR↔XMM 往復転送が消滅し 14 → 8 命令に
• store-forwarding 問題は C++ と同じ: vmovdqa [rsp+0x10], xmm14 → movzx r13d, [rsp+r10+0x10] で 36.7% のサイクルを消費
• vpshufb xmm14, xmm14, [mem]: in-place 更新でレジスタコピー不要（C++ は vmovdqa xmm2, xmm1 が必要）

パーミュテーション増分の差異

ホットループにはフリップだけでなく、次のパーミュテーションへの遷移も含まれる。

実装	手法	特徴
C	vpmovmskb + bsf で繰り上がり位置を一発検出 → 1 回の vpshufb	ベクトル化。スカラーループなし
C++	count[i] を int64_t 配列でスカラーインクリメント	ループ。大半は 1 回で break
Rust	15 段のカスケードを完全アンロール	分岐予測に依存。命令数は少ないが IPC は低い

C 版はカウンタを XMM レジスタに保持し、vpmovmskb でオーバーフロー位置をビットマスクとして抽出、bsf で最下位ビットを見つけて 1 回の pshufb で完了する。

コンパイラバージョン間の差異

gcc 12.2 → gcc 15.2 (C)

内側フリップループは同一構造（9 命令、メモリアクセスゼロ）。IPC が 1.77 → 1.67 にわずかに低下。

変化点	詳細
レジスタ割り当て	vmovd %edx, xmm → vmovd %r9d, xmm など。本質的な差ではない
L1-dcache-loads	701M → 482M に減少。初期化コードが改善
IPC 低下	ループ外の命令スケジューリングが微妙に変化。結果 +3% の性能低下

g++ 12.2 → g++ 15.2 (C++)

g++ 12.2: 10 命令（movsx ecx, al が余分）
g++ 15.2:  9 命令（add ecx, 1 に変更、1 命令削減）

変化点	詳細
内側ループ	10 → 9 命令に微改善。flips カウンタの符号拡張が不要に
branch-misses	596M → 637M に増加 (+7%)。ループ外の分岐構造が変化
総合性能	命令削減と分岐ミス増が相殺し、ほぼ同等（+3% 悪化）

store-forwarding のボトルネック (38〜39%) は両バージョンで変化なし。

rustc 1.84.0 → rustc 1.94.0 (Rust)

github.com

rust-lang/rust#142915 で DestinationPropagation MIR 最適化パスがデフォルト有効化されたこと（2025-09-17 マージ、rustc 1.92.0 で stable 化）。

stable では rustc 1.91.0 が OLD、rustc 1.92.0 が NEW。

rustc 1.91.0 (stable):                                     OLD (14命令)
nightly-2025-09-17 (a9d0a6f15, LLVM 21.1.1):               OLD (14命令)  ← 最後の OLD
nightly-2025-09-18 (4645a7988, LLVM 21.1.1):               NEW (8命令)   ← 最初の NEW
rustc 1.92.0 (stable):                                     NEW (8命令)

両 nightly とも同じ LLVM 21.1.1 を使用しており、LLVM のバージョン変更は原因ではない。DestinationPropagation が不要なコピーを排除し MIR を単純化した結果、LLVM のレジスタアロケータが u128 を GPR ペアではなく XMM レジスタに保持するようになった。

メトリクス	rustc 1.84.0	rustc 1.94.0	変化
内側ループ命令数	14	8	-43%
総 instructions	68.7B	45.3B	-34%
cycles	62.1B	55.6B	-10%
IPC	1.11	0.81	-27%
User CPU	17.77s	15.89s	-11%

;; rustc 1.84.0（14命令）— GPR↔XMM 往復転送
mov     [rsp+0x30], rbx           ; GPR → stack (low)
mov     [rsp+0x38], r11           ; GPR → stack (high)
movzx   r15d, sil
movzx   esi, [rsp+r15+0x30]      ; stack → byte
shl     r15d, 4
vmovq   xmm13, rbx               ; GPR → XMM (low)
vmovq   xmm15, r11               ; GPR → XMM (high)
vpunpcklqdq xmm13, xmm13, xmm15  ; combine
vpshufb xmm13, xmm13, [r15+r14]  ; reverse
vpextrq r11, xmm13, 1            ; XMM → GPR (high)
vmovq   rbx, xmm13               ; XMM → GPR (low)
inc     r10d
test    sil, sil
jne     .loop

;; rustc 1.94.0（8命令）— XMM 保持
vmovdqa [rsp+0x10], xmm14        ; XMM → stack
movzx   r10d, r13b
movzx   r13d, [rsp+r10+0x10]     ; stack → byte
shl     r10d, 4
vpshufb xmm14, xmm14, [r10+r14]  ; reverse (in-place)
inc     ebx
test    r13b, r13b
jne     .loop

rustc の MIR 最適化により不要なコピーが排除され、LLVM が u128 の値を GPR ペアではなく XMM レジスタで保持するようになったことで

• vmovq ×2 + vpunpcklqdq（GPR→XMM 組み立て: 3 命令）が消滅
• vpextrq + vmovq（XMM→GPR 分解: 2 命令）が消滅
• stack への store も mov ×2 → vmovdqa ×1 に統合

結果として C++ とほぼ同等の性能 (User CPU: 15.9s vs 16.0s) を達成した。

perf annotate: ホットスポット分布

生データ: perf_annotate_*.txt (gist)

各実装でサイクルの過半数を消費する命令

C (gcc 12.2)

 8.33%  vpblendvb xmm9, xmm3, xmm9, xmm9   ← 動的マスク生成
 8.23%  vpblendvb xmm14, xmm3, xmm14, xmm14  ← 2つ目のアンロール版
 6.41%  add       $1, %eax                    ← flips++
 6.30%  jne       .L20                        ← ループ末尾

メモリアクセスに起因するストールがゼロ。全サイクルが演算に使われている。

C++ (g++ 12.2)

39.09%  movzbl 0x40(%rsp,%rax,1), %edx     ← ★ store-to-load forwarding stall
11.48%  vpshufb 0xd0(%rsp,%rax,1), %xmm2   ← マスクテーブル load
13.63%  movsbq  %cl, %rdx                  ← checksum 計算

1 命令で全サイクルの 39%。直前の vmovdqa で 16B store した直後に 1B load するサイズ不一致の store-to-load forwarding。

Rust (rustc 1.84.0)

20.10%  movzbl 0x30(%rsp,%r15,1), %esi     ← ★ store-to-load forwarding stall
13.27%  mov    %rbx, 0x30(%rsp)            ← GPR → stack (low)
11.73%  vpextrq $0x1, %xmm14, %r11        ← ★ XMM → GPR (high)
10.75%  vpshufb (%r15,%r14,1), %xmm14      ← reverse
 6.36%  vpunpcklqdq %xmm15, %xmm14        ← GPR → XMM 結合
 2.31%  mov    %r11, 0x38(%rsp)            ← GPR → stack (high)

store-forwarding stall に加え、GPR↔XMM 間の往復転送がサイクルを消費している。vpextrq (11.73%) と mov ×2 + vpunpcklqdq (計 21.94%) が毎イテレーション発生。

Rust (rustc 1.94.0)

36.74%  movzbl 0x10(%rsp,%r10,1), %r13d    ← ★ store-to-load forwarding stall
11.72%  vpshufb (%r10,%r14,1), %xmm14      ← reverse
 6.27%  vmovdqa %xmm14, 0x10(%rsp)         ← store

GPR↔XMM 転送が消滅し、ボトルネックが store-forwarding に一本化された。

性能差の説明

なぜ C は 2.25 倍速いのか

1. L1-dcache-loads が 12 分の 1 (701M vs 8.4B–8.8B)

   • C: 内側ループでメモリ操作ゼロ。マスクを動的計算、perm[first] も vpshufb でレジスタ内完結
   • C++/Rust: 毎フリップで XMM → スタック store + バイト load + マスクテーブル load

2. IPC が 2 倍 (1.77 vs 0.81–0.94)

   • C: 全命令がレジスタ間演算で、依存チェーンが短い
   • C++/Rust: store-to-load forwarding ストールでパイプラインが停止。1 命令に 38–39% のサイクルが集中

3. ループアンロール (2x)

   • C: X(+=) / X(-=) で 2 パーミュテーション / イテレーション。外側ループのオーバーヘッドが半減
   • C++/Rust: 1 パーミュテーション / イテレーション

なぜ C++ と Rust は同等なのか (rustc 1.94.0 以降)

rustc 1.92.0 で DestinationPropagation MIR 最適化パスがデフォルト有効化され、rustc が LLVM に渡す IR が改善された結果、内側ループ構造が C++ とほぼ同一に

• 両者とも 8–9 命令
• 両者とも store-to-load forwarding が最大ボトルネック (37–39%)
• 両者ともマスクテーブル参照方式

まとめ

差分の要因	レベル
動的マスク生成 vs テーブル参照	アルゴリズム設計
store-to-load forwarding	コンパイラ / 言語制約
ベクトル化カウンタ vs スカラーループ	アルゴリズム設計
ループ 2x アンロール	ソースレベル最適化
GPR↔XMM 往復転送 (旧 Rust)	rustc の MIR 最適化不足
gcc 12→15 / g++ 12→15 のレジスタ割り当て変化	コンパイラバージョン

C vs C++/Rust の 2.25x の差はコンパイラの最適化品質ではなく、ソースコードレベルでのアルゴリズム設計の差。C 版の作者 (Ilya Kurdyukov) は C++ #6 を「参考にした」と記述しているが、ホットパスを完全に再設計し、メモリアクセスをゼロにしている。この差はコンパイラバージョンを上げても埋まらない。

一方、旧 Rust の C++ に対する性能差は rustc の MIR 最適化不足が原因で、LLVM に渡す IR に不要なコピーが残っていたために LLVM が u128 を GPR ペアで保持してしまっていた。rustc 1.92.0 で DestinationPropagation がデフォルト有効化されたことで解消された。x86 には「XMM レジスタから可変インデックスで 1 バイトを取得する命令」が存在しないため、store-to-load forwarding は C++/Rust のどちらでも避けられない（C 版はそもそもこの操作を行わない設計）。

プログラミング言語の性能についての考え

自分の考えをまとめたものです。

前提としてプログラミング言語間の性能ベンチマークは好きではありません。 この記事で書いてある自分の考えに基づくとあまり意味のないものだからです。

本題

プログラミング言語の性能については得られる性能とそのために必要なコストの曲線(コスパ曲線)を意識することが最も重要だと考えています。 (無限のコストを投入すればどの言語においても同じ性能に到達すると仮定しています)

コスパ曲線については以下のことを考えています。

• ビジネスの場合は投入できるコストを一定としたときに最大の利益を得られるプログラミング言語を選ぶのがよい

  • 性能によって得られる利益はビジネスごとに異なるため考える必要がある
  • 利益の積分値を最大化したい、区間についてはそれぞれで設定する

• コスパ曲線は人のスキルに依存する

  • 学習なり採用なりで人にスキルに対してコストを払うことでコスパ曲線が変化する

• コスパ曲線は対象の領域に依存する

  • 対象の領域によくテストされた高速なライブラリがある場合は自分たち以外の誰かが代わりにコストを払ってくれている
    • memmem, zlib-rs, blas, numpy, lucene
  • システムの性能におけるそのプログラミング言語が関与している割合が低い場合もある
    • I/Oが占める割合が多い(基本的には SQL を投げるだけなど)

• コスパ曲線はランタイムやコンパイラ、性能周りのエコシステムの質に依存する

  • ビジネスやチーム, 対象領域を考慮しない場合はこれが一番重要な要素になる
  • JIT, PGO, LTO, auto vectorization, ...
  • プロファイリングツール、ベンチマークツール
    • 継続的プロファイリング
    • pprof, jfr, perf, ebpf

例えば Rust がある程度かける人なのであればコンパイラの性能やランタイムにより低いコストで十分な性能を得られるなどです。

僕の場合だと Go では言語自体の習熟と testing.B, pprof, PGO のおかげで低いコストで十分な性能を得られています。 特に pprof のおかげでかかるコストが低くなっていることを感じています。 なので個人的に性能という観点では性能改善のサイクルが回しやすいこと(プロファイリングしやすいこと、ベンチマークが書きやすいこと)を重要視しています。

プログラミング言語の性能について話すときは自分はどの前提をおいているかを意識すると不毛な議論を避けることができるはずです。

そもそも性能以外にも考慮するべきことは多くあってそれだけでプログラミング言語を選ぶことはあまりありません。 ただビジネスの利益構造として性能が非常に重要なケースや規模、将来のことを考慮してより利益がでるものに乗り換えるケースは現実的にあると思います。 性能の話題がでたときこの記事で書いたことを考慮しても良いのではないでしょうか。

Goのスライスの作り方によるパフォーマンスの違い

前提

本当は -cpuprofile flag を用いてなぜこの差が出るのかまで明らかにしたほうが良いですが一旦ここまでにします。

package main

// index
func fill(a []int, n int) {
    for i := range a {
        a[i] = i
    }
}

package main

// append
func fill(a []int, n int) {
    a = a[:0]
    for i := range n {
        a = append(a, i)
    }
}

の２つの実装で 30 % 程度 index の方が速いという結果でした。

何故かというのを明らかにします。

本題

それぞれ -cpuprofile を有効にした状態でベンチマークを実行し pprof の web ui で結果を確認してみます。

今回 Go のソースコードレベルでは理由がわかりません。pprof の disasm を見る必要があります。

Go のアセンブリを読むときはまずその時点の ABIInternal を理解することが大事です。(書くときは今だと ABI0 を理解する必要があります)

Go internal ABI specification

まずは index の方の実装の結果を見てみます。

go test -bench Fill -cpuprofile=index.pb.gz
go tool pprof -http : ./foo.test index.pb.gz

      Total: 3s
ROUTINE ======================== foo.fill
     2.78s      2.95s (flat, cum) 98.33% of Total
         .          .  10010bee0: MOVD R0, 8(RSP)                         ;main.go:3
         .          .  10010bee4: MOVD ZR, R2                             ;main.go:4
         .          .  10010bee8: JMP 3(PC)
     2.69s      2.84s  10010beec: MOVD R2, (R0)(R2<<3)                    ;foo.fill main.go:5
         .          .  10010bef0: ADD $1, R2, R2                          ;main.go:4
      30ms       30ms  10010bef4: CMP R2, R1                              ;foo.fill main.go:4
         .          .  10010bef8: BGT -3(PC)                              ;main.go:4
      60ms       80ms  10010befc: ?                                       ;foo.fill main.go:7

ABIInternal から第1引数のスライス a のデータが格納されている領域のポインタが R0, スライスの長さが R1, スライスのキャパシティが R2, 第2引数の n が R3 です。

index の方ではキャパシティ(R2)と n(R3) を使ってないため別の用途で使われています。

生成されたアセンブリは至極単純で i が R2 になって添字と代入する値の両方として使われて、それが1づつ ADD されてスライスの長さ R1 になるまで繰り返されるというものです。

(Boundary Check Elimination によって範囲外かどうかの処理が含まれていないことがわかります。)

Go による擬似コードは以下です。

package main

func fill(a []int, n int) {
    r0 := &a[0:]
    r2 := 0
loop:
    if r2 >= len(a) {
        return
    }
    r0[r2] = r2
    r2 += 1
    goto loop
}

ほぼすべてのサンプルが MOVD のタイミングだという事がわかります。

次に append に実装を切り替えます。

go test -bench Fill -cpuprofile=append.pb.gz
go tool pprof -http : ./foo.test append.pb.gz

      Total: 3.02s
ROUTINE ======================== foo.fill
     2.78s      2.86s (flat, cum) 94.70% of Total
      20ms       30ms  10010bee0: MOVD 16(R28), R16                       ;foo.fill main.go:3
         .          .  10010bee4: CMP R16, RSP                            ;main.go:3
         .          .  10010bee8: BLS 31(PC)
         .          .  10010beec: MOVD.W R30, -96(RSP)
         .          .  10010bef0: MOVD R29, -8(RSP)
         .          .  10010bef4: SUB $8, RSP, R29
         .          .  10010bef8: MOVD R0, 104(RSP)
         .          .  10010befc: MOVD R3, 128(RSP)                       ;main.go:5
         .          .  10010bf00: MOVD ZR, R1
         .          .  10010bf04: MOVD ZR, R4
         .          .  10010bf08: JMP 5(PC)
         .          .  10010bf0c: SUB $1, R5, R6                          ;main.go:6
     920ms      940ms  10010bf10: MOVD R1, (R0)(R6<<3)                    ;foo.fill main.go:6
      80ms       80ms  10010bf14: ADD $1, R1, R1                          ;foo.fill main.go:5
      60ms       60ms  10010bf18: MOVD R5, R4                             ;foo.fill main.go:6
         .          .  10010bf1c: CMP R1, R3                              ;main.go:5
      90ms      100ms  10010bf20: BLE 14(PC)                              ;foo.fill main.go:5
     1.46s      1.49s  10010bf24: ADD $1, R4, R5                          ;foo.fill main.go:6
      10ms       10ms  10010bf28: CMP R5, R2
      30ms       40ms  10010bf2c: BCS -8(PC)
         .          .  10010bf30: MOVD R1, 80(RSP)                        ;main.go:5
         .          .  10010bf34: MOVD R5, R1                             ;main.go:6
         .          .  10010bf38: ORR $1, ZR, R3
         .          .  10010bf3c: ADRP 348160(PC), R4
         .          .  10010bf40: ADD $1312, R4, R4
         .          .  10010bf44: CALL runtime.growslice(SB)
         .          .  10010bf48: MOVD 128(RSP), R3                       ;main.go:5
         .          .  10010bf4c: MOVD R1, R5                             ;main.go:6
         .          .  10010bf50: MOVD 80(RSP), R1
         .          .  10010bf54: JMP -18(PC)
     100ms      100ms  10010bf58: MOVD -8(RSP), R29                       ;foo.fill main.go:8
      10ms       10ms  10010bf5c: MOVD.P 96(RSP), R30
         .          .  10010bf60: RET                                     ;main.go:8
         .          .  10010bf64: STP (R0, R1), 8(RSP)                    ;main.go:3
         .          .  10010bf68: STP (R2, R3), 24(RSP)
         .          .  10010bf6c: MOVD R30, R3
         .          .  10010bf70: CALL runtime.morestack_noctxt.abi0(SB)
         .          .  10010bf74: LDP 8(RSP), (R0, R1)
         .          .  10010bf78: LDP 24(RSP), (R2, R3)
         .          .  10010bf7c: ?

index と比較して出力されている命令が多いです。

i が R1, len(a) が R4 にマッピングされてそれぞれ1づつ ADD をしています。 R5 (R4+1) と R2 (cap(a)) を比較してキャパシティを超える場合 runtime.growslice を呼ぶ処理が生成されています。 ただ今回のベンチマークのケースにおいては決して実行されることはありません。

若干謎なのが R4 が offset として使えるはずなのにわざわざ SUB をして R6 (R5-1) として新たに求めています。

Go による擬似コードは以下です。

package main

func fill(a []int, n int) {
    r0 := &a[0:]
    r1 := 0
    r4 := 0
loop:
    if r1 >= n {
        return
    }
    {
        r5 := r4 + 1
        if r5 > cap(a) {
            // grow slice
        }
        r6 := r5 - 1
        r0[r6] = r1
        r1 += 1
        r4 = r5
    }
    goto loop
}

append の方はサンプルが MOVD, ADD のタイミングの２つに分かれています。 ADD に 1.46 秒と書いてあるので ADD が問題だと思われるかもしれませんがこの結果は ADD が重い処理であることを指しません。

スタックをサンプリングしたときに PC がその命令を指していることが多いというだけです。パイプライン実行がストールしているなどのケースも多分にあります。

結論

append の方が生成されているコードが非効率だから index の方が速いです。

しかしこんなに実行される命令数が異なっていても 30% 程度の差で済むというのはパイプライン実行や投機的実行の凄さがわかる結果となりました。

testing.B.Loop を使おう

TL;DR

• Go 1.24 からは testing.B.Loop を使う
  • 意図しない最適化を避けることができる
  • N をループで使わないことで他の場所での使用を避けることができる
• ベンチマークの結果を比較する場合は同一条件下か確認しましょう
• ベンチマークの結果の安定性を確認しましょう
• 安定したベンチマークをするために testing.B.N は反復回数以外の用途で使わない

背景

なんでappendが速いんだろ🙄 pic.twitter.com/geEqBop2kv

— ゴリラ - お餅で巻いたもち食感ロール(ショコラ)は良いぞ (@gorilla0513) 2025年2月19日

本題

まずは追試をします。

package main

import "testing"

func BenchmarkIndex(b *testing.B) {
    a := make([]int, b.N)
    b.ResetTimer()
    for i := range a {
        a[i] = i
    }
}

func BenchmarkAppend(b *testing.B) {
    a := make([]int, 0, b.N)
    b.ResetTimer()
    for i := range b.N {
        a = append(a, i)
    }
}

go test -bench .

goos: darwin
goarch: arm64
pkg: foo
cpu: Apple M2 Max
BenchmarkIndex-12       1000000000           2.040 ns/op
BenchmarkAppend-12      1000000000           0.4466 ns/op
PASS
ok      foo 3.847s

追試をした結果ポストの通り Append のほうが速いという結果になります。

Index と Append の定義順を逆にして再度ベンチマークを取ってみます。

goos: darwin
goarch: arm64
pkg: foo
cpu: Apple M2 Max
BenchmarkAppend-12      1000000000           2.206 ns/op
BenchmarkIndex-12       1000000000           0.3112 ns/op
PASS
ok      foo 4.076s

不思議なことに結果が真反対になっています。

ベンチマークの結果を比較する場合は同一条件下か確認しましょう。 順序を入れ替えると結果が逆になってしまうのはベンチマーク間の影響があるということです。

更にそれぞれ10回程度ベンチマークを実行するように count flag を使ってみます。

go test -count 10 -bench .

goos: darwin
goarch: arm64
pkg: foo
cpu: Apple M2 Max
BenchmarkIndex-12       1000000000           0.8391 ns/op
BenchmarkIndex-12       1000000000           0.3779 ns/op
BenchmarkIndex-12       1000000000           1.490 ns/op
BenchmarkIndex-12       1000000000           0.3055 ns/op
BenchmarkIndex-12       1000000000           0.3067 ns/op
BenchmarkIndex-12       1000000000           0.3056 ns/op
BenchmarkIndex-12       1000000000           0.2946 ns/op
BenchmarkIndex-12       1000000000           0.2984 ns/op
BenchmarkIndex-12       1000000000           0.3015 ns/op
BenchmarkIndex-12       1000000000           0.2974 ns/op
BenchmarkAppend-12      1000000000           0.4113 ns/op
BenchmarkAppend-12      1000000000           0.4230 ns/op
BenchmarkAppend-12      1000000000           0.4184 ns/op
BenchmarkAppend-12      1000000000           0.4130 ns/op
BenchmarkAppend-12      1000000000           0.5042 ns/op
BenchmarkAppend-12      1000000000           0.4119 ns/op
BenchmarkAppend-12      1000000000           0.4113 ns/op
BenchmarkAppend-12      1000000000           0.4162 ns/op
BenchmarkAppend-12      1000000000           0.4212 ns/op
BenchmarkAppend-12      1000000000           0.4144 ns/op
PASS
ok      foo 13.876s

10億回も反復して得られた結果が全然安定しておらず正しくベンチマークができている状況とは思えません。

ベンチマークの結果の安定性を確認しましょう。

反復回数がベンチマーク対象のコードに影響を与えないようにしましょう。

ベンチマーク対象関数の中にスライスの長さに対する最適化などが入っている場合、反復回数をサイズのパラメータとして使うと処理速度に影響してしまいます。

反復することによってデータの精度を上げたいのに反復回数によって結果にばらつきが出ては意味がありません。

今回のケースでは問題になっていませんが反復回数をスライスの長さ等に使うこともおすすめできません。 b.N が10億になったときに10億要素のメモリ確保が発生します。環境によってはメモリ確保できないでしょうし、計測したい事象と関係ない部分にコストが掛かってしまいます。

b.N が整数であるがゆえに誤って使うケースがあるので Go 1.24 からは b.Loop を使うようにしてください。

以上を踏まえてベンチマークを書いてみます。

package main

import "fmt"
import "testing"

var sizes = []int{100, 1000, 10000}


func BenchmarkIndex(b *testing.B) {
    for _, size := range sizes {
        b.Run(fmt.Sprintf("n=%d", size), func(b *testing.B) {
            a := make([]int, size)
            b.ResetTimer()
            for b.Loop() {
                for i := range a {
                    a[i] = i
                }
            }
        })
    }
}

func BenchmarkAppend(b *testing.B) {
    for _, size := range sizes {
        b.Run(fmt.Sprintf("n=%d", size), func(b *testing.B) {
            a := make([]int, 0, size)
            b.ResetTimer()
            for b.Loop() {
                a = a[:0]
                for i := range size {
                    a = append(a, i)
                }
            }
        })
    }
}

異なるベンチマーク間で比較をしたいので別々に実行します。

go test -count 5 -bench Index

goos: darwin
goarch: arm64
pkg: foo
cpu: Apple M2 Max
BenchmarkIndex/n=100-12             33369684            35.56 ns/op
BenchmarkIndex/n=100-12             33737361            34.84 ns/op
BenchmarkIndex/n=100-12             33685392            34.74 ns/op
BenchmarkIndex/n=100-12             33992768            34.81 ns/op
BenchmarkIndex/n=100-12             34148914            34.91 ns/op
BenchmarkIndex/n=1000-12             4021273           299.0 ns/op
BenchmarkIndex/n=1000-12             4005706           299.1 ns/op
BenchmarkIndex/n=1000-12             3969499           300.2 ns/op
BenchmarkIndex/n=1000-12             3990604           299.3 ns/op
BenchmarkIndex/n=1000-12             4021982           299.1 ns/op
BenchmarkIndex/n=10000-12             406077          2921 ns/op
BenchmarkIndex/n=10000-12             402190          2965 ns/op
BenchmarkIndex/n=10000-12             401497          2922 ns/op
BenchmarkIndex/n=10000-12             402040          2916 ns/op
BenchmarkIndex/n=10000-12             411480          2914 ns/op
PASS
ok      foo 18.058s

go test -count 5 -bench Append

goos: darwin
goarch: arm64
pkg: foo
cpu: Apple M2 Max
BenchmarkAppend/n=100-12            29581965            40.10 ns/op
BenchmarkAppend/n=100-12            30135168            39.37 ns/op
BenchmarkAppend/n=100-12            29709619            39.40 ns/op
BenchmarkAppend/n=100-12            30006781            39.38 ns/op
BenchmarkAppend/n=100-12            29689618            39.55 ns/op
BenchmarkAppend/n=1000-12            3022086           397.5 ns/op
BenchmarkAppend/n=1000-12            3031659           402.0 ns/op
BenchmarkAppend/n=1000-12            3016876           396.2 ns/op
BenchmarkAppend/n=1000-12            3027954           397.0 ns/op
BenchmarkAppend/n=1000-12            3023427           396.6 ns/op
BenchmarkAppend/n=10000-12            295177          4008 ns/op
BenchmarkAppend/n=10000-12            297982          4005 ns/op
BenchmarkAppend/n=10000-12            294962          4009 ns/op
BenchmarkAppend/n=10000-12            292106          4003 ns/op
BenchmarkAppend/n=10000-12            295759          4002 ns/op
PASS
ok      foo 18.010s

この結果を見ると Index の方が速いようです。

A/B 比較するときは実装の中身を差し替えたほうが benchstat が使いやすくて便利です。

index を指定した書き込み

package main

func fill(a []int, n int) {
    for i := range a {
        a[i] = i
    }
}

append を使ったもの

package main

func fill(a []int, n int) {
    a = a[:0]
    for i := range n {
        a = append(a, i)
    }
}

fill に対するベンチマーク

package main

import "fmt"
import "testing"

var sizes = []int{100, 1000, 10000}

func BenchmarkFill(b *testing.B) {
    for _, size := range sizes {
        b.Run(fmt.Sprintf("n=%d", size), func(b *testing.B) {
            a := make([]int, size)
            b.ResetTimer()
            for b.Loop() {
                fill(a, size)
            }
        })
    }
}

go test -count 6 -bench Fill | tee index.txt

goos: darwin
goarch: arm64
pkg: foo
cpu: Apple M2 Max
BenchmarkFill/n=100-12          33031190            36.01 ns/op
BenchmarkFill/n=100-12          33252932            35.60 ns/op
BenchmarkFill/n=100-12          32978319            35.50 ns/op
BenchmarkFill/n=100-12          33462651            35.98 ns/op
BenchmarkFill/n=100-12          33013930            35.60 ns/op
BenchmarkFill/n=100-12          32709542            35.51 ns/op
BenchmarkFill/n=1000-12          4013035           300.4 ns/op
BenchmarkFill/n=1000-12          3983607           299.9 ns/op
BenchmarkFill/n=1000-12          3997215           301.2 ns/op
BenchmarkFill/n=1000-12          3996417           299.2 ns/op
BenchmarkFill/n=1000-12          4003567           300.1 ns/op
BenchmarkFill/n=1000-12          4020868           300.0 ns/op
BenchmarkFill/n=10000-12          404262          2937 ns/op
BenchmarkFill/n=10000-12          404089          2910 ns/op
BenchmarkFill/n=10000-12          403375          2913 ns/op
BenchmarkFill/n=10000-12          401274          2966 ns/op
BenchmarkFill/n=10000-12          407419          2920 ns/op
BenchmarkFill/n=10000-12          401107          2930 ns/op
PASS
ok      foo 21.625s

go test -count 6 -bench Fill | tee append.txt

goos: darwin
goarch: arm64
pkg: foo
cpu: Apple M2 Max
BenchmarkFill/n=100-12          29510088            40.43 ns/op
BenchmarkFill/n=100-12          29353459            39.77 ns/op
BenchmarkFill/n=100-12          29492724            39.87 ns/op
BenchmarkFill/n=100-12          29588016            39.81 ns/op
BenchmarkFill/n=100-12          29072701            39.88 ns/op
BenchmarkFill/n=100-12          29439996            39.86 ns/op
BenchmarkFill/n=1000-12          3011271           399.5 ns/op
BenchmarkFill/n=1000-12          3008048           398.4 ns/op
BenchmarkFill/n=1000-12          3007609           399.3 ns/op
BenchmarkFill/n=1000-12          3011499           404.5 ns/op
BenchmarkFill/n=1000-12          3005859           398.4 ns/op
BenchmarkFill/n=1000-12          2997512           399.1 ns/op
BenchmarkFill/n=10000-12          297706          4016 ns/op
BenchmarkFill/n=10000-12          294171          4011 ns/op
BenchmarkFill/n=10000-12          292375          4192 ns/op
BenchmarkFill/n=10000-12          292783          4100 ns/op
BenchmarkFill/n=10000-12          293036          4012 ns/op
BenchmarkFill/n=10000-12          295321          4128 ns/op
PASS
ok      foo 21.633s

benchstat による結果の比較

benchstat index.txt append.txt

goos: darwin
goarch: arm64
pkg: foo
cpu: Apple M2 Max
                │  index.txt  │             append.txt             │
                │   sec/op    │   sec/op     vs base               │
Fill/n=100-12     35.60n ± 1%   39.86n ± 1%  +11.98% (p=0.002 n=6)
Fill/n=1000-12    300.1n ± 0%   399.2n ± 1%  +33.04% (p=0.002 n=6)
Fill/n=10000-12   2.925µ ± 1%   4.058µ ± 3%  +38.74% (p=0.002 n=6)
geomean           315.0n        401.2n       +27.38%

結果については割とどうでもいいですが int のスライスに対しては index の方が 30% 程度速いようです。

本当は -cpuprofile flag を用いてなぜこの差が出るのかまで明らかにしたほうが良いですが一旦ここまでにします。

2025/02/21追記: 続編

orisano.hatenablog.com