extreme-software-optimization

極限ソフトウェア最適化

唯一のルール： まずプロファイリングを行います。動作が変わっていないことを証明します。一度に変更するのは1つだけです。

ループ（必須）

1. BASELINE    → hyperfine --warmup 3 --runs 10 'command'
2. PROFILE     → cargo flamegraph / py-spy / clinic flame
3. PROVE       → Golden outputs + isomorphism proof per change
4. IMPLEMENT   → Score ≥ 2.0 only, one lever per commit
5. VERIFY      → sha256sum -c golden_checksums.txt
6. REPEAT      → Re-profile (bottlenecks shift)

改善機会マトリクス

ホットスポット	影響度（1-5）	確信度（1-5）	工数（1-5）	スコア
func:line	×	×	÷	影響度×確信度/工数

ルール： スコアが2.0以上の場合のみ実装します。

同型性の証明テンプレート

すべての変更について、以下を記録します。

## Change: [description]
- Ordering preserved:     [yes/no + why]
- Tie-breaking unchanged: [yes/no + why]
- Floating-point:         [identical/N/A]
- RNG seeds:              [unchanged/N/A]
- Golden outputs:         sha256sum -c golden_checksums.txt ✓

---

パターンの段階（クイックリファレンス）

段階1：すぐに取り組める改善

パターン	適用する場面	同型性
N+1 → バッチ処理	逐次フェッチ	結果は同じで、往復回数が少ない
線形探索 → HashMap	キーによる検索	O(n)→O(1)。順序が変わる場合があります
遅延評価	使用されない可能性のある値	最終的な値は同じ
メモ化	繰り返し呼び出される純粋関数	キャッシュ値＝再計算値
バッファー再利用	反復ごとの割り当て	ループ内でゼロコピー

段階2：アルゴリズム

パターン	変更	確認事項
二分探索	O(n)→O(log n)	入力がソート済みであること
ツーポインター法	O(n²)→O(n)	入力に構造があること
累積和	O(n)→O(1) のクエリ	データが静的であること
優先度付きキュー	O(n)→O(log n)	上位k件の抽出／スケジューリング

段階3：データ構造

構造	用途
HashMap	単一要素の検索
BTreeMap	範囲検索
SmallVec	通常は要素数が少ないコレクション
アリーナ	多数の割り当てと一括解放
ブルームフィルター	メンバーシップの事前フィルター

カタログ全文： TECHNIQUES.md

---

言語別チートシート

言語	CPUプロファイル	問題箇所の検索
Rust	cargo flamegraph	rg '\.clone\(\)' --type rust
Go	go tool pprof /debug/pprof/profile	rg 'interface\{\}' --type go
TS	clinic flame -- node app.js	rg 'JSON\.(parse|stringify)' --type ts
Python	py-spy record -o flame.svg -- python script.py	rg '\.iterrows\(\)' --type py

言語別ガイド全文： LANGUAGE-SPECIFIC.md

---

アンチパターン（絶対に行わない）

✗	理由
プロファイリングせずに最適化する	ホットスポットではない箇所に労力を費やします
1つのコミットで複数の変更を行う	リグレッションの原因を特定できません
改善すると決めつける	変更前後の測定が必要です
「ついでに」動作を変更する	同型性の保証が崩れます
ゴールデン出力の取得を省略する	リグレッションを検出できません

---

チェックリスト（最適化を行う前に）

• ベースラインを取得済み（p50/p95/p99、スループット、メモリ）
• プロファイリング済み：ホットスポットが時間割合の上位5件以内
• 改善機会スコアが2.0以上
• ゴールデン出力を保存済み
• 同型性の証明を記述済み
• 変更する要素は1つだけ
• ロールバック計画：git revert <sha>

---

ツールコマンド

# Benchmark
hyperfine --warmup 3 --runs 10 'command'

# Profile
cargo flamegraph                           # Rust CPU
heaptrack ./binary                         # Allocation
strace -c ./binary                         # Syscalls

# Verify
sha256sum golden_outputs/* > golden_checksums.txt
sha256sum -c golden_checksums.txt          # After changes

---

参考資料

必要な情報	参考資料
最適化手法の完全なカタログ	TECHNIQUES.md
ステップごとの手法	METHODOLOGY.md
言語別ガイド	LANGUAGE-SPECIFIC.md
上級編（ラウンド2以降）	ADVANCED.md

反復ラウンド

• ラウンド1： 標準（N+1、インデックス、バッチ処理、メモ化）
• ラウンド2： アルゴリズム（DP、凸最適化、半環）→ ADVANCED.md
• ラウンド3： 高度な手法（接尾辞オートマトン、リンクカット木）

各ラウンドで、新たにプロファイリングを行い、新しいホットスポットを見つけ、新しいマトリクスを作成します。