CSAPP Performance Lab 实战：从加速比1.02到满分的优化之路

先聊点亲身感受我第一次拿到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版本做对比算出“每元素周期数”CPECycles 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.813.21.12smooth (512x512)22.621.41.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 第一版分块实现下面是我实验里用的第一版分块实现块大小取16void 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 short16x16的块包含256个像素共1536字节加上目标块的对应数据总共约3KB可以放进L1 Cache。8x8的块更温和但循环开销会稍微大一点32x32的块是6KBL1如果只有32KB也勉强能行但块间重叠和边界浪费会增多。我当时在几台不同机器上试过结论是块大小512x512下CPE备注8x85.8循环开销偏多16x165.1推荐起步值32x325.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,j1)有6个邻居是重叠的朴素版完全没有利用这种重叠导致同一个像素的数据被反复从内存里捞。于是优化思路就变成两个方向一是把边界和内部拆开二是把垂直和水平方向的求和分开做复用中间结果。4.2 方案一边界单独处理内部无分支统一计算这个方案是“脏活累活自己干主循环清清爽爽”。四角和四条边的像素数量只有O(dim)级别用朴素方式处理无伤大雅内部是dim-2乘dim-2的大块用统一的9点累加公式完全去掉ifvoid 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, j1, dim)].red src[RIDX(i, j-1, dim)].red src[RIDX(i, j, dim)].red src[RIDX(i, j1, dim)].red src[RIDX(i1, j-1, dim)].red src[RIDX(i1, j, dim)].red src[RIDX(i1, j1, 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(i1, 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, j1, 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-64L1 32KBL2 256KB版本rotate CPEsmooth CPEnaive14.822.6第一版优化5.19.8展开restrict/two-pass4.25.7总分从最开始的60出头一路提到90多。这个提升不是代码“看起来更复杂”换来的而是每一步都对准了具体的瓶颈rotate对着Cache Misssmooth对着分支和重复访存。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养成“每个改动都有数据支撑”的习惯这比最终那张成绩单更值钱。