10 · 旧期中扩展：程序性能优化
对应教材第 5 章及旧卷优化题；不属于日程所示第一次阶段测验范围。
先保持语义，再谈快慢#
编译器受语言语义、别名、函数副作用、可见 I/O、溢出规则和浮点舍入约束。两个数学等式不一定是等价 C 程序。优化后要按相同输入、编译器、选项、硬件与计时口径比较。
| 阻碍 | 为什么不能随便改 |
|---|---|
| 函数调用 | f() 可能改变状态，两次 f() 不一定相同 |
| 指针别名 | 写 *p 可能影响随后读 *q |
| 浮点重结合 | 改变舍入次序，结果可能不同 |
| volatile / 可见 I/O | 访问次数与顺序可能本身就是语义 |
| 未定义行为 | 不能用一次“恰巧运行成功”证明合法性 |
异或交换在 p、q 指同一对象时会把值清零；临时变量交换则保留值。把循环中的 B[i] 缓存到临时变量，只有确认 A/B 不发生相关别名写读依赖后才可保语义。
计量与瓶颈#
总时间、周期数、CPI（每指令周期）、IPC、CPE（每元素周期）不同。循环常用 T(n)≈CPE·n+固定开销，从多组规模的斜率估计 CPE；只比较小 n 会把调用/计时开销误当循环成本。
指令延迟是一个输入到结果可用需要多久；发射间隔/吞吐是连续开始多少次运算的能力。某乘法器延迟 4 周期、每周期可发射一次，独立乘法可并行，但依赖链仍每步等 4 周期。
常见源代码优化#
- 消除循环不变量：长度不变时把 strlen 放循环外；如果循环会修改字符串，不能直接移动。
- 减少函数调用：在确认 getter/length 语义后消除重复调用。
- 减少内存访问：把累积值保存在局部变量，循环后写回，但要检查别名。
- 强度削减：用地址递增或便宜运算代替重复乘法；现代编译器也可能自动做。
- 循环展开：减少分支与索引更新，暴露更多独立工作；要保留尾部元素处理。
- 多路累积：拆开依赖链；浮点结果通常改变，只有题设允许时使用。
- 重结合与 SIMD：提高并行度，同时检查代数与内存边界、对齐和剩余项。
展开可能增加代码体积、寄存器压力、溢出到栈的 spill 和指令缓存压力，因此展开越多不一定越快。
延迟界与吞吐界#
考虑每元素一次乘法，运算延迟 L、机器吞吐每周期最多 U 次乘法。单累积链的 CPE 通常受 L 限制；k 个独立累积链理想依赖界约 L/k，同时受吞吐界 1/U 限制，还受 load、地址生成与分支资源约束。
例如 L=4、U=1：1 个累积器依赖界 4，2 个约 2，4 个约 1；再加到 8 个并不能突破每周期一个乘法的吞吐界。这里只是约束下界，不是保证实测必然达到。
微体系结构视角#
现代处理器可能超标量、乱序执行、寄存器重命名与分支预测。真数据依赖（RAW）不能靠重命名消除；名字依赖（WAR/WAW）可通过物理寄存器重命名处理。加载可能在存储之前执行，但要检测地址依赖；同址写后读可能依赖 store-to-load forwarding。
条件传送可减少不可预测分支，但会增加数据依赖和候选计算；高度可预测分支不一定比 cmov 慢。链表指针追逐因为下一个地址依赖前一个加载，难以并行，数组连续访问则更容易预取和向量化。
存储访问、分块与剖析#
矩阵循环交换改善行优先空间局部性，但要确保依赖允许交换。分块让一小片工作集在 cache 中反复使用，降低容量与冲突失效。结构体数组（AoS）与成员数组（SoA）对只访问部分字段、向量化等场景有不同效果，没有一劳永逸的最佳布局。
剖析先找热点，再针对瓶颈修改。Amdahl 定律解释为什么只优化占总时间很小的代码收益有限；不仅比较“某函数快了几倍”，还应看整个程序时间。
自检#
给一个优化能指出所有语义前提；能解释展开与多路累积的不同；能画出累积依赖链；能计算 CPE 下界并列出硬件资源限制；能说明 strlen 外提何时合法。