extreme-software-optimization

极致软件优化

唯一规则： 先分析性能。证明行为未变。每次只做一项更改。

循环（必须遵守）

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)	Top-k/调度

第 3 级：数据结构

结构	用例
HashMap	点查找
BTreeMap	范围查询
SmallVec	通常规模较小的集合
Arena	大量分配，批量释放
布隆过滤器	成员资格预筛选

完整目录： 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

---

反模式（绝不执行）

✗	原因
未进行性能分析就优化	在非热点上浪费精力
每次提交进行多项更改	无法单独定位回归问题
假定性能有所提升	必须测量更改前后的表现
“顺便”更改行为	破坏同构性保证
跳过黄金输出捕获	无法检测回归问题

---

检查清单（开始任何优化前）

• 已捕获基线数据（p50/p95/p99、吞吐量、内存）
• 已进行性能分析：热点按耗时占比排名前 5
• 机会得分 ≥ 2.0
• 已保存黄金输出
• 已编写同构性证明
• 仅调整一个变量
• 回滚计划：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 轮： 非常规优化（后缀自动机、Link-Cut 树）

每一轮：重新分析性能 → 发现新热点 → 制定新矩阵。