732 lines
21 KiB
Markdown
732 lines
21 KiB
Markdown
# 18. 程序代码优化
|
||
|
||
> **课程**: 操作系统 - 程序代码优化
|
||
> **核心内容**: 机器无关优化、代码移动、消除不必要的内存引用、优化障碍（指针别名、函数副作用）、性能度量
|
||
|
||
---
|
||
|
||
## 前置知识
|
||
- [[03_C语言编程基础]] -- C语言编译链接过程、指针与内存模型
|
||
- [[13_存储管理基础]] -- 存储器层次结构、局部性原理
|
||
|
||
---
|
||
|
||
## 一、代码优化的概念与意义
|
||
|
||
### 1.1 为什么需要代码优化
|
||
|
||
> [!important] 核心观点
|
||
> 常数因子也很重要！根据代码编写方式的不同，程序性能可能相差 **10倍** 以上。必须在多个层次上进行优化：算法、数据表示、过程调用和循环。
|
||
|
||
代码优化的目标：
|
||
- 理解程序如何被编译和执行
|
||
- 学习如何度量程序性能并识别瓶颈
|
||
- 在不破坏代码模块化和通用性的前提下提升性能
|
||
|
||
### 1.2 优化的层次
|
||
|
||
```mermaid
|
||
graph TB
|
||
A["算法优化<br/>选择更高效的算法"] --> B["数据结构优化<br/>选择合适的内存布局"]
|
||
B --> C["编译器优化<br/>利用编译器选项"]
|
||
C --> D["源代码级优化<br/>代码移动、消除冗余"]
|
||
D --> E["指令级优化<br/>利用底层硬件特性"]
|
||
|
||
style A fill:#e8f5e9
|
||
style B fill:#e1f5fe
|
||
style C fill:#fff3e0
|
||
style D fill:#fce4ec
|
||
style E fill:#f3e5f5
|
||
```
|
||
|
||
### 1.3 编译器优化级别
|
||
|
||
| 优化级别 | 说明 | 特点 |
|
||
|---------|------|------|
|
||
| `-O0` | 不优化 | 编译最快，调试最方便，性能最差 |
|
||
| `-O1` | 基本优化 | 消除冗余代码、简单内联，平衡编译速度和性能 |
|
||
| `-O2` | 推荐优化 | 启用大多数优化，包括循环优化、指令调度等 |
|
||
| `-O3` | 激进优化 | 包含 `-O2` 所有优化，加上循环展开、SIMD向量化等 |
|
||
|
||
```bash
|
||
# 不同优化级别的编译
|
||
gcc -O0 prog.c -o prog_O0 # 无优化（调试用）
|
||
gcc -O1 prog.c -o prog_O1 # 基本优化
|
||
gcc -O2 prog.c -o prog_O2 # 推荐优化
|
||
gcc -O3 prog.c -o prog_O3 # 激进优化
|
||
|
||
# 比较不同优化级别的汇编输出
|
||
gcc -O0 -S prog.c -o prog_O0.s
|
||
gcc -O2 -S prog.c -o prog_O2.s
|
||
diff prog_O0.s prog_O2.s
|
||
```
|
||
|
||
> [!tip] 编译器的局限性
|
||
> 编译器通常**不会**改善渐近效率（大O复杂度），这取决于程序员选择最优算法。大O节省通常比常数因子更重要，但常数因子也确实重要。编译器在面对"优化障碍"时往往难以进行优化。
|
||
|
||
---
|
||
|
||
## 二、性能度量：CPE（每元素周期数）
|
||
|
||
### 2.1 CPE 概念
|
||
|
||
CPE（Cycles Per Element）是度量向量或列表操作程序性能的便捷方式：
|
||
|
||
$$T = CPE \times n + Overhead$$
|
||
|
||
其中 $n$ 是向量长度，$T$ 是总执行时间（时钟周期数）。
|
||
|
||
### 2.2 时间尺度
|
||
|
||
| 指标 | 说明 |
|
||
|------|------|
|
||
| 绝对时间 | 通常使用纳秒（$10^{-9}$ 秒） |
|
||
| 时钟周期 | 100 MHz → 10ns/周期；2 GHz → 0.5ns/周期 |
|
||
|
||
### 2.3 CPE 度量示例
|
||
|
||
```c
|
||
// psum1: 朴素前缀和
|
||
void psum1(float a[], float p[], long int n) {
|
||
long int i;
|
||
p[0] = a[0];
|
||
for (i = 0; i < n; i++)
|
||
p[i] = p[i-1] + a[i];
|
||
}
|
||
|
||
// psum2: 循环展开的前缀和
|
||
void psum2(float a[], float p[], long int n) {
|
||
long int i;
|
||
p[0] = a[0];
|
||
for (i = 1; i < n-1; i += 2) {
|
||
float mid_val = p[i-1] + a[i];
|
||
p[i] = mid_val;
|
||
p[i+1] = mid_val + a[i+1];
|
||
}
|
||
if (i < n)
|
||
p[i] = p[i-1] + a[i];
|
||
}
|
||
```
|
||
|
||
> [!note] 性能对比
|
||
> `psum2` 通过循环展开减少了关键路径上的操作次数，从而降低了 CPE。
|
||
|
||
---
|
||
|
||
## 三、优化实例：向量求和的逐步优化
|
||
|
||
### 3.1 向量 ADT 定义
|
||
|
||
```c
|
||
typedef int data_t;
|
||
|
||
typedef struct {
|
||
int len;
|
||
data_t *data;
|
||
} vec_rec, *vec_ptr;
|
||
```
|
||
|
||
相关操作：
|
||
- `new_vec(len)` -- 创建指定长度的向量
|
||
- `vec_length(v)` -- 返回向量长度
|
||
- `get_vec_start(v)` -- 返回向量数据起始指针
|
||
- `get_vec_element(v, index, &dest)` -- 获取指定下标的元素（带边界检查）
|
||
|
||
### 3.2 combine1：抽象版本（基线）
|
||
|
||
```c
|
||
void combine1(vec_ptr v, data_t *dest) {
|
||
long int i;
|
||
*dest = IDENT;
|
||
for (i = 0; i < vec_length(v); i++) {
|
||
data_t val;
|
||
get_vec_element(v, i, &val);
|
||
*dest = *dest OP val;
|
||
}
|
||
}
|
||
```
|
||
|
||
> [!warning] 问题分析
|
||
> 每次循环迭代都调用 `vec_length(v)`，即使其返回值始终不变。这属于**循环不变量**问题。
|
||
|
||
### 3.3 combine2：代码移动（Code Motion）
|
||
|
||
```c
|
||
void combine2(vec_ptr v, data_t *dest) {
|
||
long int i;
|
||
long int length = vec_length(v); // 移出循环
|
||
*dest = IDENT;
|
||
for (i = 0; i < length; i++) {
|
||
data_t val;
|
||
get_vec_element(v, i, &val);
|
||
*dest = *dest OP val;
|
||
}
|
||
}
|
||
```
|
||
|
||
> [!tip] 代码移动优化
|
||
> 将 `vec_length()` 调用从循环体内移到循环之前。循环不变量外提（Loop-Invariant Code Motion）是最基本的优化之一。
|
||
|
||
### 3.4 combine3：消除过程调用（Reduction in Strength）
|
||
|
||
```c
|
||
void combine3(vec_ptr v, data_t *dest) {
|
||
long int i;
|
||
long int length = vec_length(v);
|
||
data_t *data = get_vec_start(v); // 获取数据指针
|
||
*dest = IDENT;
|
||
for (i = 0; i < length; i++) {
|
||
*dest = *dest OP data[i]; // 直接数组访问
|
||
}
|
||
}
|
||
```
|
||
|
||
**优化要点**：避免每次迭代都调用 `get_vec_element()` 函数来获取元素，而是在循环前获取数据指针，循环内直接进行指针引用。
|
||
|
||
### 3.5 combine4：消除不必要的内存引用
|
||
|
||
```c
|
||
void combine4(vec_ptr v, data_t *dest) {
|
||
long int i;
|
||
long int length = vec_length(v);
|
||
data_t *data = get_vec_start(v);
|
||
data_t acc = IDENT; // 使用局部变量累积
|
||
for (i = 0; i < length; i++)
|
||
acc = acc OP data[i];
|
||
*dest = acc; // 最后一次性写回
|
||
}
|
||
```
|
||
|
||
**汇编对比**：
|
||
|
||
```
|
||
combine3 的循环体（每次迭代需要3条内存指令）:
|
||
movss (%rbp), %xmm0 # 从 dest 读取累加值
|
||
mulss (%rax,%rdx,4), %xmm0 # 乘以 data[i]
|
||
movss %xmm0, (%rbp) # 写回 dest
|
||
addq $1, %rdx # i++
|
||
cmpq %rdx, %r12 # 比较 i:limit
|
||
jg .L498 # 循环跳转
|
||
|
||
combine4 的循环体（只有1条内存指令）:
|
||
mulss (%rax,%rdx,4), %xmm0 # acc *= data[i]
|
||
addq $1, %rdx # i++
|
||
cmpq %rdx, %rbp # 比较 limit:i
|
||
jg .L488 # 循环跳转
|
||
```
|
||
|
||
> [!important] 优化效果
|
||
> - `combine3`：每次迭代需要 **1次读 + 1次写** 内存
|
||
> - `combine4`：每次迭代只需要 **0次** 额外内存访问（`acc` 在寄存器中）
|
||
> - 局部变量 `acc` 告诉编译器：不需要在每轮循环都检查内存别名
|
||
|
||
### 3.6 优化效果汇总
|
||
|
||
| 函数 | 优化方法 | 整数+ CPE | 整数* CPE | 浮点+ CPE |
|
||
|------|---------|----------|----------|----------|
|
||
| combine1 | 抽象接口 | 12.00 | 12.00 | 12.00 |
|
||
| combine2 | 代码移动 | -- | -- | -- |
|
||
| combine3 | 消除过程调用 | -- | -- | -- |
|
||
| combine4 | 使用临时变量累积 | **2.00** | **3.00** | **3.00** |
|
||
|
||
---
|
||
|
||
## 四、代码移动（Code Motion）详解
|
||
|
||
### 4.1 循环不变量外提
|
||
|
||
将循环中每次迭代结果相同的计算移到循环之前：
|
||
|
||
```c
|
||
// 优化前：strlen 在每次循环都被调用
|
||
void lower1(char *s) {
|
||
int i;
|
||
for (i = 0; i < strlen(s); i++) // O(n^2) 复杂度！
|
||
if (s[i] >= 'A' && s[i] <= 'Z')
|
||
s[i] -= ('A' - 'a');
|
||
}
|
||
|
||
// 优化后：strlen 只调用一次
|
||
void lower2(char *s) {
|
||
int i;
|
||
int len = strlen(s); // O(n) 复杂度
|
||
for (i = 0; i < len; i++)
|
||
if (s[i] >= 'A' && s[i] <= 'Z')
|
||
s[i] -= ('A' - 'a');
|
||
}
|
||
```
|
||
|
||
> [!warning] 为什么编译器不能自动做这个优化？
|
||
> `strlen` 是一个函数调用，编译器**不知道**它是否有副作用，也不知道字符串长度在循环中是否会改变。编译器必须保守处理。
|
||
|
||
### 4.2 strlen 的内部实现
|
||
|
||
```c
|
||
size_t strlen(const char *s) {
|
||
int length = 0;
|
||
while (*s != '\0') {
|
||
s++;
|
||
length++;
|
||
}
|
||
return length;
|
||
}
|
||
```
|
||
|
||
`strlen` 本身是 $O(n)$ 的。如果在循环中每次迭代都调用它，整体复杂度就变成了 $O(n^2)$。
|
||
|
||
---
|
||
|
||
## 五、优化障碍（Optimization Blockers）
|
||
|
||
编译器在进行优化时受到两大根本性约束：
|
||
1. 编译器在**任何可能的条件下**都不能改变程序的行为
|
||
2. 当程序员知道的信息比编译器多时，需要程序员主动干预
|
||
|
||
### 5.1 指针别名（Memory Aliasing）
|
||
|
||
> [!danger] 别名问题
|
||
> 当两个不同的内存引用指向同一个存储位置时，就产生了别名。C语言允许地址算术运算和直接访问存储结构，因此别名问题非常容易出现。
|
||
|
||
```c
|
||
// twiddle1 和 twiddle2 看似等价，但实际上不一定！
|
||
void twiddle1(int *xp, int *yp) {
|
||
*xp += *yp;
|
||
*xp += *yp;
|
||
}
|
||
|
||
void twiddle2(int *xp, int *yp) {
|
||
*xp += 2 * *yp;
|
||
}
|
||
```
|
||
|
||
**当 `xp == yp` 时（别名情况）**：
|
||
- `twiddle1`：`*xp = *xp + *xp = 2*xp`，然后 `*xp = 2*xp + 2*xp = 4*xp`
|
||
- `twiddle2`：`*xp = *xp + 2*(*xp) = 3*xp`
|
||
- 结果不同！编译器不能将 `twiddle1` 优化为 `twiddle2`
|
||
|
||
**别名实例演示**：
|
||
|
||
```c
|
||
// v = [2, 3, 5]
|
||
combine3(v, get_vec_start(v) + 2); // dest 指向 v->data[2]
|
||
combine4(v, get_vec_start(v) + 2); // dest 指向 v->data[2]
|
||
```
|
||
|
||
| 函数 | 初始 | i=0 | i=1 | i=2 | 最终 |
|
||
|------|------|-----|-----|-----|------|
|
||
| combine3 | [2,3,5] | [2,3,1] | [2,3,2] | [2,3,6] | [2,3,36] |
|
||
| combine4 | [2,3,5] | [2,3,5] | [2,3,5] | [2,3,5] | [2,3,30] |
|
||
|
||
> [!tip] 避免别名问题的方法
|
||
> 养成使用**局部变量**的习惯。在循环中用局部变量累积结果，循环结束后再写回目标地址。这是告诉编译器"不需要检查别名"的方式。
|
||
|
||
### 5.2 函数调用的副作用
|
||
|
||
```c
|
||
int f(int);
|
||
|
||
// func1：调用 f 4次
|
||
int func1(int x) {
|
||
return f(x) + f(x) + f(x) + f(x);
|
||
}
|
||
|
||
// func2：调用 f 1次
|
||
int func2(int x) {
|
||
return 4 * f(x);
|
||
}
|
||
```
|
||
|
||
看起来 `func1` 可以优化为 `func2`，但当 `f` 有副作用时就不行了：
|
||
|
||
```c
|
||
int counter = 0;
|
||
int f(int x) {
|
||
return counter++; // 每次调用返回不同的值！
|
||
}
|
||
```
|
||
|
||
> [!warning] 编译器的保守策略
|
||
> 编译器通常假设函数调用可能有副作用，因此不会轻易将多次函数调用合并。程序员可以：
|
||
> - 使用 `inline` 关键字建议编译器内联
|
||
> - 使用 `const`、`pure` 等属性标记无副作用的函数
|
||
> - 将函数调用结果缓存到局部变量中
|
||
|
||
---
|
||
|
||
## 六、循环优化技术
|
||
|
||
### 6.1 循环展开（Loop Unrolling）
|
||
|
||
减少循环控制开销，增加指令级并行性：
|
||
|
||
```c
|
||
// 优化前
|
||
for (int i = 0; i < n; i++) {
|
||
sum += a[i];
|
||
}
|
||
|
||
// 2x 循环展开
|
||
int i;
|
||
for (i = 0; i < n - 1; i += 2) {
|
||
sum += a[i] + a[i+1];
|
||
}
|
||
for (; i < n; i++) { // 处理剩余元素
|
||
sum += a[i];
|
||
}
|
||
```
|
||
|
||
### 6.2 循环合并（Loop Fusion）
|
||
|
||
将多个独立循环合并为一个，改善数据局部性：
|
||
|
||
```c
|
||
// 优化前：两次遍历
|
||
for (int i = 0; i < n; i++)
|
||
a[i] = b[i] + c[i];
|
||
for (int i = 0; i < n; i++)
|
||
d[i] = a[i] * 2;
|
||
|
||
// 优化后：一次遍历
|
||
for (int i = 0; i < n; i++) {
|
||
a[i] = b[i] + c[i];
|
||
d[i] = a[i] * 2;
|
||
}
|
||
```
|
||
|
||
### 6.3 循环不变量外提（Loop-Invariant Code Motion）
|
||
|
||
将循环中不变的计算移到循环外：
|
||
|
||
```c
|
||
// 优化前
|
||
for (int i = 0; i < n; i++) {
|
||
a[i] = b[i] * (x * y + z); // x*y+z 在循环中不变
|
||
}
|
||
|
||
// 优化后
|
||
int tmp = x * y + z;
|
||
for (int i = 0; i < n; i++) {
|
||
a[i] = b[i] * tmp;
|
||
}
|
||
```
|
||
|
||
### 6.4 循环优化流程图
|
||
|
||
```mermaid
|
||
flowchart TD
|
||
A["循环代码"] --> B{"循环体中有<br>不变量？"}
|
||
B -->|是| C["循环不变量外提"]
|
||
B -->|否| D{"循环迭代<br>次数少？"}
|
||
C --> D
|
||
D -->|是| E["循环展开"]
|
||
D -->|否| F{"多个循环<br>数据相关？"}
|
||
E --> F
|
||
F -->|是| G["循环合并"]
|
||
F -->|否| H["保持原样"]
|
||
G --> I["优化后的循环"]
|
||
H --> I
|
||
```
|
||
|
||
---
|
||
|
||
## 七、内存访问优化与缓存友好性
|
||
|
||
### 7.1 空间局部性与时间局部性
|
||
|
||
程序的局部性原理（参见 [[13_存储管理基础]]）是内存优化的基础：
|
||
|
||
- **空间局部性**：访问了某个地址，附近地址很可能也会被访问
|
||
- **时间局部性**：刚访问过的数据很可能再次被访问
|
||
|
||
### 7.2 按行优先 vs 按列遍历
|
||
|
||
```c
|
||
#define M 2048
|
||
#define N 2048
|
||
|
||
// 方式P1：按行遍历（空间局部性好）
|
||
int sumarrayrows(int a[M][N]) {
|
||
int i, j, sum = 0;
|
||
for (i = 0; i < M; i++)
|
||
for (j = 0; j < N; j++)
|
||
sum += a[i][j]; // 顺序访问内存
|
||
return sum;
|
||
}
|
||
|
||
// 方式P2：按列遍历（空间局部性差）
|
||
int sumarraycols(int a[M][N]) {
|
||
int i, j, sum = 0;
|
||
for (j = 0; j < N; j++)
|
||
for (i = 0; i < M; i++)
|
||
sum += a[i][j]; // 每次跳过 N 个元素
|
||
return sum;
|
||
}
|
||
```
|
||
|
||
> [!important] 实测性能差距
|
||
> 在 2GHz Intel Pentium 4 上：
|
||
> - **P1（按行遍历）**：59,393,288 时钟周期
|
||
> - **P2（按列遍历）**：1,277,877,876 时钟周期
|
||
> - P1 比 P2 **快 21.5 倍**！
|
||
|
||
### 7.3 局部性分析
|
||
|
||
| 数据 | 按行遍历(P1) | 按列遍历(P2) |
|
||
|------|-------------|-------------|
|
||
| 数组 `a` | 空间局部性好（顺序访问） | 空间局部性差（每次跳2048个单元） |
|
||
| 变量 `sum,i,j` | 时间局部性好（循环中反复访问） | 时间局部性好 |
|
||
| 循环指令 | 空间局部性好 + 时间局部性好 | 空间局部性好 + 时间局部性好 |
|
||
|
||
### 7.4 缓存友好的代码编写原则
|
||
|
||
```mermaid
|
||
graph LR
|
||
A["缓存友好原则"] --> B["按行优先遍历多维数组"]
|
||
A --> C["使用连续内存布局"]
|
||
A --> D["减少跨步访问"]
|
||
A --> E["数据结构对齐缓存行"]
|
||
|
||
style A fill:#e8f5e9
|
||
```
|
||
|
||
---
|
||
|
||
## 八、函数调用优化
|
||
|
||
### 8.1 内联函数（Inline）
|
||
|
||
将函数体直接展开到调用处，消除函数调用开销：
|
||
|
||
```c
|
||
// 优化前：函数调用有开销
|
||
int square(int x) {
|
||
return x * x;
|
||
}
|
||
int result = square(5);
|
||
|
||
// 使用 inline 关键字
|
||
static inline int square_inline(int x) {
|
||
return x * x;
|
||
}
|
||
int result = square_inline(5); // 编译器可能直接展开为 5*5
|
||
```
|
||
|
||
> [!note] 编译器的内联决策
|
||
> 即使不使用 `inline` 关键字，`-O2` 及以上优化级别下，编译器也会自动内联小型函数。但大型函数的内联会增加代码体积，可能导致指令缓存不友好。
|
||
|
||
### 8.2 消除过程调用
|
||
|
||
如 combine3 的优化所示，将函数调用替换为直接内存访问：
|
||
|
||
```c
|
||
// 优化前：每次迭代调用函数
|
||
for (i = 0; i < length; i++) {
|
||
data_t val;
|
||
get_vec_element(v, i, &val); // 函数调用开销
|
||
*dest = *dest OP val;
|
||
}
|
||
|
||
// 优化后：直接指针访问
|
||
data_t *data = get_vec_start(v);
|
||
for (i = 0; i < length; i++) {
|
||
*dest = *dest OP data[i]; // 直接数组访问
|
||
}
|
||
```
|
||
|
||
### 8.3 尾调用优化
|
||
|
||
当函数最后一步是调用另一个函数时，编译器可以复用当前栈帧：
|
||
|
||
```c
|
||
// 优化前：递归可能导致栈溢出
|
||
int factorial(int n) {
|
||
if (n <= 1) return 1;
|
||
return n * factorial(n - 1); // 不是尾调用（乘法在递归之后）
|
||
}
|
||
|
||
// 尾递归版本
|
||
int factorial_tail(int n, int acc) {
|
||
if (n <= 1) return acc;
|
||
return factorial_tail(n - 1, n * acc); // 尾调用
|
||
}
|
||
```
|
||
|
||
---
|
||
|
||
## 九、SIMD 与底层优化
|
||
|
||
### 9.1 SIMD 概念
|
||
|
||
SIMD（Single Instruction, Multiple Data）允许一条指令同时处理多个数据元素：
|
||
|
||
```c
|
||
// 标量版本：一次处理一个元素
|
||
for (int i = 0; i < n; i++) {
|
||
c[i] = a[i] + b[i];
|
||
}
|
||
|
||
// SSE 向量化（伪代码）：一次处理4个float
|
||
// 编译器在 -O3 下可能自动生成 SIMD 指令
|
||
```
|
||
|
||
### 9.2 编译器自动向量化
|
||
|
||
```bash
|
||
# 查看编译器是否进行了向量化
|
||
gcc -O3 -ftree-vectorize -fopt-info-vec prog.c
|
||
|
||
# 明确启用 SIMD 优化
|
||
gcc -O3 -mavx2 prog.c # 使用 AVX2 指令集
|
||
gcc -O3 -msse4.2 prog.c # 使用 SSE4.2 指令集
|
||
```
|
||
|
||
### 9.3 数据对齐
|
||
|
||
```c
|
||
// 确保数据对齐以获得最佳 SIMD 性能
|
||
float *a = aligned_alloc(32, n * sizeof(float)); // 32字节对齐（AVX）
|
||
```
|
||
|
||
---
|
||
|
||
## 十、优化编译器的局限性
|
||
|
||
### 10.1 编译器的基本约束
|
||
|
||
> [!important] 根本约束
|
||
> 编译器在**任何可能的条件下**都不能改变程序的行为。这意味着即使某些行为只在极端情况下发生，编译器也必须保守地保留这些行为。
|
||
|
||
### 10.2 编译器难以优化的情况
|
||
|
||
| 情况 | 原因 | 程序员对策 |
|
||
|------|------|-----------|
|
||
| 指针别名 | 编译器不知道两个指针是否指向同一位置 | 使用局部变量累积结果 |
|
||
| 函数副作用 | 编译器不知道函数是否有副作用 | 使用 `inline`、`const`、`pure` 属性 |
|
||
| 数据范围 | 编译器不知道变量的实际取值范围 | 使用更精确的数据类型 |
|
||
| 循环边界 | 编译器不确定循环次数 | 使用常量或 `restrict` 关键字 |
|
||
|
||
### 10.3 `restrict` 关键字
|
||
|
||
C99 引入的 `restrict` 告诉编译器指针没有别名：
|
||
|
||
```c
|
||
// 使用 restrict 告诉编译器 src 和 dest 不重叠
|
||
void copy(int *restrict dest, const int *restrict src, int n) {
|
||
for (int i = 0; i < n; i++) {
|
||
dest[i] = src[i];
|
||
}
|
||
}
|
||
```
|
||
|
||
---
|
||
|
||
## 十一、性能测量与 Profiling 工具
|
||
|
||
### 11.1 常用性能分析工具
|
||
|
||
| 工具 | 用途 | 命令示例 |
|
||
|------|------|---------|
|
||
| `time` | 测量程序总执行时间 | `time ./prog` |
|
||
| `perf` | Linux 性能计数器分析 | `perf stat ./prog` |
|
||
| `gprof` | GNU 函数级 profiling | `gcc -pg prog.c && ./a.out && gprof` |
|
||
| `valgrind/callgrind` | 缓存和分支预测分析 | `valgrind --tool=callgrind ./prog` |
|
||
| `cachegrind` | 缓存命中率分析 | `valgrind --tool=cachegrind ./prog` |
|
||
|
||
### 11.2 使用 perf 进行分析
|
||
|
||
```bash
|
||
# 基本性能统计
|
||
perf stat ./prog
|
||
|
||
# 详细缓存分析
|
||
perf stat -e cache-references,cache-misses ./prog
|
||
|
||
# 函数级热点分析
|
||
perf record ./prog
|
||
perf report
|
||
```
|
||
|
||
### 11.3 使用 gprof 进行分析
|
||
|
||
```bash
|
||
# 编译时加入 profiling 支持
|
||
gcc -pg -O2 prog.c -o prog
|
||
|
||
# 运行程序（生成 gmon.out）
|
||
./prog
|
||
|
||
# 查看分析结果
|
||
gprof prog gmon.out > analysis.txt
|
||
```
|
||
|
||
### 11.4 优化工作流程
|
||
|
||
```mermaid
|
||
flowchart TD
|
||
A["编写正确的代码"] --> B["选择合适的算法"]
|
||
B --> C["使用 profiling 找到瓶颈"]
|
||
C --> D{"瓶颈在哪里？"}
|
||
D -->|循环| E["循环优化：展开、外提、合并"]
|
||
D -->|内存| F["内存优化：局部性、缓存友好"]
|
||
D -->|函数调用| G["内联、消除过程调用"]
|
||
D -->|I/O| H["缓冲、批量处理"]
|
||
E --> I["测量优化效果"]
|
||
F --> I
|
||
G --> I
|
||
H --> I
|
||
I --> J{"性能满足要求？"}
|
||
J -->|否| C
|
||
J -->|是| K["完成"]
|
||
```
|
||
|
||
---
|
||
|
||
## 十二、优化总结
|
||
|
||
### 12.1 机器无关优化的核心策略
|
||
|
||
| 优化策略 | 说明 | 对应函数 |
|
||
|---------|------|---------|
|
||
| **代码移动** | 将循环不变量移出循环 | combine1 → combine2 |
|
||
| **消除过程调用** | 用直接内存访问替代函数调用 | combine2 → combine3 |
|
||
| **消除不必要内存引用** | 使用局部变量/寄存器累积 | combine3 → combine4 |
|
||
| **循环展开** | 减少循环控制开销 | psum1 → psum2 |
|
||
|
||
### 12.2 关键原则
|
||
|
||
> [!abstract] 代码优化的核心原则
|
||
> 1. **先正确，后优化**：保证代码正确性是前提
|
||
> 2. **度量驱动**：使用 profiling 工具找到真正的瓶颈
|
||
> 3. **算法优先**：$O(n \log n)$ 的算法比 $O(n^2)$ 的优化更重要
|
||
> 4. **利用局部性**：按行访问数组，使用连续内存布局
|
||
> 5. **减少函数调用**：在热循环中避免不必要的函数调用
|
||
> 6. **使用局部变量**：告诉编译器数据没有别名问题
|
||
> 7. **信任编译器**：`-O2` 通常足够，除非有明确的性能需求
|
||
|
||
---
|
||
|
||
## 本章术语
|
||
|
||
| 术语 | 英文 | 说明 |
|
||
|------|------|------|
|
||
| 代码移动 | Code Motion | 将循环不变量计算移到循环外 |
|
||
| CPE | Cycles Per Element | 每元素处理所需的时钟周期数 |
|
||
| 别名 | Aliasing | 两个不同指针指向同一内存位置 |
|
||
| 循环展开 | Loop Unrolling | 复制循环体以减少循环控制开销 |
|
||
| 内联 | Inline | 将函数体展开到调用处 |
|
||
| SIMD | Single Instruction Multiple Data | 单指令多数据并行 |
|
||
| 向量化 | Vectorization | 利用 SIMD 指令并行处理数据 |
|
||
| 代码选择 | Code Selection | 编译器选择合适的机器指令 |
|
||
| 寄存器分配 | Register Allocation | 将变量分配到 CPU 寄存器 |
|
||
| `restrict` | Restrict Qualifier | 告诉编译器指针没有别名 |
|
||
|
||
---
|
||
|
||
## 复习与思考
|
||
|
||
1. 为什么 `combine1` 到 `combine4` 的优化能显著降低 CPE？每一步消除了什么开销？
|
||
2. 当 `xp` 和 `yp` 指向同一地址时，`twiddle1` 和 `twiddle2` 的结果为什么不同？
|
||
3. 为什么按列遍历二维数组比按行遍历慢很多？这与 [[13_存储管理基础]] 中的局部性原理有什么关系？
|
||
4. 编译器为什么不能自动将 `func1` 优化为 `func2`？程序员应该如何帮助编译器？
|
||
5. 在什么情况下应该使用 `-O3` 而不是 `-O2`？有什么潜在的代价？
|