Lecture 15: 代码优化 (Code Optimization)

目录 · ← l14 · l16 →

Lecture 15: 代码优化 (Code Optimization)

讲义对应：CMU 15-213 Lecture 15 — Code Optimization（素材：F25-15-optimization.txt） 教材对应：CS:APP3e 第 5 章 5.1–5.15（优化编译器的能力与局限、程序性能的表达、消除循环低效、减少过程调用、消除不必要的内存引用、理解现代处理器、循环展开、提高并行性、一些限制因素、性能提高技术、确认和消除性能瓶颈） 关联 Lab：L4 Cache Lab Part B（优化矩阵转置，CPE 评分）/ L5 Malloc Lab（吞吐量与空间利用率）

15.1 概述

前面十四讲一直在回答”计算机怎么工作”：位怎么表示、指令怎么执行、缓存怎么命中、虚拟地址怎么翻译、堆怎么分配。本讲换一个方向提问——知道了这一切之后，怎样让代码跑得更快？ 讲义给出的答案很务实：优化不是玄学，而是”把编译器做不到的常数因子工作手工补上”。同一段求和代码，未优化时 CPE 高达 11，经过消除过程调用、消除内存写回、循环展开、多累加器四步，可降到 0.5 附近——二十倍的差距，全部来自对汇编、过程调用、存储层次和处理器微架构知识的综合运用。

本讲承接第 9–10 讲的存储层次与局部性，把”缓存友好”升级为可量化的 CPE（Cycles Per Element） 语言；它也是 L4 Cache Lab Part B 的直接理论前提，并为第 24 讲线程级并行埋下”指令级并行（ILP）”的伏笔。

15.2 核心概念与底层机制图解

15.2.1 CPE：用斜率而不是秒来度量性能（Cycles Per Element）

• 定义与目的：CPE 是”平均每处理一个元素花费的时钟周期数”。不用绝对时间（毫秒）是因为它会被时钟频率污染：同一份代码在 2.0 GHz 老机器上跑 10 ms、在 4.0 GHz 新机器上跑 5 ms，但这不代表代码变好了。CPE 把频率因子除掉，剩下的才是代码与微架构的真实效率。
• 直观解释（”它是什么？”）：把程序想成流水线工厂。总耗时 = 启动成本 + 单个零件时间 × 零件数。CPE 就是”单个零件的时间”，是这条直线的斜率；截距（Overhead）无关紧要，$n$ 足够大时斜率才是主导。测 CPE 像测车的油耗：看”每公里耗油”而非”这趟烧了多少油”。
• 底层机制图解：讲义给出 $Cycles = CPE \times n + Overhead$，CPE 即拟合直线的斜率。两条不同实现的直线斜率不同，用足够大的 $n$ 就能把斜率测准。
• 与机器码/硬件的对应：CPE 的倒数就是硬件的吞吐量（每周期处理多少元素）。CPE = 1 意味着”每周期做完一个元素”，CPE = 0.5 意味着”每周期做两个”——这只有在处理器有多个功能单元并行工作时才可能，直接指向 15.2.3 的乱序执行。
• 测量方法论（讲义强调的三条纪律）：① $n$ 必须足够大，让截距可忽略；② 每个版本重复多次取最小值或中位数——调度、中断、频率波动只会让结果变慢不会变快，故最小值最接近真实能力；③ 用 clock()（或 clock_gettime(CLOCK_MONOTONIC, ...)）计时并扣除循环外的固定开销。讲义的 fsecs 工具正是把这些纪律固化成可复用的计时框架。

15.2.2 编译器能做什么、不能做什么（Limits to Compiler Optimization）

• 定义与目的：优化的首要原则是”程序员必须理解编译器能做什么、不能做什么”。它能做的（常数折叠、死代码消除、公共子表达式消除、代码移动、内联）都是局部且保守的；不能做的才是程序员的机会。
• 直观解释（”它是什么？”）：编译器像一个极其守规矩的律师：它绝不会替你做任何”可能改变合同含义”的修改，哪怕那个条款明显是笔误。你写的 if (0)、冗余赋值，它敢删；但一个它看不透的指针，它就绝不敢动。
• 编译器必须保守的三条铁律：
  1. 不能改变程序语义：程序里哪怕一个”边界情况”的行为，程序员可能不在乎，但编译器不知道他不在乎。
  2. 不能引入原程序没有的副作用：这直接导致”不能把函数调用移出循环“——它无法证明这个函数没有副作用（改全局变量、打印、改文件）。
  3. 不能处理有歧义的指针别名（aliasing）：如果 a 和 b 可能指向同一块内存，对 *b 的写就可能改变 *a 的值，任何重排都可能是错的。
• 另一条现实约束：编译器通常一次只分析一个函数（全程序分析 LTO 昂贵），跨函数优化主要靠内联。这也解释了 15.3 中”把访问函数放进另一个编译单元”为何能忠实复现讲义的低效场景。
• 与机器码/硬件的对应：讲义把优化分为局部优化（单个基本块内：常数折叠、强度削减、死代码消除）与全局优化（整个控制流图上：循环变换、代码移动、全局 CSE）。这个划分对应编译器的两套分析框架——块内快而准，跨块必须做不动点迭代。

15.2.3 现代乱序处理器：功能单元、延迟与发射时间（Out-of-Order Execution）

• 定义与目的：要理解为什么”多累加器”能提速，必须先看清处理器内部。现代 CPU 是超标量（superscalar）的：每个周期可以发射（issue）多条指令；也是乱序（out-of-order）的：指令按数据依赖关系执行，而不按程序书写顺序。
• 直观解释（”它是什么？”）：把处理器想成一个大厨房。指令控制单元（ICU）是领班，负责提前读菜谱（取指、译码）并按食材依赖关系安排任务；执行单元（EU）是一排工位：几口炒锅（浮点乘法）、几口汤锅（浮点加法）、几个砧板（整数运算）、取料台（load）、出菜台（store）。领班的目标是让每个工位都不闲着。
• 底层机制图解：讲义给出的现代 CPU 机构如下。关键点在于 ICU 必须工作在执行单元前面很多，才能持续供料；而分支是最大的障碍——在 cmp 结果出来之前，ICU 不知道该往哪儿取指，只好预测。

          现代乱序处理器 (Modern CPU Design)
+------------------------------------------------------------------------+
|  指令控制单元  Instruction Control Unit                                |
|   +------------+  +------------+  +------------------+                 |
|   | 取指 Fetch |  | 译码 Decode|  | 分支预测 Prediction|               |
|   +------------+  +------------+  +------------------+                 |
|         ^               |               |                              |
|         |               v               v                              |
|   +------------+  +------------+  +------------------+                 |
|   | 指令缓存   |  |  操作      |  |  预测错误 -> 作废 |                |
|   | I-Cache    |  |  Operations|  |  并重新取指       |                |
|   +------------+  +------------+  +------------------+                 |
+-------------------------|----------------------------------------------+
                          v
+------------------------------------------------------------------------+
|  执行单元  Execution / Functional Units                                |
|   +---------+ +---------+ +---------+ +---------+ +---------+          |
|   | Branch  | | Arith   | | Arith   | |  Load   | |  Store  |          |
|   | 分支    | | 整数ALU | | 浮点FPU | |  取数   | |  存数   |          |
|   +---------+ +---------+ +---------+ +---------+ +---------+          |
|       ^           ^           ^           ^           ^                |
|       |           |           |           | +-----------+ +-----------+|
|       |           |           |           | | 数据缓存  | | 数据缓存  ||
|       |           |           |           | |  D-Cache  | |  D-Cache  ||
|       v           v           v           v +-----------+ +-----------+|
|                               |                                        |
|                +-----------------------+                               |
|                |  退休单元 Retirement  | <-- 寄存器更新                |
|                |  寄存器文件 RegFile   |     Register Updates          |
|                +-----------------------+                               |
+------------------------------------------------------------------------+
  ^ ICU 必须远跑在 EU 前面，才能让功能单元不空闲；分支预测错误代价可达数十周期

• 三个关键微架构参数（后文所有性能界限都由它们决定）：
  • 延迟（latency）：一条指令从源操作数就绪到结果可用的周期数。它决定依赖链能跑多快。
  • 发射时间（issue time，又叫 reciprocal throughput）：连续发射两条同类、互相独立的指令所需的最小周期数间隔。它的倒数就是功能单元的条数。
  • 容量（capacity）：能同时做这条运算的功能单元有几个。
• 与机器码/硬件的对应：讲义与 CS:APP3e 以 Intel Haswell/Broadwell 为基准，其参数是：

注意：本机（AMD EPYC 7V13，Zen 3）实测 mulsd 与 addsd 延迟均为 3 周期、addq 延迟 1 周期，mulsd 发射时间 0.5 周期/条（即 2 条浮点流水线）。参数依机器而异，但”浮点乘延迟远高于发射时间“这个结构性事实在所有现代 x86 上都成立——这正是多累加器的用武之地。

15.2.4 延迟界限与吞吐量界限（Latency Bound vs Throughput Bound）

• 定义与目的：任何代码的性能都被两个下界夹住，取二者中较大的那个：
  • 延迟界限（latency bound）：由关键路径（critical path）上那条最长的串行依赖链决定。只要运算之间存在真依赖，后一条必须等前一条算完。
  • 吞吐量界限（throughput bound）：由功能单元的总条数决定，是原始计算能力的物理极限。
• 直观解释（”它是什么？”）：把求和想成一群人往一个桶里丢石头。如果只有一个桶（单一累加器），那么每次丢石头都必须等上一次丢完——瓶颈是”桶的开口速度“（延迟）。如果你摆四个桶（多累加器），四个人可以同时丢，瓶颈就变成”场地上能站几个人“（功能单元数）。桶越多，延迟越被摊薄；但桶多到超过人数之后，再增加也没用。
• 底层机制图解：单一累加器的依赖链是一条长蛇，每环都必须串行；多个累加器把长蛇切成几条互不相干的短链：

一、单一累加器 (1 accumulator)：关键路径 = n 次串行加法

    d[0]   d[1]   d[2]   d[3]   d[4]   d[5]   ...
      \      |      |      |      |      |
       +---->+---->+---->+---->+---->+---->  x0

    每一步都必须等上一步算完  ==>  CPE = L  (与功能单元个数无关，纯延迟受限)


二、四个累加器 (4 accumulators)：关键路径 = n/4 次串行加法，4 条链并行推进

    d[0]  d[4]  d[8]   ...  -->  x0  --\
    d[1]  d[5]  d[9]   ...  -->  x1  ---+-->  最后合并 x0+x1+x2+x3
    d[2]  d[6]  d[10]  ...  -->  x2  ---+
    d[3]  d[7]  d[11]  ...  -->  x3  --/

    4 条链互不依赖，可同时在多个功能单元上推进
    ==>  CPE = max( L/k , T )     k = 累加器个数, T = 发射时间
         延迟界限被摊薄成 L/k，但最终撞上吞吐量界限 T = 1/C

• 与机器码/硬件的对应：把上面的抽象变成公式。设延迟 $L$、发射时间 $T$、功能单元数 $C=1/T$，用 $k$ 个累加器：
  • 延迟界限：$CPE_{\text{lat}} = L / k$
  • 吞吐量界限：$CPE_{\text{thr}} = T = 1/C$
  • 实际 $CPE \approx \max(L/k,\ T)$

  以浮点乘为例（讲义 Haswell 数据 $L=5, T=1, C=2$）：

  • 1 个累加器：$CPE = \max(5/1, 1) = 5$ —— 纯延迟受限
  • 2 个累加器：$CPE = \max(5/2, 1) = 2.5$
  • 4 个累加器：$CPE = \max(5/4, 1) = 1.25$
  • 5 个及以上：$CPE = \max(5/5, 1) = 1$ —— 此时降到吞吐量界限，再加累加器毫无收益

  推论：*$k^\=L/T$ 是”够用”的累加器个数*。Haswell 上 $k^\ = 5/1 = 5$，所以 4 个不够、5 个刚好、8 个纯属浪费。这个不等式是本章所有性能计算的骨架。

15.3 代码示例与底层机制分析

15.3.1 本机实测环境

所有数值均在本机真实编译运行测得，读者请在自己的机器上重跑：

CPU      : AMD EPYC 7V13 64-Core (Zen 3), 实测运行主频 3.07 GHz
缓存     : L1d 32 KB / L2 512 KB / L3 32 MB(每 CCX)
编译器   : gcc 12.2.0
计时     : clock_gettime(CLOCK_MONOTONIC)
主频标定 : 16 条串行 addq 依赖链（每迭代恰好 16 周期），最小 5 次
测量纪律 : 每版本重复 15 次，报告 CPE_min 与 CPE_med

为什么必须标定主频：标称 3.7 GHz 是最大加速频率，实际持续负载下只有 3.07 GHz。若不标定，CPE 会整体偏差 20%。标定用小段内联汇编：

/* 16 条串行 addq（延迟 1 周期/条）+ 1 条无关的 decq/jnz ==> 每迭代恰好 16 个核心周期。
   写成内联汇编，保证 -O1/-O2/-O3 下都不会被优化掉。 */
static double calibrate_ghz(long iters) {
    const int REP = 5, K = 16; double best = 1e30;
    for (int r = 0; r < REP; r++) {
        long c = iters, x = 0; double t0 = now_sec();
        __asm__ __volatile__(
            "1:\n\t"
            "addq $1,%1\n\t addq $1,%1\n\t addq $1,%1\n\t addq $1,%1\n\t"
            "addq $1,%1\n\t addq $1,%1\n\t addq $1,%1\n\t addq $1,%1\n\t"
            "addq $1,%1\n\t addq $1,%1\n\t addq $1,%1\n\t addq $1,%1\n\t"
            "addq $1,%1\n\t addq $1,%1\n\t addq $1,%1\n\t addq $1,%1\n\t"
            "decq %0\n\t jnz 1b\n\t"
            : "+r"(c), "+r"(x) :: "cc");
        double dt = now_sec() - t0;
        if (dt < best) best = dt;
    }
    return (double)iters * K / best / 1e9;      /* GHz */
}

踩过的坑（真实教训）：最初用”1 条 addq + 1 条 decq/jnz”（每迭代理论上 1 周期）标定，在 -O2 下却稳定给出 1.537 GHz——正好是 3.07 的一半。用 gcc -O2 -S 反汇编发现循环体被对齐到不同的 16 字节边界，decq/jnz 与 addq 争抢同一个发射槽，导致每迭代实际 2 周期。改成 16 条串行 addq 后，整条依赖链长达 16 周期，彻底淹没了 1 周期的对齐噪声，-O1/-O2/-O3 下都稳定在 3.07 GHz。教训：微基准的标定部分本身也可能受微架构细节影响，必须交叉验证。

15.3.2 优化阶梯：从 CPE 11 到 0.46

下面五个版本全部来自同一份源码，只是写法不同；vec_length / get_vec_start / get_vec_element 用 __attribute__((noinline)) 强制保留过程调用与边界检查，忠实模拟讲义中”访问函数在另一个编译单元”的情形。

#define _GNU_SOURCE
#include <stddef.h>

typedef struct { size_t len; long *data; } vec;

__attribute__((noinline)) size_t vec_length(vec *v) { return v->len; }
__attribute__((noinline)) long  *get_vec_start(vec *v) { return v->data; }
__attribute__((noinline)) int get_vec_element(vec *v, size_t idx, long *val) {
    if (idx >= v->len)          /* 每次调用都要做的边界检查 */
        return 0;
    *val = v->data[idx];
    return 1;
}

/* ---------- v1：低效版（循环调用函数 + 每轮写回内存） ---------- */
void combine_v1(vec *v, long *dest) {
    long i;
    *dest = 0;
    for (i = 0; i < (long)vec_length(v); i++) {   /* 每轮调用 vec_length */
        long val;
        get_vec_element(v, i, &val);              /* 每轮调用 + 边界检查 */
        *dest = *dest + val;                      /* 每轮读 + 写内存 */
    }
}

/* ---------- v2：局部变量累加 + 直接数组访问 ---------- */
void combine_v2(vec *v, long *dest) {
    long i, len = (long)vec_length(v);            /* 长度提到循环外 */
    long *d = get_vec_start(v);                   /* 直接拿数据指针 */
    long t = 0;
    for (i = 0; i < len; i++)
        t += d[i];                                /* 只在寄存器里累加 */
    *dest = t;                                    /* 只写一次内存 */
}

/* ---------- v2u：v2 + 循环展开 2（仍是单一累加器） ---------- */
void combine_v2u(vec *v, long *dest) {
    long i, len = (long)vec_length(v);
    long *d = get_vec_start(v);
    long t = 0;
    for (i = 0; i + 2 <= len; i += 2)
        t = (t + d[i]) + d[i + 1];                /* 展开≠并行：仍是一条依赖链 */
    for (; i < len; i++) t += d[i];
    *dest = t;
}

/* ---------- v3：4 个累加器，打破加法依赖链 ---------- */
void combine_v3(vec *v, long *dest) {
    long i, len = (long)vec_length(v);
    long *d = get_vec_start(v);
    long x0 = 0, x1 = 0, x2 = 0, x3 = 0;
    for (i = 0; i + 4 <= len; i += 4) {
        x0 += d[i];     x1 += d[i + 1];           /* 4 条互不依赖的链 */
        x2 += d[i + 2]; x3 += d[i + 3];
    }
    for (; i < len; i++) x0 += d[i];
    *dest = (x0 + x1) + (x2 + x3);                /* 最后合并 */
}

/* ---------- v4：8 个累加器 + restrict ---------- */
long combine_v4(long *restrict d, long len) {
    long i, x0=0,x1=0,x2=0,x3=0,x4=0,x5=0,x6=0,x7=0;
    for (i = 0; i + 8 <= len; i += 8) {
        x0 += d[i  ]; x1 += d[i+1]; x2 += d[i+2]; x3 += d[i+3];
        x4 += d[i+4]; x5 += d[i+5]; x6 += d[i+6]; x7 += d[i+7];
    }
    for (; i < len; i++) x0 += d[i];
    return ((x0+x1)+(x2+x3)) + ((x4+x5)+(x6+x7));
}

【代码做什么？】

1. combine_v1 完全照搬讲义 combine1：把”取长度、取元素、累加”三件事分别写成一次函数调用。
2. combine_v2 做三件事：把 vec_length 提到循环外（代码移动），用 get_vec_start 一次性拿到数组基址从而去掉每轮的边界检查，把中间结果放进局部变量。
3. combine_v2u 额外做循环展开：一次处理两个元素，减少分支与索引递增次数——但它仍只有一个累加器，这是后面要证伪的”展开就等于快”。
4. combine_v3 / combine_v4 引入 4/8 个独立累加器，把一条长依赖链切成多条短链，并用 restrict 向编译器承诺不发生别名。

【实测验证】（n = 10^6，long 数组 8 MB，每版本 15 次取最小）

对比讲义的原始数据（Intel Haswell，CS:APP3e 表 5.1）：

【底层机制透视】绝对数值必然不同：讲义 Haswell 未优化版 CPE 高达 22.68，本机只有 11.0——编译器版本（gcc 12.2 vs 更老）与机器参数（本机 addq 延迟仅 1 周期）都不同。但优化阶梯的形状完全一致：未优化 → 消调用消内存（跃降 ~10 倍）→ 多累加器（再降 ~2 倍）。请在自己机器上重测，不要背数字，要理解为什么。

15.3.3 汇编对比：编译器到底有没有用寄存器

这是本章最关键的证据。用 gcc -O1 -S demo.c 反汇编两个版本的内层循环：

v1 的内层循环（每轮都在写内存）：

.L15:
        leaq    8(%rsp), %rdx        # val 的地址在栈上
        movq    %rbx, %rsi           # idx
        movq    %r12, %rdi           # v
        call    get_vec_element      # <== 每轮一次函数调用（含边界检查）
        movq    8(%rsp), %rax        # <== 从栈上把 val 读回来
        addq    %rax, 0(%rbp)        # <== 读 *dest、加、写回 *dest：内存往返
        addq    $1, %rbx
.L14:
        movq    %r12, %rdi
        call    vec_length           # <== 每轮还要调一次 vec_length！
        cmpq    %rbx, %rax
        jg      .L15

v2 的内层循环（累加器锁在寄存器里）：

        call    vec_length           # 循环外调用一次
        call    get_vec_start        # 循环外调用一次
.L21:
        addq    (%rdx), %rax         # <== %rax 就是累加器：直接在寄存器里累加
        addq    $8, %rdx             #     指针自己递增，不再做边界检查
        cmpq    %rcx, %rdx
        jne     .L21
        movq    %rax, (%r12)         # <== 整个循环只有这一次内存写

【底层机制透视】 逐条数一数：v1 每轮 2 次函数调用 + 1 次栈访问 + 1 次内存读改写；v2 每轮 1 条 addq 内存操作数 + 指针递增 + 比较 + 分支。这解释了 CPE 从 11 到 1.09 的十倍跃降：函数调用要压栈、跳转、返回，而内存读改写的延迟远高于寄存器操作。注意 -O1 已经足够让 GCC 把局部变量 t 放进 %rax——因为 t 的地址从未逃逸。

对照讲义幻灯片里的经典低效形态（*dest = *dest OP val，dest 是外部指针参数，因此在 -O1 下是真正的内存读改写）：

        movq    (%rdx), %rax         # 读 b[i]
        addq    %rax, (%rbx)         # 加并写回 b[i]：编译器不敢放进寄存器
        addq    $8, %rdx
        cmpq    %rcx, %rdx
        jne     .L7

为什么编译器不敢把它放进寄存器？ 因为 *dest 与 v->data 可能别名（alias）——万一调用者让 dest 指向数组内部，把中间结果留在寄存器里就会漏掉每一次”写”的可见效果，程序语义就变了。这是 15.3.4 的主题。

一个值得记录的细节：-O2 下 GCC 对指针写回版本会做一次激进变换——一边在寄存器 %rdx 里累加，一边每轮仍写回内存：

.L8:
        addq    (%rax), %rdx         # 寄存器累加
        addq    $8, %rax
        movq    %rdx, (%rbx)         # 但仍老老实实每轮写一遍内存
        cmpq    %rax, %rcx
        jne     .L8

这是”遵守语义“前提下的最优解：它消掉了”读”（从寄存器读），但”写”必须保留。实测这一版 CPE = 1.036，与真正的局部变量版 1.094 几乎相同——现代处理器的 store buffer 会把连续写合并掉。结论：”消除内存引用”的收益主要体现在消除”读回”、以及能否把值提升进寄存器上。

15.3.4 内存别名：sum_rows1 vs sum_rows2

讲义用 sum_rows 系列演示内存别名（Memory Aliasing）的代价，这是本章最干净的对照实验：

/* sum_rows1：每轮都写 b[i]，编译器无法排除 b 与 a 别名 */
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]、加、写 b[i]：每轮一次内存往返 */
    }
}

/* sum_rows2：中间结果放局部变量，循环内完全不碰内存 */
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;                  /* 每行只写一次内存 */
    }
}

【代码做什么？】 两个函数数学上都是”把 $n\times n$ 矩阵按行求和存进向量 $b$”。差别只在于中间结果放在哪里：sum_rows1 放在 b[i]（内存），sum_rows2 放在 val（寄存器）。

【底层机制透视】 编译器不能自动完成这个变换，因为它必须考虑 a 和 b 重叠的合法情形。讲义给出了反例：设 double A[9] = {0,1,2,4,8,16,32,64,128}，令 B = A + 3（B 与 A 的第 3 行重叠），调用 sum_rows1(A, B, 3)。逐步跟踪（这段跟踪已在 /tmp 下真实运行验证）：

i=0: b[0]=0  ==> 把 A[3] 清零
     内层 j=0..2 读 A[0],A[1],A[2] = 0,1,2  ==>  b[0] = 3   (写回，即 A[3]=3)

i=1: b[1]=0  ==> 把 A[4] 清零
     内层读的是 A[3],A[4],A[5]，但注意内层每次 += 都会写回 A[4]，
     而下一次迭代又要读 A[4] —— 自己刚写的值被自己读到！
        j=0: 读 A[3]=3        -> b[1]=3   (写 A[4]=3)
        j=1: 读 A[4]=3(刚写的) -> b[1]=6   (写 A[4]=6)   <== 别名在"内层"就咬人了
        j=2: 读 A[5]=16       -> b[1]=22  (写 A[4]=22)

i=2: b[2]=0  ==> 把 A[5] 清零；内层读 A[6],A[7],A[8] = 32,64,128  ==>  b[2] = 224

最终 B = [3, 22, 224]，而不重叠时正确答案是 B = [3, 28, 224]（各行真和：$0+1+2=3$，$4+8+16=28$，$32+64+128=224$）。关键洞察：别名不只在”外层迭代之间”起作用，它在内层循环内部就改变了结果——因为每轮的写会被下一轮的读看到。这正是编译器必须把 store 留在循环里、无法提升到循环外的根本原因。

【实测验证】（gcc -O1，double 元素，CPE = 周期/元素）

同一实验在 -O2 下 sum_rows1 变成 2.785 / 2.899 / 2.978，加速比降到 1.00×——因为 GCC 在 -O2 上能证明”每轮写的 b[i] 与读的 a[...] 不冲突”并做了变换（反汇编可见它把内层循环展开、用 addsd 累加后 movsd 写回）。这正是”编译器能力边界”的完美例证：同一个变换，在 -O1 的 sum_rows1 上编译器拒绝做（保守），在 -O2 上它自己就会做（安全）。所以程序员最该做的是把代码写成编译器敢优化的形式，而不是手写汇编。

restrict 是给编译器的承诺：void sum_rows2r(double *restrict a, double *restrict b, long n) 告诉编译器”这一对指针访问的内存块绝不重叠“。有了这个承诺，编译器就敢做强得多的重排与向量化。代价是：如果违反承诺（两块内存确实重叠），行为是未定义行为（UB）——不是”结果不对”这么轻，而是编译器可以生成任何东西。本机实测 sum_rows2 与 sum_rows2r 在 -O1 下 CPE 完全一致（2.78 / 2.90 / 2.98），说明对这段代码 restrict 没带来额外收益；但在 15.3.6 的逐元素运算上它决定了能否向量化。

15.3.5 延迟界限与吞吐量界限的计算过程

现在用真实测量的参数验证 15.2.4 的公式。先用内联汇编直接测本机的延迟与发射时间（8 条独立依赖链法）：

为什么”8 条独立链”能测出发射时间：$k$ 条互不依赖的链可以并行推进，只要 $k$ 足够大把延迟完全掩盖，每迭代的时间就由发射带宽决定，即 $k \times T$；所以 $T = \text{cycles/迭代} / k$。取 $k=8$ 是因为 $8 > L/T = 6$，肯定够掩盖延迟。这里有一个方法论陷阱：不能把空循环（decq/jnz，1 周期/迭代）的 1 周期从测量值里直接减掉——因为 decq/jnz 与运算指令是并行发射的，减掉会重复扣除。正确做法是直接读原始 cycles/迭代，再按链数换算。

（一）浮点乘 combine_d（OP = *，IDENT = 1.0）的界限验证

本机参数 $L=3$，$T=0.5$，单元数 $C=2$，代入 $CPE = \max(L/k,\ T)$：

三行实测值与理论值几乎完全吻合，这是本章最有说服力的证据：v2 是纯延迟受限（3.00），v3 仍是延迟受限（0.75），v4 已经撞上吞吐量天花板（0.48 ≈ 0.5）。由此也可算出”够用”的累加器数 $k^\* = L/T = 3/0.5 = 6$——6 个累加器就能达到吞吐量界限，8 个纯属保险。

对照讲义 Haswell 的同一计算：$L=5$，$T=1$，$C=2$，则 $k^\* = 5$，理论阶梯是 5 → 2.5 → 1.25 → 1.0。讲义表格中”Combine4 浮点乘 = 5.01”精确等于延迟界限 5，”展开+多累加器 = 2.51”精确等于 $5/2 = 2.5$。两个平台、两套参数、同一个公式，结论完全一致。

（二）整数加 combine（OP = +，IDENT = 0）为什么”看起来超越了界限”

本机 addq 延迟 1、发射时间 0.282，理论延迟界限 1、吞吐量界限 0.282。但实测 v2（1 个累加器）= 1.094，v4（8 个累加器）= 0.461——都高于 0.282。原因在于整数运算太便宜了，瓶颈转移到了加载单元（load unit）：每次迭代必须从内存取一个 long，而加载端口的吞吐量是有限制的：

实测 0.461–0.478 与 0.5 非常接近（略低，说明实际可维持的加载速率略高于每周期 2 次）。这个例子极其重要：它说明”延迟界限 / 吞吐量界限”不是只有两条，而是所有资源下界中的最大值——运算单元、加载单元、存储单元、分支单元各有一条界限，真正的 CPE 是它们的上包络。所以当运算变得足够便宜时，瓶颈一定会转移到访存上，这也是 L4 Cache Lab 要考的核心。再往上加累加器完全无用：整数加的实际天花板由 LSU 决定，而不是由 ALU 决定。

（三）数据超出缓存后的第三个界限：内存带宽

把 $n$ 从 $10^6$（8 MB，L3 驻留）增加到 $10^7$（80 MB，DRAM），所有版本都被拉平：

$n=10^7$ 时 v4 的 CPE = 1.000 对应 $80\,\text{MB} / 3.25\,\text{ms} \approx 24.6$ GB/s 的单核 DRAM 带宽。无论怎么优化计算，都突破不了这堵墙——此时唯一的出路是改善局部性（详见 Lecture 9–10 的存储器山与分块）。这也解释了为什么优化阶梯在高 $n$ 下会”塌缩”：8 MB 时 v2 是 1.094、v4 是 0.461（差 2.4 倍），80 MB 时变成 1.340 vs 1.000（只差 1.3 倍）。

15.3.6 突破：AVX2 / FMA 自动向量化

前面所有优化都还在”每周期处理一个元素”的量级。真正再上一个数量级要靠 SIMD（Single Instruction Multiple Data）。用 -O3 -mavx2 -mfma 编译后，GCC 能自动把循环向量化：

# gcc -O3 -mavx2 -mfma 对 combine_v2 的自动向量化
        vpxor   %xmm0, %xmm0, %xmm0          # 向量累加器清零
.L40:
        vpaddq  (%rdx), %ymm0, %ymm0         # <== 一条指令加 4 个 long (256 位)！
        addq    $32, %rdx
        cmpq    %rdi, %rcx
        jb      .L40
        vextracti128 $0x1, %ymm0, %xmm0      # 水平归约：把 4 条 lane 加起来
        vpsrldq $8, %xmm0, %xmm1
        vpaddq  %xmm1, %xmm0, %xmm0
        vmovq   %xmm0, %rdx

逐元素运算 a[i] = b[i]*k + c[i]（讲义 Scheduling 一节）则被编译成 FMA 指令：

# gcc -O3 -mavx2 -mfma 对 scale4 的自动向量化
        vmovupd         (%r9,%rax), %ymm1            # 一次载入 4 个 double
        vfmadd213pd     (%r8,%rax), %ymm2, %ymm1     # <== FMA: a = b*k + c，一条指令算 4 个
        vmovupd         %ymm1, (%rdi,%rax)

【底层机制透视】 vfmadd 把”乘”和”加”融合成一条指令，既省指令又省一次舍入（中间结果不截断，精度更高）。相比 15.3.2 中 v2 的 0.529 CPE，向量化后每周期能处理 2 个 double 甚至更多。

GCC 自动向量化的三个前提条件（缺一不可）：

1. 无别名（no aliasing）：编译器必须能证明读的数组与写的数组不重叠。这就是 restrict 的作用；缺了它，GCC 会保守地拒绝向量化。
2. 无数据依赖（no loop-carried dependency）：如果第 $i$ 次迭代要读第 $i-1$ 次写的结果（如 a[i] = a[i-1] + b[i]），无法并行。
3. 连续访问（unit stride）：步长必须为 1，才能用 vmovupd 一次载入连续 4 个元素。跨步访问（如按列遍历）会让向量化失败。

注意：本机实测 -O3 -mavx2 -mfma 下 sum_rows1 vs sum_rows2 加速比只有 1.00–1.07×，scale4 在 $n=10^7$ 时有效带宽只有 31.7 GB/s——向量化不是万能药：瓶颈是内存带宽时 SIMD 无法突破。先判断瓶颈在哪，再决定优化手段。

15.4 实验关联

L4 Cache Lab Part B（优化矩阵转置） 是本讲技巧的直接战场。trans.c 要在 -O1 下把 $N\times N$ 矩阵转置的 CPE 压到阈值以下，本质就是本讲四板斧的叠加：

• 消除内存引用：块内转置时用局部变量暂存一整行（而非逐个 B[j][i] = A[i][j]），避免对 B 的反复读改写——这正是 sum_rows1 → sum_rows2 的同一招。
• 循环展开 + 分块（blocking）：$32\times32$ 块让每次载入的缓存行被充分利用；$64\times64$ 需要 $8\times8$ 分块加”半行暂存”来同时避免 $A$、$B$ 的对角线冲突。
• 代码移动：把 i*n、基址加法的重复计算提出循环。
• 常见坑：-O1 下 GCC 不做自动向量化，必须手工做；测试务必覆盖 $N = 32,64,128,256,512,1024$，不能只针对 $32/64/128$ 调参。

L5 Malloc Lab（吞吐量部分） 用同一个思想：分配器 find_fit 每轮都调用辅助函数、反复读堆头部，CPE 极差；改成内联 + 局部变量缓存堆指针与边界，吞吐量能提升数倍。讲义 LAB-perflab.txt（早年以 rotate/smooth 两个图像算子评分的 Code Optimization Lab）给出历史基线可作对照：naive rotate CPE 14.7→94.5（随 $N$ 恶化说明缓存失效），优化后 8.0→25.3，几何平均加速 3.1×；naive smooth CPE 约 700（计算密集），优化后约 41，加速 15.2×——完美体现了”访存密集 vs 计算密集需要不同手法”。

15.5 常见错误与调试技巧

• 迷信 -O3：现象是加了 -O3 反而更慢。原因是向量化带来的对齐检查、代码膨胀挤爆 i-cache、或非临时存储在数据仍在缓存中时反而亏。调试：gcc -O2 -S -o - file.c \| less 对比 -O2/-O3 的汇编差异；用 perf stat -e cache-misses,cache-references,instructions,cycles ./prog 看指令数与 miss 率是否同步改善。
• 用 UB 换性能：现象是 restrict 化或指针强转后结果偶发错误。原因是违反 restrict 承诺、或 -O3 下依赖了未定义的有符号溢出。调试：gcc -O1 -fsanitize=undefined,address -g file.c 跑一遍；用 -fno-strict-aliasing 对比结果是否变化即可确认是否为别名 UB。
• 微基准测不准：现象是同一份代码两次测得 CPE 差两三倍。原因是频率波动、CPU 迁移、其他进程干扰、$n$ 太小截距主导。调试：taskset -c 5 ./prog 绑核；for i in $(seq 20); do taskset -c 5 ./prog; done \| sort -n \| head 取多轮最小值；用本讲的依赖链法先标定真实频率。
• 以为”展开就会快”：现象是手工展开 4 倍后 CPE 纹丝不动。原因是只展开了、没增加累加器，依赖链长度没变。调试：看 CPE 是否卡在延迟界限上（用 15.3.5 的公式算一下预期界限），若等于 $L/k$ 且 $k$ 没变，就必须加累加器。
• 累加器加太多：现象是加到 16 个累加器后反而变慢。原因是寄存器不够用导致寄存器溢出（register spilling），把值写到栈上，每次访问又多一次内存往返。调试：gcc -O2 -S -o - file.c \| grep -c 'rsp' 数栈访问；或 perf stat -e ld_blocks.store_forward ./prog。
• 混淆”测量”与”优化”：现象是改进了 CPE 但程序总时间没变。原因是这段代码在总时间中占比很小（见 15.7 的 Amdahl 计算题）。调试：先用 perf record -g ./prog && perf report 定位热点函数，再优化——不要猜热点。
• 把计时逻辑和被测代码混在一起：现象是 CPE 数值异常稳定地偏大。原因是把初始化、内存分配、printf 都算进了计时区间。调试：严格只对目标循环计时，重复 15 次以上，先跑一遍预热。

15.6 关键要点

• CPE 是代码效率的语言，不是时间：$Cycles = CPE \times n + Overhead$，用足够大的 $n$、多次重复取最小值，才能测出稳定斜率。
• 编译器的三条铁律决定了优化机会：不改语义、不加副作用、不猜别名——”不能把函数调用移出循环”和”不敢把 *dest 放进寄存器”都是这三条的直接后果。
• 优化阶梯的形状是普适的：消除过程调用（~10×）→ 消除内存引用（~1.3×）→ 循环展开与多累加器（~2×）→ SIMD（再 ~2×）；绝对数值随机器而变，但顺序与瓶颈迁移规律不变。
• $CPE \approx \max(L/k,\ T)$ 是本章的骨架公式：$k$ 个累加器把延迟界限摊成 $L/k$，但永远打不穿吞吐量界限 $T = 1/C$；”够用”的累加器数是 $k^\* = L/T$。本机实测浮点乘 $L=3, T=0.5$ 给出 $k^\*=6$，实测 1/4/8 累加器分别为 3.00/0.748/0.480 CPE，与理论 3.00/0.75/0.50 完全吻合。
• 瓶颈是多条下界的上包络：运算单元、加载单元、存储单元、DRAM 带宽各有一条界限。整数加太便宜，瓶颈转移到 2 load/cycle（CPE 0.5）；数据超出缓存后，瓶颈是 ~25 GB/s 的单核带宽。
• 先测量，再优化，最后验证：perf 找热点 → 改代码写成编译器敢优化的形式（局部变量、restrict、连续访问）→ 重新测量确认。

15.7 思考题（带答案）

题 1（计算题：延迟/吞吐量界限与累加器个数） 某处理器的浮点乘 mulsd 延迟 $L = 4$ 周期、发射时间 $T = 0.5$ 周期/条。求：(a) 功能单元数 $C$；(b) 用 1、2、4、8 个累加器做点积时各自的 CPE 下界；(c) “够用”的最少累加器个数 $k^\*$；(d) 若实测 8 个累加器得到 CPE = 1.2，瓶颈最可能是什么？

答： (a) $C = 1/T = 1/0.5 = \mathbf{2}$ 个浮点乘法单元。 (b) $CPE = \max(L/k, T) = \max(4/k, 0.5)$：

• $k=1$：$\max(4, 0.5) = \mathbf{4.00}$
• $k=2$：$\max(2, 0.5) = \mathbf{2.00}$
• $k=4$：$\max(1, 0.5) = \mathbf{1.00}$
• $k=8$：$\max(0.5, 0.5) = \mathbf{0.50}$（已到吞吐量界限） (c) $k^\* = L/T = 4/0.5 = \mathbf{8}$。所以 $k \ge 8$ 之后再加累加器毫无收益。 (d) 实测 1.2 远高于理论 0.5，说明真正瓶颈不在乘法单元上——最可能是加载延迟/带宽（每次迭代要取一个元素）、寄存器溢出到栈（8 个累加器 + 指针 + 计数器超过可用寄存器），或数据不在 L1。排查顺序：先看汇编有无 movsd ...(%rsp) 这类栈访问，再看数据规模是否超出 L1/L2。

题 2（计算题：Amdahl 定律） 某程序中 combine 占运行时间的 60%，其余 40% 与它无关。你把 combine 从 CPE 1.094 优化到 0.478（本机 -O2 实测的 v2 → v4）。(a) combine 自身的加速比是多少？(b) 整个程序的加速比是多少？(c) 若要把整体加速比做到 2.0，combine 需要再快多少倍？

答： (a) $S_{\text{combine}} = 1.094 / 0.478 = \mathbf{2.29\times}$。 (b) 设原总时间为 1，则 combine 从 0.60 降到 $0.60/2.29 = 0.262$，其余仍为 0.40，新总时间 $= 0.662$。整体加速比 $= 1 / 0.662 = \mathbf{1.51\times}$。 (c) 设 combine 需要加速 $S$ 倍，则 $\dfrac{1}{0.4 + 0.6/S} \ge 2 \Rightarrow 0.4 + 0.6/S \le 0.5 \Rightarrow 0.6/S \le 0.1 \Rightarrow S \ge \mathbf{6\times}$。注意 Amdahl 定律的硬上限：即使 combine 快到耗时为零，整体加速比也只有 $1/0.4 = 2.5\times$——所以超过 6 倍的努力已经没有意义，应该去优化那 40%。

题 3（”直观但错误的想法”） 同学 A 说：”-O3 比 -O2 优化级别高，所以任何代码用 -O3 编译一定更快。”同学 B 说：”既然循环展开能减少分支开销，我把循环展开 16 倍，性能一定最好。”同学 C 说：”restrict 只是注释，加了没坏处，加满就行。”同学 D 说：”既然 sum_rows1 慢是因为每轮写 b[i]，编译器只要聪明一点，把结尾时的值写一次就行了。”请分别指出错在哪。

答：

• 同学 A 忽略代码大小与向量化的代价。-O3 会更激进地展开与向量化，导致代码膨胀、i-cache 失效、以及为对齐插入的运行时检查；实测 -O3 -mavx2 下 sum_rows1 vs sum_rows2 的收益甚至只有 1.00–1.07×（-O1 下反而是 4.0×），因为向量化对已访存受限的代码无能为力。正确做法是两种都测。
• 同学 B 混淆了”减少循环开销”与”打破依赖链”。展开只减少分支/索引开销；若不增加累加器，依赖链长度不变，CPE 依然被延迟界限 $L$ 卡住——实测 v2u（展开 2、单一累加器）= 0.997，与不展开的 v2 = 1.094 几乎相同，而 v3（4 累加器）= 0.478。过度展开还会导致寄存器溢出，中间值被挤到栈上，反而更慢。
• 同学 C 错在 restrict 是可被违反的承诺，违反即 UB。它向编译器保证两块内存不重叠；一旦实际重叠（如 f(a, a+3)），编译器可基于该承诺做任意重排，产生”看起来完全莫名”的错误结果，而且在 -O1 下可能正常、-O3 下崩溃。正确用法是只在确实不重叠的接口上加，并当作 API 契约维护。
• 同学 D 错在这个变换并非总是等价。讲义的反例是 double A[9]={0,1,2,4,8,16,32,64,128}; double B[3]=A+3; 后调用 sum_rows1(A,B,3)——b 指向 a 的第 3 行，写 B[0] 就是写 A[3]。实测最终 B = [3, 22, 224]，而不重叠时的正确答案是 [3, 28, 224]。更关键的是：别名在内层循环内部就改变了结果——i=1 时内层先把 A[4] 清零、之后每轮 += 都写回 A[4] 而下一轮又读回 A[4]，把 4 变成了 3。所以编译器无法排除 a 与 b 重叠（15.2.2 第三条铁律），只能保守地每轮读写内存；要让它优化，程序员必须主动消除歧义（改用局部变量或加 restrict）。