当前位置： 首页 > news >正文

CSAPP Lab05——Performance Lab完成思路

news 来源：原创 2024/9/29 11:23:37

You sing me your melody and I feel so please

I want you to want me to keep your dream

Together we'll run wild by a summer symphony

This is what we enjoyed not a fantasy

——Young For You

完整代码见：CSAPP/perflab-handout at main · SnowLegend-star/CSAPP (github.com)

总的来说，这次的lab难度比上个要低很多。而且两者的本质又十分类似，故完成本lab的时间算是最近几个lab里面最短的。

Part A: Rotate

Part A是要求把一个矩阵src逆时针旋转90°后存储到矩阵dst里面，有趣的是这次的矩阵都是用以一维的形式存储的，所以操作起来要比二维更绕一点。有了上次cache lab的经验，我上来就打算用到分块加上循环展开的思路。

这次由于被测试的矩阵大小从32×32到1024×1024，所以再笼统地把分块定为8×8肯定是不妥当的。同时本次lab没有给出cache的大小，所以我测试了8×8、16×16、32×32等不同尺度的分块，最终发现32×32的分块尺度是最佳的。找到分块大小后，就可以着手循环展开了。我一下子定义了32个变量，先把src矩阵一个块内一整行的元素赋值给变量，再用变量给dst赋值过去。结果效率反而还变低了，搞得我有点一头雾水。几经思考发现我定义32个变量的举动确实有点呆，书上定义变量acc是为了减少访问内存的次数，因为这个变量acc是被存在寄存器上的。我定义这么多变量首先是以为用变量作为中介实现src给dst的赋值会减少访问内存的次数，实则不然，这样反而增加了访问时间，本来src可以直接赋值给dst，我再加入个第三者无异于画蛇添足。其次，计算机的通用寄存器是一定的，变量个数如果超过可以存变量的寄存器个数，那剩下的变量就会存储在内存中，导致访问内存的次数再次增长。

最终的后果是定义32个变量的负面效果大于分块带来的正面效果，是程序的运行速度反而变慢了。效果如下图：

后来我又想到了个优化的方法，原函数在计算数组下标时每次都要调用一次“RIDX()”函数，要是只在第一次调用这个函数计算当前访问的元素下标Xi ，后序直接在Xi 的基础上进行加法运算，那效果如何呢？

事实证明这方法有点东西，但是不多。因为“RIDX()”函数内部的运行时间与数组的规模n无关，所以调用这个函数的时间是个很小的常数。

 

最后一个提升的方法比较隐晦，我也是参考了其他人的想法——写不命中的开销比读不命中的代价更大，因此得保证对dst数组的访问是按序递增的，而对src数组的访问可以跳着来。通俗地解释就是访问了dst[0][1]后接下来访问dst[0][2]效率比较高，而不是原函数的访问了dst[1][0]后再访问dst[2][0]。可以看到效果确实大幅度提升了。 

 

那么最后的优化方法就是：分块+循环展开+减少函数调用+写优先了

 

不过可疑的是，我刚才又测试了下16×16的分块效果，居然要比32×32的要好一点点，真是奇怪。通过和网上的解决方法对比，可以发现效果基本差不多。

 

 

 这里就只提供效果最好的一份供大家参考了

char rotate_descr_bolck_loopUnroll_codeMove_wrtFirst[] = "rotate: 分块+循环展开+采用写优先";
void rotate_32X32_loopUnroll_codeMove_wrtFirst(int dim, pixel *src, pixel *dst){int i,j,k;int bsize=32;for(i=0;i<dim;i+=bsize)for(j=0;j<dim;j+=bsize){for(k=0;k<bsize;k++){dst[RIDX(dim-1-(i+k), j+0, dim)] = src[RIDX(j+0, i + k, dim)];dst[RIDX(dim-1-(i+k), j+1, dim)] = src[RIDX(j+1, i + k, dim)];dst[RIDX(dim-1-(i+k), j+2, dim)] = src[RIDX(j+2, i + k, dim)];dst[RIDX(dim-1-(i+k), j+3, dim)] = src[RIDX(j+3, i + k, dim)];dst[RIDX(dim-1-(i+k), j+4, dim)] = src[RIDX(j+4, i + k, dim)];dst[RIDX(dim-1-(i+k), j+5, dim)] = src[RIDX(j+5, i + k, dim)];dst[RIDX(dim-1-(i+k), j+6, dim)] = src[RIDX(j+6, i + k, dim)];dst[RIDX(dim-1-(i+k), j+7, dim)] = src[RIDX(j+7, i + k, dim)];dst[RIDX(dim-1-(i+k), j+8, dim)] = src[RIDX(j+8, i + k, dim)];dst[RIDX(dim-1-(i+k), j+9, dim)] = src[RIDX(j+9, i + k, dim)];dst[RIDX(dim-1-(i+k), j+10, dim)] = src[RIDX(j+10, i + k, dim)];dst[RIDX(dim-1-(i+k), j+11, dim)] = src[RIDX(j+11, i + k, dim)];dst[RIDX(dim-1-(i+k), j+12, dim)] = src[RIDX(j+12, i + k, dim)];dst[RIDX(dim-1-(i+k), j+13, dim)] = src[RIDX(j+13, i + k, dim)];dst[RIDX(dim-1-(i+k), j+14, dim)] = src[RIDX(j+14, i + k, dim)];dst[RIDX(dim-1-(i+k), j+15, dim)] = src[RIDX(j+15, i + k, dim)];dst[RIDX(dim-1-(i+k), j+16, dim)] = src[RIDX(j+16, i + k, dim)];dst[RIDX(dim-1-(i+k), j+17, dim)] = src[RIDX(j+17, i + k, dim)];dst[RIDX(dim-1-(i+k), j+18, dim)] = src[RIDX(j+18, i + k, dim)];dst[RIDX(dim-1-(i+k), j+19, dim)] = src[RIDX(j+19, i + k, dim)];dst[RIDX(dim-1-(i+k), j+20, dim)] = src[RIDX(j+20, i + k, dim)];dst[RIDX(dim-1-(i+k), j+21, dim)] = src[RIDX(j+21, i + k, dim)];dst[RIDX(dim-1-(i+k), j+22, dim)] = src[RIDX(j+22, i + k, dim)];dst[RIDX(dim-1-(i+k), j+23, dim)] = src[RIDX(j+23, i + k, dim)];dst[RIDX(dim-1-(i+k), j+24, dim)] = src[RIDX(j+24, i + k, dim)];dst[RIDX(dim-1-(i+k), j+25, dim)] = src[RIDX(j+25, i + k, dim)];dst[RIDX(dim-1-(i+k), j+26, dim)] = src[RIDX(j+26, i + k, dim)];dst[RIDX(dim-1-(i+k), j+27, dim)] = src[RIDX(j+27, i + k, dim)];dst[RIDX(dim-1-(i+k), j+28, dim)] = src[RIDX(j+28, i + k, dim)];dst[RIDX(dim-1-(i+k), j+29, dim)] = src[RIDX(j+29, i + k, dim)];dst[RIDX(dim-1-(i+k), j+30, dim)] = src[RIDX(j+30, i + k, dim)];dst[RIDX(dim-1-(i+k), j+31, dim)] = src[RIDX(j+31, i + k, dim)];}   }
}

 

#define COPY(d,s) *(d)=*(s)char rotate_descr_bolck_loopUnroll_copyOL[] = "rotate: 分块+循环展开(网上搬来的)";
void rotate_32X32_loopUnroll_copyOL(int dim, pixel *src, pixel *dst){
int i,j;for(i=0;i<dim;i+=32)//32路循环展开，32个像素依次存储for(j=dim-1;j>=0;j-=1){       pixel*dptr=dst+RIDX(dim-1-j,i,dim);pixel*sptr=src+RIDX(i,j,dim);//进行复制操作COPY(dptr,sptr);sptr+=dim;COPY(dptr+1,sptr);sptr+=dim;COPY(dptr+2,sptr);sptr+=dim;COPY(dptr+3,sptr);sptr+=dim;COPY(dptr+4,sptr);sptr+=dim;COPY(dptr+5,sptr);sptr+=dim;COPY(dptr+6,sptr);sptr+=dim;COPY(dptr+7,sptr);sptr+=dim;COPY(dptr+8,sptr);sptr+=dim;COPY(dptr+9,sptr);sptr+=dim;COPY(dptr+10,sptr);sptr+=dim;COPY(dptr+11,sptr);sptr+=dim;COPY(dptr+12,sptr);sptr+=dim;COPY(dptr+13,sptr);sptr+=dim;COPY(dptr+14,sptr);sptr+=dim;COPY(dptr+15,sptr);sptr+=dim;COPY(dptr+16,sptr);sptr+=dim;COPY(dptr+17,sptr);sptr+=dim;COPY(dptr+18,sptr);sptr+=dim;COPY(dptr+19,sptr);sptr+=dim;COPY(dptr+20,sptr);sptr+=dim;COPY(dptr+21,sptr);sptr+=dim;COPY(dptr+22,sptr);sptr+=dim;COPY(dptr+23,sptr);sptr+=dim;COPY(dptr+24,sptr);sptr+=dim;COPY(dptr+25,sptr);sptr+=dim;COPY(dptr+26,sptr);sptr+=dim;COPY(dptr+27,sptr);sptr+=dim;COPY(dptr+28,sptr);sptr+=dim;COPY(dptr+29,sptr);sptr+=dim;COPY(dptr+30,sptr);sptr+=dim;COPY(dptr+31,sptr);}
}

 

Part B: Smooth

Part B的avg函数一眼望去全是漏洞：

  • 在循环体内调用min、max函数
  • 重复计算了许多元素和，导致效率低
  • avg函数包含好几个函数调用，可能在调用函数的同时也会浪费不少时间

为了提升代码的运行效率，考虑把所有的运算步骤写进一个函数，牺牲代码可读性来换取效率。代码大致分为三大块：四个顶点，四条边上的点和内部的点。有点要吐槽的是这个lab用的是c语言，导致无法对“+”进行重载，每次都要把c++一行代码可以解决的分成三行来写，分别处理blue、green、red。偏偏点情况还有三类，直接汗流浃背了。

为了解决原函数存在的计算冗余问题，我的想法是利用下简单的dp思想：

首先用一个大小为(dim+2)×(dim+2)的二维矩阵C把src包起来，矩阵C四条边上的元素全部置0。这样我们只用处理C[1][1]~C[dim][dim]这个区间里面的元素，且所有元素的计算方法都是算九个点的和再平均，不用考虑三类特殊的点。

同时用变量tmp存储C[i][j]周围九个点的和，计算C[i][j+1]周围九个点的和时，就可以用tmp-C[i][j-2]那列三个元素和+C[i][j+1]三个元素和得到，有效利用了六个点的计算和。而每一行第一个元素C[i][1]的周围九个点的和也可以通过c[i-1][1]的九点和更快地得到。

由于在VS会有结构体的成员提示，而VSCode只能自己把结构体对应的成员打上去，于是我就打算在VS上完成。写的差不多的时候发现我把src、dst全都当做二维数组来写了，tmd，真是功亏一篑。遂道心受损，直接写了份没用dp思想的代码凑合过了。

虽然smooth用不到分块，但是运行效果还是有巨大的提升。

 

 

 

/** smooth - Your current working version of smooth. * IMPORTANT: This is the version you will be graded on*/
char smooth_descr[] = "smooth: Current working version";
void smooth(int dim, pixel *src, pixel *dst)
{int i,j;int dim0=dim;int dim1=dim-1;int dim2=dim-2;pixel *P1, *P2, *P3;pixel *dst1;P1=src;P2=P1+dim0;//左上角像素处理dst->red=(P1->red+(P1+1)->red+P2->red+(P2+1)->red)>>2;dst->green=(P1->green+(P1+1)->green+P2->green+(P2+1)->green)>>2;dst->blue=(P1->blue+(P1+1)->blue+P2->blue+(P2+1)->blue)>>2;dst++;//上边界处理for(i=1;i<dim1;i++){dst->red=(P1->red+(P1+1)->red+(P1+2)->red+P2->red+(P2+1)->red+(P2+2)->red)/6;dst->green=(P1->green+(P1+1)->green+(P1+2)->green+P2->green+(P2+1)->green+(P2+2)->green)/6;dst->blue=(P1->blue+(P1+1)->blue+(P1+2)->blue+P2->blue+(P2+1)->blue+(P2+2)->blue)/6;dst++;P1++;P2++;}//右上角像素处理dst->red=(P1->red+(P1+1)->red+P2->red+(P2+1)->red)>>2;dst->green=(P1->green+(P1+1)->green+P2->green+(P2+1)->green)>>2;dst->blue=(P1->blue+(P1+1)->blue+P2->blue+(P2+1)->blue)>>2;dst++;P1=src;P2=P1+dim0;P3=P2+dim0;//左边界处理for(i=1;i<dim1;i++){dst->red=(P1->red+(P1+1)->red+P2->red+(P2+1)->red+P3->red+(P3+1)->red)/6;dst->green=(P1->green+(P1+1)->green+P2->green+(P2+1)->green+P3->green+(P3+ 1)->green)/6;dst->blue=(P1->blue+(P1+1)->blue+P2->blue+(P2+1)->blue+P3->blue+(P3+1)->blue)/6;dst++;dst1=dst+1;//中间主体部分处理for(j=1;j<dim2;j+=2){        //同时处理两个像素dst->red=(P1->red+(P1+1)->red+(P1+2)->red+P2->red+(P2+1)->red+(P2+2)->red+P3->red+(P3+1)->red+(P3+2)->red)/9;dst->green=(P1->green+(P1+1)->green+(P1+2)->green+P2->green+(P2+1)->green+(P2+2)->green+P3->green+(P3+1)->green+(P3+2)->green)/9;dst->blue=(P1->blue+(P1+1)->blue+(P1+2)->blue+P2->blue+(P2+1)->blue+(P2+2)->blue+P3->blue+(P3+1)->blue+(P3+2)->blue)/9;dst1->red=((P1+3)->red+(P1+1)->red+(P1+2)->red+(P2+3)->red+(P2+1)->red+(P2+2)->red+(P3+3)->red+(P3+1)->red+(P3+2)->red)/9;dst1->green=((P1+3)->green+(P1+1)->green+(P1+2)->green+(P2+3)->green+(P2+1)->green+(P2+2)->green+(P3+3)->green+(P3+1)->green+(P3+2)->green)/9;dst1->blue=((P1+3)->blue+(P1+1)->blue+(P1+2)->blue+(P2+3)->blue+(P2+1)->blue+(P2+2)->blue+(P3+3)->blue+(P3+1)->blue+(P3+2)->blue)/9;dst+=2;dst1+=2;P1+=2;P2+=2;P3+=2;}for(;j<dim1;j++){         dst->red=(P1->red+(P1+1)->red+(P1+2)->red+P2->red+(P2+1)->red+(P2+2)->red+P3->red+(P3+1)->red+(P3+2)->red)/9;dst->green=(P1->green+(P1+1)->green+(P1+2)->green+P2->green+(P2+1)->green+(P2+2)->green+P3->green+(P3+1)->green+(P3+2)->green)/9;dst->blue=(P1->blue+(P1+1)->blue+(P1+2)->blue+P2->blue+(P2+1)->blue+(P2+2)->blue+P3->blue+(P3+1)->blue+(P3+2)->blue)/9;dst++;P1++;P2++;P3++;}//右侧边界处理dst->red=(P1->red+(P1+1)->red+P2->red+(P2+1)->red+P3->red+(P3+1)->red)/6;dst->green=(P1->green+(P1+1)->green+P2->green+(P2+1)->green+P3->green+(P3+1)->green)/6;dst->blue=(P1->blue+(P1+1)->blue+P2->blue+(P2+1)->blue+P3->blue+(P3+1)->blue)/6;dst++;P1+=2;P2+=2;P3+=2;} //右下角处理dst->red=(P1->red+(P1+1)->red+P2->red+(P2+1)->red)>>2;dst->green=(P1->green+(P1+1)->green+P2->green+(P2+1)->green)>>2;dst->blue=(P1->blue+(P1+1)->blue+P2->blue+(P2+1)->blue)>>2;dst++;//下边界处理for(i=1;i<dim1;i++){dst->red=(P1->red+(P1+1)->red+(P1+2)->red+P2->red+(P2+1)->red+(P2+2)->red)/6;dst->green=(P1->green+(P1+1)->green+(P1+2)->green+P2->green+(P2+1)->green+(P2+2)->green)/6;dst->blue=(P1->blue+(P1+1)->blue+(P1+2)->blue+P2->blue+(P2+1)->blue+(P2+2)->blue)/6;dst++;P1++;P2++;} //右下角像素处理dst->red=(P1->red+(P1+1)->red+P2->red+(P2+1)->red)>>2;dst->green=(P1->green+(P1+1)->green+P2->green+(P2+1)->green)>>2;dst->blue=(P1->blue+(P1+1)->blue+P2->blue+(P2+1)->blue)>>2;}

总的来说这次的lab确实轻松，思维难度也没前面的那么高，就是有点麻烦，得对比各种改进的效率。一言蔽之，还算是一个比较愉快的思维交锋。 

相关文章：

  • GPT-4o：重塑人机交互的未来
  • 上位机图像处理和嵌入式模块部署（f407 mcu中fatfs中间件使用）
  • npm安装依赖报错npm ERR! code ENOTFOUNDnpm ERR! syscall getaddrinfo
  • static修饰变量和函数
  • Ubuntu中安装和配置SSH的完全指南
  • LeetCode 算法：三数之和c++
  • Java中的泛型类型参数详解
  • 代碼隨想录 day22|day23
  • 7EPhone云手机各功能详解
  • Java 面试题：Java 的动态代理是基于什么原理？
  • js文件 .mjs和.umd.js结尾的文件的区别
  • 【光伏预测】基于BP神经网络实现光伏发电功率预测附Matlab代码
  • Spring Cloud Gateway 集成 Nacos、Knife4j
  • 计算机网络7——网络安全3 互联网使用的安全协议
  • 网关（Gateway）- 自定义过滤器工厂
  • 【干货分享】SpringCloud微服务架构分布式组件如何共享session对象
  • 08.Android之View事件问题
  • 4. 路由到控制器 - Laravel从零开始教程
  • create-react-app做的留言板
  • laravel 用artisan创建自己的模板
  • 纯 javascript 半自动式下滑一定高度，导航栏固定
  • 缓存与缓冲
  • 马上搞懂 GeoJSON
  • 模仿 Go Sort 排序接口实现的自定义排序
  • 前端代码风格自动化系列（二）之Commitlint
  • 一个6年java程序员的工作感悟，写给还在迷茫的你
  • 译米田引理
  • media数据库操作，可以进行增删改查，实现回收站，隐私照片功能 SharedPreferences存储地址：
  • 从如何停掉 Promise 链说起
  • 翻译 | The Principles of OOD 面向对象设计原则
  • ​MySQL主从复制一致性检测
  • ​第20课 在Android Native开发中加入新的C++类
  • # Redis 入门到精通（七）-- redis 删除策略
  • #Datawhale AI夏令营第4期#AIGC文生图方向复盘
  • #NOIP 2014# day.1 T3 飞扬的小鸟 bird
  • #进阶：轻量级ORM框架Dapper的使用教程与原理详解
  • $.ajax()
  • $LayoutParams cannot be cast to android.widget.RelativeLayout$LayoutParams
  • ()、[]、{}、(())、[[]]命令替换
  • (1/2) 为了理解 UWP 的启动流程，我从零开始创建了一个 UWP 程序
  • （13）：Silverlight 2 数据与通信之WebRequest
  • (2/2) 为了理解 UWP 的启动流程，我从零开始创建了一个 UWP 程序
  • （SERIES12）DM性能优化
  • (紀錄)[ASP.NET MVC][jQuery]-2 純手工打造屬於自己的 jQuery GridView (含完整程式碼下載)...
  • (一)kafka实战——kafka源码编译启动
  • (转)Oracle 9i 数据库设计指引全集(1)
  • .gitignore文件—git忽略文件
  • .NET CORE使用Redis分布式锁续命(续期)问题
  • .NET DataGridView数据绑定说明
  • .net oracle 连接超时_Mysql连接数据库异常汇总【必收藏】
  • .NET Standard / dotnet-core / net472 —— .NET 究竟应该如何大小写？
  • .net web项目 调用webService
  • .Net 高效开发之不可错过的实用工具
  • .Net 基于MiniExcel的导入功能接口示例
  • .NET/C# 使窗口永不获得焦点