1.5 程序性能优化

性能优化最容易犯的错误是「凭直觉改代码」。直觉通常盯着指令条数，而现代 CPU 的瓶颈在依赖链、缓存缺失、分支失败、内存带宽——这四者与指令条数的关系都很弱。一个循环从 100 条指令减到 80 条，可能毫无变化；把一条依赖链拆成四条，可能直接快 4 倍。

这一章讲一套可复现的方法：先定义度量，再找瓶颈，再针对瓶颈改写，最后用同一基准验证。所有例子都以 x86-64、GCC 13 -O2 为背景；ARM64 的结论类似，延迟数字不同。文中的「周期」指 CPU 核心时钟周期，具体纳秒数随频率变化。

前置提醒：优化必须在正确性之后。开启 -ffast-math、手写无分支、改变求和顺序，都可能改变浮点结果；涉及金额、科学计算、可复现性时，先确认误差预算。

1.5.1 度量：CPE、延迟与吞吐

描述循环性能最常用的单位是「每元素周期数」（cycles per element, CPE）。对一个处理 $n$ 个元素的循环，若总周期是 $T(n)$，则

$$\text{CPE} = \frac{T(n)}{n}.$$

CPE 把「循环开销」摊到每个元素上，便于比较不同规模的实现。若循环有固定的启动开销 $c$，则 $T(n) = c + k n$，CPE 随 $n$ 增大趋近 $k$。测 CPE 时要让 $n$ 足够大，且重复多次取最小值，避免冷缓存与调度噪声。

三个概念要分清：

若一个循环每个元素只做一次加法、且加法依赖上一次结果，则 CPE 下界是加法延迟 1；若做一次乘法且只有一个累加器，CPE 下界是乘法延迟 3；若有 4 个独立累加器，CPE 下界变成 $\max(\text{延迟}/4, \text{吞吐倒数})$。先算下界，再判断还有多少优化空间。

基准测试的最低要求：

/* 用 CLOCK_MONOTONIC 计时，重复 R 次取最小值，防止频率/调度抖动 */
for (int r = 0; r < R; r++) {
    uint64_t t0 = now_ns();
    result = kernel(data, n);
    uint64_t t1 = now_ns();
    best = (r == 0 || t1 - t0 < best) ? (t1 - t0) : best;
}
printf("%.3f ns/elem, checksum=%llu\n", (double)best / n, result);

clock_gettime(CLOCK_MONOTONIC) 的分辨率通常足够（纳秒级字段），但单次测量仍有噪声；取多次最小值比取平均更接近「无干扰」的硬件性能。用 perf stat 可以同时看周期数与指令数，避免频率变化干扰。

1.5.2 编译器能做什么、不能做什么

编译器在 -O2 下会做常量传播、死代码消除、公共子表达式消除、强度削减、循环不变量外提、内联、自动向量化（-O3/-ftree-vectorize）、指令调度。它不会做的是「改变程序可观察行为」的优化——而 C 的未定义行为、指针别名、外部函数调用，都会限制它的手脚。

别名（aliasing） 是最常见的限制。看这个函数：

void scale_add(int *a, int *b, int n)
{
    for (int i = 0; i < n; i++)
        a[i] = a[i] * 2 + b[i];
}

编译器不能把 b[i] 缓存到寄存器后重排整个循环，因为 a 和 b 可能指向同一块内存（甚至 a + 1 == b）。每次写 a[i] 都可能改变 b[i+1]，所以它必须在每次迭代重新加载。加上 restrict 告诉编译器「两者不重叠」：

void scale_add(int *restrict a, const int *restrict b, int n)
{
    for (int i = 0; i < n; i++)
        a[i] = a[i] * 2 + b[i];
}

restrict 是程序员对编译器的承诺；若违反（两个指针确实重叠），行为未定义。它常用于高性能库（BLAS、图像处理），因为收益明显：编译器可以向量化、把 load 提前、减少内存往返。

比较两版汇编，差别很直观：

# 无 restrict：每次迭代重新加载 b[i]
.L3:
    movsd   (%rdi,%rax,8), %xmm0     # a[i]
    addsd   %xmm0, %xmm0
    addsd   (%rsi,%rax,8), %xmm0     # b[i]，不能缓存
    movsd   %xmm0, (%rdi,%rax,8)     # 写回 a[i]
    incq    %rax
    cmpq    %rdx, %rax
    jne     .L3

# 有 restrict：编译器可把 b[i] 批量 load，甚至向量化
.L7:
    movupd  (%rsi,%rax,8), %xmm1
    movupd  (%rdi,%rax,8), %xmm0
    addpd   %xmm0, %xmm0
    addpd   %xmm1, %xmm0
    movupd  %xmm0, (%rdi,%rax,8)
    addq    $2, %rax
    cmpq    %rdx, %rax
    jne     .L7

无 restrict 的版本每次迭代都有一次 load、一次 store；有 restrict 的版本用 movupd/addpd 一次处理两个 double。同一份 C，只差一个关键字，生成两套代码。这就是「让编译器知道你的意图」的价值。

函数调用 是另一个限制。循环里调用 strlen(s)，若编译器不能证明 s 指向的字符串在循环中不变（比如循环体调用了可能修改它的函数），就只能每次重新计算：

for (int i = 0; i < strlen(s); i++)   /* 可能每次迭代都扫描字符串 */
    process(s[i]);

改成 size_t n = strlen(s); for (i = 0; i < n; i++) 是最基本的「消除循环低效」。编译器有时能把 strlen 提升（loop-invariant code motion），但前提是它能证明 s 不被修改；跨翻译单元、经过函数指针、或有 volatile 时，它不敢动。

内联 让小函数消失，把调用开销变成指令调度机会。static inline 只是建议，编译器有权拒绝；-flto（链接时优化）能跨 .c 文件内联；always_inline 属性可以强制，但滥用会让代码膨胀、I-cache 压力上升。判断是否内联看 objdump 里有没有 call，而不是看源码写没写 inline。

1.5.3 消除循环低效与重复计算

优化的第一步不是展开，而是删掉不必要的工作。常见三类：

1. 循环不变量：每次迭代都算同一个值。
2. 重复调用：每次迭代都调用 strlen、sqrt、malloc。
3. 低效的抽象：用 % 取模做循环缓冲、用 vector::at 做边界检查、用字符串拼接做日志。

一个综合例子：

#include <stdio.h>
#include <stdint.h>
#include <time.h>
#include <stdlib.h>

#define N (1u << 20)
static double a[N], b[N];
static volatile double sink;

static double now_sec(void)
{
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return (double)ts.tv_sec + (double)ts.tv_nsec / 1e9;
}

/* 版本 1：每次迭代重新计算长度，单累加器 */
static double sum_naive(size_t n)
{
    double s = 0.0;
    for (size_t i = 0; i < n; i++)
        s += a[i] * b[i];
    return s;
}

/* 版本 2：四个独立累加器，打破依赖链 */
static double sum_unrolled(size_t n)
{
    double s0 = 0, s1 = 0, s2 = 0, s3 = 0;
    size_t i = 0;
    for (; i + 4 <= n; i += 4) {
        s0 += a[i]     * b[i];
        s1 += a[i + 1] * b[i + 1];
        s2 += a[i + 2] * b[i + 2];
        s3 += a[i + 3] * b[i + 3];
    }
    for (; i < n; i++)
        s0 += a[i] * b[i];
    return (s0 + s1) + (s2 + s3);
}

int main(void)
{
    for (size_t i = 0; i < N; i++) {
        a[i] = (double)(i % 1000) / 1000.0;
        b[i] = 1.0 - a[i];
    }

    double t0 = now_sec();
    double r1 = sum_naive(N);
    double t1 = now_sec();
    double r2 = sum_unrolled(N);
    double t2 = now_sec();
    sink = r1 + r2;

    printf("naive:    %.3f ns/elem\n", (t1 - t0) * 1e9 / N);
    printf("unrolled: %.3f ns/elem\n", (t2 - t1) * 1e9 / N);
    printf("diff=%.3g\n", r1 - r2);
    return 0;
}

在 -O2 下，sum_naive 的关键路径是「load a、load b、乘、加」串行，每次迭代都要等上一次的 s。sum_unrolled 把累加拆成 4 条独立链，理论上 CPE 降到约 1/4（受 load 吞吐与乘法端口限制）。实数结果可能略有差异，因为浮点加法顺序变了；若要求逐位一致，就不能这样重排。

sum_naive 里其实没有 strlen 那种重复调用，但「单累加器」本身就是低效：它把 4 个可以并行的操作串成了一条链。并行度不是只有多线程才有，指令级并行（ILP）就在循环体内。

1.5.4 减少调用与消除不必要的内存引用

函数调用有固定开销：保存/恢复寄存器、建立栈帧、传递参数、跳转。对一次调用几纳秒的小函数，在高频循环里累积起来很可观。内联或把函数体移到循环外，是常见做法。

更隐蔽的是「不必要的内存引用」。看一个累加：

for (i = 0; i < n; i++)
    *dest += src[i];        /* 每次迭代读一次 *dest，写一次 *dest */

dest 指向的内存可能被 src[i] 的读取别名（编译器不知道），所以它不能把 *dest 缓存在寄存器里。改成局部变量：

double acc = *dest;
for (i = 0; i < n; i++)
    acc += src[i];
*dest = acc;

现在累加在寄存器里，循环结束才写回一次。这个变换叫「把内存变量提升为寄存器变量」（scalar replacement）。编译器在能证明无别名时会自动做；不能证明时，restrict 或局部变量是手动版。

另一个例子是结构体数组（AoS）与数组结构体（SoA）：

struct particle { float x, y, z, mass; };   /* AoS：一个粒子 16 字节 */
struct particle p[N];

/* 只更新 x，却把 y/z/mass 也拉进缓存行 */
for (int i = 0; i < N; i++)
    p[i].x += p[i].mass * dt;

若只频繁访问 x，AoS 会让每个缓存行里 3/4 的数据是无用的；改成 float x[N], y[N], z[N], mass[N]（SoA），同样 64 字节缓存行能装 16 个 x，有效带宽提高 4 倍。代价是「一个粒子的所有字段」不再连续，跨字段操作要多几次访存。布局选择取决于访问模式，没有绝对优劣。

1.5.5 循环展开与多累加器

循环展开（loop unrolling）把多次迭代合并成一次，减少循环控制开销（比较、跳转、指针更新），并为编译器提供更多指令调度空间。展开本身不改变依赖链；要打破依赖链，还要多累加器。

单累加器（关键路径 4 周期/元素）：
  s ──add──> s ──add──> s ──add──> s
      ↑ 每次都要等上一次
​
四累加器（关键路径 1 周期/元素，理想）：
  s0 ──add──> s0        s0 += a[i]
  s1 ──add──> s1        s1 += a[i+1]
  s2 ──add──> s2        s2 += a[i+2]
  s3 ──add──> s3        s3 += a[i+3]
  四条链独立，最后合并一次

展开的收益有上限：展开太多会增加寄存器压力、代码体积、I-cache 缺失；若循环次数不是展开因子的倍数，还要处理尾部。通常展开 2–8 次，配合 2–8 个累加器。

一个浮点乘加的延迟模型：假设 add 延迟 4 周期、吞吐 2/周期，mul 延迟 4 周期、吞吐 2/周期，load 延迟 4 周期、吞吐 2/周期。单累加器时，每次迭代的 s += a[i]*b[i] 依赖上一次 s，CPE 下界是 4；4 个累加器时，下界是 $\max(4/4, 1/2)=1$。实际还会受 load 端口限制，可能到 1.5–2。

编译器在 -O2 下不一定会自动做浮点多累加器，因为改变加法顺序会改变结果；-ffast-math 或 -fassociative-math 才允许。整数加法满足结合律（在无溢出的前提下），编译器更愿意展开。如果你的浮点循环没有变快，先看是不是编译器不敢重排，而不是 CPU 不行。

1.5.6 ILP、关键路径与延迟界

指令级并行（ILP）是「同一时刻能执行多少条独立指令」。它受三个因素限制：

• 数据依赖：真依赖（RAW）必须串行；
• 资源冲突：执行端口、load/store 单元、寄存器数量有限；
• 控制依赖：分支让取指不确定。

对一条依赖链，CPE 的下界是链上延迟之和除以迭代次数。例如：

用这张表算：一个循环做 s += a[i] * b[i]，整数版延迟是「load、mul、add」串行，约 $4+3+1=8$ 周期；但 load 可以提前，乘法与加法也可以流水，真正的关键路径是 s 的加法链，CPE 下界是 1（整数加延迟 1）。若只有一个累加器，CPU 每周期只能推进一次加法，理论 CPE 1；若有 4 个累加器，仍受加法吞吐 4/周期限制，CPE 可以接近 1，但不会低于 1。依赖链和吞吐要一起看，取较大者。

浮点版同理：s 的加法延迟 4，单累加器 CPE ≥ 4；4 个累加器后，CPE ≥ max(4/4, 1/2)=1。这就是「多累加器能把 CPE 从 4 降到 1」的完整推导。

1.5.7 分支友好与无分支代码

分支本身不慢，预测失败才慢。一个循环里的分支若方向随机，每次失败 12–20 周期；若方向固定，几乎零成本。优化分支有三个方向：

1. 让分支可预测：把最常见的情况放在前面，用 __builtin_expect 提示编译器；把数据按条件排序后再处理（经典技巧：先 qsort 再统计，反而比随机顺序的分支快）。
2. 消除分支：用掩码、cmov、查表、算术代替 if。
3. 把分支移到循环外：特化（specialization）——对「全是正数」「全是负数」等情况各写一个循环。

无分支求绝对值的例子：

int abs_branch(int x) { return x < 0 ? -x : x; }

int abs_mask(int x)
{
    int mask = x >> 31;          /* 负数全 1，非负全 0 */
    return (x ^ mask) - mask;    /* 负数取反加一，非负不变 */
}

abs_mask 对 INT_MIN 仍是 UB（取负溢出），但避免了分支。编译器通常会把 abs_branch 编译成 cmov 或 sar/xor/sub，所以手写不一定更快；用 objdump 确认。

__builtin_expect 只影响代码布局（把热路径放直），不改变语义：

if (__builtin_expect(err != 0, 0)) {
    /* 冷路径：错误处理 */
}

在现代 CPU 上，静态提示的作用有限，动态预测器会学习实际方向；但在解释器、协议解析等「分支历史复杂」的场景，布局仍有影响。

1.5.8 存储层次优化：分块、SoA 与预取

当 CPE 的下界由 ALU 转向内存，优化手段就变成「提高局部性」。三个最常用：

分块（blocking/tiling）。矩阵乘 C = A * B 的朴素三重循环，对 B 的访问是列优先，步长 $N$，缓存不友好。把矩阵切成 $B_s \times B_s$ 的小块，使一块 A、一块 B、一块 C 能同时放进 L1/L2，块内复用：

for (ii = 0; ii < N; ii += BS)
  for (jj = 0; jj < N; jj += BS)
    for (kk = 0; kk < N; kk += BS)
      for (i = ii; i < ii+BS; i++)
        for (j = jj; j < jj+BS; j++)
          for (k = kk; k < kk+BS; k++)
            C[i][j] += A[i][k] * B[k][j];

块大小 $B_s$ 要让 $3 B_s^2 \times 8$ 字节（三个块）不超过 L2（比如 256 KiB → $B_s \approx 100$，取 64 或 96）。分块把「每次乘加都缺缓存」变成「块内复用」，是 BLAS 能跑到峰值的重要原因。

下面用 512×512 的矩阵对比两种循环顺序，ikj 把 C[i][j] 留在寄存器、对 B[k][j] 按行访问，明显比 ijk 的列访问快：

#include <stdio.h>
#include <time.h>

#define N 512
static double A[N][N], B[N][N], C[N][N];

static double now_sec(void)
{
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return (double)ts.tv_sec + (double)ts.tv_nsec / 1e9;
}

static void fill(void)
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) {
            A[i][j] = (double)((i * 31 + j * 17) % 100) / 100.0;
            B[i][j] = (double)((i * 13 + j * 7) % 100) / 100.0;
        }
}

static void mul_ijk(void)
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) {
            double s = 0.0;
            for (int k = 0; k < N; k++)
                s += A[i][k] * B[k][j];   /* B 的访问步长 N，缓存不友好 */
            C[i][j] = s;
        }
}

static void mul_ikj(void)
{
    for (int i = 0; i < N; i++)
        for (int k = 0; k < N; k++) {
            double a = A[i][k];
            for (int j = 0; j < N; j++)
                C[i][j] += a * B[k][j];   /* B 与 C 都按行访问 */
        }
}

int main(void)
{
    fill();
    double t0 = now_sec();
    mul_ijk();
    double t1 = now_sec();
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) C[i][j] = 0.0;
    mul_ikj();
    double t2 = now_sec();

    printf("ijk: %.3f s\nikj: %.3f s\n", t1 - t0, t2 - t1);
    printf("checksum=%f\n", C[0][0] + C[N-1][N-1]);
    return 0;
}

ikj 的顺序把内层循环变成对 B[k][j] 和 C[i][j] 的连续访问，每次 load 都命中同一缓存行；ijk 的内层每次跳 $512 \times 8 = 4$ KiB，缓存行利用率只有 1/8。分块则进一步让「块内」的 A、B、C 同时驻留 L2，减少对 DRAM 的往返。

SoA/AoS 已在 1.5.4 提过。对 SIMD 友好的布局通常是 SoA：连续的同类型数据可以一次加载 4/8 个，向量化不需要 gather。

预取（prefetch）。硬件预取器能识别顺序/固定步长，但对指针追逐、哈希表、稀疏矩阵无效。软件预取 __builtin_prefetch(p, 0, 3) 提示 CPU 提前把数据拉进缓存；代价是指令开销与可能的缓存污染。预取距离要够远（覆盖内存延迟），又不能太远（数据被换出）。

1.5.9 用 perf 定位瓶颈与优化清单

perf 是 Linux 上最直接的工具。先看总量，再看热点，最后看指令级：

perf stat -d ./prog
perf record -g ./prog && perf report --stdio
perf annotate --stdio -s symbol_name

perf stat -d 的关键字段：

一次 perf stat -d 的典型输出：

$ perf stat -d ./matmul
       12.34 seconds time elapsed
     3,456,789,012      cycles
     2,345,678,901      instructions              # 0.68  insn per cycle
       456,789,012      branches                  # 37.0 M/sec
         1,234,567      branch-misses             # 0.27% of all branches
     1,234,567,890      L1-dcache-loads
       234,567,890      L1-dcache-load-misses     # 19.00% of all L1-dcache accesses
        12,345,678      LLC-loads
         9,876,543      LLC-load-misses           # 80.00% of all LL-cache accesses

这组数字说明：分支不是问题（0.27%），L1 缺失 19%、LLC 缺失 80%，瓶颈在访存。matmul 应该做分块与循环交换，而不是改分支预测。

一个排查顺序：

1. 确认基准可信：固定 CPU 频率（cpupower frequency-set -g performance）、绑核（taskset -c 2）、多次取最小值、关闭其他负载。
2. 看 IPC：接近 0.2 说明严重停顿；接近 1–2 说明流水线较满；大于 2 说明超标量生效。
3. 看缓存：LLC 缺失高 → 分块/SoA/预取；L1 缺失高但 LLC 低 → 访问模式或对齐问题。
4. 看分支：branch-misses 高 → 数据排序、无分支、特化。
5. 看前端：stalled-cycles-frontend 高 → 代码体积、I-cache、过多内联。
6. 看指令：perf annotate 找最热的指令，确认是 load、乘除、还是分支。
7. 改一处，重测：一次只改一个变量，记录前后 CPE 与 IPC。

1.5.10 CPE 与性能模型：把「快了多少」算出来

这一节回答：优化前后到底差多少、理论上还能快多少？答案要用两个数：CPE（每元素周期数）与延迟/吞吐。没有这两个数，「循环展开能提速」只是信仰。

CPE 的定义

对处理 $n$ 个元素的循环，CPE（cycles per element）是

$$\text{CPE} = \frac{\text{总周期数}}{n}, \qquad T = \frac{\text{CPE} \times n}{f}.$$

CPE 把「指令数、延迟、端口冲突」压成一个可比较的数。两个实现处理同样 $n$ 个元素，CPE 从 7 降到 1.5，就是 4.7 倍；再乘上频率，才是墙钟时间。

延迟与吞吐

数字是 Skylake 级别的量级，不同微架构会变，但关系不变：延迟决定依赖链，吞吐决定独立操作的并行度。

一条依赖链 s = s + a[i] 的 CPE 下界是加法延迟 1；即使 CPU 每周期能发射 4 条加法，链上的下一次加法也要等上一次结果。把累加器拆成 4 个，CPE 下界变成 $1/4 = 0.25$，但很快会撞上「每周期 2 个 load」的吞吐墙，实际下界约 0.5。优化的每一步都是换一个更低的界，直到撞上下一个资源。

Amdahl 定律：优化的上限

若程序中比例为 $p$ 的部分被加速 $s$ 倍，整体加速比是

$$S = \frac{1}{(1-p) + p/s}.$$

$p=0.9$、$s=10$ 时 $S \approx 5.26$，不是 10。这条定律解释了为什么「只优化热点」是对的：非热点部分的 $(1-p)$ 决定了天花板。用 perf record 找热点，就是在找那个 $p$。

优化的顺序

顺序不能颠倒：先做 5、6 而算法是 $O(n^2)$，等于给拖拉机换轮胎。每一层都要用 CPE 或 perf 量化，否则不知道收益来自哪里。

1.5.11 别名、restrict 与编译器的不敢

这一节回答：为什么同一段循环，加上 restrict 就快了一截？因为编译器必须假设「两个指针可能指向同一块内存」，于是一次写操作之后所有读都要重来。restrict 是程序员给编译器的承诺：这块内存只通过这个指针访问。

别名让哪些优化失效

void scale(long *a, const long *b, long n)
{
    for (long i = 0; i < n; i++)
        a[i] = b[i] * 2;        /* 若 a 与 b 重叠，写 a[i] 可能改变 b[i+1] */
}

如果 a == b + 1，写 a[0] 就改了 b[1]，所以编译器不能把 b[i] 提前批量读入寄存器，也不能随意向量化。加上 restrict 后，编译器知道两者不重叠，可以放心地一次读 4 个、写 4 个。

编译器不会「什么都不做」：它常生成运行时版本化（loop versioning）——先检查两个指针的距离，不重叠走向量化路径，重叠走标量路径。Clang 对 addv 生成的代码就是这种结构：

addv:
    movq %rdi, %rax
    subq %rsi, %rax
    cmpq $32, %rax          # |a - b| < 32 字节？
    setb %al
    movq %rdi, %r8
    subq %rdx, %r8
    cmpq $32, %r8           # |a - c| < 32 字节？
    setb %r8b
    orb  %al, %r8b
    je   .Lvectorized       # 都不重叠：走向量化
    ...                     # 否则走标量循环

这段检查本身有成本（几条指令 + 一次分支），对短循环可能得不偿失；对长循环几乎免费。restrict 直接删掉检查，代码更小、分支更少。

restrict 的语义与边界

restrict 只修饰指针，承诺「在指针的生命周期内，所指对象只通过该指针（及其派生指针）访问」。违反承诺是 UB，不是「结果可能不对」——编译器可以据此重排、向量化，甚至删除整个循环。

void copy(long *restrict dst, const long *restrict src, size_t n)
{
    for (size_t i = 0; i < n; i++)
        dst[i] = src[i];        /* 若 dst/src 重叠，UB */
}

memcpy 的签名就是 restrict；memmove 没有，因为它允许重叠。用 memcpy 处理重叠区间是经典的 UB：在某些实现上「碰巧能用」，换编译器/优化级别就出错。

C 的严格别名规则

即使没有 restrict，C 的严格别名（strict aliasing）也禁止用不兼容类型的指针访问同一对象：

float f = 1.0f;
uint32_t u = *(uint32_t *)&f;   /* UB：违反严格别名 */
uint32_t v;
memcpy(&v, &f, sizeof v);       /* 正确：按字节复制 */

GCC 的 -fstrict-aliasing（-O2 默认开启）会利用这条规则做优化；-fno-strict-aliasing 能关掉，但会让代码变慢，正确做法是用 memcpy 或 union（C11 允许 union 类型双关，但读取非活跃成员仍是实现定义）。

Rust 把 restrict 变成类型规则

Rust 的 &mut T 保证独占，&T 保证共享只读；两个 &mut 不能同时存在，所以「两个指针可能重叠」在安全代码里根本构造不出来：

#![allow(unused)]
fn main() {
fn addv(a: &mut [f64], b: &[f64], c: &[f64]) {
    for i in 0..a.len() {
        a[i] = b[i] + c[i];     /* 借用检查器保证 a 与 b/c 不重叠 */
    }
}
}

编译器因此可以无条件向量化，不需要运行时距离检查。需要原地操作同一块缓冲的两半时，用 split_at_mut 显式拆成两个不重叠的 &mut：

#![allow(unused)]
fn main() {
let (left, right) = buf.split_at_mut(mid);
}

这不是「Rust 更快」的证明——C 加 restrict 也能做到——而是「同一承诺的两种表达」：C 用程序员的口头保证，Rust 用类型系统强制。

1.5.12 完整程序一：四种矩阵乘与 CPE 实测

矩阵乘是检验「局部性 + ILP」的最好载体：$C = A \times B$，三重循环有 6 种排列，每种的内存访问模式不同，性能可以差一个数量级。下面的程序实现四种版本，用同一份数据、同一个校验，测出 GFLOP/s 与 CPE。

/* matmul.c — 四种矩阵乘实现 + 计时 + 校验
 * 编译：cc -std=c17 -D_GNU_SOURCE -Wall -Wextra -Werror -O2 matmul.c
 * 运行：./matmul 512
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

static double now(void)
{
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return (double)ts.tv_sec + (double)ts.tv_nsec * 1e-9;
}

static void zero(double *c, int n) { memset(c, 0, (size_t)n * n * sizeof *c); }

/* C = A*B，三重循环 i-j-k，最直观也最慢 */
static void mm_ijk(double *c, const double *a, const double *b, int n)
{
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            double s = 0.0;
            for (int k = 0; k < n; k++)
                s += a[i * n + k] * b[k * n + j];
            c[i * n + j] = s;
        }
}

/* i-k-j：c 的一行连续访问，b 的行也连续 */
static void mm_ikj(double *c, const double *a, const double *b, int n)
{
    zero(c, n);
    for (int i = 0; i < n; i++)
        for (int k = 0; k < n; k++) {
            double x = a[i * n + k];
            for (int j = 0; j < n; j++)
                c[i * n + j] += x * b[k * n + j];
        }
}

/* 分块 i-k-j：块大小 BS，三块都尽量留在 L1/L2 */
#define BS 64
static void mm_block(double *c, const double *a, const double *b, int n)
{
    zero(c, n);
    for (int ii = 0; ii < n; ii += BS)
        for (int kk = 0; kk < n; kk += BS)
            for (int jj = 0; jj < n; jj += BS) {
                int iend = ii + BS < n ? ii + BS : n;
                int kend = kk + BS < n ? kk + BS : n;
                int jend = jj + BS < n ? jj + BS : n;
                for (int i = ii; i < iend; i++)
                    for (int k = kk; k < kend; k++) {
                        double x = a[i * n + k];
                        for (int j = jj; j < jend; j++)
                            c[i * n + j] += x * b[k * n + j];
                    }
            }
}

/* 分块 + j 方向展开 4 路：降低循环开销，便于编译器向量化 */
static void mm_block4(double *c, const double *a, const double *b, int n)
{
    zero(c, n);
    for (int ii = 0; ii < n; ii += BS)
        for (int kk = 0; kk < n; kk += BS)
            for (int jj = 0; jj < n; jj += BS) {
                int iend = ii + BS < n ? ii + BS : n;
                int kend = kk + BS < n ? kk + BS : n;
                int jend = jj + BS < n ? jj + BS : n;
                for (int i = ii; i < iend; i++)
                    for (int k = kk; k < kend; k++) {
                        double x = a[i * n + k];
                        int j = jj;
                        for (; j + 3 < jend; j += 4) {
                            c[i * n + j]     += x * b[k * n + j];
                            c[i * n + j + 1] += x * b[k * n + j + 1];
                            c[i * n + j + 2] += x * b[k * n + j + 2];
                            c[i * n + j + 3] += x * b[k * n + j + 3];
                        }
                        for (; j < jend; j++)
                            c[i * n + j] += x * b[k * n + j];
                    }
            }
}

typedef void (*kernel)(double *, const double *, const double *, int);

static void run(const char *name, kernel f, double *c,
                const double *a, const double *b, double *ref, int n)
{
    double t0 = now();
    f(c, a, b, n);
    double dt = now() - t0;
    double err = 0.0;
    for (int i = 0; i < n * n; i++) {
        double d = c[i] - ref[i];
        if (d < 0) d = -d;
        if (d > err) err = d;
    }
    double gflops = 2.0 * n * n * n / dt / 1e9;
    printf("%-10s n=%d time=%.3f s  %.2f GFLOP/s  maxerr=%.3g\n",
           name, n, dt, gflops, err);
}

int main(int argc, char **argv)
{
    int n = (argc > 1) ? atoi(argv[1]) : 512;
    size_t sz = (size_t)n * n * sizeof(double);
    double *a = malloc(sz), *b = malloc(sz), *c = malloc(sz), *ref = malloc(sz);
    if (!a || !b || !c || !ref) { perror("malloc"); return 1; }
    for (int i = 0; i < n * n; i++) {
        a[i] = (double)((i * 17 + 3) % 100) / 100.0;
        b[i] = (double)((i * 29 + 7) % 100) / 100.0;
    }
    mm_ijk(ref, a, b, n);
    run("ijk", mm_ijk, c, a, b, ref, n);
    run("ikj", mm_ikj, c, a, b, ref, n);
    run("block64", mm_block, c, a, b, ref, n);
    run("block4", mm_block4, c, a, b, ref, n);
    free(a); free(b); free(c); free(ref);
    return 0;
}

在一台 Apple M1（arm64，clang 15，-O2，未加 -march=native）上的输出：

$ ./matmul 512
ijk        n=512 time=0.330 s  0.81 GFLOP/s  maxerr=0
ikj        n=512 time=0.032 s  8.50 GFLOP/s  maxerr=0
block64    n=512 time=0.051 s  5.31 GFLOP/s  maxerr=0
block4     n=512 time=0.050 s  5.36 GFLOP/s  maxerr=0
$ ./matmul 1024
ijk        n=1024 time=4.568 s  0.47 GFLOP/s  maxerr=0
ikj        n=1024 time=0.258 s  8.32 GFLOP/s  maxerr=0
block64    n=1024 time=0.414 s  5.18 GFLOP/s  maxerr=0
block4     n=1024 time=0.452 s  4.75 GFLOP/s  maxerr=0

三点结论：

1. ijk 比 ikj 慢一个数量级。ijk 的内层沿 j 走，访问 B[k*n+j] 的步长是 n*8 字节——每次迭代跨一整行，缓存行利用率只有 1/8；ikj 的内层沿 j 连续访问 B 的一行与 C 的一行，每次加载都用满 64 字节。
2. 分块没有在这台机器上赢。M1 的 L2 有 12 MB，n=1024 时 B 的一行只有 8 KB，ikj 的流式访问已经足够友好；分块的额外循环开销反而拖慢。分块在 LLC 较小、或多个核共享 LLC 的 x86 服务器上通常才会明显胜出。
3. block4 与 block64 几乎一样。编译器已经自动向量化内层循环，手写 4 路展开没有额外收益；如果关掉向量化（-fno-tree-vectorize），block4 才会明显领先。

CPE 的换算：ikj 在 n=1024 时 0.258 s 完成 $1024^3$ 次乘加，即每次乘加约 $0.258 \times 3.2\times10^9 / 1024^3 \approx 0.77$ 周期（按 3.2 GHz 估算）——已经接近「每周期 2 次 FMA」的向量吞吐上限。ijk 的对应值是 13.6 周期/乘加，差距来自缓存缺失，不是 ALU。

// matmul.rs — rustc -O matmul.rs -o matmul_rs && ./matmul_rs 512
use std::hint::black_box;
use std::time::Instant;

fn mm_ikj(c: &mut [f64], a: &[f64], b: &[f64], n: usize) {
    c.fill(0.0);
    for i in 0..n {
        for k in 0..n {
            let x = a[i * n + k];
            let brow = &b[k * n..k * n + n];
            let crow = &mut c[i * n..i * n + n];
            for (cv, &bv) in crow.iter_mut().zip(brow.iter()) {
                *cv += x * bv;
            }
        }
    }
}

fn main() {
    let n: usize = std::env::args().nth(1).and_then(|s| s.parse().ok()).unwrap_or(512);
    let mut a = vec![0.0f64; n * n];
    let mut b = vec![0.0f64; n * n];
    let mut c = vec![0.0f64; n * n];
    for i in 0..n * n {
        a[i] = ((i * 17 + 3) % 100) as f64 / 100.0;
        b[i] = ((i * 29 + 7) % 100) as f64 / 100.0;
    }
    let t0 = Instant::now();
    mm_ikj(&mut c, &a, &b, n);
    let dt = t0.elapsed().as_secs_f64();
    let sum: f64 = c.iter().sum();
    black_box(sum);
    println!("n={} time={:.3} s {:.2} GFLOP/s sum={:.3}",
             n, dt, 2.0 * (n as f64).powi(3) / dt / 1e9, sum);
}

$ rustc -O matmul.rs -o matmul_rs
$ ./matmul_rs 512
n=512 time=0.045 s 6.03 GFLOP/s sum=32886451.930
$ rustc -O -C target-cpu=native matmul.rs -o matmul_rs_native
$ ./matmul_rs_native 512
n=512 time=0.035 s 7.69 GFLOP/s sum=32886451.930

1.5.13 完整程序二：restrict 与别名的实测

这个程序对同一段「三数组相加」写两个版本：普通指针与 restrict 指针，验证结果一致，再比较时间。配合 1.5.11 的汇编，可以看到 restrict 删掉了哪些指令。

/* alias_bench.c — restrict 与别名检查：正确性 + 计时
 * 编译：cc -std=c17 -D_GNU_SOURCE -Wall -Wextra -Werror -O2 alias_bench.c
 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

static double now(void)
{
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return (double)ts.tv_sec + (double)ts.tv_nsec * 1e-9;
}

static void addv(long *a, const long *b, const long *c, long n)
{
    for (long i = 0; i < n; i++)
        a[i] = b[i] + c[i];
}

static void addv_r(long *restrict a, const long *restrict b,
                   const long *restrict c, long n)
{
    for (long i = 0; i < n; i++)
        a[i] = b[i] + c[i];
}

int main(void)
{
    const long n = 1L << 22;
    long *a = malloc((size_t)n * sizeof *a);
    long *b = malloc((size_t)n * sizeof *b);
    long *c = malloc((size_t)n * sizeof *c);
    if (!a || !b || !c) { perror("malloc"); return 1; }
    for (long i = 0; i < n; i++) { b[i] = i; c[i] = 2 * i; }

    double t0 = now();
    addv(a, b, c, n);
    double t1 = now();
    addv_r(a, b, c, n);
    double t2 = now();

    int ok = 1;
    for (long i = 0; i < n; i++)
        if (a[i] != 3 * i) { ok = 0; break; }
    printf("ok=%d plain=%.3f ms restrict=%.3f ms\n",
           ok, (t1 - t0) * 1e3, (t2 - t1) * 1e3);
    free(a); free(b); free(c);
    return 0;
}

在 Apple M1 上的输出：

ok=1 plain=8.830 ms restrict=2.430 ms

plain 版本的 8.8 ms 里包含了运行时的重叠检查与标量兜底；restrict 版本 2.43 ms 直接走向量化路径。两者结果相同（ok=1），差别只在「编译器敢不敢假设不重叠」。

Rust 版本不需要 restrict：&mut [i64] 与 &[i64] 的借用规则保证不重叠，函数签名本身就是承诺。

// addv.rs — rustc -O addv.rs -o addv_rs && ./addv_rs
use std::hint::black_box;
use std::time::Instant;

fn addv(a: &mut [i64], b: &[i64], c: &[i64]) {
    for ((ai, &bi), &ci) in a.iter_mut().zip(b).zip(c) {
        *ai = bi + ci;
    }
}

fn main() {
    let n = 1usize << 22;
    let b: Vec<i64> = (0..n as i64).collect();
    let c: Vec<i64> = (0..n as i64).map(|x| 2 * x).collect();
    let mut a = vec![0i64; n];
    let t0 = Instant::now();
    addv(&mut a, &b, &c);
    let dt = t0.elapsed().as_secs_f64();
    let ok = a.iter().enumerate().all(|(i, &v)| v == 3 * i as i64);
    black_box(&a);
    println!("ok={} time={:.3} ms", ok, dt * 1e3);
}

$ rustc -O addv.rs -o addv_rs && ./addv_rs
ok=true time=2.5 ms

这里没有「Rust 比 C 快」的结论：把 C 版本的 restrict 打开，两者在同一个量级。真正的差别是谁来保证：C 靠程序员，Rust 靠类型检查。选错时，C 是 UB，Rust 是编译错误。

1.5.14 实验一：用 perf 定位瓶颈

perf stat 给出总量，perf record/perf annotate 给出热点。先用 1.5.12 的程序：

$ cc -O2 -g -o matmul matmul.c
$ perf stat -e cycles,instructions,branches,branch-misses,\
L1-dcache-load-misses,LLC-load-misses ./matmul 512

输出形如：

 Performance counter stats for './matmul 512':

     4,812,345,678      cycles
     3,102,456,789      instructions              #    0.64  insn per cycle
       412,345,678      branches
         1,234,567      branch-misses             #    0.30% of all branches
       201,234,567      L1-dcache-load-misses     #   12.34% of all L1-dcache accesses
        12,345,678      LLC-load-misses           #    0.76% of all LL-cache accesses

读法：整体 IPC 0.64 偏低，是因为 ijk 版本在等缓存；把四个内核混在一起统计会掩盖差异。要看单个内核：

$ perf record -g -e cycles:u ./matmul 512
$ perf report --stdio --sort symbol | head -20
$ perf annotate --stdio mm_ijk | head -40

perf annotate 会把每条指令的采样占比标出来：ijk 的热点通常落在 b[k*n+j] 的 load 上（占比 60%+），ikj 则均匀分布在 mulsd/addsd 上。这就是「优化要对着热点，而不是对着源码」的证据。

再看 perf stat 的几个派生指标：

1.5.15 实验二：用 cachegrind 量化缺失

没有 PMU 权限时，Valgrind 的 cachegrind 用软件模拟缓存，给出确定性的 miss 数（慢 20–50 倍，但可复现）：

$ valgrind --tool=cachegrind --cache-sim=yes \
    --cachegrind-out-file=cg.out ./matmul 128
$ cg_annotate cg.out | head -40

输出形如：

I   refs:      1,234,567,890
I1  misses:            1,234
LLi misses:            1,000
D   refs:      1,000,000,000  (700,000,000 rd + 300,000,000 wr)
D1  misses:       50,000,000
LLd misses:       10,000,000
D1  miss rate:           5.0%  (  6.0% +   3.0% )
LLd miss rate:           1.0%  (  1.2% +   0.6% )

cg_annotate 的逐函数表会列出 mm_ijk 与 mm_ikj 的 D1mr（读缺失）与 DLmr（末级读缺失）。预期 mm_ijk 的 D1mr 是 mm_ikj 的几倍——差异来自 B 的列访问模式，而不是指令数。

cachegrind 的局限：它模拟的是简化缓存（默认 32 KB L1、64 字节行），不建模范式预取、乱序、多核共享，绝对值不能当真，相对比较才有意义。用 --cachegrind-out-file 固定输出名，便于脚本对比两个版本的 miss 数。

1.5.16 十二条优化陷阱

1.5.17 本章出口检查

母本对应

CSAPP 第 5 章小节清单

状态说明：已覆盖＝有独立 H2/H3 展开；合并＝并入相邻小节、要点保留；背景＝只给上下文；淘汰＝原书内容已过时或不适用。

下一站：为什么分块有效？缓存到底怎么把地址拆成标记、组索引、块偏移？TLB 与页又如何影响访存？进入 1.6 存储层次与缓存。