先聊点亲身感受：我第一次拿到CSAPP performance lab的时候，心里想的是“不就一个图像旋转、一个图像平滑吗，半小时搞定”。结果写了个自以为很美的版本，跑完driver，加速比1.02，几乎等于没优化。后来我才意识到，这个实验根本不是让你“把函数写对”，而是逼着你去理解程序在真实处理器上到底怎么执行、内存怎么搬运。做完它，再看CSAPP第五章“优化程序性能”，你会觉得每个字都变成了自己的肌肉记忆。
这个实验适合谁？只要是正在啃《深入理解计算机系统》、或者想系统学性能优化的同学，都建议完整跑一遍。它不需要你懂什么高深的编译原理，但需要你愿意对着数据一点点抠细节。下面我按自己做实验的流程，把内核函数、评测机制、优化思路、踩坑记录全部摊开讲。
1. 实验内核：两个函数和一套评测框架
1.1 你需要改的代码长什么样
performance lab的实验文件解压后，核心文件就是一个kernels.c。你要改的就是里面的rotate和smooth这两个函数。整个实验的背景是处理一张正方形图像，每个像素叫pixel，结构体里有三个unsigned short，分别存红、绿、蓝三个通道。
typedef struct { unsigned short red; unsigned short green; unsigned short blue; } pixel; #define RIDX(i, j, dim) ((i) * (dim) + (j))注意这个RIDX宏，后面所有索引都靠它，基本所有“输出错得离谱”的bug都是从这来的。图像按行优先存储，RIDX(i, j, dim)就是第i行第j列的扁平索引。
rotate的任务是把图像顺时针旋转90度，朴素版本长这样：
void naive_rotate(int dim, pixel *src, pixel *dst) { int i, j; for (i = 0; i < dim; i++) for (j = 0; j < dim; j++) dst[RIDX(dim - 1 - j, i, dim)] = src[RIDX(i, j, dim)]; }smooth的任务是给图像做3x3邻域平均，通俗说就是“模糊”。每个像素取它周围最多9个像素的平均值，边界上的点邻居不足9个就按实际个数算。朴素版本就是三重循环加一堆边界判断。
void naive_smooth(int dim, pixel *src, pixel *dst) { int i, j, di, dj; for (i = 0; i < dim; i++) { for (j = 0; j < dim; j++) { int red = 0, green = 0, blue = 0; int cnt = 0; for (di = -1; di <= 1; di++) for (dj = -1; dj <= 1; dj++) { int ni = i + di, nj = j + dj; if (ni >= 0 && ni < dim && nj >= 0 && nj < dim) { red += src[RIDX(ni, nj, dim)].red; green += src[RIDX(ni, nj, dim)].green; blue += src[RIDX(ni, nj, dim)].blue; cnt++; } } dst[RIDX(i, j, dim)].red = red / cnt; dst[RIDX(i, j, dim)].green = green / cnt; dst[RIDX(i, j, dim)].blue = blue / cnt; } } }这个朴素版本虽然正确，但性能可以说是“教科书级地差”。为什么差，后面我会拆开细讲。
1.2 评分规则：加速比怎么算，分数怎么拿
实验自带的评测程序是driver.c，它会拿你的函数和对应的naive版本做对比，算出“每元素周期数”（CPE，Cycles Per Element），再换算成加速比。加速比越高，得分越高，但一般有个上限，不同老师的评分脚本略有差异。
以我当时用的版本为例，每个内核满分50分，总分100分。加速比大概达到3.5到4倍左右就能接近满分，再往上收益明显递减。所以这个实验的核心目标不是“无限优化”，而是“先把最容易拿的分拿到”。
评测时driver会跑多组不同尺寸的图，尺寸从64x64到512x512不等，最后取加权平均。小尺寸图考察循环开销，大尺寸图考察访存局部性，两者都不能偏科。
1.3 编译、运行和读输出
实验文件的编译非常直接：
tar xvf perflab-handout.tar cd perflab-handout make ./driver运行后你会看到类似这样的输出：
Rotate: Version = naive_rotate: Dim 64 0.0 0.0 Dim 128 0.0 0.0 ... Rotate: Version = my_rotate: Dim 64 2.3 4.1 ... Smooth: Version = naive_smooth: ... Smooth: Version = my_smooth: Dim 128 2.1 3.2 ... Summary of Your Results: Rotate: 42.3 Smooth: 38.7 Total: 81.0每次改完代码，重新make再./driver就能看到分数变化。如果分数完全没动，先别急着怀疑机器，大概率是改了函数但没重新编译，或者注册的函数名不对。kernels.c底部有register_rotate_func和register_smooth_func，你新写的函数必须在这里注册，driver才会去测。
2. 动手优化前，先搞懂瓶颈到底在哪
2.1 CPE不是运行时间，而是“每元素周期数”
很多新手第一次看输出会懵：为什么driver不直接告诉我函数跑了多少毫秒，非要给个CPE？因为评测要和CPU频率、编译器版本解耦。CPE表示处理每个像素平均消耗多少个时钟周期，它是一个架构级别的指标，能直接反映算法的指令效率和访存效率。
举个例子：如果某个内核CPE是4.0，说明平均每个像素要消耗4个周期。在3GHz的机器上，处理一张512x512的图（262144像素），大概就是0.35毫秒。CPE越低越好，但“低”是有下限的——一个像素至少要被读写几次，每个像素的数据量摆在那，不可能无限快。
2.2 两个内核为什么慢：访存模式和分支判断
rotate朴素版本最大的问题是列跳跃写入。源图像按行读是连续的，但写入目标时，dim - 1 - j决定了列方向的变化。一行源数据内的j连续增加时，目标地址每次跳dim个像素，也就是跨行写入。图稍微大一点，比如512x512，一行就是3KB，目标列跳来跳去，Cache里的line反复被替换，就会产生大量Cache Miss。
smooth朴素版本的问题更明显。第一，每个像素都要做边界判断，9个邻域全被if包着，分支预测器在边界和内部之间反复横跳，开销很大。第二，每个像素的9个邻居会被相邻像素重复加载，数据复用率极差。第三，内层9次访存是按小3x3窗口移动的，虽然局部性还行，但循环本身的开销和边界判断分摊到每次像素上，非常亏。
2.3 优化前的基线数据
我第一次跑driver，基线大概是这样的：
| 内核 | 朴素版CPE | 我的第一版CPE | 加速比 |
|---|---|---|---|
| rotate (512x512) | 14.8 | 13.2 | 1.12 |
| smooth (512x512) | 22.6 | 21.4 | 1.06 |
这种“改了半天代码，加速比还在1.1徘徊”的感觉，我相信很多人经历过。原因就是没抓到主要矛盾：rotate的瓶颈在Cache Miss，而我只做了循环展开；smooth的瓶颈在边界分支和重复访存，而我只把内层循环的变量提到了外面。
从这一步起，我开始记一个原则：优化之前先问一句，这个函数的时间花在哪了？没有数据支撑的优化，大多是在感动自己。
3. rotate内核优化：把“列跳跃”变成“块搬运”
3.1 朴素版rotate为什么慢到让人怀疑人生
朴素版rotate的访存模式可以这样理解：源是老老实实从第一行读到第N行，目标是按照“列转置”的方式写回去。写一个512x512的图，每个目标像素地址相隔512个像素，也就是3KB步长。如果L1 Cache只有32KB，那么同一时刻Cache里能覆盖的目标行非常有限，写入时经常Miss。
有人可能会说：那我把内层循环改成按目标行连续写不就行了？比如让j作为目标行索引。但这样源就又变成列跳跃了。治标不治本。真正有效的思路是分块：让源和目标在某个局部范围内都保持连续或近似连续。
3.2 分块（blocking）为什么有效
分块的核心逻辑很简单：把大图像切成若干小方块，每个方块内部，源像素连续读入，目标像素落在一个小范围内写入，块与块之间再移动。小块内部数据能塞进Cache，大幅降低Miss率。
打个比方，你要把一整本书的内容抄到另一本按列排版的笔记本里。整体抄写时，每写几个字就要翻到很远的一页；但如果把书分成一小节一小节，每次只抄一寸厚的纸，这样翻页距离大大缩短。分块就是这个道理。
3.3 第一版分块实现
下面是我实验里用的第一版分块实现，块大小取16：
void rotate_block(int dim, pixel *src, pixel *dst) { int i, j, k, l; for (i = 0; i < dim; i += 16) { for (j = 0; j < dim; j += 16) { for (k = i; k < i + 16 && k < dim; k++) { for (l = j; l < j + 16 && l < dim; l++) { dst[RIDX(dim - 1 - l, k, dim)] = src[RIDX(k, l, dim)]; } } } } }对比朴素版，唯一的区别就是外层多了两层块循环。但就是这一点改变，512x512下CPE从14.8掉到了5.1，加速比接近2.9倍。我第一次看到这个数据才意识到，Cache Miss对性能的影响可以比代码本身慢一个数量级。
3.4 块大小怎么选：16x16不是拍脑袋拍的
块大小的选择取决于Cache容量和像素大小。一个pixel是6字节（三个unsigned short），16x16的块包含256个像素，共1536字节，加上目标块的对应数据，总共约3KB，可以放进L1 Cache。8x8的块更温和，但循环开销会稍微大一点；32x32的块是6KB，L1如果只有32KB也勉强能行，但块间重叠和边界浪费会增多。
我当时在几台不同机器上试过，结论是：
| 块大小 | 512x512下CPE | 备注 |
|---|---|---|
| 8x8 | 5.8 | 循环开销偏多 |
| 16x16 | 5.1 | 推荐起步值 |
| 32x32 | 5.3 | 大图有Cache压力 |
块大小不是越极端越好。如果块大到接近整张图，就又变回朴素版的列跳跃；如果块太小，每个块都要重复循环控制，开销占比上升。16x16通常是比较稳的起点。
3.5 再加一点展开和restrict
分块之后还能继续压榨。一个容易忽略的优化是给指针加上restrict关键字，告诉编译器src和dst不会指向同一块内存，编译器就能更大胆地调整读写顺序：
void rotate_block(int dim, pixel *restrict src, pixel *restrict dst)另外一个有效操作是内层循环展开。比如每轮处理4个源像素，减少循环跳转和比较次数：
void rotate_block_unroll(int dim, pixel *restrict src, pixel *restrict dst) { int i, j, k, l; for (i = 0; i < dim; i += 16) { for (j = 0; j < dim; j += 16) { for (k = i; k < i + 16 && k < dim; k++) { for (l = j; l + 3 < j + 16 && l + 3 < dim; l += 4) { dst[RIDX(dim - 1 - l, k, dim)] = src[RIDX(k, l, dim)]; dst[RIDX(dim - 2 - l, k, dim)] = src[RIDX(k, l + 1, dim)]; dst[RIDX(dim - 3 - l, k, dim)] = src[RIDX(k, l + 2, dim)]; dst[RIDX(dim - 4 - l, k, dim)] = src[RIDX(k, l + 3, dim)]; } } } } }注意l + 3 < dim这个边界条件，最后一个不满4的像素需要单独处理。这样优化后，CPE能从5.1再降到4.2左右，加速比能到3.5倍。
4. smooth内核优化：干掉边界判断和重复访存
4.1 朴素版smooth到底慢在哪
smooth的朴素版每个像素要执行9次邻居遍历，每次遍历里都有边界判断。但实际上，只有图像外圈的像素才需要判断边界，内部像素永远可以取满9个邻居。让每个像素都背上边界判断的开销，非常不划算。
另一个问题是重复访存。像素(i,j)和它右边的像素(i,j+1)有6个邻居是重叠的，朴素版完全没有利用这种重叠，导致同一个像素的数据被反复从内存里捞。于是优化思路就变成两个方向：一是把边界和内部拆开，二是把垂直和水平方向的求和分开做，复用中间结果。
4.2 方案一：边界单独处理，内部无分支统一计算
这个方案是“脏活累活自己干，主循环清清爽爽”。四角和四条边的像素数量只有O(dim)级别，用朴素方式处理无伤大雅；内部是dim-2乘dim-2的大块，用统一的9点累加公式，完全去掉if：
void smooth_boundary(int dim, pixel *src, pixel *dst) { int i, j; // 四角：2x2或3x3区域 // 四条边：一行/一列上的点，区域内判断 for (i = 0; i < dim; i++) { for (j = 0; j < dim; j++) { if (i == 0 || i == dim - 1 || j == 0 || j == dim - 1) { int r = 0, g = 0, b = 0, cnt = 0; for (int di = -1; di <= 1; di++) for (int dj = -1; dj <= 1; dj++) { int ni = i + di, nj = j + dj; if (ni >= 0 && ni < dim && nj >= 0 && nj < dim) { r += src[RIDX(ni, nj, dim)].red; g += src[RIDX(ni, nj, dim)].green; b += src[RIDX(ni, nj, dim)].blue; cnt++; } } dst[RIDX(i, j, dim)].red = r / cnt; dst[RIDX(i, j, dim)].green = g / cnt; dst[RIDX(i, j, dim)].blue = b / cnt; } else { dst[RIDX(i, j, dim)].red = (src[RIDX(i-1, j-1, dim)].red + src[RIDX(i-1, j, dim)].red + src[RIDX(i-1, j+1, dim)].red + src[RIDX(i, j-1, dim)].red + src[RIDX(i, j, dim)].red + src[RIDX(i, j+1, dim)].red + src[RIDX(i+1, j-1, dim)].red + src[RIDX(i+1, j, dim)].red + src[RIDX(i+1, j+1, dim)].red) / 9; // green, blue 同理 } } } }这个版本的好处是代码直观、不容易写错，内部主循环没有分支。坏处是重复访存问题依然存在——每个内部像素还是从边上捞了9次数据。实测下来，在512x512图上CPE能从22.6降到9.8，加速比大约2.3倍。
4.3 方案二：两步滑动窗口，数据重复利用
方案一已经能拿不少分了，但真正的性能提升来自“把二维求平均拆成两次一维求平均”。思路是这样：每个内部像素的3x3平均，可以先对每一列做垂直方向的3像素累加，得到一个中间数组tmp；再对tmp的每一行做水平方向的3像素累加，最后除以9。这样每个源像素在垂直方向被读一次，中间结果在水平方向被读一次，总量从每个像素9次访存降到大约3次。
void smooth_two_pass(int dim, pixel *src, pixel *dst, int *tmp) { int i, j; // pass 1: 垂直方向，先不加权，只求和 // 第一行 for (j = 0; j < dim; j++) { tmp[RIDX(0, j, dim)] = src[RIDX(0, j, dim)].red + src[RIDX(1, j, dim)].red; tmp[RIDX(1, j, dim)] = src[RIDX(0, j, dim)].red + src[RIDX(1, j, dim)].red + src[RIDX(2, j, dim)].red; } // 中间行 for (i = 2; i < dim - 1; i++) { for (j = 0; j < dim; j++) { tmp[RIDX(i, j, dim)] = src[RIDX(i-1, j, dim)].red + src[RIDX(i, j, dim)].red + src[RIDX(i+1, j, dim)].red; } } // 最后一行 for (j = 0; j < dim; j++) { tmp[RIDX(dim-1, j, dim)] = src[RIDX(dim-2, j, dim)].red + src[RIDX(dim-1, j, dim)].red; } // 为了简洁，红色通道只写了垂直方向的一部分 // 实际要分别处理 red / green / blue，或把tmp改成3通道结构体 // pass 2: 水平方向，累加tmp的值并除以实际邻居个数 for (i = 0; i < dim; i++) { for (j = 0; j < dim; j++) { int sum = 0, cnt = 1; if (j > 0) { sum += tmp[RIDX(i, j-1, dim)]; cnt++; } sum += tmp[RIDX(i, j, dim)]; if (j < dim - 1) { sum += tmp[RIDX(i, j+1, dim)]; cnt++; } dst[RIDX(i, j, dim)].red = sum / cnt; } } }上面代码我为了演示垂直方向只写了red通道，实际做的时候要注意green和blue也不能漏。一个更工程化的写法是把tmp定义成int tmp[MAXDIM * MAXDIM * 3]，分别存三个通道。这个方案的优点在于访问模式非常线性，Cache友好度远高于9点随机抓取。配合前面rotate用到的restrict和循环展开，512x512下CPE能压到5.5到6.0，加速比大约3.8倍。实验分数基本能到满分附近。
4.4 近似除法要不要用
很多人在smooth里纠结怎么优化“除以9”这个整数除法。实验机上整数除法周期确实不低，但如果为了省几次除法去做乘法和移位近似，很容易引入误差。比如用(x * 455) >> 12来近似x / 9，误差在部分取值下可能达到1。有的driver校验很严格，要求输出与朴素版本完全一致，这时候近似就是给自己挖坑。
我的经验是：先把访存和分支优化到位，最后再看除法。实测下来，在大多数处理器上，除法的开销占比远没有访存Miss大。如果确实想动除法，建议先确认你们实验的校验策略允不允许像素值有1的偏差，再决定要不要冒险。
4.5 实测数据对比
我自己实验里跑出来的数据大概是这样（512x512，机器是x86-64，L1 32KB，L2 256KB）：
| 版本 | rotate CPE | smooth CPE |
|---|---|---|
| naive | 14.8 | 22.6 |
| 第一版优化 | 5.1 | 9.8 |
| 展开+restrict/two-pass | 4.2 | 5.7 |
总分从最开始的60出头，一路提到90多。这个提升不是代码“看起来更复杂”换来的，而是每一步都对准了具体的瓶颈：rotate对着Cache Miss，smooth对着分支和重复访存。
5. 常见问题与排查实录
5.1 输出错得离谱：多半是索引写反了
我第一次写rotate分块时，RIDX(dim - 1 - j, i, dim)写成了RIDX(dim - 1 - i, j, dim)，结果出来的图像不是旋转，是镜像加转置。怎么排查？最土的办法是在小尺寸下打印几个关键位置的像素值，手动算一下期望值。
driver本身有正确性校验，出错时会明确提示有多少个像素不一致。定位索引错误时，建议把dim设成4或8这种小尺寸，肉眼对比src和dst的映射关系。一个快准则：旋转90度，原图的宽度会变成新图的高度，所以新旧索引里一定有一个坐标发生了“交换”。如果两个索引都没交换，那肯定是错的。
5.2 segfault/段错误：越界读写
分块循环最容易犯的错就是边界处理：一个16x16的块，在图像边缘可能不足16像素，如果还是无脑访问i + 16，就会越界。所有分块循环里都要加&& k < dim、&& l < dim之类的限制条件。
另外别忘了dst的大小和src一样，旋转时目标索引算错也可能写到分配区域外面去。跑driver之前先在终端里用小型数据自测，不要直接上512的大图。
5.3 加速比一直卡在1.1左右
这是最常见的挫败来源。我的诊断顺序是：
- 确认改的是不是被register的函数。很多人改了
naive_rotate，但注册的还是旧函数。 - 确认重新编译了。加了
restrict或改了大循环，不make就直接跑driver，分数当然不变。 - 检查访存模式是不是还带列跳跃。如果rotate没分块，无论怎么展开，Cache Miss都压不下去。
- 用perf之类的工具看一眼Cache Miss数量。如果优化后Cache Miss几乎没变，说明优化方向根本不对。
5.4 优化后结果不对：误差问题
smooth用两步滑动窗口时，tmp里的中间结果必须存“和”，不能存“平均值”。如果你第一步就除以了3，第二步再除以3，等于整体除以9，但边界像素的实际邻居个数不是9，结果很容易错。更稳妥的做法是第一步完全不除法，第二步按实际邻居数除。
如果driver对误差是零容忍，那任何乘除法近似都要慎用。我见过有人用位运算近似除9，结果数据有1个灰度值偏差，直接被扣分，得不偿失。
5.5 调试与验证技巧速查
| 现象 | 可能原因 | 快速排查 |
|---|---|---|
| 输出错乱 | RIDX坐标写反 | 小尺寸下手动推几个坐标 |
| 段错误 | 分块越界 | 检查所有块循环边界条件 |
| 分数不涨 | 没重新编译 | make clean && make |
| 分数不涨 | 优化点没对准瓶颈 | 对比Cache Miss或CPE |
| 结果偏差1 | 除法近似误差 | 改用整数除法或调整验证方式 |
| driver运行慢 | 开了过多调试打印 | 去掉printf再测 |
还有一个小技巧：driver本身支持只跑某个内核或某个尺寸，阅读它的命令行参数，可以省很多等待时间。调rotate时只测rotate，调smooth时只测smooth，别每次跑全套。
6. 收尾：实验做完之后的几点体会
这个实验最让我意外的不是“分块能提速”，而是提速幅度可以这么大。一个看起来很简单的两层循环，调整访存模式后性能翻三倍，这在日常业务代码里很少见，因为业务代码的瓶颈往往在数据库和网络，CPU访存优化不是第一优先。但如果你做大模型推理、图像处理、高性能计算，这些底层的Cache意识和数据复用能力，就是实打实的竞争力。
我个人建议做完lab后再做两件事：一是回去重读CSAPP第五章，把所有“循环展开”“分块”“寄存器溢出”这些词和实验中的现象对一遍；二是把两个内核的最终版本留好，以后面试聊性能优化时，直接拿数据说话，比背概念有说服力得多。另外，实验里多试几组块大小、多记录几组CPE，养成“每个改动都有数据支撑”的习惯，这比最终那张成绩单更值钱。
