CSAPP Perflab优化实战：从60分到满分的Cache友好代码技巧

如果你正在刷《深入理解计算机系统》CSAPP那第五章课后配套的Performance Lab基本是绕不过去的一道坎。我当初做这个实验的时候以为就是“把C代码改快一点”结果一折腾就是一周多分数从最开始的60多分慢慢磨到接近满分中间踩过的坑比前面几章碰到的所有问题加起来都多。这篇东西不打算把官方README复述一遍而是以一个刚做完实验的学生视角把rotate图像旋转和 smooth图像平滑到底怎么优化、评分机制怎么利用、Cache友好代码怎么写、以及那些让你分数“莫名其妙消失”的隐蔽原因全部摊开讲。适合正在赶Perflab作业的大学生、自学CSAPP想验证自己优化能力的读者以及以后想做高性能计算、想搞清楚“为什么编译器有时候不听话”的朋友。1. 先搞清楚任务本质rotate和smooth到底在优化什么很多人上来就改代码结果改了三天还在原地打转原因是没读懂实验到底想考你什么。Performance Lab的整体目标很简单给你两个图像处理函数你把它改到尽可能快但不能改变计算结果。听起来像初中生就能理解的任务实际做起来会发现这其实是第五章“优化程序性能”和第六章“存储器层次结构”的一次联合大考。1.1 官方代码框架里到底有什么CSAPP Perflab的代码框架一般长这样一个kernel.c里面有两个核心函数需要你来填一个是处理图像旋转的函数另一个是处理图像平滑的函数。图像用二维数组表示每个像素是一个包含RGB三个分量的结构体每分量8bit。评测程序会构造若干固定尺寸的测试图像调用你的函数然后测量运行时间。旋转函数要做的操作是把一张 N x N 的像素矩阵顺时针旋转90度。最直白的写法就是双重循环里把像素搬到目标位置参考版本通常会写成类似dst[j][N-1-i] src[i][j]的形式具体是顺时针还是逆时针看你拿到的原始框架但优化思路完全相同。平滑函数要做的操作更简单对每个像素取它周围3x3邻域内9个像素的RGB均值作为新像素值输出。参考版本会对每个像素分别判断是角、边还是内部然后套用不同的均值计算逻辑。这些功能本身一点都不复杂任何一个学过C语言的人都能写出来。实验难就难在完全相同的功能不同的写法性能可以差5倍甚至10倍。1.2 “优化”指的是什么层面的优化做这个lab之前我一直以为性能优化就是“把循环改成更高级的算法”比如把冒泡排序换成快排。但Perflab里两个函数已经是接近最优的算法了——旋转本来就是O(N²)平滑也是O(N²)算法层面没有下降空间。真正需要你优化的是两件事第一减少CPU访问内存的次数和成本也就是让Cache命中率变高尽量让数据在寄存器里解决而不是反复去内存里搬第二减少无效指令的执行比如减少函数调用、循环控制、地址计算等“附加动作”。一个特别反直觉的事实你的代码写得好不好很大程度上取决于你对硬件Cache行为的理解而不是取决于你背了多少优化技巧。同样的循环展开放在Cache友好和不友好的写法里效果天差地远。1.3 分数到底怎么算出来的不同学校用的评分脚本不一样但本质大同小异。最典型的方式是评测脚本里有一个参考实现的运行时间然后和你的实现运行时间做对比算出一个0到100之间的分数。比值越大分数越高。比如某个测试尺寸下参考版本跑了100毫秒你跑了50毫秒那你在这个尺寸上就是200分然后脚本会把分数截断到100。注意这里有个细节评分脚本通常会测试多组不同尺寸的图片然后按某种加权方式汇总。这意味着你不能只把一个尺寸优化到极致而要在所有测试尺寸上都表现稳定。另外评测通常是在编译优化-O2下进行的不是默认不开优化也不是往死里开-O3。很多人本地用-O3跑出高分传到评测机上反而低了就是这个原因。2. 环境与评测机制不懂规则等于白忙活一个非常容易被忽略的问题是代码写好了环境不对分数照样不理想。我有同学在macOS上把代码优化得自我感觉良好结果评测一跑分数比Linux下低了将近20分。不是代码不行是环境本身的差异。2.1 评测脚本究竟做了什么Perflab的评测脚本一般会经历这么几步先用GCC把你的kernel.c编译成可执行文件或者动态库然后运行一个driver程序对每个测试尺寸的图像调用你的函数若干次取稳定运行时间通常是取最小值或者平均值再用这个时间和某个参考时间对比计算出分数。这里面有一个很重要的点评测程序为了保证公平一般会做“预热”和“循环多次计时”。你以为你只被调用了一次实际上你的函数会被反复调用几十上百次。这种机制带来的副作用是如果你的代码里偷偷做了“第一次调用时把结果缓存下来后续直接读缓存”这种事情评测脚本很容易发现并且直接判0分。不要去挑战评测脚本的边界老老实实优化函数本身就好。2.2 环境搭建的隐性要点下面这些环境问题是我自己踩过或者看别人踩过的列出来给你提个醒。尽量在Linux原生环境做。不是说我歧视macOS而是Perflab的评分基准、编译器行为、Cache几何结构都是以Linux环境为参考的。macOS的clang在默认情况下某些优化行为和GCC差别挺大可能导致你本地测出来的时间完全不能反映评测机上的情况。关掉图形界面和后台任务。计时这种敏感操作一个后台Chrome进程都可能导致你的运行时间抖动20%以上。评测前用cpupower frequency-set -g performance把CPU锁到最高频率能有效减少波动。尽量不要在虚拟机里做最终测试。虚拟机有虚拟化层CPU频率变化和Cache行为都和裸机不太一样用来估个大概可以但别拿虚拟机里的时间当作优化依据。Docker容器如果直接跑在裸金属上影响会小一些但也不如原生干净。Windows下直接用原生评测是地狱难度。性能计数器经常出各种莫名其妙的问题比如系统里“无法读取 usbperf\performance 注册表项下的 First Counter 值”这种报错就会让基于性能计时的评分脚本直接崩掉。有这功夫排查Windows性能计数器问题不如装个Linux虚拟机或者WSL。2.3 分模块修改别指望一次成型Perflab是单文件提交但你在本地开发时千万别只在kernel.c里反复修改然后直接测。我的习惯是rotate和smooth分开维护版本每次只改其中一个函数然后立即跑一次完整评测并记录结果。比如我有一张表格记录第几次修改、改了什么、rotate分数多少、smooth分数多少、总分多少。这样一旦分数下降很快就能定位到是哪个改动导致的。这个习惯可能听起来很基础但在实验后期特别有用。我见过太多人改了一个小时改完发现总分反而降了却完全想不起来改了什么。3. baseline为什么这么慢从Cache和汇编两个角度看在动手优化之前我先花了一下午研究参考版本为什么慢。这一步看似浪费时间实际上决定了后续所有优化方向。你连对手的弱点都找不到优化就只能是瞎猫碰死耗子。3.1 旋转函数Naive版慢在“写列”而不是“读行”我们用最朴素的旋转代码来分析void naive_rotate(int dim, pixel *src, pixel *dst) { for (int i 0; i dim; i) { for (int j 0; j dim; j) { dst[RIDX(dim-1-j, i, dim)] src[RIDX(i, j, dim)]; } } }这个版本的时间和Cache行为到底发生了什么先说读src是按行循环的也就是一行一行连续读这是顺序访问Cache命中率相当高。但看写dst的目标位置是RIDX(dim-1-j, i, dim)也就是说当i固定、j在变化时目标地址的列在变行也在变本质上是按列跳跃写入。每一行写一个像素就会把一个Cache Line填满一部分然后下一行又跳到别的Cache Line去了。结果就是写操作几乎每写一个像素都会把一个完整的Cache Line从内存加载到Cache改掉其中的一小部分然后再写回内存。这种“写撕裂”是性能杀手。具体来说一个64字节的Cache Line可以装16个像素假设像素结构体16字节但你写一个像素就浪费了剩下15个像素的带宽。所以naive版本的瓶颈主要不在指令数量而在Cache Line的利用效率极低。这也是为什么单纯循环展开对这个函数帮助不大因为循环展开解决的是指令级并行解决不了访存模式问题。3.2 平滑函数Naive版慢在“重复计算”和“冗余判断”平滑函数参考版本通常写成这样static void avg(int dim, pixel *src, pixel *dst, int i, int j) { // 根据 i, j 是否在边界取不同的邻域大小然后对RGB分量分别求平均 // ... } void naive_smooth(int dim, pixel *src, pixel *dst) { for (int i 0; i dim; i) { for (int j 0; j dim; j) { avg(dim, src, dst, i, j); } } }表面上看内部像素每个都要算9个像素的均值外部边界少一点。问题在于每个像素的9个邻居里有一半左右是跟前一个像素共享的。比如处理(i, j)和处理(i, j1)时两行三列6个像素是完全相同的只有3个是新引入的。Naive版本把这些共享计算全部重复了一遍浪费了大约2/3的加法操作。更致命的是内层循环每次都要用一堆if判断当前像素是不是边界然后走进不同的分支。CPU的分支预测器在边界和内部之间跳来跳去预测失败率很高每次预测失败都会浪费十几个CPU周期。这就是为什么你只优化判断逻辑不优化重复计算也能看到明显提升的原因。3.3 用objdump -S看看编译器到底生成了什么我强烈建议你在优化之前做一次这个动作gcc -O2 -S kernel.c -o kernel.s打开生成的汇编文件你会看到真实情况一个看起来简简单单的avg函数调用会被编译成几十条指令每读一个像素都可能伴随若干次内存加载指令如果没有开启优化函数调用开销还要再加上栈帧的建立和销毁。看汇编的过程很枯燥但会彻底改变你对C代码性能的看法。比如你会发现数组下标src[Row * dim col]在循环里其实被优化成了指针加偏移量的形式这点你不需要手动改但你也会发现如果编译器无法证明src和dst指向的内存不重叠它就会老老实实地把每次写入都严格执行不敢乱重新排序这时候restrict关键字就派上用场了。4. rotate优化实战局部性原理的一次完整应用理解了瓶颈在哪优化方向就清晰了。对rotate来说核心目标只有一个把“按列写入”变成“小块内的连续写入”。这就是常说的分块优化blocking也是整个Perflab最重要的技巧。4.1 分块blocking为什么有效思路很简单既然整幅图像太大Cache装不下按列跳跃的写入序列那我每次只取一小块比如32x32像素这一小块足够装进L1或者L2 Cache然后对这个小块做旋转时源数据块和目标数据块都能在Cache里待着读写都不会反复访问内存。伪代码如下void rotate_block(int dim, pixel *src, pixel *dst, int block_size) { for (int i 0; i dim; i block_size) { for (int j 0; j dim; j block_size) { for (int ii i; ii i block_size; ii) { for (int jj j; jj j block_size; jj) { dst[RIDX(dim-1-jj, ii, dim)] src[RIDX(ii, jj, dim)]; } } } } }注意这里的索引坐标dst[RIDX(dim-1-jj, ii, dim)]。这是我们熟知的顺时针旋转90度映射即源图像的第i行第j列像素会跑到目标图像的第dim-1-j行第i列。当你用小块表示时块内写操作不再是全幅按列跳跃而是变成了“小范围内的按行/按列混合跳跃”这个跳跃的范围如果足够小目标块的全部行都能被Cache容纳效率自然就上来了。但块大小不是越大越好也不是越小越好。块太大Cache装不下块太小循环控制开销和分块边界跳动反而拖慢速度。我实测最常见的表现是块大小8到16时比naive快2到3倍块大小32到64时通常达到峰值块大小达到128以上时效果开始回落因为L2 Cache已经放不下了还要留一部分给源块。块大小相对naive的加速比N512时实测直观感受1等于naive1.00x写列风暴82.1x稍有改善162.8x明显提升323.4x最佳区域643.2x开始回落1282.4x块太大Cache放不下了不同CPU的Cache容量和Cache Line大小不同最佳块大小也会有差异。所以“32”这个数字不是拍脑袋想出来的而是你对着一组测试尺寸一个个跑出来的。4.2 块内循环展开给编译器更多发挥空间分块解决了Cache问题但块内循环依然有大量控制指令和地址计算。接下来可以做循环展开。以4x4展开为例void rotate_4x4_block(int dim, pixel *src, pixel *dst, int block_size) { for (int i 0; i dim; i block_size) { for (int j 0; j dim; j block_size) { for (int ii i; ii i block_size; ii 4) { for (int jj j; jj j block_size; jj 4) { pixel p0 src[RIDX(ii, jj, dim)]; pixel p1 src[RIDX(ii, jj1, dim)]; pixel p2 src[RIDX(ii, jj2, dim)]; pixel p3 src[RIDX(ii, jj3, dim)]; dst[RIDX(dim-1-jj, ii, dim)] p0; dst[RIDX(dim-1-(jj1), ii, dim)] p1; dst[RIDX(dim-1-(jj2), ii, dim)] p2; dst[RIDX(dim-1-(jj3), ii, dim)] p3; // ... 依次处理 ii1, ii2, ii3 行 } } } } }这样做的效果有两个一是把像素值先读进局部变量再写减少多次索引计算的重复二是让编译器有机会用寄存器批量处理多个像素而不是每次都去算一遍RIDX。不过要注意如果块尺寸不是展开维度的整数倍需要额外的边界处理。Perflab的测试尺寸通常是固定的32倍数如32、64、128、256、512所以很多提交版本直接不考虑非整数倍情况。为了保险还是建议加上边界分支避免在未知测试上翻车。4.3 指针遍历和restrict两个锦上添花的优化在循环里用数组下标src[Row * dim Row]编译器在-O2下一般能优化成指针增量形式所以手动改成指针不一定有明显收益。但有一个优化值得做给函数参数加上restrict。restrict的作用是告诉编译器“我保证src和dst指向的内存区域没有重叠你可以放心大胆地调整读写顺序、用更激进的指令调度。”在Perflab默认的kernel.c结构里src和dst通常是两个不同的全局数组不会重叠所以加上restrict是安全的。这一项优化通常能带来5%到10%的提升。小心一点如果你的代码里真的让src和dst指向同一块内存restrict会导致未定义行为可能触发难以排查的bug。我建议改之前先确认评测脚本调用你的函数时传入的是独立数组。4.4 实测记录一次完整的优化过程我自己在N512的测试尺寸下做过一组记录展示每一步的效果修改动作运行时间毫秒相对naive的加速比初始naive68.21.00x加32x32分块20.13.39x分块 4x4循环展开15.84.32x分块 展开 restrict14.24.80x把块大小调成64并微调展开13.94.91x从这组数据能看出来绝大部分收益来自分块循环展开和restrict属于锦上添花。如果你优化时间有限先把分块做到位分数不会太低。5. smooth优化实战滑动窗口和边界处理是全部难点smooth这个函数不像rotate那样有明显的“列写风暴”问题它的瓶颈更均匀地分布在计算重复和分支错误上。优化思路也可以说更“算法”一些。5.1 重新审视平滑操作的计算模式朴素的smooth对内部每个像素做9次加法然后除以9。假设N512内部像素大概有26万个每个像素9次加法总共约234万次加法而这些加法里有大量重复——横向相邻的两个像素各自需要的3x3邻域里有6个像素是重复的。这就像你在统计一个月每天的温度每天都把过去30天的气温重新加一遍其实完全可以维护一个滑动窗口每天只加上新的一天、去掉旧的一天。对图像平滑来说这个“滑动”可以分成两步第一步对每一行先计算水平方向的连续3像素和。定义一个中间数组hsum[i][j] src[i][j-1] src[i][j] src[i][j1]RGB每个分量分别算。这一步每个像素只需做2次加法把前一个水平窗口的结果加一个数、减一个数甚至直接加两个数也行。为简单起见可以用直接加法hsum src[i][j-1] src[i][j] src[i][j1]单个像素2次加法。第二步对每一列把垂直方向上相邻三行的hsum加起来就是3x3总和。即total[i][j] hsum[i-1][j] hsum[i][j] hsum[i1][j]然后除以9。这样每个像素总共只需要4次加法水平2次垂直2次加一次除法比最初的9次加法加一次除法节省了一半以上的运算量而且访问模式非常规则第一步按行扫第二步按列扫都能保持很好的Cache局部性。5.2 用几个数组把边界问题化整为零直接实现上面的滑窗时边界会带来烦恼第0行的像素没有上一行第0列的像素没有左一列。如果在内循环里每次判断边界分支预测器会疯掉。我的做法是分而治之先单独处理四个角和四条边然后用一个不包含任何边界判断的主循环处理内部区域。这样主循环里没有任何if分支预测器非常开心。边界代码虽然看起来多一些但只用跑O(N)次对总时间影响很小。关键是主循环的清爽// 以处理内部像素为例i 从 1 到 dim-2, j 从 1 到 dim-2 for (int i 1; i dim-1; i) { for (int j 1; j dim-1; j) { int r 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; dst[RIDX(i, j, dim)].red r / 9; // green 和 blue 同理 } }有同学会问那边界就直接调用naive里的avg函数处理也行但要注意函数调用开销。更好的做法是把边界处理也展开成显式代码虽然啰嗦但性能极稳。5.3 除法不是主要瓶颈但可以打表很多优化贴会说“用移位代替除法”“用乘法模拟除法”。对一个8bit像素的3x3邻域总和最大值是255*92295这个范围非常小。我的建议是直接用一张除9查找表把每个可能的总和映射到对应的商static int div9_table[2296]; void init_div9_table() { for (int i 0; i 2295; i) { div9_table[i] i / 9; } }然后主循环里所有r / 9都变成div9_table[r]。这样一来不仅避免了整数除法还顺手把一个访存操作变成了查表访存。由于表足够小几乎永远命中L1 Cache性能很好。不过要提醒一句不要为了炫技去用(x * 0x1C71C71D) 27这种魔数除法近似。魔数除法在完全整除的时候结果是对的但在某些情况下会有舍入差异。Perflab的评分脚本一般会做像素级比对如果和参考版本结果不一致直接判负。查表法既快又精确这属于“安全的优化”优先采用。5.4 smooth的实测记录我在自己的机器上记录了smooth的优化过程修改动作运行时间毫秒相对naive的加速比初始naive含大量avg函数调用和边界判断82.51.00x去掉avg函数调用主循环直接展开69.31.19x内部区域去掉边界判断60.11.37x引入水平垂直滑窗31.82.59x滑窗 除法查表24.53.37x从这组数据可以明显看出函数调用消除和边界判断消除只是“小头”真正的大头是滑窗带来的计算量下降。这和rotate的分块逻辑一样你解决的是问题的本质而不是表面的指令数量。6. 提交前必查那些让分数“神秘蒸发”的坑代码优化到你觉得差不多了别急着提交。Perflab的评测并不只看代码跑得快不快还看正确性、鲁棒性、有没有违规操作。下面这些坑我或者身边人都踩过列出来帮你避雷。6.1 正确性永远排在性能前面评测脚本里通常包含一个“正确性验证”步骤把你的输出和参考版本输出做逐像素比对。只要有一丁点不一致这一项直接0分。很多人优化到后期为了追求速度会用一些不安全的招数——比如用整数溢出来取巧、少处理某几行、对非内部像素随便给个值。这些操作在本地测试的小尺寸上可能看不出来但评测的“神秘测试”尺寸一变大越界访问可能直接段错误或者像素值错误被Diff抓个正着。我见过最可惜的情况一个同学rotate优化得非常漂亮速度几乎是满分但忘记处理dim不能被块大小整除的情况结果测评脚本里出现一个dim97的神秘测试直接越界整体被判0分。所以块循环的边角一定要处理哪怕它让你的速度降低一点点也远比0分强。6.2 CFLAGS和编译选项别乱动Perflab的评测脚本通常使用固定的编译参数一般是-O2你在本地能做的最多是用-O2对齐评测环境。不要在代码里依赖任何-O3才会生效的优化更不要试图去修改评测脚本的编译参数来自欺欺人。还有一点不要用-ffast-math这种会改变浮点语义的参数。Perflab处理的是整数像素虽然这个参数影响不大但它背后代表的态度是“不尊重评测规则”真要遇到严格检查可能直接判违规。6.3 别依赖未定义行为哪怕它看起来很快C语言标准里有一堆“未定义行为”比如有符号整数溢出、数组越界、指针指向错误内存等。评测机的编译器和本地完全一样但编译优化等级和运行环境可能不同未定义行为的表现可能完全不同。你的代码可能在本地跑得好好的一上评测机就崩溃。我自己的建议是所有优化手段都必须是在“标准C语义不变”的前提下进行。通过数学变换正确减少计算量是没问题的但依赖“恰好这段代码在这台机器上跑得对”是绝对不行的。6.4 过度展开会撑爆指令缓存循环展开是一个经典优化手段但展开因子不是越大越好。我试过把rotate的块内循环展开到8x8结果比分4x4慢了不少。原因很简单展开因子越大生成的机器码越多指令缓存i-cache放不下反而导致取指变慢。这是一个很好的“做减法”的例子。性能优化不是一味地加技巧很多时候需要你不断做实验找到一个平衡点。我建议每次修改只改变一个变量然后记录分数。比如先只改块大小确定最佳值后再加入循环展开再确定展开因子最后再加restrict。6.5 提交前的固定检查流程我在最后一次提交前给自己定了一个检查流程每次都能用上跑一遍make clean make driver确认代码能在干净的编译环境下通过。跑一遍./driver确认所有测试尺寸都通过正确性验证。连续跑三次完整的评测脚本确认分数稳定如果波动超过5分说明环境不稳定先锁频再测。检查是否有printf、assert等调试代码留在最终提交版本里。这些代码不仅拖慢速度还可能让评分脚本以为你作弊。6.6 一个容易被忽略的“扬长避短”技巧另外Perflab的评分规则大致可以理解为“你越快分数越高”但不同的测试尺寸权重往往不同。如果你时间有限优先优化N比较大比如256和512的测试尺寸。因为这些尺寸通常权重更高而且对访存优化更敏感同样的优化手段在N512上带来的收益远大于N32。在有多个版本代码时也可以用一些“土办法”来扬长避短比如你的分块大小对N256特别好对N64稍差那就在函数里加一个if (dim 256) { ... } else { ... }的分支针对不同尺寸走不同优化版本。这种做法不算作弊因为它还是没有改评测逻辑只是更精细地匹配了不同工作负载的特征。不过要注意分支判断本身也有开销一般只有在差异足够大的时候才值得这么做。做完整个Perflab我最大的感受是性能优化不是“凭感觉堆技巧”而是“先理解机器怎么访问数据再让代码顺着硬件的习惯走”。你选多大块、展开几层、怎么处理边界这些看似是经验问题本质都对应着Cache容量、指令数、分支预测这些底层事实。最后再分享一个我个人的经验技巧每次修改只改一个变量并且把时间记录下来。你会发现最高效的那几分往往是靠“删代码”删出来的比如删掉一个没必要的边界判断删掉一层多余的循环控制带来的提升比增加一个花哨的优化更明显。这个实验做完后面再看多线程优化、SIMD优化相关的内容你会觉得顺畅很多——因为Perflab帮你把“以数据为中心的思考方式”练扎实了。