CSAPP - 09.Optimization

Program Optimization (程序性能优化)

1. 性能现状 (Performance Realities)

常数因子至关重要 (Constant factors matter)：在渐进复杂度 (Asymptotic Complexity) 之外，同样的算法逻辑，代码写法的不同可能导致 10:1 的性能差异。
多层级优化 (Optimize at multiple levels)：必须在多个层面进行优化：
- 算法 (Algorithm)
- 数据表示 (Data representations)
- 过程 (Procedures)
- 循环 (Loops)
系统认知 (Understand System)：必须理解程序是如何编译和执行的，如何测量性能瓶颈，以便在不破坏代码模块化 (Modularity) 和通用性 (Generality) 的前提下提升性能。

2. 优化编译器 (Optimizing Compilers)

2.1 编译器的能力 (Capabilities)

寄存器分配 (Register Allocation)：这是最关键的优化之一。CPU 访问寄存器的速度远快于内存。编译器会分析哪些变量使用最频繁，并将它们放入有限的寄存器中，而不是放在栈（内存）上。
代码选择与调度 (Code Selection and Ordering)：编译器会选择最适合当前 CPU 的指令序列，并重新排列指令顺序（Scheduling），以便让 CPU 的流水线更顺畅地运行，掩盖指令延迟。
死代码消除 (Dead Code Elimination)：如果一段代码计算的结果从未被使用，或者一段代码永远无法被执行（例如 if (0) {...}），编译器会直接将其删除，减少代码体积和执行时间。
消除微小低效 (Eliminating minor inefficiencies)：比如去除多余的跳转指令等。

2.2 编译器的局限性 (Limitations)

虽然编译器很聪明，但它必须遵守一个基本约束 (Fundamental Constraint)：绝对不能改变程序的行为 。这意味着：

保守策略 (Conservative Strategy)：
- 编译器无法像程序员那样了解代码的“意图”。如果编译器无法确定一个优化是否安全（例如，它不确定两个指针是否指向同一块内存，即内存别名 Memory Aliasing），它就必须假设最坏的情况，从而放弃优化。
- 例子：如果你的代码中有两个指针参数，编译器不敢轻易把其中一个的值缓存在寄存器里太久，因为它担心通过另一个指针的写入可能会修改这个值。
分析范围受限：
- 大多数优化分析仅限于过程 (Procedure/Function) 内部。编译器通常看不到函数调用的内部细节（除非内联），因此它必须假设函数调用会有副作用 (Side-effects)，比如修改全局变量。
- 全程序分析 (Whole-program analysis) 虽然存在，但对于大型程序来说，编译时间开销过大，通常不作为默认选项。
静态信息局限：
- 编译器只能看到代码的静态结构，无法知道运行时变量的具体值（例如 n 到底是大是小）。因此它很难针对特定的运行时情况做极致优化。

3. 通用优化方法 (Generally Useful Optimizations)

无论使用何种处理器或编译器，程序员都应尝试的优化手段。

3.1 代码移动 (Code Motion) / 预计算 (Precomputation)

原理：减少计算执行的频率。
场景：将计算结果不会改变的代码从循环内部移到循环外部。
案例 1：矩阵行访问
- 未优化：在 for (j=0; j<n; j++) 循环内部写 a[n*i + j]。这里 n*i 在每次 j 循环中都要算一次，但其实 i 和 n 在内层循环里没变。
- 优化后：在循环前定义 long ni = n*i;，循环内直接用 a[ni + j]。这减少了 n 次乘法运算。

案例 2：过程调用 (strlen) —— 经典反面教材
- 问题代码：for (i=0; i < strlen(s); i++) { ... }
- 性能陷阱：strlen 需要遍历整个字符串来确定长度，复杂度是 $O(N)$ 。把它放在循环终止条件里，意味着每次迭代都要执行一次。总复杂度变成了 $O(N^2)$ 。
- 优化后：
1
2
int len = strlen(s); for (i=0; i < len; i++) { ... }
- 效果：将复杂度降回 $O(N)$ 。这是一种极大的性能提升，且编译器往往因为担心 strlen 有副作用（虽然标准库函数通常没问题，但编译器视其为黑盒）而不敢自动优化。

3.2 强度削减 (Reduction in Strength)

原理：用代价更低 (Simpler/Costly less) 的操作替代高代价操作。
示例：
- 移位代替乘除：例如用 x << 4 代替 16 * x。
- 累加代替乘法：在循环中用 ni += n 代替 ni = n * i。

核心思想：不要让 CPU 重复计算已经算过的东西。
案例：图像处理/矩阵邻居求和
- 假设你要访问像素 (i, j) 的上下左右四个邻居：
  - 上：(i-1)*n + j
  - 下：(i+1)*n + j
  - 左：i*n + j - 1
  - 右：i*n + j + 1
- 未优化：代码中直接写上述公式，导致进行了 3 次乘法：i*n, (i-1)*n, (i+1)*n 。
- 优化后
  1
  2
  3
  4
  5
  long inj = i * n + j; // 算出中心点索引，只做一次乘法 up = val[inj - n]; down = val[inj + n]; left = val[inj - 1]; right = val[inj + 1];
- 这样只需要 1 次乘法和几次简单的加减法，大大减少了计算量。

4. 优化障碍 (Optimization Blockers)

4.1 过程调用 (Procedure Calls)

问题：编译器通常将函数调用视为黑盒 (Black Box)。
- 函数可能有副作用 (Side Effects)（如修改全局状态），阻止了代码移动。
- 编译器难以确定函数返回值在参数不变时是否恒定。
解决方案：
- 内联函数 (Inline functions)：减少调用开销，允许跨过程优化。
- 手动代码移动：显式地将函数调用（如 strlen）移出循环。

void lower(char *s) 
{ 
	int i; 
	for (i = 0; i < strlen(s); i++) 
		if (s[i] >= 'A' && s[i] <= 'Z') 
			s[i] -= ('A' - 'a'); 
}

4.2 内存别名 (Memory Aliasing)

定义：两个不同的内存引用指向同一个物理位置 (Two different memory references specify single location)。
影响：编译器必须假设任何内存写入都可能影响后续的读取，因此不敢将内存值缓存在寄存器中，导致频繁的内存读写。
解决方案：
- 引入局部变量 (Local Variables/Accumulators)：在循环中使用局部变量累加结果，循环结束后再一次性写入内存。这告诉编译器不需要检查别名。

void sum_rows1(double *a, double *b, long n) {
    long i, j;
    for (i=0; i<n; i++) {
        b[i] = 0;
        for (j=0; j<n; j++)
            b[i] += a[i*n+j]; // ⚠️ 关键点：每次循环都直接读写内存 b[i]
    }
}

void sum_rows2(double *a, double *b, long n) {
    long i, j;
    for (i=0; i<n; i++) {
        double val = 0; // ✅ 引入局部变量
        for (j=0; j<n; j++)
            val += a[i*n+j]; // 在寄存器中累加
        b[i] = val; // ✅ 循环结束后只写一次内存
    }
}

但是编译器不回自动进行上面的优化，因为有可能b数组使用的是a中的内存。

编译器总是偏于保守；因此，为了改进代码，程序员必须经常帮助编译器显式地完成代码的优化。

5. 利用指令级并行 (Exploiting Instruction-Level Parallelism, ILP)

5.1 现代 CPU 架构 (Modern CPU Design)

1. 超标量 (Superscalar)

定义：超标量处理器可以在一个时钟周期内发射并执行多条指令。
机制：CPU 从顺序的指令流中读取指令，但通过硬件动态地将它们分发到多个独立的执行单元上并行处理。
对比：传统的标量处理器一个周期只能执行一条指令，而现代超标量处理器（自 Pentium Pro 起）可以同时处理 3-4 条甚至更多。

2. 乱序执行 (Out-of-Order Execution)

原理：指令的执行顺序不需要严格遵守程序代码的编写顺序。
流程：
1. 只要操作数准备好了，指令就可以立即执行，而不必等待前面的慢速指令（如缓存未命中）。
2. 虽然执行是乱序的，但为了保证程序逻辑正确，提交（Retirement/Write-back）必须是按顺序的。
优势：极大地掩盖了长延迟操作（如内存读取）的开销，防止 CPU 流水线因为单条指令的阻塞而停滞。

现代 CPU 主要分为两个核心部分：指令控制单元 (Instruction Control Unit, ICU) 和 执行单元 (Execution Unit, EU)。

3. 指令控制单元 (ICU)

负责从内存中读取指令，并将其转化为微操作，准备交给执行单元。

取指控制 (Fetch Control)：包含分支预测逻辑，决定下一步从哪里读取指令。
指令译码 (Instruction Decode)：将复杂的 x86 指令翻译成简单的微指令 (Micro-ops)。
退役单元 (Retirement Unit)：
- 记录正在执行的指令状态。
- 控制寄存器文件的更新。
- 关键作用：确保指令虽然是乱序执行的，但结果是按顺序提交到寄存器和内存的。如果预测错误（如分支预测失败），它负责回滚状态并刷新流水线。

4. 执行单元 (EU)

负责实际的运算操作。它接收来自 ICU 的微指令，并在操作数就绪时将其分发给具体的功能单元。

功能单元 (Functional Units)：现代 CPU 拥有多个冗余的执行端口，可以并行工作。例如：
- Integer ALU：处理整数加减、逻辑运算。
- Integer Mult/Div：专门处理整数乘除。
- FP Add：浮点加法器。
- FP Mult/Div：浮点乘除法器。
- Load/Store Units：专门负责内存读写的单元（通常有独立的地址计算逻辑）。
并行能力：在同一个周期内，CPU 可能同时在做一个浮点乘法、两个整数加法和一个内存读取。

5. 延迟与吞吐量 (Latency vs. Throughput)

这是理解性能界限的关键。

延迟 (Latency)：完成一条指令所需的总时间（周期数）。
- 例如：浮点乘法可能需要 4-5 个周期，整数除法可能需要 10-20 个周期。
吞吐量 (Throughput) / 发射时间 (Issue Time)：连续发射两条相同类型指令之间的最小间隔。
- 流水线化 (Pipelining)：得益于功能单元的流水线设计，即使浮点乘法需要 5 个周期才能算完，CPU 依然可以每个周期发射一条新的浮点乘法指令（Issue Time = 1）。
- 这意味着如果没有任何依赖，系统的理论吞吐量非常高。

分支预测 (Branch Prediction)

为了保持流水线满载，CPU 必须在知道分支结果之前就“猜测”下一条指令在哪里。
投机执行 (Speculative Execution)：CPU 会执行猜测路径上的指令。如果猜对了，性能极大提升；如果猜错了，必须丢弃所有投机计算的结果（这也是性能开销的主要来源之一）。

可以把现代 CPU 想象成一个 “并行小王子”，它拥有强大的并行处理能力，但需要程序员的配合才能释放潜力。

硬件能力：
- 算术运算单元通常是完全流水线化的（吞吐量为 1）。
- 有多个算术单元（如 2 个加法器，1 个乘法器）。
- 可以并行执行加载和存储。
程序员的任务：
- 打破数据依赖：如果不打破顺序依赖（如 x = x + ...），CPU 只能被迫串行工作，无法利用多余的功能单元。
- 利用代码并行性：通过循环展开和多路累积 (Separate Accumulators)，人为地创造出多条独立的数据流，让 CPU 的多个功能单元同时忙碌起来。

6. 高级优化技术 (Advanced Techniques)

目标：利用 ILP (指令级并行)，打破延迟界限，逼近吞吐量界限。

6.1 性能指标 CPE (Cycles Per Element)

CPE (Cycles Per Element)：
- 定义：处理向量中每个元素所需的平均时钟周期数。它是衡量循环微观效率的核心指标。
- 计算视角：
  - 实验测量：在 $Cycles = CPE \times n + Overhead$ 公式中，CPE 对应测量直线的斜率 (Slope)。
  - 理论分析：通过分析循环体内的关键路径和硬件资源来估算性能下限。
延迟界限 (Latency Bound)：
- 定义：由于指令执行需要时间，且数据之间存在顺序依赖 (Sequential Dependency)，导致 CPU 必须等待上一条指令结果生成才能开始下一条。
- 理论公式： $\text{理论 CPE} = \frac{\text{关键路径上的总延迟 (Total Latency)}}{\text{每次迭代处理的元素数 (Unrolling Factor)}}$
- 意义：这是串行代码的性能瓶颈。如果不打破依赖链（如 x = x * d[i]），无论硬件多么强大，性能都会被锁死在延迟界限上。
- 例子：浮点乘法延迟为 5 周期。若存在 r = r * ... 的强依赖，即使循环展开 2 次，CPE 依然是 $10/2 = 5.0$ 。
- 突破手段：重新结合变换 (Reassociation)，利用结合律改变计算顺序（如 r = r * (x * y)），缩短关键路径。
吞吐量界限 (Throughput Bound)：
- 定义：由 CPU 硬件的物理特性（功能单元数量、发射宽度、流水线能力）决定的理论最大处理速度。
- 理论公式： $\text{理论 CPE} = \frac{1}{\text{功能单元的总吞吐能力}}$
- 意义：这是程序性能的物理极限。当代码中没有数据依赖阻塞时，性能将受限于“CPU 算得有多快”。
- 例子：如果 CPU 有 2 个乘法器，且每个都能每周期输出 1 个结果（流水线化），那么乘法的极限 CPE 为 $1.0 / 2 = 0.5$ 。
- 逼近手段：分离累积变量 (Separate Accumulators)，创建多路完全独立的计算链（如 x0, x1…），填满 CPU 的所有流水线级数。

6.2 循环展开 (Loop Unrolling)

原理：增加每次迭代处理的元素数量，减少循环开销（分支预测、索引更新）。

对整数运算有效：课件数据显示，对于整数加法和乘法，CPE 确实降低了。这是因为现代 CPU 甚至可以重组简单的整数运算，而且减少了循环辅助指令的干扰。
对浮点运算无效 (瓶颈所在)：对于浮点乘法，CPE 依然卡在 延迟界限 上（例如 3.0 或 5.0）。
- 原因：顺序依赖 (Sequential Dependency)。
- 虽然你写在一行里，但编译器默认是从左到右计算：x = (x OP d[i]) OP d[i+1]。
- 第二次 OP 必须等第一次 OP 算出 x 的新值后才能开始。这导致 CPU 的流水线必须空转等待（Stall），无法并行。

// 2x Unrolling
for (i = 0; i < limit; i+=2) {
    x = (x OP d[i]) OP d[i+1]; 
}

r_old (上一轮)
   |
   v
[ Mul 1 ] <--- d[i]       (时刻 T+0 开始)
   |
   v (中间结果)
[ Mul 2 ] <--- d[i+1]     (时刻 T+5 开始，必须等 Mul 1)
   |
   v
r_new (这一轮结果)        (时刻 T+10 完成)
   |
   v
(下一轮...)

6.3 重新结合变换 (Reassociation)

原理：利用数学上的结合律，改变计算的顺序，打破对累积变量 x 的依赖链。

变换前：x = (x OP d[i]) OP d[i+1] （必须串行）
变换后：x = x OP (d[i] OP d[i+1]) （括号内的可以并行）。

为什么能提速？

d[i] OP d[i+1] 这部分计算不依赖当前的 x。
当 CPU 正在计算上一轮的 x 更新时，另一个空闲的功能单元可以同时计算 d[i] OP d[i+1] 。
效果：这使得关键路径（Critical Path）上的操作减少了，性能可以接近 2 倍 提升，突破了延迟界限。

时间轴 (Time)
  |
  |     [ 计算 v0 = d[0]*d[1] ]      [ 计算 v2 = d[2]*d[3] ] ... (支线任务，并行狂奔)
  |              |                            |
  |              | (5周期后准备好)            | (5周期后准备好)
  |              v                            v
  |  r_init --->[ Mul ]--------------------->[ Mul ]---------------------> r_final
  |              (主线)                       (主线)
  |            耗时 5 周期                  耗时 5 周期
  v

注意：对于浮点数，(a+b)+c 和 a+(b+c) 结果可能因精度舍入而略有不同，但在大多数高性能计算中通常是可以接受的。

6.4 分离累积变量 (Separate Accumulators)

原理：使用多个独立的局部变量并行累积结果，彻底打破顺序依赖。

x0 = x0 OP d[i];
x1 = x1 OP d[i+1];
...
*dest = x0 OP x1;

效果：
- 打破依赖：计算 x0 不需要等 x1，计算 x1 也不需要等 x0。它们是完全独立的两条指令流 。
- 填满流水线：如果一个乘法延迟是 5 个周期，通过展开成 5 个或更多独立的累积变量（x0…x4），我们可以让 CPU 在等待 x0 结果出来的间隙，依次发射 x1 到 x4 的计算指令。
- 逼近吞吐量界限：当累积变量足够多（K足够大），所有的功能单元都被喂饱了，CPE 将不再受延迟限制，而是受限于硬件有多少个计算单元（吞吐量界限）。

7. 向量指令 (Vector Instructions)

原理：前面的优化虽然并行了，但还是一条指令算一个数（SISD）。SIMD (Single Instruction Multiple Data) 允许一条指令同时算多个数（例如一条 addpd 指令同时算 2 个 double 加法）。
SSE / AVX：这是 Intel CPU 提供的具体指令集。
效果：通过使用 SIMD，可以进一步将性能提升到超越标量吞吐量界限的水平。例如，如果标量最优 CPE 是 1.0，向量指令可能达到 0.25（一次处理 4 个）。

8. Combine 函数优化

优化的目标是针对一个向量归约函数（Vector Reduction，即计算向量元素的和或积），通过一系列手段降低 CPE (Cycles Per Element，每元素周期数)。

数据结构：定义了一个 vec 结构体，包含数组长度 len 和数据指针 data 。
计算任务：函数 combine，遍历向量的所有元素，计算它们的和 (Sum) 或 积 (Product) 。
- 数据类型包括：Integer (整数) 和 Double FP (双精度浮点数)。
- 运算操作包括：Add (+) 和 Mult (*) 。

1. 起点：低效的原始代码 (Combine1)

这是未经优化的原始版本，虽然逻辑正确，但包含两个严重的性能杀手。

代码分析

void combine1(vec_ptr v, data_t *dest) {
    long int i;
    *dest = IDENT; // 初始化
    for (i = 0; i < vec_length(v); i++) { // ⚠️ 问题1：循环条件中调用函数
        data_t val;
        get_vec_element(v, i, &val);      // ⚠️ 问题2：边界检查开销
        *dest = *dest OP val;             // ⚠️ 问题3：每次迭代读写内存
    }
}

性能瓶颈

重复的函数调用：vec_length(v) 在每次循环迭代中都被调用，复杂度 $O(N)$ 。
内存别名隐患：每次迭代都更新 *dest。编译器因担心内存别名，被迫每次都进行读写内存。
CPE：Integer Add: 29.0。

2. 第一阶段：基础优化 (Combine4)

这是程序员应该养成的基本编码习惯，消除明显开销。

优化手段

代码移动 (Code Motion)：将 vec_length(v) 移出循环。
消除内存别名：引入局部变量 t (Accumulator) 在寄存器中累加，循环结束后再一次性写入 *dest。
直接数组访问：使用 get_vec_start 获取数组起始地址，直接通过 d[i] 访问。

代码演变

void combine4(vec_ptr v, data_t *dest) {
    int length = vec_length(v);    // ✅ 移出循环
    data_t *d = get_vec_start(v);
    data_t t = IDENT;              // ✅ 使用局部变量
    for (i = 0; i < length; i++)
        t = t OP d[i];             // ✅ 寄存器内操作
    *dest = t;                     // ✅ 最终写回内存
}

性能提升

效果：消除了循环开销和内存读写。
CPE：Integer Add: 2.0。
新瓶颈：撞上了 延迟界限 (Latency Bound)。t = t OP d[i] 存在顺序依赖，必须等上一次运算完成。

3. 第二阶段：循环展开 (Loop Unrolling)

尝试通过减少循环迭代次数来降低开销。

优化手段

2x1 循环展开：每次迭代处理 2 个元素。
逻辑：x = (x OP d[i]) OP d[i+1]。

void unroll2a_combine(vec_ptr v, data_t *dest) 
{
    int length = vec_length(v);
    int limit = length - 1;           // 限制循环边界，防止越界
    data_t *d = get_vec_start(v);
    data_t x = IDENT;                 // 累积变量
    int i;

    /* Combine 2 elements at a time */
    for (i = 0; i < limit; i += 2) {
        x = (x OP d[i]) OP d[i+1];    // ⚠️ 依然存在顺序依赖
    }

    /* Finish any remaining elements (处理剩下的尾部元素) */
    for (; i < length; i++) {
        x = x OP d[i];
    }

    *dest = x;
}

结果分析

Integer Mult：CPE 降至 1.5（编译器进行了重组优化）。
Double FP Add/Mult：几乎没有提升。因为依然存在顺序依赖，无法突破延迟界限。

4. 第三阶段：打破依赖 (ILP 高级优化)

利用 CPU 的 超标量 和 乱序执行 能力，突破延迟界限。

方法 A：重新结合变换 (Reassociation)

利用结合律改变计算顺序，增加并行度。

代码变换：
- 原代码：x = (x OP d[i]) OP d[i+1] （串行）
- 新代码：x = x OP (d[i] OP d[i+1]) （并行）
原理：d[i] OP d[i+1] 不依赖累积变量 x，可提前并行计算。
效果：Double Add CPE 降至 1.5，打破了顺序依赖链。

void unroll2aa_combine(vec_ptr v, data_t *dest) 
{
    int length = vec_length(v);
    int limit = length - 1;
    data_t *d = get_vec_start(v);
    data_t x = IDENT;
    int i;

    /* Combine 2 elements at a time */
    for (i = 0; i < limit; i += 2) {
        // ✅ 关键改变：括号位置变了
        // CPU 可以独立计算 (d[i] OP d[i+1])，不需要等待上一轮的 x
        x = x OP (d[i] OP d[i+1]); 
    }

    /* Finish any remaining elements */
    for (; i < length; i++) {
        x = x OP d[i];
    }

    *dest = x;
}

方法 B：分离累积变量 (Separate Accumulators)

使用多个独立的变量并行累积，彻底利用硬件吞吐量。

代码变换：

// 2路并行
x0 = x0 OP d[i];     // 流 1
x1 = x1 OP d[i+1];   // 流 2
...
*dest = x0 OP x1;    // 最后合并

原理：创建两条完全独立的数据依赖链，CPU 同时执行。
效果：所有操作的 CPE 大幅下降，逼近 吞吐量界限 (Throughput Bound)。这是标量代码的最佳性能。

void unroll2a_combine_separate(vec_ptr v, data_t *dest) 
{
    int length = vec_length(v);
    int limit = length - 1;
    data_t *d = get_vec_start(v);
    data_t x0 = IDENT;      // 累积变量 1 (负责偶数索引)
    data_t x1 = IDENT;      // 累积变量 2 (负责奇数索引)
    int i;

    /* Combine 2 elements at a time */
    for (i = 0; i < limit; i += 2) {
        x0 = x0 OP d[i];    // ✅ 独立的指令流 1
        x1 = x1 OP d[i+1];  // ✅ 独立的指令流 2
    }

    /* Finish any remaining elements */
    for (; i < length; i++) {
        x0 = x0 OP d[i];    // 将剩余元素合并到 x0
    }

    *dest = x0 OP x1;       // ✅ 最后将两条流的结果合并
}

5. 最终阶段：向量化 (Vector Instructions)

手段：使用 SSE / AVX 指令集 (SIMD)。
原理：单条指令同时运算多个数据。
效果：突破标量处理器的吞吐量界限。

总结：CPE 性能演进表

优化阶段	关键技术	性能瓶颈	Int Add CPE
Combine1	原始代码	函数调用、内存读写	29.0
Combine4	代码移动、局部变量	延迟界限 (顺序依赖)	2.0
Unrolling	循环展开	延迟界限	2.0
Reassoc	重新结合	吞吐量界限 (部分并行)	1.5
Sep Accum	分离累积变量	吞吐量界限 (完全并行)	1.0

通过这一系列优化，性能从最初的 29.0 CPE 提升到了 1.0 CPE，实现了近 29 倍 的加速。

9. 总结：如何获取高性能 (Getting High Performance)

编译器与选项：使用优秀的编译器并开启 -O1 或更高优化。
避免低效算法：警惕隐蔽的算法低效（如循环内的 strlen）。
编写编译器友好的代码：
- 消除优化障碍（过程调用、内存引用/别名）。
- 使用局部变量代替频繁的内存引用。
聚焦最内层循环 (Innermost Loops)：大部分计算发生在这里。
针对机器调优：
- 利用指令级并行 (ILP)。
- 避免不可预测的分支 (Unpredictable branches)。
- 编写对缓存友好 (Cache friendly) 的代码。

CSAPP

#CSAPP

CSAPP - 09.Optimization

https://yima-gu.github.io/2026/01/14/CSAPP/09-Optimization/

作者

Yima Gu

发布于

2026年1月15日

许可协议

Network - 02.Transport Layer-01 上一篇

Network - 01.Application Layer 下一篇

CSAPP - 09.Optimization

Program Optimization (程序性能优化)

1. 性能现状 (Performance Realities)

2. 优化编译器 (Optimizing Compilers)

2.1 编译器的能力 (Capabilities)

2.2 编译器的局限性 (Limitations)

3. 通用优化方法 (Generally Useful Optimizations)

3.1 代码移动 (Code Motion) / 预计算 (Precomputation)

3.2 强度削减 (Reduction in Strength)

3.3 公共子表达式共享 (Share Common Subexpressions)

4. 优化障碍 (Optimization Blockers)

4.1 过程调用 (Procedure Calls)

4.2 内存别名 (Memory Aliasing)

5. 利用指令级并行 (Exploiting Instruction-Level Parallelism, ILP)

5.1 现代 CPU 架构 (Modern CPU Design)

1. 超标量 (Superscalar)

2. 乱序执行 (Out-of-Order Execution)

3. 指令控制单元 (ICU)

4. 执行单元 (EU)

5. 延迟与吞吐量 (Latency vs. Throughput)

6. 高级优化技术 (Advanced Techniques)

6.1 性能指标 CPE (Cycles Per Element)

6.2 循环展开 (Loop Unrolling)

6.3 重新结合变换 (Reassociation)

6.4 分离累积变量 (Separate Accumulators)

7. 向量指令 (Vector Instructions)

8. Combine 函数优化

1. 起点：低效的原始代码 (Combine1)

代码分析

性能瓶颈

2. 第一阶段：基础优化 (Combine4)

优化手段

代码演变

性能提升

3. 第二阶段：循环展开 (Loop Unrolling)

优化手段

结果分析

4. 第三阶段：打破依赖 (ILP 高级优化)

方法 A：重新结合变换 (Reassociation)

方法 B：分离累积变量 (Separate Accumulators)

5. 最终阶段：向量化 (Vector Instructions)

总结：CPE 性能演进表

9. 总结：如何获取高性能 (Getting High Performance)