计算机系统 - 程序性能优化

This post is not yet available in English. Showing the original version.

June 11, 2026 Notes 学习 / 计算机系统 zh-CN

Table of Contents

〇、性能度量基础

0.1 程序性能的表达

指标	含义	说明
CPE	Cycles Per Element	处理每个数据元素所需的时钟周期数，越小越快
CPI	Cycles Per Instruction	每条指令平均时钟周期数
IPC	Instructions Per Cycle	每周期完成的指令数（= 1/CPI）
吞吐量	Throughput	单位时间内完成的操作数
延迟	Latency	一次操作从开始到完成的总时间

优化的核心目标：降低 CPE。同一个算法，通过代码写法、编译器选项和硬件利用方式的不同，CPE 可以相差数倍甚至数十倍。

0.2 Amdahl 定律

对系统某部分加速时，整体加速比受该部分占比限制。

S = \frac{1}{(1 - f) + \frac{f}{k}}

符号	含义
$f$	可优化部分占总执行时间的比例
$k$	该部分的加速倍数
$S$	整体加速比

例子：某程序 60% 时间花在循环 A 上，将 A 加速 3 倍：

S = \frac{1}{0.4 + \frac{0.6}{3}} = \frac{1}{0.4 + 0.2} = \frac{1}{0.6} ≈ 1.67

启示：即使把 A 加速到无限快（ $k → ∞$ ），整体也最多加速 $\frac{1}{0.4} = 2.5$ 倍。优化要先找瓶颈，对占比小的部分做极致优化收益很低。

一、代码级优化

这一层不依赖编译器，靠程序员改写代码来消除不必要的开销。

1.1 消除循环低效（Code Motion）

把每次迭代都会计算但结果不变的表达式移到循环外面。

// ❌ 优化前：strlen 每次循环都被调用，O(n²)
for (int i = 0; i < strlen(s); i++) {
    // ...
}

// ✅ 优化后：提到循环外
int len = strlen(s);
for (int i = 0; i < len; i++) {
    // ...
}

为什么编译器不一定能帮你做？ 编译器无法确定 strlen(s) 是否有副作用——如果循环体里修改了 s 的内容，每次调用 strlen 的结果可能不同。编译器必须保守，不敢擅自移动。

1.2 减少函数调用开销

// ❌ 每次循环调用 get_length()
for (int i = 0; i < get_length(v); i++) {
    int val = get_element(v, i);
    // ...
}

// ✅ 直接访问数据，消除调用
int length = v->length;
int *data = v->data;
for (int i = 0; i < length; i++) {
    int val = data[i];
    // ...
}

函数调用本身有开销（压栈、跳转、返回），更重要的是它会阻止编译器做进一步优化——编译器把函数调用当作"黑盒"，不敢假设函数没有副作用。

1.3 消除不必要的内存访问

// ❌ 每次循环都写回内存
void sum(int *data, int n, int *result) {
    *result = 0;
    for (int i = 0; i < n; i++)
        *result += data[i];  // 每次迭代：读 *result → 加 → 写 *result
}

// ✅ 用局部变量累加，最后一次写回
void sum(int *data, int n, int *result) {
    int acc = 0;
    for (int i = 0; i < n; i++)
        acc += data[i];       // acc 在寄存器中，无需访存
    *result = acc;
}

为什么编译器不能自动做？ 因为内存别名（Memory Aliasing）：编译器不知道 result 是否指向 data 数组内部的某个元素。如果 result == &data[3]，两种写法的结果就不同——编译器必须保守地每次都写回内存。

1.4 强度削减（Strength Reduction）

用代价低的运算替换代价高的运算。

替换	说明
乘法 → 移位 + 加法	`x * 8` → `x << 3`
除法 → 移位	`x / 4` → `x >> 2`（无符号数）
乘法 → 累加	循环中 `i * k` → 每次迭代加 `k`

// ❌ 每次循环做乘法
for (int i = 0; i < n; i++)
    a[i * 4] = 0;

// ✅ 强度削减：乘法 → 加法
for (int j = 0; j < n * 4; j += 4)
    a[j] = 0;

1.5 公共子表达式消除

// ❌ 重复计算
int u = a * b + c;
int v = a * b + d;

// ✅ 提取公共部分
int t = a * b;
int u = t + c;
int v = t + d;

1.6 小结：代码级优化速查表

技术	目标	效果
Code Motion	循环不变量外提	减少重复计算
减少函数调用	消除调用开销 + 暴露优化机会	允许编译器进一步优化
消除内存访问	用寄存器变量替代指针反复读写	避免 aliasing 导致的冗余访存
强度削减	高代价运算 → 低代价运算	降低每次迭代的指令延迟
公共子表达式消除	提取重复计算	减少运算次数

二、编译器优化

2.1 优化级别

以 GCC 为例：

级别	含义	典型优化
`-O0`	不优化（默认）	便于调试，代码与源码一一对应
`-O1`	基础优化	常量折叠、死代码消除、简单的寄存器分配
`-O2`	标准优化	循环优化、指令调度、更积极的内联
`-O3`	激进优化	自动向量化（SIMD）、函数内联、循环展开
`-Os`	优化代码体积	类似 `-O2` 但避免增大代码的优化

2.2 编译器能做的

优化	说明
常量折叠	`x = 3 * 4` → `x = 12`，编译期直接算好
常量传播	`a = 5; b = a + 1;` → `b = 6;`
死代码消除	删除不可达代码或结果未被使用的计算
内联展开	将小函数体直接插入调用处，消除调用开销
循环展开	减少循环控制开销（详见处理器级优化部分）
寄存器分配	将频繁使用的变量分配到寄存器
指令调度	重排指令顺序以减少流水线停顿
自动向量化	用 SIMD 指令（如 SSE/AVX）一次处理多个数据

2.3 编译器做不了的（优化的障碍）

编译器必须保证优化后的程序行为与原程序完全一致，因此遇到以下情况时会放弃优化：

内存别名（Memory Aliasing）

void foo(int *p, int *q) {
    *p += 1;
    *q += 1;
    *p += 1;
}

编译器不敢把两次 *p += 1 合并为 *p += 2——因为 p 和 q 可能指向同一地址。如果 p == q，合并后结果会从 +3 变成 +2 + 1 = +3……等等，这个例子中恰好结果一样。换一个：

void bar(int *p, int *q) {
    *p = 10;
    *q = 20;
    int x = *p;  // 如果 p == q，x 应为 20，不是 10
}

编译器不能假设 x = 10（常量传播），因为 *q = 20 可能已经覆盖了 *p。

C99 的 restrict：程序员用 restrict 关键字承诺"这个指针指向的内存不会被其他指针修改"，从而允许编译器大胆优化。

函数副作用

int counter = 0;
int f() { return counter++; }

int x = f() + f();  // 编译器不能优化为 2 * f()

关键理解：编译器只做安全的优化。如果你知道某个函数无副作用、某两个指针不会别名，就需要程序员主动把优化做了，或者用 restrict、const、inline 等关键字给编译器更多信息。

三、处理器级优化

这一层的优化是利用现代 CPU 的微架构特性，让代码的执行模式与硬件更契合。

3.1 理解现代 CPU 的执行模型

现代处理器（如 Intel Core 系列）远不只是"五级流水线"，它们使用超标量 + 乱序执行：

特性	说明
超标量（Superscalar）	每个周期可以发射多条指令到不同功能单元
乱序执行（OoO）	不按程序顺序，而是数据就绪即执行
多功能单元	有多个加法器、乘法器、load/store 单元可并行工作
寄存器重命名	消除假依赖（WAR、WAW），暴露更多并行度
分支预测	在分支结果确定之前就投机执行预测路径

关键概念：延迟（Latency）vs 吞吐量（Throughput）

操作延迟（周期）吞吐量（周期/操作）
整数加法 1 0.5（每周期可做 2 次）
整数乘法 3 1
浮点加法 3 1
浮点乘法 5 1~2
除法 20~40 20~40

延迟 = 一次操作从输入到输出的完整时间；吞吐量 = 流水化后每隔多久可以启动下一次操作。乘法延迟 3 周期但吞吐量 1 周期——因为乘法单元是流水化的，上一个乘法还在算的时候下一个已经可以进去了。

操作	延迟（周期）	吞吐量（周期/操作）
整数加法	1	0.5（每周期可做 2 次）
整数乘法	3	1
浮点加法	3	1
浮点乘法	5	1~2
除法	20~40	20~40

3.2 循环展开（Loop Unrolling）

将循环体复制多份，减少循环控制开销（分支、自增、比较），同时给 CPU 更多指令级并行的机会。

// ❌ 原始循环
for (int i = 0; i < n; i++)
    sum += a[i];

// ✅ 2×1 展开
for (int i = 0; i < n - 1; i += 2) {
    sum += a[i];
    sum += a[i + 1];
}
if (n % 2) sum += a[n - 1];  // 处理剩余

展开本身效果有限——因为 sum += a[i] 和 sum += a[i+1] 之间仍有数据依赖（都要等上一次加法的结果写入 sum）。真正的威力要配合下面的技术。

3.3 多路并行累加（Multiple Accumulators）

打破数据依赖链，让 CPU 的多个功能单元同时工作。

// ✅ 2×2 展开 + 双累加器
int sum0 = 0, sum1 = 0;
for (int i = 0; i < n - 1; i += 2) {
    sum0 += a[i];      // 独立的依赖链 ①
    sum1 += a[i + 1];  // 独立的依赖链 ②
}
int sum = sum0 + sum1;

flowchart LR
    subgraph 依赖链①
        A0["a[0]"] --> S0_1["sum0"] --> A2["a[2]"] --> S0_2["sum0"] --> A4["a[4]"]
    end
    subgraph 依赖链②
        A1["a[1]"] --> S1_1["sum1"] --> A3["a[3]"] --> S1_2["sum1"] --> A5["a[5]"]
    end

效果：两条独立的依赖链可以在不同功能单元上并行执行，CPE 接近减半。如果 CPU 有 k 个加法单元，理论上用 k 路累加器就能打满吞吐量。

3.4 重结合变换（Reassociation）

改变运算的结合顺序，缩短关键路径。

// ❌ 原始：每步都依赖上一步的 sum
sum = ((sum + a[0]) + a[1]) + a[2];
//    ^^^^^^^^^^ 必须先算完才能 + a[1]

// ✅ 重结合：先算括号内，再合并
sum = sum + (a[0] + a[1]);
//           ^^^^^^^^^^^^^ 这部分可以独立计算，不依赖 sum

// 在循环中的体现：
// ❌ 顺序依赖
for (int i = 0; i < n - 1; i += 2)
    sum = (sum + a[i]) + a[i+1];  // 关键路径长度 = 2×加法延迟

// ✅ 重结合
for (int i = 0; i < n - 1; i += 2)
    sum = sum + (a[i] + a[i+1]);  // a[i]+a[i+1] 与 sum 并行 → 关键路径 = 1×加法延迟

注意：对整数来说结合律成立，编译器理论上可以做这个变换。但对浮点数，加法不满足结合律（舍入误差），编译器不会自动做——需要程序员手动改。

3.5 分支预测友好的代码

CPU 流水线深度可达 15~~20 级，分支预测失败的代价是冲刷整条流水线（15~~20 个周期的惩罚）。

// ❌ 分支难以预测（数据依赖的随机分支）
for (int i = 0; i < n; i++) {
    if (a[i] > threshold)
        sum += a[i];
}

// ✅ 用条件移动消除分支（编译器可能自动做）
for (int i = 0; i < n; i++) {
    int mask = -(a[i] > threshold);  // 全 1 或全 0
    sum += a[i] & mask;
}

技巧	说明
减少不可预测的分支	数据相关的条件分支预测准确率低
用条件移动（`cmov`）	将 if-else 转为无分支的条件赋值
有规律的分支更好	总是执行 / 总是不执行 / 交替 → 预测器容易学习

3.6 缓存友好编程（Cache-Friendly Code）

内存访问是最大的性能杀手之一（L1 命中 ~4 周期，主存 ~200 周期）。写出缓存友好的代码就是要提高时间局部性和空间局部性。

空间局部性：按行优先访问

// ❌ 逐列访问（步长 = N，每次跳过一整行）
for (int j = 0; j < N; j++)
    for (int i = 0; i < N; i++)
        sum += a[i][j];  // 每次跳 N 个元素 → 缓存行不断被换出

// ✅ 逐行访问（步长 = 1，连续访问）
for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
        sum += a[i][j];  // 顺序访问 → 每个缓存行充分利用

C 语言二维数组按**行优先（Row-major）**存储，a[i][0] 到 a[i][N-1] 在内存中连续。逐行访问步长为 1，正好匹配缓存行预取。

时间局部性：分块（Blocking / Tiling）

处理大矩阵时，将矩阵分成小块，让每一块能装进缓存，在块内完成尽可能多的操作再换下一块。

// 矩阵乘法分块示意
for (int ii = 0; ii < N; ii += B)
  for (int jj = 0; jj < N; jj += B)
    for (int kk = 0; kk < N; kk += B)
      // B×B 的小块乘法
      for (int i = ii; i < ii + B; i++)
        for (int j = jj; j < jj + B; j++)
          for (int k = kk; k < kk + B; k++)
            C[i][j] += A[i][k] * B[k][j];

选择合适的块大小 B，使三个 B×B 的块（A 的一块、B 的一块、C 的一块）总共能装入 L1 Cache。

3.7 关键路径与性能瓶颈分析

优化循环的核心思路是找到关键路径（Critical Path）——循环中最长的数据依赖链决定了最小 CPE。

以向量求和为例：

写法	关键路径	CPE（整数加法，延迟=1）
原始	n 次串行加法	1.0
2×1 展开	n 次串行加法（没变！）	1.0
2×2 多路累加	n/2 次串行加法 × 2 路并行	0.5（如果有 2 个加法单元）
2×1a 重结合	n/2 次串行加法	0.5

CPE 的下界由两个因素决定，取较大者：

延迟界（Latency Bound）：关键路径上的总延迟 / 元素数

吞吐量界（Throughput Bound）：功能单元的最大吞吐量

只展开不拆依赖链 → 受延迟界限制。多路累加 / 重结合 → 突破延迟界，逼近吞吐量界。

四、总结：优化层次与优先级

flowchart TD
    A["① 选对算法和数据结构"] --> B["② 代码级优化"]
    B --> C["③ 利用编译器优化"]
    C --> D["④ 处理器级优化"]
    style A fill:#e8f5e9
    style B fill:#e3f2fd
    style C fill:#fff3e0
    style D fill:#fce4ec

优先级	层次	效果量级	说明
最高	算法 + 数据结构	O(n²) → O(n log n)	这是最大的杠杆，任何底层优化都弥补不了算法的差距
高	代码级优化	2~5×	消除冗余计算、减少内存访问
中	编译器优化	1.5~3×	用 `-O2` / `-O3`，给编译器足够的信息（`restrict`、`inline`）
可观	处理器级优化	2~10×	循环展开 + 多路累加 + 缓存友好

先 profile，再优化。用 gprof、perf、valgrind --tool=cachegrind 等工具找到热点，然后集中火力优化瓶颈部分——Amdahl 定律告诉我们，优化非热点代码几乎没有收益。

Loading comments...