算法合集之《论程序底层优化的一些方法与技巧》.ppt
论程序底层优化的一些方法与技巧论程序底层优化的一些方法与技巧 成都七中成都七中 骆可强骆可强T(nT(n)=)=O(O(f(nf(n)效率效率效率效率时间效率时间效率时间效率时间效率=+=+空间效率空间效率空间效率空间效率算法！算法！算法！算法！T(nT(n)f(nf(n)C CC1C2C1C2算法算法算法算法算法算法底层优化底层优化底层优化底层优化底层优化底层优化?/最初版程序int get_max(int*a,int l)int mx=0,i;for(i=0;imx)mx=ai;return mx;/第一次优化int get_max(int*a,int l)int mx=0,*ed=a+l;while(a!=ed)if(*amx)mx=*a;a+;return mx;/第二次优化int get_max(int*a,int l)assert(l%8=0);#define D(x)mx#x=0 int D(0),D(1),D(2),D(3),D(4),D(5),D(6),D(7),*ed=a+l;#define CMP(x)if(*(a+x)mx#x)mx#x=*(a+x);while(a!=ed)CMP(0);CMP(1);CMP(2);CMP(3);CMP(4);CMP(5);CMP(6);CMP(7);a+=8;#define CC(x1,x2)if(mx#x1mx#x2)mx#x2=mx#x1;CC(1,0);CC(3,2);CC(5,4);CC(7,6);CC(2,0);CC(6,4);CC(4,0);return mx0;/第三次优化int get_max(int*a,int l)int ret;_asm_ _volatile_(movl$0,%eaxnt .p2align 4,15n LP1:nt cmpl -4(%1,%2,4),%eaxnt jge EDnt movl -4(%1,%2,4),%eaxn ED:nt /loop LP1nt decl%2nt jnz LP1nt movl%eax,%0nt :=m(ret):r(a),c(l):%eax);return ret;/第四个优化int get_max(int*a,int l)assert(l%2=0);int ret;_asm_ _volatile_(movl$0,%eaxnt movl$0,%edxnt .p2align 4,15n LP2:nt cmpl (%1),%eaxnt jge ED2nt movl (%1),%eaxn ED2:nt cmpl 4(%1),%edxnt jge ED3nt movl 4(%1),%edxn ED3:nt addl$8,%1nt subl$2,%2nt jnz LP2nt cmpl%edx,%eaxnt cmovll%edx,%eaxnt movl%eax,%0nt :=m(ret):r(a),r(l):%eax,%edx);return ret;/第五次优化int get_max(int*a,int l)assert(l%4=0);assert(sse2);int ret,tmp4;_asm_ _volatile_(txorps%xmm0,%xmm0n LP3:n tmovdqa%xmm0,%xmm1n tpcmpgtd (%1),%xmm1n tandps%xmm1,%xmm0n tandnps (%1),%xmm1n torps%xmm1,%xmm0n taddl$16,%1n tsubl$4,%2n tjnz LP3n tmovdqu%xmm0,(%3)n tmovl (%3),%eaxn tcmpl 4(%3),%eaxn tcmovll 4(%3),%eaxn tcmpl 8(%3),%eaxn tcmovll 8(%3),%eaxn tcmpl 12(%3),%eaxn tcmovll 12(%3),%eaxn tmovl%eax,%0n :=m(ret):r(a),r(l),r(tmp):%eax);return ret;/第六次优化 int get_max(int*a,int l)assert(l%4=0);assert(sse4);int ret,tmp4;_asm_ _volatile_(txorps%xmm0,%xmm0n LP4:n tpmaxsd (%1),%xmm0n taddl$16,%1n tsubl$4,%2n tjnz LP4n tmovdqu%xmm0,(%3)n tmovl (%3),%eaxn tcmpl 4(%3),%eaxn tcmovll 4(%3),%eaxn tcmpl 8(%3),%eaxn tcmovll 8(%3),%eaxn tcmpl 12(%3),%eaxn tcmovll 12(%3),%eaxn tmovl%eax,%0n :=m(ret):r(a),r(l),r(tmp):%eax);return ret;一个简单的例子一个简单的例子编号编号编号编号平均平均平均平均时钟周期时钟周期时钟周期时钟周期优化优化优化优化(%)(%)优化方法优化方法优化方法优化方法7.53 6.60 12%3.48 54%2.13 72%1.74 77%1.59 80%？优化寻址多路求值内嵌汇编内嵌汇编+多路求值SIMDSSE4:求最大值求最大值论文中所覆盖的主题论文中所覆盖的主题CPUCPU指令运行的效率表现指令运行的效率表现指令运行的效率表现指令运行的效率表现CPUCPU优化特性优化特性优化特性优化特性数值运算的优化数值运算的优化数值运算的优化数值运算的优化高维数组的使用高维数组的使用高维数组的使用高维数组的使用位运算技巧位运算技巧位运算技巧位运算技巧除法除法除法除法高精度高精度高精度高精度乘法乘法乘法乘法缓存机制缓存机制缓存机制缓存机制乱序执行乱序执行乱序执行乱序执行分支预测分支预测分支预测分支预测位压缩位压缩位压缩位压缩消除分支消除分支消除分支消除分支打包统计打包统计打包统计打包统计寻址寻址寻址寻址底层表现底层表现底层表现底层表现浮点浮点浮点浮点除常数除常数除常数除常数高维数组访问的底层表现高维数组访问的底层表现A1,1A1,2A1,2048A2,1int a20482048;int main()int i,x,y;for(i=1;i=100;i+)for(x=0;x2048;x+)for(y=0;y2048;y+)axy=x+y;return 0;int a20482048;int main()int i,x,y;for(i=1;i=100;i+)forfor(y=0;y2048;y+)(y=0;y2048;y+)forfor(x=0;x2048;x+)(x=0;x2048;x+)axy=x+y;return 0;int a2049 92049 9;int main()int i,x,y;for(i=1;i=100;i+)for(y=0;y2049 9;y+)for(x=0;x 3535a/=7 除以常数比除以变量更快除以常数比除以变量更快除以常数比除以变量更快除以常数比除以变量更快 在某些场合，我们需要多次除以同一个变量，也可在某些场合，我们需要多次除以同一个变量，也可在某些场合，我们需要多次除以同一个变量，也可在某些场合，我们需要多次除以同一个变量，也可以以以以事先计事先计事先计事先计算出这些常数起到优化效果算出这些常数起到优化效果算出这些常数起到优化效果算出这些常数起到优化效果ai=i%2ai=rand()%2CPU的分支预测机制的分支预测机制x=(x=a?b:a)int abs(int x)return x0?x:-x;int cmp(int a)if(!a)return 0;return a0?-1:1;int t=0;for(int i=0;i31)+(-a31&1);int abs(int x)int y=x31;return(x+y)y;x=ab0 01 10 01 10 01 10 0测量结果测量结果测量结果测量结果1 1：3.2103.2107 7个时钟周期个时钟周期个时钟周期个时钟周期测量结果测量结果测量结果测量结果2 2：1 1.0210.02108 8个时钟周期个时钟周期个时钟周期个时钟周期1 11 11 10 00 01 10 0if if aiai elseelse消除条件分支消除条件分支在信息学奥赛中的实践在信息学奥赛中的实践题目：麦森数(mason)来源：NOIP2003算法：朴素的高精度计算测试情况：优化：消除除法与条件分支优化情况：100分题目：瑰丽的华尔兹(adv1900)来源：NOI2005算法：朴素的动态规划，O(N4)测试情况：优化：优化高维数组寻址优化情况：题目：翻译玛雅著作(writing)来源：IOI2006算法：O(字符集串长)的枚举测试情况：优化：汇编优化循环与数组访问优化情况：70分100分（均在0.5s内出解）60分70分100分总结总结过早的优化是过早的优化是效率低下的根源效率低下的根源Keep It Simple and Stupid程序的优化是无止境的程序的优化是无止境的 谢谢大家谢谢大家欢迎提问欢迎提问
