ChoChoX/obsidian

Fork 0

Files

ChoChoX 224c3dc574 vault backup: 2026-06-13 23:46:22

2026-06-13 23:46:22 +08:00

21 KiB

Raw Permalink Blame History

18. 程序代码优化

课程: 操作系统 - 程序代码优化 核心内容: 机器无关优化、代码移动、消除不必要的内存引用、优化障碍（指针别名、函数副作用）、性能度量

前置知识

03_C语言编程基础 -- C语言编译链接过程、指针与内存模型
13_存储管理基础 -- 存储器层次结构、局部性原理

一、代码优化的概念与意义

1.1 为什么需要代码优化

[!important] 核心观点常数因子也很重要！根据代码编写方式的不同，程序性能可能相差 10倍 以上。必须在多个层次上进行优化：算法、数据表示、过程调用和循环。

代码优化的目标：

理解程序如何被编译和执行
学习如何度量程序性能并识别瓶颈
在不破坏代码模块化和通用性的前提下提升性能

1.2 优化的层次

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向量化等

# 不同优化级别的编译
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 度量示例

// 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 定义

typedef int data_t;

typedef struct {
    int len;
    data_t *data;
} vec_rec, *vec_ptr;

3.2 combine1：抽象版本（基线）

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）

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）

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：消除不必要的内存引用

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 循环不变量外提

将循环中每次迭代结果相同的计算移到循环之前：

// 优化前：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 的内部实现

size_t strlen(const char *s) {
    int length = 0;
    while (*s != '\0') {
        s++;
        length++;
    }
    return length;
}

strlen 本身是 O(n) 的。如果在循环中每次迭代都调用它，整体复杂度就变成了 $O(n^2)$。

五、优化障碍（Optimization Blockers）

编译器在进行优化时受到两大根本性约束：

编译器在任何可能的条件下都不能改变程序的行为
当程序员知道的信息比编译器多时，需要程序员主动干预

5.1 指针别名（Memory Aliasing）

[!danger] 别名问题当两个不同的内存引用指向同一个存储位置时，就产生了别名。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

别名实例演示：

// 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 函数调用的副作用

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 有副作用时就不行了：

int counter = 0;
int f(int x) {
    return counter++;  // 每次调用返回不同的值！
}

[!warning] 编译器的保守策略编译器通常假设函数调用可能有副作用，因此不会轻易将多次函数调用合并。程序员可以：

使用 inline 关键字建议编译器内联

使用 const、pure 等属性标记无副作用的函数

将函数调用结果缓存到局部变量中

六、循环优化技术

6.1 循环展开（Loop Unrolling）

减少循环控制开销，增加指令级并行性：

// 优化前
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）

将多个独立循环合并为一个，改善数据局部性：

// 优化前：两次遍历
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）

将循环中不变的计算移到循环外：

// 优化前
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 循环优化流程图

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 按列遍历

#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 缓存友好的代码编写原则

graph LR
    A["缓存友好原则"] --> B["按行优先遍历多维数组"]
    A --> C["使用连续内存布局"]
    A --> D["减少跨步访问"]
    A --> E["数据结构对齐缓存行"]

    style A fill:#e8f5e9

八、函数调用优化

8.1 内联函数（Inline）

将函数体直接展开到调用处，消除函数调用开销：

// 优化前：函数调用有开销
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 的优化所示，将函数调用替换为直接内存访问：

// 优化前：每次迭代调用函数
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 尾调用优化

当函数最后一步是调用另一个函数时，编译器可以复用当前栈帧：

// 优化前：递归可能导致栈溢出
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）允许一条指令同时处理多个数据元素：

// 标量版本：一次处理一个元素
for (int i = 0; i < n; i++) {
    c[i] = a[i] + b[i];
}

// SSE 向量化（伪代码）：一次处理4个float
// 编译器在 -O3 下可能自动生成 SIMD 指令

9.2 编译器自动向量化

# 查看编译器是否进行了向量化
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 数据对齐

// 确保数据对齐以获得最佳 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 告诉编译器指针没有别名：

// 使用 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 进行分析

# 基本性能统计
perf stat ./prog

# 详细缓存分析
perf stat -e cache-references,cache-misses ./prog

# 函数级热点分析
perf record ./prog
perf report

11.3 使用 gprof 进行分析

# 编译时加入 profiling 支持
gcc -pg -O2 prog.c -o prog

# 运行程序（生成 gmon.out）
./prog

# 查看分析结果
gprof prog gmon.out > analysis.txt

11.4 优化工作流程

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] 代码优化的核心原则

先正确，后优化：保证代码正确性是前提

度量驱动：使用 profiling 工具找到真正的瓶颈

算法优先：O(n \log n) 的算法比 O(n^2) 的优化更重要

利用局部性：按行访问数组，使用连续内存布局

减少函数调用：在热循环中避免不必要的函数调用

使用局部变量：告诉编译器数据没有别名问题

信任编译器：-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	告诉编译器指针没有别名

复习与思考

为什么 combine1 到 combine4 的优化能显著降低 CPE？每一步消除了什么开销？
当 xp 和 yp 指向同一地址时，twiddle1 和 twiddle2 的结果为什么不同？
为什么按列遍历二维数组比按行遍历慢很多？这与 13_存储管理基础中的局部性原理有什么关系？
编译器为什么不能自动将 func1 优化为 func2？程序员应该如何帮助编译器？
在什么情况下应该使用 -O3 而不是 -O2？有什么潜在的代价？

21 KiB Raw Permalink Blame History Unescape Escape