程序速度优化案例分析

程序速度优化案例分析2006-3-27软件DSC简介凸阵式扇形扫查的回波信号是极坐标形式的。图示出这种极坐标形式的采样点与光栅扫描显示像素间的位置关系。软件DSC简介对于每一个象素点，需要找到与其相邻的四个采样点进行线性插值，得到该点灰度值。软件DSC简介ar1r2x1x4x6x2x3x5x7xyoDSC要解决的两个主要问题是：坐标变换及插补处理。首先要将屏幕上每个象素点(DisX,DisY)转化为以探头圆心为原点的直角坐标系中的坐标(X,Y)，再将(X,Y)转换为极坐标(R,θ)，然后求得对应扫描线线号(Col,Row)。提高代码执行效率的准备工作建立起时间测试框架以递增方式做测试打开编译器的优化选项打开编译器的优化选项为了便于调试，编译器在Debug下一般对代码不作或只作很少的优化，所以依据Debug版的测试结果来作为效率改进的依据有时可能意义并不大，编译器可能已经作了你想作的优化。软件DSC速度改进过程单B图像（35c50ha探头，深度5.17），速度大约为13.7帧/秒，显然不具备实时性。(测试所用机器配置如下：cpu:奔腾四2.8G，L1datacache8KBytes，L2cache512KBytes。)95％以上时间花费在此UConvexDSC::DSC()for(DisY=0;DisYm_usDisplayHeight;DisY++){将DisY变为以探头圆心为原点的坐标Yfor(DisX=0;DisXm_usDisplayWidth;DisX++){将DisX变为以探头圆心为原点的坐标X计算线号Col，行号RowIf(点不在扫描线以内){灰度值设为0;continue;}根据插值系数和线号、行号、插值系数求该点象素值}}对于屏幕上每个象素点来说，对于给定探头，如果深度、放大系数、偏移系数固定，每个点对应极坐标位置和插值系数是固定的。如果将第一次的计算结果存储到表格中，以后计算时不需要重新计算每个点的坐标位置和插值系数，而使用表格中存储的数据，直接进行插值运算。不需要每帧都进行计算以空间效率换取时间效率经过这一步优化，耗时从72ms减少到8.8ms，达到113.9帧/秒。循环内判断应当移到循环外部将循环体的逻辑判断移到循环体外通过这一修改，耗时从8.8ms减少到5.5ms，达到180.8帧/秒。存在冗余计算存在冗余计算循环体内工作量最小化，减少冗余的操作这一步改进使得耗时从5.5ms减少3.6ms，达到274帧/秒。for(DisY=0;DisYm_usDisplayHeight;DisY++){将DisY变为以探头圆心为原点的坐标Yfor(DisX=0;DisXm_usDisplayWidth;DisX++){将DisX变为以探头圆心为原点的坐标X从表格中获取Col值If(点不在扫描线以内){灰度值设为0;continue;}从表格中获取Row,insert0,insert1,insert2,insert3值根据插值系数和线号、行号、插值系数求该点象素值}}CPU的cache对性能的影响内存CPU芯片L1高速缓存(SRAM)寄存器堆ALU总线接口L2高速缓存(SRAM)高速缓存总线I/O桥存储器总线系统总线位于CPU芯片上的L1高速缓存的访问速度几乎和访问寄存器堆一样快，CPU可以在一个时钟周期内访问它们。L2高速缓存是通过一条特殊的总线连接到处理器的，访问L2的时间开销要比访问L1大5倍。而通常CPU需要几十或几百个时钟周期才能访问到内存。存储器层次结构寄存器L1高速缓存(SRAM)L2高速缓存(SRAM)主存储器(DRAM)L0L1L2L3本地二级存储(本地磁盘)远程二级存储(分布式文件系统、Web服务器)L4L5分层结构的中心思想是，对于每个k，位于k层的更快更小的存储设备作为位于k+1层的更大更慢的存储设备的缓存。存储器层次结构中的基本缓存原理431494765032181110912151413第K层：第K＋1层：数据以块为大小为传输单元在层与层之间拷贝L0和L1层之间传送通常使用1个字的块，L1和L2之间以及L2和L3之间的传送通常使用4~8个字的块。局部性原理时间局部性在一个具有良好时间局部性的程序中，被引用过一次的变量很可能在不远的将来再多次被引用(重复引用一个变量)。空间局部性在一个具有良好空间局部性的程序中，如果一个存储器位置被引用了一次，那么程序很可能在不远的将来引用附近的一个存储器位置。局部性原理对速度的影响for(disy=0;disym_usDisplayHeight;disy++){for(disx=0;disxm_usDisplayWidth;disx++){访问Insert0[disy][disx]}}for(disx=0;disxm_usDisplayWidth;disx++){for(disy=0;disym_usDisplayHeight;disy++){访问Insert0[disy][disx]}}测得软件DSC耗时增大了5.07ms，速度为98.0帧/秒，速度降低65%！局部性原理对速度的影响C语言以行优先顺序存储数组，二维数组在内存中存放顺序如下：如果高速缓存和内存之间传送数据块大小是4个字，则原来的代码缓存命中率为75%，而调整后的代码缓存命中率为0。Cpu每次读数据时都必须到内存中去读，导致效率大幅度降低。…...[0][0][0][1][0][N]…...[1][0][1][1][1][N]…...[M][0][M][1][M][N]×××√√√√数据存储方式对效率的影响intPixelRow_I[IMG_HEIGHT][IMG_WIDTH];intPixelCol_I[IMG_HEIGHT][IMG_WIDTH];intInsert0[IMG_HEIGHT][IMG_WIDTH];intInsert1[IMG_HEIGHT][IMG_WIDTH];intInsert2[IMG_HEIGHT][IMG_WIDTH];intInsert3[IMG_HEIGHT][IMG_WIDTH];structDSC_PARAM{intPixelRow_I;intPixelCol_I;intInsert0;intInsert1;intInsert2;intInsert3;};DSC_PARAMg_DscParam[IMG_HEIGHT][IMG_WIDTH];修改后耗时减少0.0486ms，速度变为277.7帧/秒，速度只提高了1.38%。原因分析cacheInsert0[0]Insert1[0]Insert2[0]Insert3[0]Col[0]Row[0]假设L2cache每次从内存中读入6个字的数据，在读某个象素的参数时没有命中，将该参数所在数据块一起读入到cache中，如上图所示。之后对row、insert0~insert3的访问都会命中，命中率为5/6。原因分析cacheInsert0[0]Insert1[0]Insert2[0]Insert3[0]Col[0]Row[0]Insert0[1]Insert1[1]Insert2[1]Insert3[1]Col[1]Row[1]Insert0[2]Insert1[2]Insert2[2]Insert3[2]Col[2]Row[2]Insert0[3]Insert1[3]Insert2[3]Insert3[3]Col[3]Row[3]Insert0[4]Insert1[4]Insert2[4]Insert3[4]Col[4]Row[4]Insert0[5]Insert1[5]Insert2[5]Insert3[5]Col[5]Row[5]而原来的存储方式在读col[0]时没有命中，会将col[0]~col[5]内容读入cache中，对于Row[0]等也是如此，虽然在读第0点参数时命中率为0，但后面的5个点的参数已经读入到cache中，命中率同样为5/6。因而速度变化并不显著。代码耗时比例for(disy=0;disym_usDisplayHeight;disy++){for(disx=0;disxm_usDisplayWidth;disx++){if(g_DscParam[disy][disx].PixelCol_Imin_col){gray[disposi+disx]=0;continue;}//进行插值adr1=m_pImgBuffer+g_DscParam[disy][disx].PixelCol_I*m_usImageHeight+g_DscParam[disy][disx].PixelRow_I;adr2=adr1+m_usImageHeight;tmp_gray=(BYTE)(((*(adr1))*g_DscParam[disy][disx].Insert0+(*(adr2))*g_DscParam[disy][disx].Insert1+(*(adr1+1))*g_DscParam[disy][disx].Insert2+(*(adr2+1))*g_DscParam[disy][disx].Insert3)7);//查灰度表进行后处理gray[disposi+disx]=m_pImgPara-pB_Gray_Table[2*tmp_gray];}disposi+=IMG_WIDTH;}插值和后处理耗时46％双重循环耗时8％比较这一步耗时39%耗时不在比较和赋值操作，而在于从内存中读取数据通过提高空间效率提高时间效率调整完后的DSC_PARAM结构所占内存空间只有原来的1/3，通过测试，耗时从3.6ms减少到3.1ms，运算速度变为317帧/秒，速度提高13%。这一步修改通过减少数组的大小，减少了cpu从访问内存的次数，提高了cache的利用率。测试数据表格测试所用机器配置cpu:奔腾四2.8G，L1datacache8KBytes，L2cache512KBytes，512M内存。测试单B图像，35c50ha探头，深度为5.17。原始运算速度为15.7帧/秒。耗时（ms/帧）软件DSC速度(帧/秒)速度提高百分比优化之前7214--------以空间换时间8.8113.9625%循环体内判断移到循环外5.5180.859%梳理流程，减少冗余3.627452%减小保存插值系数数组大小3.131713%不同pc上的比较测试CPUCache(KBytes)计算速度(帧/秒)相对速度奔腾四2.8G5122741奔腾四3.0G10243531.29奔腾四3.5G10244131.51奔腾四3.75G10244551.66对于奔四3.0G～3.75G，cache大小一样，计算速度和cpu时钟频率基本呈线性关系。对于奔四3.0G和奔四2.8G，cpu时钟频率增大了1.07倍，而速度却增大了1.29倍，原因在于cache增大了一倍。提高代码执行效率的一些原则1.不要一味地追求程序的效率，应当在满足正确性、可靠性、健壮性、可读性等质量因素的前提下，设法提高程序的效率。2.局部效率应为全局效率服务，不能因为提高局部效率而对全局效率造成影响。3.不要一味追求紧凑的代码，因为紧凑的代码并不代表高效的机器码。提高代码执行效率的一些原则4.先优化算法，再优化执行代码。比如计算从1到100的和，使用以下代码intsum=0;for(inti=1;i=100;i++)sum+=i;需要执行200次加法指令，100次比较指令，100次跳转指令。而如果使用高斯公式sum=(1+100)*100/2;只需要执行1次加法，1次乘法，1次移位。5.找到影响代码速度的瓶颈。在优化程序的效率时，应当先找出限制效率的“瓶颈”，不要在无关紧要之处优化。提高代码执行效率的一些原则6.有时候时间效率和空间效率可能对立，此时应当分析那个更重要，作出适当的折衷。7.如果循环体内存在逻辑判断，并且循环次数很大，宜将逻辑判断移到循环体的外面。8.循环体内工作量最小化，减少冗余的操作提高代码执行效