1.4 程序优化的方法论

学习目标

读完这一节，你应该能够：

用 CPE 而不是"秒"来度量程序性能，并说明为什么。
用 Amdahl 定律算出一次优化的性能上限，从而判断它值不值得做。
按优先级列出一套优化顺序，并说出每一步在做什么。
说清编译器能做什么、不能做什么——从而知道人的价值在哪里。

一、度量：为什么不能只看"秒"

最直觉的性能度量是运行时间。但它有个问题：换一台机器、换一份输入，数字全变了，你无法判断改进是来自你的优化还是来自环境。

一个更可移植的度量是 CPE（Cycles Per Element，每元素周期数）：

\text{CPE} = \frac{\text{程序消耗的总周期数}}{\text{处理的元素个数}}

比如一段对长度为 $n$ 的数组求和的代码，消耗 $1000 + 3n$ 个周期，那么它的 CPE 就是 3，外加 1000 个周期的固定开销。

为什么这个拆分有用？ 因为它把优化分成了两类，方向完全不同：

项	含义	怎么优化
固定开销	与数据规模无关的部分（函数调用、初始化、循环外的准备工作）	消除它、或者把它摊薄（增大数据规模）
CPE（斜率）	每个元素的平均代价	减少访存、提高并行度

💡 新手最常犯的错误是：把固定开销优化了半天，而 CPE 根本没动。两者对应的手段完全不同，先判断你的瓶颈在哪一项。

二、Amdahl 定律：先算上限，再动手

在优化任何东西之前，先算一下它最多能带来多少收益。

设程序中有比例 $p$ 的部分可以被加速 $s$ 倍，那么整体加速比是：

S = \frac{1}{(1 - p) + \dfrac{p}{s}}

算一个例子：程序 40% 的时间花在某个函数上（ $p = 0.4$ ），你把它优化得无限快（ $s \to \infty$ ）：

S = \frac{1}{1 - 0.4} = \frac{1}{0.6} \approx 1.67

即使你把那部分优化到零耗时，整体也只能快 1.67 倍。

再看另一种情况：只把 90% 的部分优化 2 倍（ $p = 0.9$ ， $s = 2$ ）：

S = \frac{1}{0.1 + 0.45} = \frac{1}{0.55} \approx 1.82

结论很反直觉但极其重要：把一大块优化一点点，通常胜过把一小块优化到极致。

⚠️ Amdahl 定律的一个隐含前提是：被优化的部分不会因为优化而变成新的瓶颈。真实系统里常常会——优化完一处，瓶颈就跑到别处去了。所以它是一个上限估计，不是预测。

三、优化的优先级

按收益从高到低排，顺序不能反：

优先级	做什么	为什么排这个位置
1	换算法、换数据结构	量级变化。 $O(N^2)$ 换 $O(N \log N)$ 是几百倍的事，后面所有微调加起来也比不过
2	改善访存模式（循环顺序、分块、数据布局）	1.2、1.3 节讲的全部内容。常常有数倍收益
3	消除循环内的低效（见下一节）	稳定有百分之几十
4	手工微调（展开、多累加器、指令选择）	通常只有百分之几到几十，且编译器往往已经做了

为什么顺序不能反？ 因为高位优化的收益是乘法关系，而低位优化是在剩余的那部分时间里做的。如果第一项就把时间降到了原来的十分之一，后面三项能影响的总量也只剩十分之一。

💡 实践中，做完第 1、2 项，第 3、4 项往往就不需要做了。

四、消除低效：三个反复出现的模式

这三类问题在真实代码里极其常见，而且识别方法很简单。

模式一：循环内重复计算

// 反例：每次迭代都调用一次 strlen，而长度根本不变
for (int i = 0; i < strlen(s); i++) {
    total += s[i];
}

strlen 要扫描整个字符串，于是这段代码变成了 $O(n^2)$ 。

// 改法：把不变量挪出循环
int n = strlen(s);
for (int i = 0; i < n; i++) {
    total += s[i];
}

识别方法：看循环条件里有没有函数调用、有没有可以提前算出来的表达式。

模式二：不必要的函数调用

如果内层循环里调用一个小函数几十万次，而它只做几个算术运算，那么调用开销（保存现场、传参、跳转、返回）可能超过运算本身。

解法：内联（编译器常常自动做）、或者手工把逻辑展开。

模式三：不必要的内存引用（最高频）

这是最隐蔽也最常见的一个。

// 反例：累加器在内存里，每次迭代都要写回、再读回
void sum_rows(int* a, long* dest, int n) {
    for (int i = 0; i < n; i++) {
        *dest = 0;                       // 写内存
        for (int j = 0; j < n; j++) {
            *dest += a[i * n + j];       // 读内存 + 写内存
        }
    }
}

// 改法：累加器放进局部变量，编译器会把它分配在寄存器里
void sum_rows(int* a, long* dest, int n) {
    for (int i = 0; i < n; i++) {
        long acc = 0;                    // 寄存器
        for (int j = 0; j < n; j++) {
            acc += a[i * n + j];         // 仅在寄存器里累加
        }
        *dest = acc;                     // 循环结束才写一次内存
    }
}

为什么差别巨大？ 因为编译器很难确定 dest 指向的地址会不会被别的指针改掉。如果它不能证明"没人偷改 *dest"，就必须每次迭代都把值写回内存、再从内存读回来——即使寄存器里有现成的值。

💡 这就是"内存别名（aliasing）"问题。它解释了为什么 C 语言里的 restrict 关键字（承诺"这个指针不会被别的指针访问"）能带来显著的性能提升——它把编译器从怀疑中解放了出来。

五、指令级并行（ILP）

前面讲的都是"少做点事"。这一节讲"同时做更多事"。

流水线

现代 CPU 把一条指令分成多个阶段（取指、译码、执行、访存、写回），不同指令的这些阶段可以重叠。所以虽然每条指令要 15 个周期走完，但吞吐可以达到每个周期完成 2 到 6 条指令。

关键在于：重叠的前提是相邻指令之间没有依赖。

// 有依赖链：每一步都要等上一步的结果
for (int i = 0; i < n; i++) {
    acc = acc * x[i] + y[i];     // 每次迭代都依赖上一次的 acc
}

这条路线的浮点乘法必须串行执行。如果乘法延迟是 4 个周期，那么每个元素至少花 4 个周期——CPE 下限是 4，而硬件的浮点乘吞吐可能只需要 0.5 个周期。

打破依赖链：多路并行

// 用多个累加器，让加法彼此独立
long acc0 = 0, acc1 = 0;
for (int i = 0; i < n; i += 2) {
    acc0 += x[i];
    acc1 += x[i + 1];       // 这条不依赖上一条的 acc0
}

两个累加器的加法可以同时在流水线里推进，最后再合并。按这个思路开 4 路、8 路，CPE 就能一路降到接近硬件的吞吐上限。

⚠️ 浮点数的坑：浮点加法不满足结合律。多个累加器改变了运算顺序，结果可能与串行版本有微小差异。对精度敏感的场景（比如科学计算的求和）要格外小心，或者使用补偿求和技术。

循环展开

把循环体复制几遍，每次迭代处理多个元素。好处不只是"减少循环开销"，更重要的正是上面说的：为多路并行创造了机会。

现代编译器通常会自动展开，所以手工展开的收益一般不大——除非编译器因为别的原因（比如别名）不敢做。

六、分支预测

CPU 是流水线化的：它必须提前取出后面几条指令。但如果下一条指令取决于一个还没算出来的条件分支，它就得猜。

猜对了：流水线不停，几乎没有代价。
猜错了：要清空流水线重新取指，代价是十几个周期。

所以：

分支类型	代价
高度可预测（几乎总是同一方向、或者有规律）	接近零
不可预测（随机，比如随机数据的条件求和）	高昂，可能占总时间的绝大部分

一个反直觉的例子：一段"对大于阈值的元素求和"的代码，输入数据排好序时可能比随机顺序快好几倍——运算次数完全相同，唯一差别是分支是否可预测。

缓解手段：条件传送（cmov）指令可以消除分支——把两个结果都算出来，再用条件选一个。在分支不可预测时这更快（多做了计算，但不跳转）；在分支可预测时反而更慢。

💡 对 AI Infra 的意义：GPU 上有个同构的问题叫 warp 发散。一个 warp 里的 32 个线程如果走了不同的分支，硬件只能把两条路径都执行一遍，代价是 32 倍浪费。所以 GPU kernel 里要尽量让同组线程走同一条路径——思想完全一样，只是惩罚方式不同。

七、编译器能做什么，不能做什么

这是本节最重要的一节。判断清楚这条边界，你就知道该在哪儿花力气。

编译器做得很好（别手工重做）

寄存器分配、指令选择与调度
局部公共子表达式消除
强度削减（把乘法换成移位/加法）
循环展开、常量传播
自动向量化（把循环变成 SIMD 指令）
死代码消除

编译器不敢做或做不到（人的价值在这里）

编译器做不到的事	原因
跨编译单元/跨函数的优化	看不到别的文件的代码（除非开启链接时优化 LTO）
跨循环重构	需要理解算法语义，比如把两层循环交换、分块
算法替换	它不知道你想用快速排序替代冒泡
改变浮点运算顺序	可能改变结果，默认不允许
在存在指针别名时重排访存	无法证明安全，只能保守

👉 结论：人的价值集中在"结构层面"——循环结构、数据布局、算法选择、分块策略。这些恰好都是第 1.2、1.3 节的主题。

💡 "编译器会帮我优化"是一个危险的半真命题。 它会把 i * 8 换成 i << 3，但不会帮你把按列遍历改成按行遍历，也不会帮你分块。

八、工具：不要靠猜

工具	用途
`perf stat`	看总览指标：周期数、指令数、cache 缺失率、分支预测失败率
`perf record` + `perf report`	找出热点函数，看时间花在哪儿
Cachegrind（Valgrind）	精确到行的 cache 模拟，适合理解局部性问题
编译器优化报告	`-fopt-info`（GCC）、`-Rpass=loop-vectorize`（Clang）——看编译器到底做了什么优化、以及为什么没做某个优化
计时器 + 控制变量	最朴实也最可靠：只改一个因素，测多次，看中位数

⚠️ macOS 上没有 perf，替代方案见 1.6 动手实验。

优化流程应该是：

度量 → 找出瓶颈 → 判断瓶颈类型（算力？带宽？分支？）→ 对类型下手 → 重新度量
  ↑                                                                      │
  └──────────────────────────────────────────────────────────────────────┘

不要跳过第一个箭头。

九、与 AI Infra 的连线

1. 这一节就是 kernel 优化的方法论。

第三篇要讲的 GPU kernel 优化，用的完全是同一套流程：先 profile，判断是算力受限还是带宽受限，再决定是减少计算还是减少访存。判断依据来自 1.1 节，优化手段来自 1.3 节，流程来自本节。

2. "多累加器打破依赖链"在 GPU 上就是"多路并行归约"。

归约（reduction）是 AI 里最常见的操作之一（求和、softmax 的归一化）。GPU 上的实现同样要避免单线程串行依赖，只不过它是用树形归约而不是多累加器。

3. warp 发散是分支预测问题的 GPU 版本。

理解了 CPU 侧"猜错要清空流水线"，你在 GPU 上看到"分支导致同组线程串行两条路径"时就不会觉得是全新的知识。

关键结论

用 CPE 而不是秒来度量；区分固定开销和每元素代价。
Amdahl 定律：先算优化的收益上限。把一大块优化一点点，胜过把一小块优化到极致。
优化优先级：算法/数据结构 → 访存模式 → 消除循环低效 → 手工微调。顺序不能反。
三个反复出现的低效模式：循环内重复计算、不必要的函数调用、不必要的内存引用（别名问题）。
ILP 靠打破依赖链获得；多累加器与循环展开是主要手段，注意浮点结合律。
分支不可预测的代价是清空流水线；GPU 上的同构问题是 warp 发散。
编译器负责局部指令级优化，人负责结构级优化。这条边界决定了力气该往哪花。
永远先度量再优化。

自测问题

一段代码消耗 $500 + 2n$ 个周期。它的固定开销和 CPE 分别是多少？如果 $n$ 从 1000 增到 100 万，总时间里固定开销占多大比例？
程序 60% 的时间在一个函数里。把它优化 3 倍，整体加速比是多少？如果改成优化一个只占 10% 但能优化 100 倍的部分呢？哪个更划算？
为什么把累加器从"指针指向的内存"改成"局部变量"会有明显提升？用"别名"解释。
写出一个 CPE 下限被依赖链卡住的循环，并改写它来打破依赖链。
举出一个"编译器不会做、但你能做"的优化，并说明编译器为什么不做。
为什么"输入已排序"能让一段条件求和代码快好几倍，哪怕运算次数完全相同？